h1

Puzzle #9 – The Snail – Solution

March 27, 2008

I will keep this post short. First make sure you take a look at the original puzzle – link here.

The shortest sequence is 6 bits long and is “100110” (or its inverse “011001”). The smallest amount of bits needed to determine a direction is 5, i.e. any 5 consecutive bits seen by the snail could help him determine the direction home.

Advertisements

6 comments

  1. Can you please explain me in detail.I could not understand the question and answer as well.


  2. can you please explain me in detail?


  3. I cant see how 6 bits are enough to uniquely identify the repeatation? What is the same 6 bits repeats on the wrong route the snail has chosen?


  4. I figured it out in a very unsatisfying way. I just wrote increasing sequences and checked to see if they could be palindromes. I wrote 010101 first and showed how easily it was a palindrome, Then I wrote 011011011 which was 011 repeated and saw how easily it could be a palindrome. 0110 is a palindrome to begin with. 011101110111 is bad. So next to five bit sequences. 01011 repeats as 010110101101011 which can find a similar sequence in both directions (01101). Then I tried 010011 which I thought of as an increasing sequence. First 01 then 00-11 I thought of the second part 0011 as the 01 sequence expanded by a factor of two. So 010011010011010011 and then reversed it. So I looked at it and convinced myself there was no way to find the same patter in both directions in the sequence after repeating it three times. Next I checked each bit in a 6 bit sequence to see how far I had to go before I didn’t match any other possible pattern if I had picked a different bit position. The worst case I found was five. Is the requirement that there must be 6 bits and and equal number of 1’s and 0’s arranged such that it is asymmetric? Or did I miss something in my answer?


  5. The Snail can encode its direction from the home (E,W,N,S) as a 2-bit code.This will enable the snail to know exactly which path to select irrespective of any number of intersections. I think this is the easiest solution. Lemme know if i missed anything ?


  6. Code 110010, only 4 bits are needed (since 1100 only occurs forwards and not backwards)



Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: