Finde das Wiegenlied des Brandstifters

26

Stellen Sie sich einen Brandstifter vor, der durch die Stadt läuft und seine Opfer nach einem ganz bestimmten Muster auswählt (oder stellen Sie sich eine Biene vor, die durch den Garten fliegt und ihre Blumen pflückt, um sie nach einem ganz bestimmten Muster zu pollen ). Angenommen, die Stadt ist eine N × N- Matrix, wobei N eine ganze Zahl größer oder gleich 2 ist . Der Brandstifter beginnt in der oberen linken Ecke und setzt nacheinander die M- Punkte des Hauses vor sich (wobei M die Nummer des Hauses ist, in dem er sich gerade befindet), während er die Richtung ändert, in die er sich nach jedem Brand bewegt, in der angegebenen Reihenfolge Osten ⟶ Süden ⟶ Westen ⟶ Norden ⟶ Osten ⟶ Süden ... und so weiter. Das Wiegenliedder Brandstifter ist der Wert von M , der sie dazu bringt, die Stadt zu verlassen (dh das letzte Haus, das sie besuchen, bevor sie den Greuel stoppen). Dies ist anhand eines Beispiels viel einfacher zu verstehen. Nehmen Sie zum Beispiel die folgende Matrix:

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
  • Wir beginnen in der oberen linken Ecke, also ist M = 3 ( Xmarkiert die aktuelle und vorherige Position des Brandstifters):
    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
    
  • Gemäß der bekannten Ordnung, geht es zunächst nach Osten M (3) Punkte und landet auf einem 2 so M entsprechend ändert:
    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
    
  • Dann geht es nach Süden 2 Spots und M ist jetzt 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
    
  • Jetzt rückt es 1 Punkt nach Westen und M wird 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
    
  • Nachdem es sich 3 Punkte nach Norden bewegt hat , verlässt es die Stadt! Deshalb ist 3 das Wiegenlied dieses Brandstifters:
        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
    

Wenn Sie eine N × N- Matrix haben (Sie können optional auch N als Eingabe verwenden), finden Sie das Wiegenlied des Brandstifters. Ich habe ein Programm geschrieben, mit dem Sie weitere Testfälle generieren und den Weg des Brandstifters visualisieren können: Probieren Sie es online aus!

  • Sie können davon ausgehen , dass der arsonist hat ein Schlaflied hat (das heißt, es tatsächlich die Matrix heraus kann).
  • Die Matrix enthält der Einfachheit halber nur positive ganze Zahlen, die kleiner oder gleich 9 (Ziffern) sind. Lösungen, die mit jeder positiven Ganzzahl umgehen, sind ausdrücklich erwünscht.
  • Beachten Sie, dass der Brandstifter an einer Stelle landen kann , an der er sich bereits niedergebrannt hat, für den Fall, dass das Gefühl, in das er sich bewegt, sich vom ersten Mal unterscheidet. Nehmen Sie in einem solchen Szenario einfach den Wert dieses Elements und verschieben Sie es wie gewohnt.
  • Sie können in jeder Programmiersprache antreten und über jede Standardmethode Eingaben und Ausgaben vornehmen. Beachten Sie jedoch, dass diese Lücken standardmäßig verboten sind. Dies ist , daher gewinnt die kürzeste Übermittlung (in Bytes) für jede Sprache .

Testfälle

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

Wiegenlied: 9
-------------
2 1 2 1
3 1 1 2
1 2 2 1
1 1 1 3

Wiegenlied: 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

Wiegenlied: 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

Wiegenlied: 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

Wiegenlied: 3
-------------

Die Matrizen in einem anderen 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], [4, 5, 2, 3, 1, 1, 1], [1, 2, 1, 2, 1, 2, 2], [1, 2, 2, 3, 2, 1, 2]]

Der fünfte Testfall ist sehr interessant zu visualisieren .

Mr. Xcoder
quelle
1
Dies ist wie eine Verallgemeinerung von Skip wie ein Kaninchen in zwei Dimensionen mit einem etwas anderen Ziel. Das Thema dieser Herausforderung und ihr Titel wurden von einem Lied von Hozier
Mr. Xcoder
Was passiert, wenn der Brandstifter auf einem bereits verbrannten Platz landet?
Level River St
2
Können wir annehmen, dass der Brandstifter eigentlich kein Brandstifter ist und stattdessen an jedem Ort etwas Schönes tut, anstatt es niederzubrennen? +1 für eine sehr schöne Idee :)
ElPedro
2
@ElPedro Sicher, eine alternative Version für Sie: Stellen Sie sich vor, eine Biene fliegt durch den Garten und pflückt ihre Blüten, um sie nach einem ganz bestimmten Muster zu pollen. : D Happy freundliches Golfen!
Mr. Xcoder
1
Das ist ein viel schöner Gedanke. Wenn ich nochmal upvoten könnte, würde ich das tun.
ElPedro

Antworten:

11

MATL , 32 Bytes

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

Probieren Sie es online! Oder überprüfen Sie alle Testfälle .

Wie es funktioniert

Die Eingabematrix wird beispielsweise mit einem Frame von fünf Nullen aufgefüllt

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

wird

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 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

Der Nullrahmen wird verwendet, um festzustellen, wann die Brandstifterbiene die Matrix verlassen hat. Die Erweiterung mit fünf Nullen stellt sicher, dass eine modulare Verschiebung der Länge 9von einem Eintrag ungleich Null bis in eine beliebige Richtung korrekt in einer Null landet, ohne dass ein Eintrag ungleich Null umgebrochen wird.

In Matrixkoordinaten beginnt die Biene mit der Eingabe (6,6)der erweiterten Matrix. Es liest diesen Eintrag und aktualisiert die Koordinaten nach Bedarf, wobei eine (modulare) Verschiebung der gelesenen Länge in die entsprechende Richtung angewendet wird. Dies wird in einer Schleife wiederholt, bis der gelesene Wert ist 0. Der Eintrag, der vor diesem gelesen wurde (dh der letzte Eintrag ungleich Null), ist die Ausgabe.

Die Koordinaten werden eigentlich als komplexe Zahl gespeichert ist , so beispielsweise (6,6)wird 6+6j. Auf diese Weise können die vier zyklischen Richtungen als Potenzen der imaginären Einheit realisiert werden. Die entsprechende Leistung ( j, 1, -joder -1) durch den Leseeintrag multipliziert die komplexe Verschiebung zu erhalten , die für die Aktualisierung der Koordinaten verwendet wird.

Die nacheinander gelesenen Werte bleiben auf dem Stapel. Wenn die Schleife verlassen wird, enthält der Stapel alle Lesewerte ungleich Null in der Reihenfolge, dann den zuletzt gelesenen Wert 0, also die neuesten komplexen Koordinaten. Das drittoberste Element ist also die erforderliche Ausgabe.

Luis Mendo
quelle
1
+1 für einen sehr innovativen Ansatz.
LastStar007
7

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)

Probieren Sie es online!

Kommentiert

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

Da das Vorzeichen des Moduls in JS das der Dividende ist, wird die Richtung folgendermaßen aktualisiert:

 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
Arnauld
quelle
4

Holzkohle , 25 18 Bytes

PS↶WKK«≔ιθ×Iι¶↷»⎚θ

Probieren Sie es online! Link ist eine ausführliche Version des Codes. Erläuterung:

PS

Drucken Sie die Eingabezeichenfolge, aber verschieben Sie die Druckposition nicht.

Drehen Sie den Zapfen nach links, sodass die Druckrichtung jetzt oben ist.

WKK«

Wiederholen, solange sich ein Zeichen unter der Druckposition befindet.

≔ιθ

Speichern Sie das Zeichen in einer Variablen.

×Iι¶

Wirf den Charakter in eine Zahl und drucke so viele Zeilenumbrüche. Da die Druckrichtung jetzt oben ist, wird horizontal gedruckt. Das Ergebnis ist, dass wir die Druckposition um den Betrag in die gewünschte Richtung verschoben haben, den die Zahl unter der Druckposition angibt.

↷»

Drehen Sie den Drehpunkt so, dass die nächsten Zeilen die Druckposition für den nächsten Durchgang der Schleife im Uhrzeigersinn verschieben.

F⟦ωθ⟧¿ιι⎚

Leider haben wir immer noch die Eingabe, die unsere Zeichenfläche überfüllt, und noch bedauerlicher ist, dass wir, wenn wir die Zeichenfläche löschen, auch unsere Variable löschen. Das ist also ein kleiner Trick: Eine Liste der leeren Zeichenfolge und der Variablen wird durchgeschleift. Beim ersten Durchlauf der Schleife ist die Schleifenvariable leer, sodass die Zeichenfläche und die Schleifenvariable sowie die Ergebnisvariable gelöscht werden. Aber die Schleife ist noch nicht fertig! Beim zweiten Durchlauf der Schleife erhalten wir weiterhin Zugriff auf unsere Variable, die sorgfältig in unserer Schleifenliste gespeichert wurde. Es bleibt nur zu drucken.

⎚θ

Löschen Sie die Zeichenfläche und drucken Sie die gespeicherte Variable. (Danke an @ ASCII-only für die Korrektur von Charcoal.)

Neil
quelle
2

Charcoal , 50 49 46 34 33 26 Bytes

NθEθSMθ↑WKK«MIι✳⊗Lυ⊞υι»⎚⊟υ

Probieren Sie es online aus

Der Link verweist auf die ausführliche Version des Codes

Die Eingabe muss N in einer eigenen Zeile sein, danach die Zeilen des Arrays in separaten Zeilen.

Jegliche Möglichkeiten, Bytes auszuschalten, sind willkommen und erwünscht, da ich kein guter Golfer in Charcoal bin!

-12 Bytes dank @Neil! -1 Byte dank nur @ ASCII! -7 Bytes dank @ ASCII-only (Fehler beim ClearZurücksetzen von Variablen behoben)

Zacharý
quelle
1

Rot , 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]

Probieren Sie es online!

Besser lesbar:

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
]
Galen Ivanov
quelle
1

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

Probieren Sie es online!

Definiert die Funktion ? :: {#{#Int}} -> Int, indem ein nicht gepacktes Array von nicht gepackten Arrays von Ganzzahlen verwendet und das Ergebnis zurückgegeben wird.

Οurous
quelle
1

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

Probieren Sie es online aus.

Alternative mit der gleichen Anzahl von 121 Bytes :

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

Verwendet try-finally, anstatt zu überprüfen, ob die x,y-Koordinate noch innerhalb der Grenzen liegt.

Probieren Sie es online aus.

Erläuterung:

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
Kevin Cruijssen
quelle
0

Perl 5 , 92 Bytes

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

Probieren Sie es online!

Wie?

Der Satz verschachtelter Maps und der Join erzeugen Folgendes:

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

welches dann ausgewertet wird, um zu bestimmen, ob die Schleife endet. Da der Boolesche Wert von links nach rechts ausgewertet wird, $nändert sich der Wert von tatsächlich (bis zu) viermal während der Auswertung. Da die boolesche Logik in Perl kurzschließt, ist der Wert von $ndas Schlaflied, wenn die Schleife verlassen wird.

Xcali
quelle
0

Python 3 , 85 84 Bytes

xcoder: -1 (Ich erinnere mich nie an den + ~ 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

Probieren Sie es online!

Anstatt sich in verschiedene Richtungen (E, S, W, N) zu bewegen, bewegt sich diese Lösung immer nach Osten und dreht das Gitter nach jeder Bewegung gegen den Uhrzeigersinn. Nach dem Drehen ist die letzte Spalte jetzt die erste Zeile. Wenn der Zeilenindex also kleiner als Null ist, bedeutet dies, dass wir vom Brett gerannt sind.

RootTwo
quelle
84 Bytes : -d-1=>+~d
Mr. Xcoder
0

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

Probieren Sie es online!

TwiNight
quelle