Wyobraź sobie podpalacza spacerującego po mieście i zbierającego ofiary według ściśle określonego wzoru (lub, alternatywnie, wyobraź sobie pszczołę latającą po ogrodzie i zbierającą kwiaty do zapylania według określonego wzoru ). Powiedzmy, że miasto jest macierzą N × N , gdzie N jest liczbą całkowitą większą lub równą 2 . Rozpocznie podpalacz z lewym górnym rogu i kolejno ustawia dom M plamy przed nimi (gdzie M oznacza liczbę domu w którym się obecnie), przy zmianie kierunku to poruszający się po każdym pożarze, w kolejności Wschód ⟶ Południe ⟶ Zachód ⟶ Północ ⟶ Wschód ⟶ Południe ... i tak dalej. kołysankapodpalacza to wartość M, która sprawia, że ​​opuszczają miasto (tzn. ostatni dom, który odwiedzają przed zatrzymaniem obrzydliwości). Jest to o wiele łatwiejsze do zrozumienia na przykładzie. Weźmy na przykład następującą macierz:

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

• Zaczynamy w lewym górnym rogu, więc M = 3 ( Xoznacza obecną i poprzednią pozycję podpalacza):

  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
  

• Zgodnie ze znaną kolejnością najpierw przechodzi na wschodnie M (3) miejsca i ląduje na 2, więc M odpowiednio się zmienia:

  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
  

• Potem idzie na południe o 2 miejsca, a M ma teraz 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
  

• Teraz przesuwa się o 1 miejsce na Zachód, a M staje się 3 :

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

• Po przesunięciu 3 miejsc na północ opuszcza miasto! Dlatego 3 jest kołysanką tego podpalacza:

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

Biorąc pod uwagę macierz N × N (opcjonalnie możesz też wziąć N jako dane wejściowe), znajdź kołysankę podpalacza. Napisałem program, dzięki któremu możesz wygenerować więcej przypadków testowych i wizualizować ścieżkę podpalacza: Wypróbuj online!

• Można założyć, że podpalacz nie mają kołysankę (to jest, może faktycznie wyjść z matrycy).
• Dla uproszczenia macierz będzie zawierać tylko dodatnie liczby całkowite mniejsze lub równe 9 (cyfry). Rozwiązania, które obsługują każdą dodatnią liczbę całkowitą są mile widziane.
• Zwróć uwagę, że podpalacz może wylądować w miejscu, które już spalił, na wypadek gdyby poruszenie się było inne niż za pierwszym razem. W takim scenariuszu po prostu weź wartość tego elementu i przejdź ponownie jak zwykle.
• Możesz konkurować w dowolnym języku programowania i możesz przyjmować dane wejściowe i generować dane wyjściowe za pomocą dowolnej standardowej metody , zwracając uwagę, że te luki są domyślnie zabronione. To jest golf golfowy , więc wygrywa najkrótsze przesłanie (w bajtach) dla każdego języka .

Przypadki testowe

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

Kołysanka: 9
-------------
2 1 2 1
3 1 1 2
1 2 2 1
1 1 1 3

Kołysanka: 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

Kołysanka: 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

Kołysanka: 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

Kołysanka: 3
-------------

Matryce w innym formacie:

[[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]]

Piąty przypadek testowy jest bardzo interesujący do wizualizacji .

MATL , 32 bajty

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

Wypróbuj online! Lub sprawdź wszystkie przypadki testowe .

Jak to działa

Matryca wejściowa jest wypełniona ramką pięciu zer, więc na przykład

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

staje się

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

Ramka zer jest używana do wykrywania, kiedy podpalacz opuści matrycę. Rozszerzenie z pięcioma zerami zapewnia, że modułowe przesunięcie długości 9w dowolnym kierunku od dowolnego z niezerowych wpisów poprawnie wyląduje w zera bez zawijania do jakiegoś niezerowego wpisu.

We współrzędnych matrycy pszczoła zaczyna się przy wejściu (6,6)do matrycy rozszerzonej. Odczytuje ten wpis i aktualizuje współrzędne zgodnie z wymaganiami, stosując (modułowe) przesunięcie długości odczytu w odpowiednim kierunku. Jest to powtarzane w pętli, dopóki nie zostanie odczytana wartość 0. Wpis, który został przeczytany przed tym (tj. Ostatni niezerowy wpis) jest wyjściem.

Współrzędne są faktycznie przechowywane jako liczba zespolona, ​​więc na przykład (6,6)staje się 6+6j. W ten sposób cztery cykliczne kierunki mogą być realizowane jako moce urojonej jednostki. Odpowiednią moc ( j, 1, -ji -1) jest mnożona przez wejście odczytu w celu uzyskania złożonego przemieszczenia, która jest wykorzystywana do aktualizacji współrzędnych.

Kolejno odczytywane wartości są przechowywane na stosie. Po wyjściu z pętli stos zawiera wszystkie niezerowe wartości odczytu w kolejności, następnie ostatnią odczytaną wartość 0, a następnie ostatnie złożone współrzędne. Tak więc trzeci element jest wymaganym wyjściem.

JavaScript (ES6), 70 68 bajtów

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

Wypróbuj online!

Skomentował

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

Biorąc pod uwagę, że znakiem modulo w JS jest znak dywidendy, kierunek jest aktualizowany w następujący sposób:

 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

Węgiel , 25 18 bajtów

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

Wypróbuj online! Link jest do pełnej wersji kodu. Wyjaśnienie:

ＰＳ

Wydrukuj ciąg wejściowy, ale nie zmieniaj pozycji drukowania.

↶

Obróć oś obrotu w lewo, aby kierunek drukowania był teraz w górę.

ＷＫＫ«

Powtarzaj, gdy pod pozycją drukowania jest znak.

≔ιθ

Zapisz znak w zmiennej.

×Ｉι¶

Rzuć znak na liczbę i wydrukuj tyle nowych linii. Ponieważ kierunek drukowania jest teraz w górę, drukowanie kończy się w poziomie. Wynik jest taki, że przesunęliśmy pozycję drukowania w pożądanym kierunku o wartość podaną przez liczbę pod pozycją drukowania.

↷»

Obróć oś, aby następne znaki nowej linii przesunęły pozycję drukowania w następnym kierunku zgodnie z ruchem wskazówek zegara dla następnego przejścia pętli.

Ｆ⟦ωθ⟧¿ιι⎚

Niestety nadal mamy do czynienia z zaśmiecaniem naszego obszaru roboczego, a jeszcze bardziej niestety, jeśli wyczyścimy obszar roboczy, usuwamy również naszą zmienną. To trochę sztuczka: lista pustych ciągów znaków i zmiennej jest zapętlona. W pierwszym przejściu pętli zmienna pętli jest pusta, więc obszar roboczy i zmienna pętli oraz zmienna wynikowa są czyszczone. Ale pętla nie jest skończona! W drugim przejściu pętli nadal uzyskujemy dostęp do naszej zmiennej starannie zachowanej na naszej liście pętli. Pozostaje po prostu go wydrukować.

⎚θ

Wyczyść płótno i wydrukuj zapisaną zmienną. (Dzięki @ ASCII-tylko za poprawkę na węgiel drzewny.)

Python 2 , 85 84 bajtów

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

Wypróbuj online!

Przechyl kapelusz do pana Xcodera za 1 bajt.

Węgiel , 50 49 46 34 33 26 bajtów

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

Wypróbuj online

Link jest do pełnej wersji kodu

Dane wejściowe muszą znajdować się na N we własnej linii, a następnie linie tablicy na osobnych liniach.

Wszelkie sposoby na odrzucenie bajtów są mile widziane i pożądane, ponieważ nie jestem dobrym golfistą w Charcoal!

-12 bajtów dzięki @Neil! -1 bajt dzięki tylko @ ASCII! -7 bajtów dzięki tylko @ ASCII (zmieniono błąd powodujący Clearresetowanie zmiennych)

Czerwony , 145 bajtów

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]

Wypróbuj online!

Bardziej czytelny:

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
]

Perl 6 , 62 bajtów

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

Wypróbuj online!

Traktuje macierz jako płaską listę i szerokość.

Czysty , 141 bajtów

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

Wypróbuj online!

Definiuje funkcję ? :: {#{#Int}} -> Int, biorąc rozpakowaną tablicę rozpakowanych tablic liczb całkowitych i zwracając wynik.

Java 8, 121 bajtów

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;}

Wypróbuj online.

Alternatywnie z taką samą liczbą bajtów 121 bajtów :

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;}}

Używa try-wreszcie zamiast sprawdzania, czy x,ywspółrzędna jest nadal w granicach.

Wypróbuj online.

Wyjaśnienie:

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

Perl 5 , 92 bajtów

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

Wypróbuj online!

W jaki sposób?

Zestaw zagnieżdżonych map i łączenie tworzą:

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

który jest następnie oceniany w celu ustalenia, czy pętla się kończy. Ponieważ wartość logiczna jest obliczana od lewej do prawej, wartość $nfaktycznie zmienia się (maksymalnie) cztery razy podczas oceny. Ponieważ logiczne zwarcie logiczne w Perlu, wartością $njest kołysanka po wyjściu z pętli.

Python 3 , 85 84 bajtów

xcoder: -1 (nigdy nie pamiętam sztuczki + ~)

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

Wypróbuj online!

Zamiast poruszać się w różnych kierunkach (E, S, W, N), to rozwiązanie zawsze przesuwa się na wschód i po każdym ruchu obraca siatkę przeciwnie do ruchu wskazówek zegara. Po obróceniu ostatnia kolumna jest teraz pierwszym rzędem, więc jeśli indeks wiersza jest mniejszy od zera, oznacza to, że uciekliśmy z planszy.

Retina , 161 bajtów

.
 $.%`*_#$&*
(?<=(.+¶)+|^)
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

Wypróbuj online!