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.
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: }
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.
No comments:
Post a Comment