Ausrichtung auf dreieckigen Gittern

18

Sechseckige Gitter wurden in letzter Zeit zu einer ziemlich beliebten Variante für Herausforderungen im Zusammenhang mit zweidimensionalen Daten. Die ebenso interessanten Dreiecksgitter scheinen jedoch bisher weitgehend vernachlässigt worden zu sein. Ich würde das gerne mit einer ziemlich einfachen Herausforderung korrigieren.

Erstens, wie stellen wir ein Dreiecksgitter dar? Betrachten Sie das folgende Beispiel (ignorieren Sie vorerst das richtige Diagramm):

Bildbeschreibung hier eingeben Bildbeschreibung hier eingeben

Die Zellen fallen ordentlich auf ein reguläres Gitter (der Unterschied zu einem regulären Gitter besteht nur darin, welche Zellen als benachbart betrachtet werden):

1234567
89abcde
fghijkl
mnopqrs

Wie das rechte Diagramm zeigt, hat ein Dreiecksgitter drei Hauptachsen: eine horizontale und zwei diagonale.

Markieren Sie diese im ASCII-Raster:

AVAVAVA
VAabcAV
fVAiAVl
mnVAVrs

Die Herausforderung

Sie erhalten eine rechteckige Zeichenfolge, die ein Dreiecksgitter darstellt (wobei die linke obere Ecke ein nach oben zeigendes Dreieck ist). Die meisten Zellen sind ., aber genau zwei Zellen #, zB:

....#
.#...
.....

Bestimmen Sie, ob die beiden #entlang einer der drei Achsen des Rasters ausgerichtet sind (dh ob sie in einer der drei oben hervorgehobenen Richtungen in einer einzelnen Zeile liegen). In diesem Beispiel lautet die Antwort "nein".

Sie können ein Programm oder eine Funktion schreiben, indem Sie eine Eingabe über STDIN (oder die nächstgelegene Alternative), ein Befehlszeilenargument oder ein Funktionsargument vornehmen und das Ergebnis über STDOUT (oder die nächstgelegene Alternative), einen Funktionsrückgabewert oder einen Funktionsparameter (out) ausgeben.

Die Eingabe kann eine einzelne Zeichenfolge sein, die durch Zeilenvorschübe oder ein anderes geeignetes Zeichen begrenzt wird, oder eine Liste von Zeichenfolgen. Sie können anstelle von .und zwei beliebige (konsistente) druckbare ASCII-Zeichen verwenden #.

Die Ausgabe sollte ein wahrer Wert sein, wenn die markierten Zellen ausgerichtet sind, andernfalls ein falscher Wert.

Es gelten die Standardregeln für .

Testfälle

Wahrheitsgitter:

.#..#.

#
#

...........
...#.......
...........
...........
...........
.......#...
...........

...........
.......#...
...........
...........
...........
...#.......
...........

.#.........
...........
...........
...........
...........
.......#...
...........

...........
...#.......
...........
...........
...........
...........
.......#...

.........#.
...........
...........
...........
...........
...#.......
...........

...........
.......#...
...........
...........
...........
...........
...#.......

...........
.#.....#...
...........
...........
...........

Falsche Gitter:

#.....
.....#

.....#
#.....

...#.......
...........
...........
...........
...........
.......#...
...........

...........
...#.......
...........
...........
...........
...........
.........#.

.......#...
...........
...........
...........
...........
...#.......
...........

...........
.......#...
...........
...........
...........
...........
.#.........
Martin Ender
quelle

Antworten:

3

Schnecken , 40 39 Bytes

\#{z|=(ul.ul.`,l~a~)(l.a3|.a|d.ea5}.,\#
\# ,, Spiel '#'
{
  z | ,, Entweder in eine beliebige oktinale Richtung drehen, oder alles andere vor dem
  = (,, Wenn diese Behauptung erfolgreich ist, ist die Startzelle ein "nach oben zeigendes Dreieck"
    ul.ul.`, ,, Gehe zweimal eine Zelle nach oben oder links, beliebig oft.
              ,, Dies hätte mit ul.`2 oder ul.`2 + ein Byte kürzer sein sollen? aber
              ,, Das Parsen von `ist fehlerhaft.
    l ~ a ~ ,, Überprüfen Sie, ob wir uns in der oberen linken Zelle befinden, indem Sie die Grenzüberschreitungen nach links und dann nach Nordosten abgleichen
  )
  (l.a3 | ,, Gehe einmal nach links und dann in nordwestliche Richtung; oder
    .a | ,, Bewegen Sie sich einmal nach rechts (in die ursprüngliche Richtung) und stellen Sie dann die Richtung nach Nordosten ein. oder
    d.ea5 ,, Bewegen Sie sich einmal nach unten und stellen Sie dann die Richtung nach Nordwesten oder Nordosten ein
}
., ,, Übereinstimmung mit beliebig vielen Zeichen (in die aktuelle Richtung)
\# ,, Spiel '#'
Feersum
quelle
2

CJam, 47 Bytes

Nun, da es eine kürzere Lösung gibt, fühle ich mich nicht mehr schlecht, wenn ich meine eigene teile. :) (Hauptsächlich um zu zeigen, dass dies nicht besonders schwierig ist, auch wenn Sie keine 2D-Pattern-Matching-Sprache haben ...)

qN%:eeee::f+:~{S&},2f<:P0f=P::+Xf|P::-Xf|]::=:|

Dies nutzt Leerzeichen anstelle von #und wirklich alles andere für ..

Führen Sie alle Testfälle online aus.

Ich hasse die Vervielfältigung in wirklich, P::+Xf|P::-Xf|aber bisher habe ich nichts gefunden, um es loszuwerden.

Erläuterung

Lesen Sie nicht weiter, wenn Sie selbst eine Lösung finden möchten.

Zunächst der langweilige Teil: Ermitteln der beiden Koordinatenpaare der beiden Räume im Eingaberaster:

qN%   e# Read input and split into lines.
:ee   e# Enumerate the characters in each line. I.e. turn each character 'x into a pair
      e# [N 'x] where N is its horizontal 0-based index.
ee    e# Enumerate the lines themselves, turning each line [...] into [M [...]] where M
      e# is its vertical 0-based index.
::f+  e# This distributes the vertical index over the individual lines, by prepending it
      e# to each pair in that line. So now we've got a 2-D array, where each character 'x
      e# has been turned into [M N 'x].
:~    e# Flatten the outermost dimension, so that we have a flat list of characters with
      e# their coordinates.
{S&}, e# Filter only those lists that contain a space.
2f<   e# Truncate the two results to only their first two elements.
:P    e# Store the result in P.

Nun ist der interessante Teil, wie man bestimmt, ob diese Koordinaten ausgerichtet sind oder nicht. Mein Code berechnet alle drei Achsen separat:

  • Die horizontale Achse ist trivial. Überprüfen Sie, ob die vertikalen Koordinaten übereinstimmen.
  • Schauen wir uns die Nordostdiagonale an. Im ASCII-Raster gibt es immer zwei Antidiagonalen, die zu jeder Tri-Raster-Diagonale gehören:

    ....AV..
    ...AV...
    ..AV....
    

    Wir können die aktuelle Antidiagonale identifizieren, indem wir die Koordinaten xund addieren y:

    01234567
    12345678
    23456789
    

    Wir möchten 0und müssen also 1zu derselben Diagonale gehören, ebenso wie 2und 3und und 4und 5und. Das heißt, sobald wir unseren Anti-Diagonal-Index haben, möchten wir auf die nächste ungerade Zahl aufrunden. Mit anderen Worten, wir nehmen das bitweise ODER mit 1. (Wir könnten auch bitweise UND mit auf die nächste gerade Zahl abrunden, -2aber das ist im Code teurer.)

  • Nun die Südostdiagonalen:

    .VA.....
    ..VA....
    ...VA...
    

    Um Diagonalen um einen Index zu geben, wir subtrahieren die xvon den yKoordinaten (welche als negative Zahlen Buchstaben):

    0abcdefg
    10abcdef
    210abcde
    

    In diesem Fall möchten 0und müssen wir 1zur selben Diagonale gehören, sowie -1und -2, oder 2und 3. Also wollen wir noch einmal auf die nächste ungerade Zahl aufrunden.

Hier ist der Code dafür:

0f=  e# The coordinates are still on the stack. Replace each with its vertical coordinate
     e# to check for the horizontal axis.
P    e# Push the coordinates again.
::+  e# Sum each pair to get an anti-diagonal index.
Xf|  e# OR each index with 1 to round up to the next odd number.
P    e# Push the coordinates again.
::-  e# In each pair, subtract the horizontal coordinate from the vertical, to
     e# get a diagonal index.
Xf|  e# OR each index with 1.
]    e# Wrap all three index pairs in an array.
::=  e# Check equality for each pair.
:|   e# Fold bitwise OR over the results to check if at least one pair of indices
     e# was equal.
Martin Ender
quelle