## 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.

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)