26
\$\begingroup\$

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

Improve this question
\$\endgroup\$
6
  • 1
    \$\begingroup\$ This is like a generalisation of Skip like a Rabbit in two dimensions, with a slightly different goal. The thematic of this challenge and its title were inspired by a song by Hozier \$\endgroup\$
    – Mr. Xcoder
    May 9, 2018 at 18:23
  • \$\begingroup\$ what happens when the arsonist lands on a square that is already burnt? \$\endgroup\$
    – Level River St
    May 9, 2018 at 19:11
  • 2
    \$\begingroup\$ Can we assume that the arsonist is not actually an arsonist and is instead doing something nice at each location rather than burning it down? +1 for a very nice idea :) \$\endgroup\$
    – ElPedro
    May 9, 2018 at 19:56
  • 2
    \$\begingroup\$ @ElPedro Sure, an alternate version for you: Imagine a bee flying around the garden and picking its flowers to pollenize according to a very specific pattern. :D Happy friendly golfing! \$\endgroup\$
    – Mr. Xcoder
    May 9, 2018 at 20:05
  • 1
    \$\begingroup\$ That's a much nicer thought. If I could upvote again I would for that. \$\endgroup\$
    – ElPedro
    May 9, 2018 at 20:06

12 Answers 12

Reset to default
11
\$\begingroup\$

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.

Improve this answer
\$\endgroup\$
1
  • 1
    \$\begingroup\$ +1 for a very innovative approach. \$\endgroup\$
    – LastStar007
    May 10, 2018 at 13:53
7
\$\begingroup\$

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
Improve this answer
\$\endgroup\$
4
\$\begingroup\$

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

Improve this answer
\$\endgroup\$
2
\$\begingroup\$

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.

Improve this answer
\$\endgroup\$
0
2
\$\begingroup\$

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)

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

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
]
Improve this answer
\$\endgroup\$
1
\$\begingroup\$

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.

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

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.

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

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
Improve this answer
\$\endgroup\$
0
\$\begingroup\$

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.

Improve this answer
\$\endgroup\$
0
\$\begingroup\$

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.

Improve this answer
\$\endgroup\$
1
  • \$\begingroup\$ 84 bytes: -d-1 => +~d \$\endgroup\$
    – Mr. Xcoder
    May 13, 2018 at 17:57
0
\$\begingroup\$

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!

Improve this answer
\$\endgroup\$

Your Answer

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

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