Puzzle #9 – The Snail
September 10, 2007It’s been a while since I posted a nice puzzle and since I know they are so popular, here is a relatively simple one. It was used in job interviews btw (the last line will boost the amount of views for this post…)
A snail leaves his warm house and takes a crawl through the forest leaving behind him on the ground a trail of “0”s and “1”s. He takes a very complicated route crossing his path several times. At one point he becomes tired and disoriented and wishes to go back home. He sees his own path of “0”s and “1”s on the ground which he is about to cross (i.e. not the trail ending in his tail) and wonders whether to follow the trail towards the left or towards the right.
What is the shortest repeating code of “0”s and “1”s he should leave as he crawls in order to easily and deterministically track the way back home? What is the minimum amount of bits he needs to observe (or the sample length of the code)?
Adventures in ASIC Digital Design 
ROT-13 protected to avoid a possible spoiler (assuming I was correct):
V sbhaq n fbyhgvba erdhvevat n ercrngvat cnggrea bs yratgu avar. Vg pbafvfgf bs n bar sbyybjrq ol guerr mrebf gura n bar sbyybjrq ol gjb mrebf gura n bar gura n mreb. Ernqvat rvtug ovgf jvyy nyjnlf fhssvpr gb qrgrezvar gur qverpgvba, naq vf fbzrgvzrf arprffnel. V’z abg lrg cercnerq gb pynvz gung avar vf gur fznyyrfg cbffvoyr frdhrapr.
http://www.rot13.com/index.php
Phil,
you can find a shorter pattern. Thanks for encrypting your answer though.
I’m quite sure I could easily write a program to do an exhaustive search, but I’m going to see if I can find some time to reason a solution instead. No promises; I have a business trip coming up tomorrow.
Take it easy.
I think all the fun will be gone if you would write some code to do it for ya…
gel gur ybtvp orybj…
gnxr n flzzrgevpny cnggrea(fnl bb){flzzrgevpny nybat gur zvq cbvag}
nqq nabgure flzzrgevpny cnggrea (yy) gb gur evtug…
abj nqq n aba flzzrgevpny cnggra (by) gb gur yrsg…
Abgr: (b === 0) (y === 1)
so what is the sequence length? and what is the sampling vector size???
ROT-13 protected
Abgr: Sbe gur plcure, V hfrq B sbe 0 naq V sbe 1.
Gur fubegrfg fbyhgvba V pna svaq vf BVVBBV (be gur vairefr). Nal frdhrapr bs bayl 5 ovgf jvyy or flzzrgevp va rvgure qverpgvba, fb ng yrnfg 6 ovgf ner arrqrq.
Jvgu gur frdhrapr BVVBBV, gur fanvy fubhyq fnzcyr nal 5 pbafrphgvir ovgf sebz yrsg gb evtug. Vs ur frrf nal bs gur sbyybjvat frdhraprf, gura ur jnf geniryvat sebz yrsg gb evtug jura ur ynvq gur ovgf qbja.
BVVBB
VVBBV
VBBVB
BBVBV
BVBVV
VBVVB
Vs ur frrf gur erirefr bs nal bs gubfr frdhraprf, gura ur jnf geniryvat sebz evtug gb yrsg jura ur ynvq gurz qbja.
Va fbzr pnfrf, ur bayl arrqf gb fnzcyr 4 ovgf. Vs ur frrf VVBB, BBVB be VBVV, gura ur jnf geniryvat yrsg gb evtug jura ur ynvq gurz qbja. Gur erirefr bs rnpu jbhyq vaqvpngr evtug gb yrsg.
http://www.rot13.com/index.php
very good – correct answer
I guess I should post more difficult puzzles in the future…
[…] Adventures in ASIC Digital Design Tricks and Tips for ASIC Digital Designers « Puzzle #8 – Clock Frequency Driver – Solution 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. […]
I came to the same solution as Ben, but by thinking somewhat differently. I thought let the snail to leave a simple pattern of 01 and let her (a snail is feminine in my mother tongue 🙂 ) put some unique symbols in between. I found that a convenient unique symbol could be 0110. So, all the snail has to do to make her decision is to find a unique symbol, which can’t be more than 2 bits away, and then to look at one symbol before it or after it.
Assumption :
1> It only requires to reach back home
2> Need NOT to be shortest path
Solution is :
a; Snail shold start with code ‘0’ until it changes a direction
b : After change in direction it should put compliment of current code (here it will be ‘1’).
With this it has to sample only 1 bit and it can determine the exact way back as it came from.
I didn’t understand the above solution cos of the unknown language, and the solution is encrypted. Can someone please explain the solution to me in English?