Ist das ein gültiges Spiel von Five Up (Domino)?

8

Eine Gruppe von Dominosteinen besteht aus Kacheln mit zwei Zahlen, sodass jede Kombination von ganzen Zahlen von 0 bis N dargestellt wird. Die folgenden Beispiele beziehen sich der Einfachheit halber auf N = 6, aber auch N = 9 und N = 12 sind üblich. Die Ausrichtung der Fliesen spielt keine Rolle (sie sind in der Regel mit Punkten statt Ziffern gedruckt), so [1-6]und [6-1]bezieht sich auf die gleichen Fliesen, von denen nur eine in einem Satz ist.

Bei den meisten Spielen mit Dominosteinen fügen die Spieler abwechselnd Dominosteine ​​zu einer Linie der bereits auf dem Tisch gespielten hinzu, sodass eine der Zahlen auf dem neuen Dominostein neben derselben Zahl an einem Ende der Linie auf dem Tisch platziert wird. Sie können also [2-5]an jedem Ende einer vorhandenen Zeile ein [2-3][3-3][3-5], produzierendes [5-2][2-3][3-3][3-5]oder ein hinzufügen[2-3][3-3][3-5][5-2] .

Viele solcher Spiele erfordern "Doppel", Dominosteine ​​mit zwei der gleichen Anzahl, um senkrecht zu den anderen mit ihnen verbundenen Dominosteinen platziert zu werden. Abgesehen von der Wertung, um die es uns hier nicht geht, hat dies keine Auswirkung, außer wenn ...

Viele dieser Spiele erlauben es dann der "Linie", einige oder alle Doppel zu teilen. Five Up ist ein solches Spiel, bei dem die Linie bei jedem Double in 3 neue Linien zerfallen kann, sodass an allen vier Seiten eines Double möglicherweise ein passender Domino angebracht ist.

Hier ist ein Beispiellayout von Dominosteinen aus einer "Doppel 6" in einem Five Up-Spiel (wobei A | B oder AB ein einzelner Dominostein ist):

     4
     -
     0

3|0 0|0 0|2

     0
     -
     1

4|1 1|1 1|6
                3
     1          -
     -          6
     5
                6
6|5 5|5 5|0 0|6 - 6|2 2|1
                6
     5
     -          6
     4          -
                4

Ihre Aufgabe ist es, eine Liste der Dominosteine ​​in der Reihenfolge zu erstellen, in der sie der Tabelle hinzugefügt wurden, und festzustellen, ob diese Reihenfolge ein legales Spiel von Five Up darstellt oder nicht.

Sie können ein ganzes Programm schreiben, das Eingaben von stdin übernimmt, oder eine Funktion, die Eingaben als einen oder mehrere Parameter verwendet.

Kanonische Eingabe wäre eine Liste oder ein Array von zwei Tupeln von ganzen Zahlen. Eine Liste von Listen, ein Array von Arrays, ein Vektor von Tupeln usw. sind alle gültigen Formen, in denen Eingaben vorgenommen werden können, wie eine Zeichenfolge, die eine der oben genannten darstellt, oder mehrere Zeichenfolgen. Die Eingabe enthält nur Paare nicht negativer Ganzzahlen, gültige Dominosteine.

Die Ausgabe sollte für gültige bzw. ungültige Spiele ein wahrer oder falscher Wert sein.

Ihr Code sollte beliebig große Domino-Zahlen akzeptieren, die den maximalen Ganzzahlwerten Ihrer Sprache entsprechen.

Beispiele:

  • 0-6 ist gültig, wie jedes andere einzelne Domino
  • 0-6 6-0ist nicht gültig, es gibt nur einen 0-6Domino in einem Set
  • 6-6 6-5 5-3 3-0 ist gültig, eine einfache lineare Anordnung
  • 6-6 6-5 3-0 5-3ist nicht gültig, es gibt kein 3oder 0im Spiel, mit dem sich der dritte Domino vor dem 5-3Spielen verbinden kann
  • 1-1 1-2 1-3 1-4 1-5 1-6ist nicht gültig, alle vier offenen 1Enden sind aufgebraucht und lassen nirgendwo die Verbindung1-6
  • 1-1 1-2 1-3 1-4 1-5 3-6 1-6 ist gültig, die 3-6 verbindet sich mit der 1-3, dann kann die 1-6 mit der 3-6 verbinden
  • 5-5 5-4 5-0 0-6 6-6 6-4 6-2 2-1 6-3 5-1 1-1 1-6 4-1 1-0 0-0 2-0 3-0 0-4 ist gültig, das oben abgebildete Beispiel
  • 12-12 12-1 3-12 3-1 1-2 3-3 ist gültig, verwendet größere Dominosteine ​​und hat eine mehrdeutige Platzierung

HINWEIS: Die hier erforderliche Funktion ist keine perfekte Überprüfung für gültige Five Up-Spiele. Wir ignorieren hier die Regeln, nach denen Domino zuerst gespielt wird, was mehr Informationen über die Variante des Spiels und die Anzahl der Spieler erfordern und eine signifikante Minderheit der Eingaben disqualifizieren würde.

Sparr
quelle
Müssen wir geometrische Einschränkungen bei der Platzierung berücksichtigen, dh die Domino-Kette stürzt in sich selbst?
xnor
@xnor du nicht. Ich habe vergessen, die übliche Konvention zu erwähnen, dass sich die "Linie" zur Vereinfachung in jedem Domino-Spiel willkürlich biegen kann. auch gut zur Vermeidung von Tischkanten :)
Sparr
Ich denke, es könnte möglich sein, eine pathologische Spielordnung mit einem doppelten Satz von 12 Dominosteinen zu erzeugen, die eine Selbstüberschneidung nicht vermeiden können. Mit größeren Sets ist das definitiv möglich. Lassen Sie uns diese Fälle einfach ignorieren. Im schlimmsten Fall können sie durch Biegen der Linie in 3D gelöst werden :)
Sparr
Müssen wir tatsächlich mit Dominosteinen mit Werten> 6 umgehen können? Wenn ja, könnten Sie dies in der Spezifikation klarer machen und möglicherweise einen Testfall hinzufügen. Ansonsten aber schöne Herausforderung - +1 von mir.
Shaggy
@ Shaggy fügte einen Testfall für einen größeren Domino hinzu
Sparr

Antworten:

1

Haskell , 188 174 168 Bytes

f(p:r)=[p]!r$p?p
(s!(p:r))o|b<-[p,reverse p]=or[(q:s)!r$q%o|q<-b,elem(q!!0)o,all(`notElem`s)b]
(s!_)o=1<3
p@[x,y]?r=[c|x==y,c<-p]++r
p@[x,y]%(a:r)|a/=x=a:p%r|z<-y:r=p?z

Probieren Sie es online aus! Anwendungsbeispiel: f [[6,6],[6,5],[5,3],[3,0]]AusbeutenTrue .

Ungolfed:

f :: [[Int]] -> Bool
f (p:r) = check [p] (double p p) r

check :: [[Int]] -> [Int] -> [[Int]] -> Bool
check seen open [] = True
check seen open ([x,y]:r) = 
	  notElem [x,y] seen
   && notElem [y,x] seen
   && (elem x open && check ([x,y]:seen) (update [x,y] open) r 
   ||  elem y open && check ([y,x]:seen) (update [y,x] open) r)

double :: [Int] -> [Int] -> [Int]
double [x,y] rest = 
    if x==y 
    then [x,y] ++ rest 
    else rest

update :: [Int] -> [Int] -> [Int]
update [x,y] (a:rest) = 
    if x==a 
    then double [x,y] (y:rest) 
    else a : update [x,y] rest

Probieren Sie es online aus!

Laikoni
quelle
0

R , 224 Bytes

function(L,x=c(),y=c()){o=T
z=length
if(z(L)){p=sort(L[1:2])
w=rep(p,2-(p[2]>p[1]))
x=rbind(p,x)
if(z(y)){m=match(p,y,0)
v=which.max(m)
if(m[v]>0){y=y[-m[v]]
w=w[-v]}}
y=c(y,w)
L=L[-1:-2]
o=o&f(L,x,y)&!sum(duplicated(x))}
o}

Probieren Sie es online aus!

Der Code empfängt die Teile als geordnete Liste und gibt TRUE oder FALSE gemäß den Spezifikationen zurück. Die Funktion scannt rekursiv jedes Stück, fügt das Stück einem Index hinzu, um das Fehlen von Duplikaten zu überprüfen, und verfolgt die verfügbaren Einfügepunkte, um zu überprüfen, ob das Stück effektiv zum Stapel hinzugefügt werden kann. Die Handhabung von Stückverbindungen (z. B. Anbringen eines 1-2 durch das 1 oder durch das 2) erfolgt auf gierige Weise, so dass es nicht völlig unmöglich ist, dass einige seltsame Konfigurationen explodieren.

NofP
quelle
Gier ist leider nicht gut genug. Bedenken 6-6 6-3 6-2 2-3Sie, dass Sie in der Lage sein müssen, dies mit 2-_oder als 3-_nächstes zu handhaben, da das 2-3an beiden Enden platziert werden könnte.
Sparr
Ich gucke mal.
NofP