Dreiecksgitter: Einfach verbundene Polyiamanten

9

Während wir uns auf einem dreieckigen Gitterkick befinden , möchte ich darauf hinweisen, dass es auf einem dreieckigen Gitter ein Äquivalent zu Polyominoes gibt . Sie werden Polyiamanten genannt und sind Formen, die durch Zusammenkleben gleichseitiger Dreiecke entlang ihrer Kanten gebildet werden. In dieser Herausforderung werden Sie entscheiden, welche Teilmengen eines Dreiecksgitters Polyiamanten sind und ob sie Löcher aufweisen. Da nur 9 Dreiecke erforderlich sind, um einen Polyiamanten mit einem Loch darin zu erstellen, muss Ihr Code so kurz wie möglich sein.

Das Gitter

Wir werden Martins dreieckiges Gitterlayout für die Eingabe verwenden:

ein dreieckiges Gitter

Achten Sie darauf, dass die Zentren der Dreiecke ein ungefähr rechteckiges Gitter bilden und das obere linke Dreieck nach oben "zeigt". Wir können dann eine Teilmenge dieses Gitters beschreiben, indem wir eine rechteckige "Sternenkarte" angeben, die angibt, welche Dreiecke enthalten sind und welche nicht. Zum Beispiel diese Karte:

** **
*****

entspricht dem kleinsten Polyiamanten, der ein Loch enthält:

9-iamond mit Loch

Löcher

Ein Polyiamant, der ein Loch wie im obigen Beispiel enthält (eine Region, die nicht Teil des Polyiamanten ist und allseitig von Regionen umgeben ist ), ist topologisch nicht einfach verbunden .

Die Herausforderung

Schreiben Sie eine Funktion oder ein Programm, das wie oben beschrieben eine "Sternenkarte" als Eingabe verwendet und genau dann eine Wahrheit ausgibt, wenn die angegebene Teilmenge des Dreiecksgitters ein einfach verbundener Polyiamant ist .

Mehr Beispiele

*** ***
*******

entspricht dem Polyiamanten

13-iamond ohne Loch

das ist einfach verbunden.


*   *
** **
 ***

entspricht dem Polyiamanten

9-iamond ohne Loch

das ist einfach verbunden.


**  **
*** **
 ****

entspricht dem Nicht- Polyiamanten

13 Dreiecke, die nichts Interessantes sind

das würde nicht einfach selbst angeschlossen werden , wenn es war ein polyiamond.

Eingabespezifikation

  • Die Eingabe besteht nur aus Sternchen, Leerzeichen und Zeilenvorschüben.
  • Das erste Zeichen der Eingabe ist immer ein Leerzeichen oder ein Sternchen (entsprechend dem nach oben zeigenden Dreieck in der oberen linken Ecke des Rasters).
  • In der ersten und letzten Zeile befindet sich immer mindestens ein Sternchen.
  • Es gibt KEINE Garantie dafür, dass Zeilen nach der ersten Zeile nicht leer sind. Zwei Zeilenvorschübe hintereinander können in einer legitimen Eingabe erscheinen.
  • Die Leitungslängen müssen nicht alle gleich sein.

Gewinnbedingung

Dies ist , also gewinnt die kürzeste Antwort in Bytes.

Testfälle

Wahrheitskarten:

1) *

2) *
   *

3) **

4) *** ***
   *******

5) *   *
   ** **
    ***

6) *
   **
    *

7)    **
     ***
   ****

8) ****
   **   *
    *****

9) ***********
   **    **  **
    ****  **  **
              **
   ************

Falsche Karten:

1) *
   *
   *

2) * *

3) *
    *

4)  **
   **

5) ***

   ***

6) ** **
   *****

7) **  **
   *** **
    ****

8)  *
    *

9) *****
   **   *
    *****
Quintopie
quelle
1
gute Frage. Wenn dreieckige Gitter zu einer Sache werden sollen, kann ich vorschlagen, dass sie beispielsweise dargestellt werden, AV VA\nVAVAVanstatt dass dies die ** **\n*****Visualisierung für einen Menschen erleichtert. Ich habe bereits eines von Martins ASCII-Diagrammen bearbeitet.
Level River St
Ich war nicht besonders besorgt um die menschliche Lesbarkeit, nein. Ich wollte alles tun, was für ein Programm leichter zu lesen ist, während ich klein bleibe.
Quintopia
Also im Grunde genommen falsch, wenn es einen Abschnitt gibt, der nur durch Ecken "verbunden" ist?
Michael Klein
1
Oder wenn es Teile gibt, die überhaupt nicht verbunden sind. Martin drückte es so aus: Richtig, wenn Figur und Boden entlang der Kanten verbunden sind, so dass 2 Flutfüllungen ausreichen, um das Flugzeug neu einzufärben.
Quintopia

Antworten:

4

Schnecken , 95 Bytes

F&
lr|=((ul.)2 ,l~a~)d|!((ul.)2 ,l~a~)u}\*}+l\ ,~a~|{\ (lr|=((ul.)2 ,l~a~)d|!((ul.)2 ,l~a~)u}+~

Dies litt wirklich unter Doppelarbeit, da ich keine Makros oder Rückverweise implementiert habe. Es wird überprüft, ob für jeden Stern ein Pfad zum Stern ganz links in der obersten Zeile vorhanden ist. und für jeden Raum gibt es einen Pfad zu einer Kante des Gitters.

F&                         ,, option F: pad lines with spaces to the length of the longest
                           ,, option &: print 1 iff match succeeds from every cell
lr                         ,, direction left or right, or
      | =((ul.)2 ,l~a~) d  ,, direction down, if we are an even number of orthogonal moves from the top left
      | !((ul.)2 ,l~a~) u  ,, or, direction up if we are odd number of moves from the top left
    }  \*                  ,, literal '*'
}+                         ,, 1 or more times
l\ ,~a~                    ,, check that we are on the leftmost * in the top line

|                          ,, the part before this is for starting on '*'; part after for starting on ' '

{ \                        ,, literal ' '
    (   lr                 ,, direction left or right, or
      | =((ul.)2 ,l~a~) d  ,, same drill as before...
      | !((ul.)2 ,l~a~) u 
}+                         ,, 1 or more times
~                          ,, end on an out of bounds cell
Feersum
quelle
Ich verstehe nicht, wie es funktioniert, aber es funktioniert total.
Quintopia
3

CJam, 101 98 Bytes

qN/_z,f{' e]}{S2*f+W%z}4*:eeee::f+:~{_(aL{+_{_2,.+1$2,.-@_:+1&!2*(a.+}%2${a1$&},\;@1$-@@}h;\;-}2*!

Probieren Sie es online aus.

Ich habe endlich meine Angst überwunden, eine Flutfüllung in CJam zu implementieren. Es ist ungefähr so ​​hässlich wie ich erwartet hatte und es kann definitiv Golf gespielt werden.

Die allgemeine Idee besteht darin, zwei Flutfüllungen durchzuführen (die tatsächlich als Entfernungen aus der Liste der nicht besuchten Zellen implementiert werden). Der erste Durchgang entfernt alle Bereiche, die vom Rand aus erreichbar sind. Der zweite Durchgang wählt dann den ersten *in Lesereihenfolge aus und entfernt alle erreichbaren Dreiecke. Wenn und nur wenn die resultierende Liste leer ist, wurde der Polyiamant einfach verbunden:

  • Wenn der Polyiamant ein Loch hatte, kann die erste Flutfüllung dieses Loch nicht erreichen und entfernen.
  • Wenn der Eingang aus mehreren getrennten Polyiamanten besteht, kann die zweite Flutfüllung nicht alle erreichen und entfernen.
Martin Ender
quelle