Connect 4: Finde die Fälschung!

35

In die Bank wurde eingebrochen, und alle lokalen Mafia-Schläger haben ein ungewöhnliches Alibi: Sie waren zu Hause und haben Connect 4 gespielt! Um bei der Untersuchung behilflich zu sein, müssen Sie ein Programm zur Validierung aller beschlagnahmten Connect 4-Karten schreiben, um zu überprüfen, ob die Positionen tatsächlich Positionen aus einem gültigen Connect 4-Spiel sind und nicht hastig zusammengesetzt wurden sobald die polizei an die tür geklopft hat.

Die Regeln für Connect 4: Spieler Rund Ywechseln sich ab, um Kacheln ihrer Farbe in Spalten eines 7x6-Gitters abzulegen. Wenn ein Spieler ein Plättchen in die Spalte fallen lässt, fällt es nach unten, um die niedrigste unbesetzte Position in dieser Spalte einzunehmen. Gelingt es einem Spieler, einen horizontalen, vertikalen oder diagonalen Durchgang von vier Steinen seiner Farbe auf dem Brett zu erzielen, gewinnt er und das Spiel endet sofort.

Zum Beispiel (beim RStarten) ist das Folgende eine unmögliche Connect 4-Position.

| | | | | | | |
| | | | | | | |
| | | | | | | |
| | |R| | | | |
| | |Y| | | | |
|R| |Y| | | | |

Ihr Programm oder Ihre Funktion muss eine Connect 4-Karte aufnehmen und entweder zurückgeben

  • Ein falscher Wert, der angibt, dass die Position unmöglich ist oder
  • Eine Reihe von Zahlen von 1 bis 7, was auf eine mögliche Folge von Bewegungen zu dieser Position (die Spalten führen , sind nummeriert , 1um 7von links nach rechts, so dass die Sequenz 112, zum Beispiel zeigt eine rote Bewegung in der Spalte 1, gefolgt von einem gelben move in der Spalte 1, gefolgt von einem roten Zug in der Spalte 2). Sie können eine andere Spaltennummer als 1234567 wählen, sofern Sie dies in Ihrer Lösung angeben. Wenn Sie die Liste in einem anderen Format zurückgeben möchten; Zum Beispiel als Array, [2, 4, 3, 1, 1, 3]dann ist das auch in Ordnung, solange es einfach ist zu sehen, was die Bewegungen sind.

Sie können die Tafel in jedem vernünftigen Format lesen, auch mit anderen Buchstaben als Rund Yfür die Spieler, aber Sie müssen angeben, welcher Spieler zuerst spielt. Sie können davon ausgehen, dass das Board immer 6x7 ist und zwei Spieler anwesend sind.

Sie können davon ausgehen, dass die Positionen, die Sie erhalten, zumindest physisch auf einer Standard-Connect 4-Karte erstellt werden können. dh, dass es keine "schwebenden" Teile geben wird. Sie können davon ausgehen, dass das Board nicht leer ist.

Dies ist Codegolf, also gewinnt die kürzeste Antwort. Es gelten Standardlücken.

Beispiele

| | | | | | | |
| | | | | | | |
| | | | | | | |
| | | | | | | | --> 1234567 (one possible answer)
| | | | | | | |
|R|Y|R|Y|R|Y|R|

| | | | | | | |
| | | | | | | |
| | | | | | | |
| | |R| | | | | --> false
| | |Y| | | | |
|R| |Y| | | | |

| | | | | | | |
| | |Y| | | | |
| | |R| | | | |
| | |Y| | | | | --> 323333 (only possible answer)
| | |R| | | | |
| |Y|R| | | | |

| | | | | | | |
| | | | | | | |
| | | | | | | |     
| | | | | | | | --> false (this is the position arising after
| |Y|Y|Y|Y| | |     the moves 11223344, but using those moves
| |R|R|R|R| | |     the game would have ended once R made a 4)

| | | | | | | |
| | | | | | | |
|Y| | | | | | |     
|R|Y| | | | | | --> 2134231211 (among other possibilities)
|R|R|Y| | | | |
|Y|R|R|Y| | | |

| | | | | | | |
| | | | | | | |
|Y| | | | | | |     
|R|Y| | | | | | --> false (for example, 21342312117 does not
|R|R|Y| | | | |     work, because Y has already made a diagonal 4)
|Y|R|R|Y| | |R|

| | | | | | | |
| | | | | | | |
| | | | | | | |     
| | | | | | | | --> 112244553 or similar
|Y|Y| |Y|Y| | |
|R|R|R|R|R| | |
John Gowers
quelle
John, weißt du aus Neugier, ob es einen Non-Brute-Force-Algorithmus gibt?
Jonah

Antworten:

9

Jelly , 57 Bytes

ŒṪŒ!µ0ịŒṬ¬a³ZU,Ɗ;ŒD$€Ẏṡ€4Ḅo1%15;Ḋ€ṢṚ$Ƒƙ$Ȧȧœị³$2R¤ṁ$ƑµƇṪṪ€

Nimmt eine Matrix, in der nicht 0gefüllt ist, 1zuerst und dann 2gespielt wird. Ergibt eine Liste mit 1-indizierten Spalten, die leer sind, wenn eine Fälschung identifiziert wurde.

Probieren Sie es online! (zu ineffizient für mehr als 7 Teile in weniger als einer Minute)

Hinweis:

  1. Nimmt an, dass keine "schwebenden" Teile vorhanden sind (korrigieren Sie dies, indem Sie ZṠṢ€Ƒȧ+6 Bytes voranstellen )
  2. Nimmt an, dass das leere Brett eine Fälschung ist
Jonathan Allan
quelle
11

JavaScript (ES6),  202 194 187  183 Bytes

Nimmt die Eingabe als Matrix mit 2 für rot, 4 für gelb und 0für leer. Gibt eine Zeichenfolge mit 0 indizierten Zügen zurück (oder eine leere Zeichenfolge, wenn es keine Lösung gibt). Rote beginnen das Spiel.

m=>(p=[...'5555555'],g=(c,s=o='')=>/2|4/.test(m)?['',0,2,4].some(n=>m.join``.match(`(1|3)(.{1${n}}\\1){3}`))?o:p.map((y,x)=>m[m[y][x]--^c||p[g(c^6,s+x,p[x]--),x]++,y][x]++)&&o:o=s)(2)

Probieren Sie es online!

Wie?

Die rekursive Funktion G versucht alles zu ersetzen 2und 4gibts in der eingabematrix mit 1und 3jeweils.

Dabei wird sichergestellt, dass keine vier aufeinanderfolgenden ungeraden Werte gespielt werden, bis alle geraden Werte verschwunden sind (dh wenn eine Seite gewinnt, muss dies der letzte Zug sein).

Die Reihe y des nächsten verfügbaren Steckplatzes für jede Spalte x ist gespeichert in p[x].

Kommentiert

m => (                            // m[] = input matrix
  p = [...'5555555'],             // p[] = next row for each column
  g = (c,                         // g = recursive function taking c = color,
          s = o = '') =>          //     s = current solution, o = final output
    /2|4/.test(m) ?               // if the matrix still contains at least a 2 or a 4:
      ['', 0, 2, 4]               //   see if we have four consecutive 1's or 3's
      .some(n =>                  //   by testing the four possible directions
        m.join``                  //   on the joined matrix, using
        .match(                   //   a regular expression where the number of characters
          `(1|3)(.{1${n}}\\1){3}` //   between each occurrence is either 1, 10, 12 or 14
        )                         //   (horizontal, diagonal, vertical, anti-diagonal)
      ) ?                         //   if we have a match:
        o                         //     abort and just return the current value of o
      :                           //   else:
        p.map((y, x) =>           //     for each cell at (x, y = p[x]):
          m[                      // 
            m[y][x]--             //       decrement the value of the cell
            ^ c ||                //       compare the original value with c
            p[                    //       if they're equal:
              g(                  //         do a recursive call with:
                c ^ 6,            //           the other color
                s + x,            //           the updated solution
                p[x]--            //           the updated row for this column
              ),                  //         end of recursive call
              x                   //         then:
            ]++,                  //         restore p[x]
            y                     //         and restore m[y][x]
          ][x]++                  //         to their initial values
        ) && o                    //     end of map(); yield o
    :                             // else:
      o = s                       //   we've found a solution: copy s to o
)(2)                              // initial call to g() with c = 2
Arnauld
quelle
Hinweis Ich habe gefragt: "Dürfen wir davon ausgehen, dass die leere Karte nicht als Eingabe angegeben wird?" - Wenn wir damit fertig werden müssen, muss Ihr Code angepasst werden.
Jonathan Allan
Ich weiß nicht warum, f([ [0,0,0,0,0,0,0], [0,0,0,0,0,0,0], [0,0,0,0,0,0,0], [0,0,2,0,2,0,0], [0,2,2,0,2,2,0], [1,1,1,1,1,1,1] ])endet 0 und f([ [0,0,0,0,0,0,0], [0,0,0,0,0,0,0], [0,0,0,0,0,0,0], [0,0,2,0,2,0,0], [2,2,2,0,2,2,1], [1,1,1,1,1,1,1] ])sollte wahr sein
Nahuel Fouilleul
@NahuelFouilleul Vielen Dank für den Hinweis. Ich habe den Code korrigiert und diese Testfälle hinzugefügt.
Arnauld
2

Python 2 , 295 285 Bytes

def f(a):
 if 1-any(a):return[]
 p=sum(map(len,a))%2
 for i in R(7):
	if a[i][-1:]==`p`:
	 b=a[:];b[i]=b[i][:-1];L=f(b)
	 if L>1>(`1-p`*4in','.join([J((u[j]+' '*14)[n-j]for j in R(7))for n in R(12)for u in[b,b[::-1]]]+b+map(J,zip(*[r+' '*7for r in b])))):return L+[i]
R=range;J=''.join

Probieren Sie es online!

-10 Danke an Jo King .

Die Eingabe ist eine Liste von Zeichenfolgen, die die Spalten darstellen. mit '1' für Rot und '0' für Gelb. Die Saiten sind nicht gepolstert. Also der (falsche) Fall:

| | | | | | | |
| | | | | | | |
|Y| | | | | | |
|R|Y| | | | | |
|R|R|Y| | | | |
|Y|R|R|Y| | |R|

wird eingegeben als:

[
  '0110',
  '110',
  '10',
  '0',
  '',
  '',
  '1'
]

Die Ausgabe ist eine Liste von Spaltenindizes, die 0-indiziert sind und das Board bilden können. oderNone wenn es nicht gültig ist.

Akzeptiert die leere Karte als gültig (gibt die leere Liste []anstelle von zurück)None ).

Dieser Ansatz ist vom letzten bis zum ersten Zug rekursiv: Basierend auf der Parität der Gesamtzahl der ausgeführten Züge entfernen wir entweder den letzten roten Zug oder den letzten gelben Zug (oder schlagen fehl, wenn dies nicht möglich ist). Überprüfen Sie das resultierende Brett, um festzustellen, ob der Gegner 4-in-a-row hat (in diesem Fall scheitern Sie, weil das Spiel bereits gestoppt sein sollte). ansonsten rekursiv, bis die Karte leer ist (was gültig ist).

Der 4-in-eine-Zeile-Code ist der aufgedunsenste Teil. Alle diagonalen Zeichenfolgen für die Matrix bwerden generiert von:

[
    ''.join(
        (u[j]+' '*14)[n-j] for j in range(7)
    )
    for u in[b,b[::-1]]for n in range(12) 
]

Hier werden zuerst die "abfallenden" Diagonalen und dann die "auffallenden" Diagonalen aufgelistet.

Chas Brown
quelle