Find arsonist's lullaby

Question

Imagine an arsonist walking around the town and picking its victims according to a very specific pattern (Or, alternatively, Imagine a bee flying around the garden and picking its flowers to pollenize according to a very specific pattern). Let's say the town is an N × N matrix, where N is an integer higher than or equal to 2. The arsonist starts from the upper-left corner and successively sets the house M spots in front of them (where M is the number of the house they're currently in), while changing the direction it's moving in after each fire, in the order East ⟶ South ⟶ West ⟶ North ⟶ East ⟶ South... and so on. The lullaby of the arsonist is the value of M that makes them exit the town (i.e. the last house they visit before stopping the abomination). This is way easier to understand with an example. Take the following matrix for instance:

3 2 3 2 7
3 1 4 1 6
2 5 3 1 1
4 4 3 2 4
1 1 1 1 1

• We start in the upper-left corner, so M = 3 (X marks the current and previous positions of the arsonist):

  X 2 3 2 7
  3 1 4 1 6
  2 5 3 1 1
  4 4 3 2 4
  1 1 1 1 1
  

• According to the known order, it first goes east M (3) spots and lands on a 2 so M changes accordingly:

  X 2 3 X 7
  3 1 4 1 6
  2 5 3 1 1
  4 4 3 2 4
  1 1 1 1 1
  

• Then it goes south 2 spots and M is now 1:

  X 2 3 X 7
  3 1 4 1 6
  2 5 3 X 1
  4 4 3 2 4
  1 1 1 1 1
  

• Now it moves 1 spot to the West and M becomes 3:

  X 2 3 X 7
  3 1 4 1 6
  2 5 X X 1
  4 4 3 2 4
  1 1 1 1 1
  

• After it moves 3 spots north, it exits the town! Therefore, 3 is this arsonist's lullaby:

      X
  X 2 3 X 7
  3 1 4 1 6
  2 5 X X 1
  4 4 3 2 4
  1 1 1 1 1
  

Given an N × N matrix (you can optionally take N as input too), find the lullaby of the arsonist. I've written a program with which you can generate more test cases and visualise the path of the arsonist: Try it online!

• You may assume that the arsonist does have a lullaby (that is, it can actually get out of the matrix).
• The matrix will only contain positive integers less than or equal to 9 (digits), for simplicity. Solutions that handle any positive integer are completely welcome.
• Note that the arsonist can land on a spot they've already burned, in case the sense they're moving in is different from the first time. In such a scenario, just take the value of that element and move again as usual.
• You can compete in any programming language and can take input and provide output through any standard method, while taking note that these loopholes are forbidden by default. This is code-golf, so the shortest submission (in bytes) for every language wins.

Test cases

-------------
9 2 3
1 7 2
8 7 6

Lullaby: 9
-------------
2 1 2 1
3 1 1 2
1 2 2 1
1 1 1 3

Lullaby: 2
-------------
3 2 3 2 7
3 1 4 1 6
2 5 3 1 1
4 4 3 2 4
1 1 1 1 1

Lullaby: 3
-------------
1 2 1 2 1 2
1 2 1 2 1 2
1 2 1 2 1 2
1 2 1 2 1 2
1 2 1 2 1 2
1 2 1 2 1 2

Lullaby: 2
-------------
3 2 1 2 1 1 1
2 3 2 3 2 1 1
2 1 1 1 3 1 2
3 1 1 1 1 1 1
4 5 2 3 1 1 1
1 2 1 2 1 2 2
1 2 2 3 2 1 2

Lullaby: 3
-------------

The matrices in a different format:

[[9, 2, 3], [1, 7, 2], [8, 7, 6]]
[[2, 1, 2, 1], [3, 1, 1, 2], [1, 2, 2, 1], [1, 1, 1, 3]]
[[3, 2, 3, 2, 7], [3, 1, 4, 1, 6], [2, 5, 3, 1, 1], [4, 4, 3, 2, 4], [1, 1, 1, 1, 1]]
[[1, 2, 1, 2, 1, 2], [1, 2, 1, 2, 1, 2], [1, 2, 1, 2, 1, 2], [1, 2, 1, 2, 1, 2], [1, 2, 1, 2, 1, 2], [1, 2, 1, 2, 1, 2]]
[[3, 2, 1, 2, 1, 1, 1], [2, 3, 2, 3, 2, 1, 1], [2, 1, 1, 1, 3, 1, 2], [3, 1, 1, 1, 1, 1, 1], [4, 5, 2, 3, 1, 1, 1], [1, 2, 1, 2, 1, 2, 2], [1, 2, 2, 3, 2, 1, 2]]

The fifth test case is very interesting to visualise.

Answer 1

MATL, 32 bytes

JQ6*`G5thYay&Zj3$)wyJ2@-^*+8M]b&

Try it online! Or verify all test cases.

How it works

The input matrix is padded with a frame of five zeros, so for example

3 2 3 2 7
3 1 4 1 6
2 5 3 1 1
4 4 3 2 4
1 1 1 1 1

becomes

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 3 2 3 2 7 0 0 0 0 0
0 0 0 0 0 3 1 4 1 6 0 0 0 0 0
0 0 0 0 0 2 5 3 1 1 0 0 0 0 0
0 0 0 0 0 4 4 3 2 4 0 0 0 0 0
0 0 0 0 0 1 1 1 1 1 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

The frame of zeros is used to detect when the arsonist bee has exited the matrix. The extension with five zeros ensures that a modular displacement of length up to 9 in any direction from any of the nonzero entries will correctly land in a zero without wrapping around to some non-zero entry.

In matrix coordinates, the bee starts at entry (6,6) of the extended matrix. It reads that entry, and updates the coordinates as required, applying a (modular) displacement of the read length in the corresponding direction. This is repeated in a loop until the read value is 0. The entry that was read before that one (i.e. the last non-zero entry) is the output.

The coordinates are actually stored as a complex number, so for example (6,6) becomes 6+6j. This way the four cyclic directions can be realized as powers of the imaginary unit. The corresponding power (j, 1, -j or -1) is multiplied by the read entry to obtain the complex displacement which is used for updating the coordinates.

The successively read values are kept on the stack. When the loop is exited, the stack contains all non-zero read values in order, then the last read value which is 0, then the latest complex coordinates. So the third-top element is the required output.

Answer 2

JavaScript (ES6), 70 68 bytes

m=>(g=d=>(n=(m[y]||0)[x])?g(--d&3,x-=d%2*(y+=--d%2*n,L=n)):L)(x=y=0)

Try it online!

Commented

m => (                        // given m = input matrix
  g = d =>                    // g = recursive function taking the direction d
    (n = (m[y] || 0)[x]) ?    // let n be the content of the current cell; if it's defined:
      g(                      //   do a recursive call:
        --d & 3,              //     with the next direction (0 = E, 3 = S, 2 = W, 1 = N)
        x -=                  //     update x by subtracting ...
          d % 2 * (           //       ... ((d - 1) % 2) * n
            y += --d % 2 * n, //       and update y by adding ((d - 2) % 2) * n
            L = n             //       save n into L
          )                   //     end of x update
      )                       //   end of recursive call
    :                         // else:
      L                       //   stop recursion and return L
)(x = y = 0)                  // initial call to g() with x = y = d = 0

Given that the sign of the modulo in JS is that of the dividend, the direction is updated this way:

 d | d' = --d&3 | dx = -(d%2)  | dy = --d%2 | direction
---+------------+--------------+------------+------------------
 0 |     3      | -(-1%2) = +1 | -2%2 =  0  | (+1,  0) = East
 3 |     2      | -( 2%2) =  0 |  1%2 = +1  | ( 0, +1) = South
 2 |     1      | -( 1%2) = -1 |  0%2 =  0  | (-1,  0) = West
 1 |     0      | -( 0%2) =  0 | -1%2 = -1  | ( 0, -1) = North

Answer 3

Charcoal, 25 18 bytes

ＰＳ↶ＷＫＫ«≔ιθ×Ｉι¶↷»⎚θ

Try it online! Link is to verbose version of code. Explanation:

ＰＳ

Print the input string, but don't move the print position.

↶

Rotate the pivot left, so that the print direction is now up.

ＷＫＫ«

Repeat while there is a character under the print position.

≔ιθ

Save the character in a variable.

×Ｉι¶

Cast the character to a number and print that many newlines. As the print direction is now up, this ends up printing horizontally. The upshot is that we've moved the print position in the desired direction by the amount given by the number under the print position.

↷»

Rotate the pivot so that the next newlines move the print position in the next direction clockwise for the next pass of the loop.

Ｆ⟦ωθ⟧¿ιι⎚

Unfortunately we still have the input cluttering our canvas, and even more unfortunately, if we clear the canvas we also clear our variable. So, this is a bit of a trick: a list of the empty string and the variable is looped over. On the first pass of the loop, the loop variable is empty, so the canvas and the loop variable and the result variable are all cleared. But the loop is not finished! On the second pass of the loop, we still get to access our variable carefully preserved in our loop list. It simply remains to print it.

⎚θ

Clear the canvas and print the saved variable. (Thanks to @ASCII-only for the fix to Charcoal.)

Answer 4

Python 2, 85 84 bytes

a=input();x=y=e=0;d=1
while-1<y<len(a)>x>=0:v=a[y][x];x+=v*d;y+=e*v;d,e=-e,d
print v

Try it online!

Tip o' the hat to Mr. Xcoder for 1 byte.

Answer 5

Charcoal, 50 49 46 34 33 26 bytes

ＮθＥθＳＭθ↑ＷＫＫ«ＭＩι✳⊗Ｌυ⊞υι»⎚⊟υ

Try it online

Link is to the verbose version of the code

Input must be N on its own line, then the lines of the array on separate lines after that.

Any ways to knock off bytes are welcome and wanted, as I am not a good golfer in Charcoal!

-12 bytes thanks to @Neil! -1 byte thanks to @ASCII-only! -7 bytes thanks to @ASCII-only (changed a bug that made Clear reset variables)

Answer 6

Red, 145 bytes

func[b][h:[0 1 0 -1 0]x: y: 1 i: 0
until[y: h/(i: i % 4 + 1) *(t: b/(y)/(x)) + y x: h/(i + 1) * t + x none = b/(y) or(x < 1 or(x > length? b))]t]

Try it online!

More readable:

f: func[b][
    h: [0 1 0 -1 0]                                ; step lengths (combined for x and y) 
    x: y: 1                                        ; starting coords (1,1)
    i: 0                                           ; step counter 
    until[
        y: h/(i: i % 4 + 1) * (t: b/(y)/(x)) + y   ; next y; t stores the lullaby
        x: h/(i + 1) * t + x                       ; next x
        none = b/(y) or (x < 1 or (x > length? b)) ; until x or y are not valid indices
    ]
    t                                              ; return the lullaby
]

Answer 7

Perl 6, 62 bytes

{$^w;$^m[0,{$_+$m[$_]*(1,$w,-1,-$w)[$++%4]}...{!$m[$_]}][*-2]}

Try it online!

Takes the matrix as flat list and width.

Answer 8

Clean, 141 bytes

import StdEnv
d=[0,1,1,0,0,-1,-1,0:d]
$m[x,y]n[a,b:l]#r=size m
#u=x+a*n
#v=y+b*n
|0>u||0>v||u>=r||v>=r=n= $m[u,v]m.[u,v]l
?m= $m[0,0]m.[0,0]d

Try it online!

Defines the function ? :: {#{#Int}} -> Int, taking an unboxed array of unboxed arrays of integers and returning the result.

Answer 9

Java 8, 121 bytes

m->{int l=m.length,x=0,y=0,f=0,r=0;for(;x*y>=0&x<l&y<l;x+=f<1?r:f==2?-r:0,y+=f==1?r:f>2?-r:0,f=++f%4)r=m[y][x];return r;}

Try it online.

Alternative with same 121 bytes byte-count:

m->{int l=m.length,x=0,y=0,f=0,r=0;try{for(;;x+=f<1?r:f==2?-r:0,y+=f==1?r:f>2?-r:0,f=++f%4)r=m[y][x];}finally{return r;}}

Uses try-finally instead of checking if the x,y-coordinate is still within bounds.

Try it online.

Explanation:

m->{                   // Method with integer-matrix parameter and integer return-type
  int l=m.length,      //  Dimensions of the matrix
      x=0,y=0,         //  x,y coordinate, starting at [0,0]
      f=0,             //  Direction-flag, starting at 0 (east)
      r=0;             //  Result-integer
  for(;x*y>=0&x<l&y<l  //  Loop as long as the x,y coordinates are still within bounds
      ;                //    After every iteration:
       x+=f<1?         //     If the direction is east:
           r           //      Increase the `x` coordinate by `r`
          :f==2?       //     Else-if the direction is west:
           -r          //      Decrease the `x` coordinate by `r`
          :            //     Else (it's north/south):
           0,          //      Leave the `x` coordinate the same
       y+=f==1?        //     If the direction is south:
           r           //      Increase the `y` coordinate by `r`
          :f>2?        //     Else-if the direction is north:
           -r          //      Decrease the `y` coordinate by `r`
          :            //     Else:
           0,          //      Leave the `y` coordinate the same
       f=++f%4)        //     Go to the next direction (0→1→2→3→0)
    r=m[y][x];         //   Set `r` to the value of the current cell
  return r;}           //  Return the last `r` before we went out of bounds

Answer 10

Perl 5, 92 bytes

sub b{1while eval join'&&',map{/./;map"(\$$_$&=".'$n=$_[$y][$x])'.$',x,'y'}'+<@_','->=0';$n}

Try it online!

How?

The set of nested maps and the join produce this:

($x+=$n=$_[$y][$x])<@_&&($y+=$n=$_[$y][$x])<@_&&($x-=$n=$_[$y][$x])>=0&&($y-=$n=$_[$y][$x])>=0

which is then evaluated to determine if the loop ends. Because the Boolean is evaluated left to right, the value of $n actually changes (up to) four times during the evaluation. Because Boolean logic short-circuits in Perl, the value of $n is the lullaby when the loop is exited.

Answer 11

Python 3, 85 84 bytes

xcoder: -1 (I never remember the +~ trick)

def f(x):
 r=c=0
 while-1<r:d=x[r][c];r,c=len(x)-c+~d,r;x=[*zip(*x)][::-1]
 return d

Try it online!

Instead of moving in different directions (E,S,W,N), this solution always moves east and rotates the grid counter clockwise after every move. After rotating, what was the last column is now the first row, so if the row index is less than zero it means we ran off the board.

Answer 12

Retina, 161 bytes

.
 $.%`*_#$&*
(?<=(.+¶)+|^)
A ¶A$#1*
~(K`{`^X\1YZ¶1S$4¶1XYZ¶2$4$2$4$3¶2XYZ¶3S¶3XY\1Z¶S
X
(_$*)(A_$*)
Y
( _$*)
Z
(?=\n\D$*\2\b.$*\3#(_+))
)`S
$$4$$2$$3
L$0`_+
$.0

Try it online!