21
\$\begingroup\$

You are trapped in this 5x5 labyrinth - each room is labelled from 1 to 25 and the exit is in room 1.

enter image description here

You are given as input the room you are currently in. Your task is to output the shortest sequence of moves (north, east, south, west) needed to reach room 1.

Moves can be output in any format you wish (list, string, array...) as long as you use the characters n,w,e,s.

Here are all the test cases:

1 => empty string/list
2 => w
3 => ww
4 => swwnw
5 => wswwnw
6 => seenwnw
7 => nw
8 => wnw
9 => wwnw
10 => swwnwnw
11 => eenwnw
12 => enwnw
13 => nwnw
14 => wnwnw
15 => wwnwnw
16 => enenwnw
17 => nenwnw
18 => wnenwnw
19 => nwnwnw
20 => wnwnwnw
21 => nenenwnw
22 => enwnenwnw
23 => nwnenwnw
24 => wnwnenwnw
25 => nwnwnwnw

Shortest answer in bytes wins!

\$\endgroup\$
12
  • 3
    \$\begingroup\$ How flexible is the room labeling / input? Can we 0-index instead of 1-index? Can we take the room number as a character (thinking, as in base 36)? \$\endgroup\$
    – Chas Brown
    Sep 17, 2019 at 7:04
  • 2
    \$\begingroup\$ @Therandomguy no, you need to handle this specific labyrinth. \$\endgroup\$
    – Arnaud
    Sep 17, 2019 at 7:12
  • 6
    \$\begingroup\$ Since it is possible, I think all possible cases should be included in the test cases. \$\endgroup\$ Sep 17, 2019 at 7:27
  • 1
    \$\begingroup\$ @UnrelatedString This question take 1 input, and output different path based on its input. I believe this requirement does not fit the kolmogorov-complexity tag. \$\endgroup\$
    – tsh
    Sep 17, 2019 at 8:06
  • 2
    \$\begingroup\$ Someone needs to provide an answer in Labyrinth. \$\endgroup\$ Sep 18, 2019 at 15:09

16 Answers 16

21
\$\begingroup\$

Python 2, 64 bytes

def f(n):d=0x1211252b5375>>2*n-4&3;print"nwes"[d];f(n+d*3+d%2-5)

Try it online!

A function that prints one direction per line, terminating with error.

The constant 0x1211252b5375 encodes in base 4 the direction d we travel from each room number as a number 0 through 3. The extraction digit >>2*n-4&3 is also designed to give a negative shift error when n=1, terminating the code. We update the room number n via an offset that's computed from the direction d as d*3+d%2-5, which maps:

d   d*3+d%2-5
0  -> -5
1  -> -1
2  ->  1
3  ->  5 
\$\endgroup\$
1
  • 1
    \$\begingroup\$ I'm not sure if this is valid as-is, functions have to be reusable, and you need error trapping (try/except) to be able to continue execution after calling this function. \$\endgroup\$ Sep 17, 2019 at 22:38
10
\$\begingroup\$

Python 2, 95 93 bytes

f=lambda n:n>1and Q[n]+f(n+[-5,5,1,-1]['nsew'.find(Q[n])])or''
Q='  wwswsnwwseenwwenwnwnenwn'

Try it online!

Could shave off 3 2 bytes if 0-indexed room labeling is allowed.

\$\endgroup\$
1
  • \$\begingroup\$ 89 bytes \$\endgroup\$
    – Arnauld
    Sep 17, 2019 at 13:04
6
\$\begingroup\$

05AB1E, 30 29 bytes

-1 byte thanks to a miraculous coincidence with prime numbers

[Ð#•θzƶ‰`Ó•4вsè<DˆØ·5-+}'‹™¯è

Try it online!

[                      }    # infinite loop:
 Ð                          #  triplicate the room number (initially, the input)
  #                         #  break if room number == 1
   •θzƶ‰`Ó•4в               #  compressed list 202232302231102210202010
             sè             #  use the room number to index into that list
               <            #  decrement
                Dˆ          #  add a copy to the global array
                  Ø         #  nth prime (-1 => 0, 0 => 2, 1 => 3, 2 => 5)
                   ·        #  double
                    5-      #  subtract 5
                      +     #  add that to the room number
'‹™                         # dictionary string "western"
   ¯                        # push the global array
    è                       # index (wraps around, so -1 => n, 0 => w, 1 => e, 2 => s)
\$\endgroup\$
2
  • 1
    \$\begingroup\$ This outputs 1 for input 1, instead of an empty string (easy fix would be to add a leading õ?). Apart from that, nice answer! \$\endgroup\$ Sep 17, 2019 at 11:39
  • 1
    \$\begingroup\$ @KevinCruijssen thanks for pointing out that mistake! I found a single-byte fix. \$\endgroup\$
    – Grimmy
    Sep 17, 2019 at 11:55
5
\$\begingroup\$

Ruby, 72 62 bytes

f=->n{n<2?'':' en  sw'[x=4*18139004[n]+6*4267088[n]-5]+f[n+x]}

Try it online!

How?

The trick here is to use 2 constants to build the next step for each cell, then recursively solve the problem.

The 2 constants 18139004 and 4267088 are binary strings giving the direction of the next move, by extracting a single bit from both for each cell, we can get:

"n" = 4*0+6*0-5 = -5
"w" = 4*1+6*0-5 = -1
"e" = 4*0+6*1-5 = +1
"s" = 4*1+6*1-5 = +5

Easier than shifting around and masking a single big binary number IMHO.

When we get the direction, we extract the corresponding letter from the string " en sw":

  1   5
  |   |
" en  sw"
   |   |
  -5  -1

And proceed recursively on the cell [n+x]

\$\endgroup\$
4
\$\begingroup\$

JavaScript (ES7),  62  58 bytes

Port of xnor's answer.

f=n=>--n?"nwes"[d=79459389361621/4**n&3]+f(n+d*3+d%2-4):''

Try it online!

\$\endgroup\$
3
\$\begingroup\$

Perl 5 (-n), 94 bytes

-5 bytes thanks to Grimy

@A=map/./g,__wwswsnwwseenwwenwnwnenwn;%H=(n,-5,s=>5,e,1,w,-1);$_+=$H{$,=$A[$_]},say$,until$_<2

TIO

\$\endgroup\$
6
  • \$\begingroup\$ -8 \$\endgroup\$
    – Grimmy
    Sep 17, 2019 at 8:01
  • \$\begingroup\$ -2 \$\endgroup\$
    – Grimmy
    Sep 17, 2019 at 8:03
  • \$\begingroup\$ -5 \$\endgroup\$
    – Grimmy
    Sep 17, 2019 at 8:06
  • 1
    \$\begingroup\$ Do you mean I should post it as a separate answer? \$\endgroup\$
    – Grimmy
    Sep 17, 2019 at 8:08
  • 1
    \$\begingroup\$ yes because it seems you did the most of the work, it was interesting to see how we can always save space \$\endgroup\$ Sep 17, 2019 at 8:10
3
\$\begingroup\$

Perl 5, 79 bytes

say$,while$_+={n,-5,s=>5,e,1,w,-1}->{$,=substr _wwwswsnwwseenwwenwnwnenwn,$_,1}

Try it online!

\$\endgroup\$
2
\$\begingroup\$

JavaScript, 80 73 71 bytes

Adapted from Chas' Python solution so please +1 him, too.

f=n=>--n?(d=" wwswsnwwseenwwenwnwnenwn"[n])+f(n+~~{n:-4,s:6,e:2}[d]):``

Try it Online!

1 byte saved thanks to Arnauld.

\$\endgroup\$
1
  • \$\begingroup\$ Thanks, @Arnauld :) Had just spotted that myself, too. \$\endgroup\$
    – Shaggy
    Sep 17, 2019 at 10:10
2
\$\begingroup\$

Charcoal, 43 40 bytes

NθW⊖θ«≔I§”)“⊞x⟧∧⎚⁵2”ιι§nwesι≧⁺⁻⁺﹪ι²×³ι⁵θ

Try it online! Link is to verbose version of code. Based on both @ChasBrown's and @xnor's answers. Explanation:

Nθ

Input the room.

W⊖θ«

Set the loop variable i to one less than the room number and repeat while it is non-zero.

«≔I§”)“⊞x⟧∧⎚⁵2”ιι

Extract the direction from the compressed string 0113130113220112010102010. (The leading 0 is just a filler digit.)

§nwesι

Print the direction.

≧⁺⁻⁺﹪ι²×³ι⁵θ

Use @xnor's formula to calculate the new room number.

\$\endgroup\$
2
\$\begingroup\$

Jelly, 30 29 bytes

“þ&ƊĿñ÷°e’b6Ḥ_5Ż⁸+ị¥ƬI‘ị“®ȯẹ»

Try it online!

A monadic link taking the starting cell and returning a string with the directions.

I love the fact that Jelly’s dictionary has a word like ‘Kennesaw’ (a city northwest of Atlanta, Georgia), used here because indexing into it with [5, 1, -5, -1] + 1 gives nesw!

Explanation

“þ...e’                    | Base-250 integer 1962789844189344852  
       b6                  | Convert to base 6 (2, 2, 5, 2, 5, 0, 2, 2, 5, 3, 3, 0, 2, 2, 3, 0, 2, 0, 2, 0, 3, 0, 2, 0)
         Ḥ                 | Double
          _5               | Subtract 5
            Ż              | Prepend 0
             ⁸  ¥Ƭ         | Using this as the right argument and the original link argument as the left argument, loop the following as a dyad until there is no change, collecting up results
              +            | - Add the left argument to:
               ị           |   - The left argument indexed into the right argument
                  I        | Differences between consecutive numbers
                   ‘       | Increment by 1
                    ị“®ȯẹ» | Index into "Kennesaw"
\$\endgroup\$
2
\$\begingroup\$

PHP, 110 bytes

A solution which isn't a port of Chas Brown's great answer or xnor's great answer. I know this is longer but I wanted to have a different solution!

for($n=$argn;$n>1;$n=ord($s[$n*2+1])%30)echo($s='0000w<w sEw"s)n w%w&s-e*e+n&w+w,e/n*w/n,w1n.e5n0w5n2')[$n*2];

Try it online!

I have created a mapping string which has 2 characters for every cell in the board. First character for each cell is a move (n/e/s/w) or 0 and the second character's ASCII code mod 30 will return another cell number which we should follow its move in recursive mode until we get to exit cell (cell < 2).

For example for input of 8:

  • 2 characters for cell 8 are: w%
  • It means print w and continue with moves for cell of %
  • ASCII code of % is 37 which mod 30 will be 7, so next cell to follow is 7.
  • 2 characters for cell 7 are: n (last character is space, ASCII code = 32)
  • It means print n and continue with moves for cell of 32 mod 30 which is 2.
  • 2 characters for cell 2 are: w< (last character ASCII code = 60)
  • It means print w and continue with moves for cell of 60 mod 30 which is 0.
  • If cell number is less than 2, loop stops!
  • Final printed result: wnw

PHP, 75 bytes

This version is written by Grimy, it is 35 bytes shorter than my original answer because he/she is smarter! Grimy's comment: "4 * 25 < 256, so you only need 1 byte per cell, not 2"

for($n=$argn;$n=ord("0\0~f;6o4R:s%ql&rup*@^tIDbx"[$n%25]);)echo news[$n%4];

Try it online!


PHP, 71 bytes

This port of Arnauld's answer which is port of xnor's answer, but as a loop instead of recursive function, since it turns out to be shorter in PHP.

for($n=$argn;--$n;$n+=$d*3+$d%2-4)echo nwes[$d=79459389361621/4**$n&3];

Try it online!

\$\endgroup\$
4
  • 2
    \$\begingroup\$ 4 * 25 < 256, so you only need 1 byte per cell, not 2: Try it online! \$\endgroup\$
    – Grimmy
    Sep 17, 2019 at 15:33
  • 1
    \$\begingroup\$ @Grimy, amazing, I think you have to post it as a separate answer, it is different enough. \$\endgroup\$
    – Night2
    Sep 17, 2019 at 15:55
  • 1
    \$\begingroup\$ I'm not gonna do that, so you choose whether to incorporate it in your answer or leave it as just a comment. \$\endgroup\$
    – Grimmy
    Sep 17, 2019 at 16:07
  • 1
    \$\begingroup\$ @Grimy, added your version with your name. Thanks anyways. \$\endgroup\$
    – Night2
    Sep 18, 2019 at 6:52
2
\$\begingroup\$

C (clang), 81 bytes

v;f(p){p-1&&putchar(v="00wwswsnwwseenwwenwnwnenwn"[p])+f(p+=v%5?6-v%8:v%2?5:-5);}

Try it online!

Thanks to @Tommylee2k suggestion -8! + recursive call

C (clang), 90 bytes

v;f(p){for(char*l="00wwswsnwwseenwwenwnwnenwn";p-1;p+=v%5?6-v%8:v%2?5:-5)putchar(v=l[p]);}

Try it online!

Similar to all not compressed solutions.

\$\endgroup\$
1
  • 1
    \$\begingroup\$ can be shortened: v;f(p){for(;p-1;p+=v%5?6-v%8:v%2?5:-5)putchar(v="00wwswsnwwseenwwenwnwnenwn"[p]);} \$\endgroup\$
    – Tommylee2k
    Sep 18, 2019 at 12:55
1
\$\begingroup\$

05AB1E, 45 43 bytes

õ?[Ð#.•DUo¢ê`Ω÷‰₂¡)R€ûK•¦sè©?Ž₁9₂в6-'€Ã®kè+

Port of @ChasBrown's Python 2 answer.

Try it online or verify all test cases.

Explanation:

õ?               # Output an empty string
                 # (to overwrite the implicit output if the input is 1)
[                # Start an infinite loop:
 Ð               #  Triplicate the top of the stack
                 #  (which is the (implicit) input in the first iteration)
  #              #  If it's exactly 1: stop the infinite loop
  .•DUo¢ê`Ω÷‰₂¡)R€ûK•
                 #  Push compressed string "a  wwswsnwwseenwwenwnwnenwn"
   ¦             #  Remove the first character
    sè           #  Swap to get the number, and use it to index into the string
      ©          #  Store it in variable `®` (without popping)
       ?         #  Print it without trailing newline
  Ž₁9            #  Push compressed integer 22449
     ₂в          #  Convert to base-26 as list: [1,7,5,11]
       6-        #  Subtract 6 from each: [-5,1,-1,5]
         '€Ã    '#  Push dictionary string "news"
            ®k   #  Get the index in this string of character `®`
              è  #  And use that to index into the integer-list
               + #  And add it to the originally triplicated integer

See this 05AB1E tip of mine (all four sections) to understand why .•DUo¢ê`Ω÷‰₂¡)R€ûK• is "a wwswsnwwseenwwenwnwnenwn"; Ž₁9 is 22449; Ž₁9₂в is [1,7,5,11]; and '€Ã is "news".

\$\endgroup\$
2
  • 1
    \$\begingroup\$ That convenient dictionary string must have been good news! \$\endgroup\$
    – Neil
    Sep 17, 2019 at 15:22
  • \$\begingroup\$ @Neil Definitely. :) Although apparently the dictionary string western is better. ;p \$\endgroup\$ Sep 17, 2019 at 15:23
1
\$\begingroup\$

Bash, 120 bytes

S=__wwswsnwwseenwwenwnwnenwn
N=n-5w-1s05e01
for((i=$1;$i>1;i+=$j)){ d=${S:$i:1};j=${N:`expr index $N $d`:2};printf $d; }

Try it online!

I toyed for a while with trying to bit-pack the string as nibbles, but the decoding would require more characters than the number saved.

How it works:

S=__wwswsnwwseenwwenwnwnenwn

String $S holds a single character (n,w,s,e) for each room showing which direction to take to move one room towards the exit, skipping rooms 0 and 1.

N=n-5w-1s05e01

String $N has the delta to add to/subtract from the current room number for each direction change (n: -5, w: -1, s: +5, e: +1)

for((i=$1;$i>1;i+=$j)){ d=${S:$i:1};j=${N:`expr index $N $d`:2};printf $d; }

Start with $i equal to the room number given on the command line ($1). Assign the character at index $i in string $S to $d. Retrieve the delta value from $N for the direction to take to the next room, assigning it to $j.

Print the next direction to take in $d.

Add/subtract the delta in $j to/from $i.

Loop until we leave room #2 (while $i>1).

\$\endgroup\$
1
\$\begingroup\$

Stax, 31 bytes

α-J╒Θ▀╣ô¥$v╞||T←]┬yΣ╨z§£sU╕τR"┌

Run and debug it

\$\endgroup\$
1
\$\begingroup\$

Kotlin, 112 bytes

val d="  113130113220112010102010"
fun p(r:Int):String=if(r>1)"nwes"[d[r]-'0']+p("046:"[d[r]-'0']-'5'+r)
else ""

Try it online!

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.