h1

Puzzle #9 – The Snail

September 10, 2007

It’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)?

Advertisements

11 comments

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


  2. Phil,
    you can find a shorter pattern. Thanks for encrypting your answer though.


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


  4. Take it easy.
    I think all the fun will be gone if you would write some code to do it for ya…


  5. 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)


  6. so what is the sequence length? and what is the sampling vector size???


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


  8. very good – correct answer
    I guess I should post more difficult puzzles in the future…


  9. […] 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. […]


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


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



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: