P001 -- Message Decoding

Please restrict discussions in this forum to project related topics.

P001 -- Message Decoding

Postby DrJump » Sun Mar 07, 2010 6:48 pm

Problem started: 16-Feb-2010

Some message encoding schemes require that an encoded message be sent in two parts. The first part, called the header, contains the characters of the message. The second part contains a pattern that represents the message. You must write a program that can decode messages under such a scheme.

The heart of the encoding scheme for your program is a sequence of "key" strings of 0's and 1's as follows:

Code: Select all
     0, 00, 01, 10, 000, 001, 010, 011, 100, 101, 110, 0000, 0001, ... , 1011, 1110, 00000, ...


The first key in the sequence is of length 1, the next 3 are of length 2, the next 7 of are length 3, the next 15 of length 4, etc. If two adjacent keys have the same length, the second can be obtained from the first by adding 1 (base 2). Notice that there are no keys in the sequence that consist only of 1's.

The keys are mapped to the characters in the header in order. That is, the first key (0) is mapped to the first character of the header, the second key (00) to the second character in the header, and the k-th key is mapped to the k-th character in the header. For example, suppose the header is:

Code: Select all
     AB#TANCnrtXc


Then 0 is mapped to A, 00 to B, 01 to #, 10 to T, 000 to A, ... , 110 to X, and 0000 to c.

The encoded message contains only 0's and 1's and possibly carriage returns, which are to be ignored. The message is divided into segments. The first 3 digits of a segment give the binary representation of the length of the keys in the segment. For example, if the first three digits are 010, then the remainder of the segment consists of keys of length 2 (00, 01, or 10). The end of the segment is a string of 1's which is the same length as the length of the keys in the segment. So a segment of keys of length 2 is terminated by 11. The entire encoded message is terminated by 000 (which would signify a segment in which the keys have length 0). The message is decoded by translating the key in the segments one-at-a-time into the header characters to which they have been mapped.

Input

The input file contains several data sets. Each data set consists of a header, which is a single line by itself, and a message, which may extend over several lines. The length of the header is limited only by the fact that key strings have a maximum length of 7 (111 in binary). If there are multiple copies of a character in a header, then several keys will map to that character. The encoded message contains only 0's and 1's, and it is a legitimate encoding according to the described scheme. That is, the message segments begin with the 3-digit length sequence and end with the appropriate sequence of 1's. The keys in any given segment are all the same length, and they all correspond to characters in the header. The message is terminated by 000.

Carriage returns may appear anywhere in the message part. They are not considered as part of the message.

Output

For each data set, your program must write its decoded message on a separate line. There should not be blank lines between messages.

Sample Input
Code: Select all
TNM AEIOU
0010101100011
1010001001110110011
11000
$#**\
0100000101101100011100101000


Sample Output
Code: Select all
TAN ME
##*\$
DrJump
 
Posts: 19
Joined: Sun Mar 07, 2010 6:08 pm

Re: Message Decoding (World Finals, 1991, San Antonio)

Postby DrJump » Thu Mar 11, 2010 9:01 pm

So ... is anybody working on the implementation?
DrJump
 
Posts: 19
Joined: Sun Mar 07, 2010 6:08 pm

Re: Message Decoding (World Finals, 1991, San Antonio)

Postby Ted J. » Mon Mar 15, 2010 9:18 pm

This is called stirring Stirring the Pot, No. 1...

Code: Select all
@HSW[] a"bcdefg()i*jkl,mn.o/prstuvwy{;}
10100001111111000111011111110110101111000111111101101011101000111000001101010101
11010000011111011010111101010000000000011111111001010000011110110101111010010011
11011011111100110011111010001011111100101000011011111101101011110010001111101001
11000100001011111101101011110000101111101000000001111111011010111100100101101111
11110111101111001001111110100100111111001110111101101011110001111111101000010001
00101111101101111011110010011111011011111100001100011111011010111100100111110111
01101111010101100010001101111101110111110010100110111101111001011011110010101111
11110110111111010010000100111110110101110100011100000110101010111110100000111110
10101111010101000001111111000111011111110110101111000111111101101011100101101000
01011111011011111101000111111101101111110011001111011010011111101000111111110000
11111110100100111110110101111000111111110100001000100011011111011101111100101001
10111101111001011110100100001011111101101111110100101111111000110111101111001011
11101001110000011111100011000001111011010111100110011110110111111000110110101001
10100111101001010001111111100011011010011111101100000101001111110100011111111000
11111101001001111110001011111011010111101010101111101001111010100100100001011111
11111000001110011101111101000000011000101111111001110111110100010000111111110001
10110111111010010111111100101011010100111101110011101000111000001101010101111101
10100000111110110101110101011101000000001111111100101000001111011100111100010111
1110101011011000110011111000
Ted J.
 
Posts: 10
Joined: Sun Mar 07, 2010 5:40 pm

Re: Message Decoding (World Finals, 1991, San Antonio)

Postby DrJump » Tue Mar 16, 2010 4:01 pm

Ted --

I'm looking at what you posted and I'm curious ... where the blank spaces in the middle of the message come from?

The problem states that the message consists of 0s and 1s and possibly carriage returns ... a

DrJump
DrJump
 
Posts: 19
Joined: Sun Mar 07, 2010 6:08 pm

Re: Message Decoding (World Finals, 1991, San Antonio)

Postby Ted J. » Tue Mar 16, 2010 5:33 pm

Honestly, off the top of my head I don't know. Doesn't violate the format specification though.

May be a side effect of my manually chopping the file into multiple lines.

Probably is some kind of bug though, but I double I'll figure that out before I abandon this silly keyboard.

addendum: They're tab characters. The spec says to "eat and ignore" them when decoding, so on the ENCODER I inferred that they could just be ignored and passed through. My rule for my encoder was "anything on the ignore list for the decoder is passed through unchanged."
Ted J.
 
Posts: 10
Joined: Sun Mar 07, 2010 5:40 pm

Re: Message Decoding (World Finals, 1991, San Antonio)

Postby Ted J. » Wed Mar 17, 2010 9:07 am

My teaser message has been updated to remove characters that violate the spec.
Ted J.
 
Posts: 10
Joined: Sun Mar 07, 2010 5:40 pm

Re: P001 -- Message Decoding

Postby MichaelVasquez » Sat Apr 17, 2010 7:41 pm

I was working on this program a bit today and I'm getting this weird compiler error saying the program is using unsafe or unchecked variables, and to Recompile with -Xlint:unchecked for details. The line of code causing this problem is hm.put(header.charAt(i), new String(cBin(i))); which is where i put the char from the head together with the value its representing. I have googled it but honestly I cant understand what is the problem. If i uncheck this one option in preferences then this problem isnt displayed but i believe still exists. Any suggestions? I am using BlueJ.
MichaelVasquez
 
Posts: 2
Joined: Tue Apr 13, 2010 8:46 pm

Re: P001 -- Message Decoding

Postby Ted J. » Thu May 13, 2010 6:57 am

MichaelVasquez wrote:... using unsafe or unchecked variables ... hm.put(header.charAt(i), new String(cBin(i))); ...


Sorry for the long delay in modding the message, i need to check the email notification settings. ;^(

Dr. J. will probably need to drop in on this, but my guess is a combination of your inline String object creation is the trigger for your error message. Have you tried pulling that out as a separate step so that you can see which part of the code is actually triggering the error? e.g.:

Code: Select all
String value = new String(cBin(i));
hm.put(header.charAt(i), value );


Short of doing that to try to narrow it down, I'd need more of your code to work with to try to figure out.

If you're still curious, at this later date. ;^)
Ted J.
 
Posts: 10
Joined: Sun Mar 07, 2010 5:40 pm

Re: P001 -- Message Decoding

Postby DrJump » Thu May 13, 2010 7:04 am

Hi there,

So I also have been bad at checking in here ... but here I am too .

That compiler warning message that you are getting results from something that uses generic not getting the generic type.

What is "something that uses generics"? That is anything specified with angle-braces. e.g., ArrayList<String> or HashMap<String,String>. It is called a generic because the data structure "ArrayList" or "HashMap" is coded without specifying what data it holds leaving that up to the programmer using it to specify. Using it like this:

HashMap<String, String> map;
map = new HashMap();

will generate this warning message because you have not specified the types leaving it "unchecked".

We can talk details about this if you are interested in knowing more.

-Dr Jump
DrJump
 
Posts: 19
Joined: Sun Mar 07, 2010 6:08 pm


Return to Problems

Who is online

Users browsing this forum: No registered users and 1 guest

cron