BinaryCode

Problem:

Link to Problem Statement

Overview:

You are asked to decode a string. The original String is in binary format. The encoded string is formed by adding both neighboring digits to the current digit.

Java Source:

01: public class BinaryCode {
02:
03:     /*
04:     Decodes the string. The string is encoded by adding it's two neighbors to
05:     it's values. So: 1001001 becomes 1111111
06:     In some cases the message may decode to two different values depending on
07:     if pos1 = 0 or 1.
08:     In other cases a value of 0 or 1 may lead to a message that cannot be
09:     decoded.
10:     i.e. would require a a digit other than 0 or 1 to make the sums add up.
11:      */
12:     private static String decode(char[] message, char pos1) {
13:
14:         /*
15:         Create a return array that is 1 element larger than the message. This
16:         extra space will make it easier to compute the last element, and will
17:         ultimately get chopped off before returning anyway.
18:          */
19:         char[] ret = new char[message.length + 1];
20:
21:         // Set the first position to either a 0 or 1 depending on the parameter.
22:         ret[0] = pos1;
23:
24:         // Loop through the return array starting at position 1.
25:         for (int i = 1; i < ret.length; i++) {
26:             Integer a = Integer.parseInt("" + message[i - 1]);
27:             Integer b = Integer.parseInt("" + ret[i - 1]);
28:
29:             // This protects from going in front of the beginning of the array.
30:             Integer c = (i == 1) ? 0 : Integer.parseInt("" + ret[i - 2]);
31:
32:             /*
33:             The current value in the return array will equal:
34:             (one position back in the message) - (one position back in the
35:             return array) - (2 positions back in the return array)
36:             Write this out on papers until you're convinced that it works.
37:              */
38:             int val = a - b - c;
39:
40:             /*
41:             If we arrive at a non-binary digit, then the encoding was
42:             impossible given the value of pos1.
43:               */
44:             if ((val > 1) || (val < 0)) {
45:                 return "NONE";
46:             }
47:
48:             // Convert the number to a character.
49:             ret[i] = (char) (val + '0');
50:         }
51:
52:         // Convert the array to a String, and chop off the last place.
53:         return new String(ret).substring(0, ret.length - 1);
54:     }
55:
56:     public String[] decode(String message) {
57:
58:         // Create an array of Strings to return.
59:         String[] ret = new String[2];
60:
61:         /*
62:         Populate the return array with the results of decoding.
63:         First when we assume that the first digit was a 0.
64:         Then when we assume the first digit was a 1.
65:          */
66:         ret[0] = decode(message.toCharArray(), '0');
67:         ret[1] = decode(message.toCharArray(), '1');
68:
69:         return ret;
70:     }
71: }

Notes:

The toughest part of this problem is determining how to calculate the value at the current location of the return String - Line 38. I suggest you write this out on paper to see how it works. For example:

message:	1	2	3	2
return:	0	1	1	?

The value of the ? will be one space back in the message array (3) - one space back in the return array (1) - two spaces back in the return array (1). 3 - 1 - 1 = 1. These values are calculated on lines 50, 51, and 54.

If you insert 1 for the ?, you'll see that the encoding/decoding of the message is correct up to that point.

The next position in the return array must be 0, since the 2 is already the total the 1 (at the ? location) and 1 (one space before the ?).

Thank you for taking the time to read this solution. I welcome any feedback you may have.