Escape the labyrinth!

Question

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

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!

Answer 1

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 

Answer 2

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.

Answer 3

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)

Answer 4

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]

Answer 5

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!

Answer 6

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

Answer 7

Perl 5, 79 bytes

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

Try it online!

Answer 8

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.

Answer 9

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!

Answer 10

Charcoal, 43 40 bytes

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

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

Ｎθ

Input the room.

Ｗ⊖θ«

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

«≔Ｉ§”)“⊞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.

Answer 11

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"

Answer 12

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.

Answer 13

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

Answer 14

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

Answer 15

Stax, 31 bytes

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

Run and debug it

Answer 16

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!