Accordion ist ein Solitaire-Kartenspiel, auf das ich kürzlich gestoßen bin. Fast jedes Layout ist lösbar, aber unglaublich schwer. Sie können es hier spielen .

Regeln

52 Bildkarten werden in zufälliger Reihenfolge aufgedeckt. In jedem Spielzug ersetzst du eine Karte durch eine spätere, wobei die beiden Karten :

• Teilen Sie einen Anzug oder eine Nummer und
• Sind in einem Abstand von 1 (nebeneinander) oder 3 (zwei Karten dazwischen).

Das Spiel ist gewonnen, wenn nur noch 1 Karte übrig ist . Sie können davon ausgehen, dass jede Eingabe lösbar ist. Die ersetzte Karte muss immer vor der ersetzenden Karte stehen.

Beispiel

Betrachten Sie als Beispiel das folgende Layout:

2H,2S,1S,2D  (H: Hearts, S: Spades, D: Diamonds)

Hier gibt es 3 mögliche Züge:

1. Ersetzen Sie das 2Hdurch das benachbarte 2S, so dass wir am Ende mit2S,1S,2D
2. Ersetzen Sie das 2Sdurch das benachbarte 1S, so dass wir am Ende mit2H,1S,2D
3. Ersetzen Sie die 2Hmit 2D(in einem Abstand von 3), so dass wir am Ende mit2D,2S,1S

Von diesen 3 bewegt, hat nur die letzte , die Möglichkeit zu gewinnen (Sie gewinnen durch den Austausch 2D <- 2S, dann 2S <- 1S).

Input-Output

Ihre Aufgabe ist es, einen Akkordeonlöser zu schreiben . Sie erhalten eine Liste mit Karten und müssen eine Liste mit Zügen zurückgeben, um das Spiel zu lösen.

Sie erhalten eine Kartenliste als durch Kommas getrennte Zeichenfolge. Dabei wird jede Karte als Ganzzahl übergeben, die ihren numerischen Wert darstellt, und anschließend als Zeichen, das ihre Farbe darstellt.

Sie müssen eine Liste der Ersetzungen als durch Kommas getrennte Zeichenfolge zurückgeben, wobei jede Ersetzung im Format Card <- Card(entsprechend dem oben beschriebenen Kartenformat) vorliegt. Die erste Karte in jedem Paar ist die Karte, die ersetzt wird.

Testfälle:

5H,1C,12S,9C,9H,2C,12C,11H,10C,13S,3D,8H,1H,12H,4S,1D,7H,1S,13D,13C,7D,12D,6H,10H,4H,8S,3H,5D,2D,11C,10S,7S,4C,2H,3C,11S,13H,3S,6C,6S,4D,11D,8D,8C,6D,5C,7C,5S,9D,10D,2S,9S
5H,9C,11H,7S,7D,12D,6H,10S,3H,4D,12C,2S,3C,5C,7H,6S,1H,8S,2H,11S,4C,10D,12H,9H,2D,4H,6C,13H,11C,2C,10H,8C,1S,11D,3S,12S,7C,5D,13S,8D,4S,6D,13C,3D,8H,13D,1D,9D,9S,1C,5S,10C
7H,11C,8C,7S,10D,13H,4S,10C,4D,2C,4H,13D,3C,2H,12C,6C,9H,4C,12H,11H,9S,5H,8S,13S,8H,6D,2S,5D,11D,10S,1H,2D,5C,1C,1S,5S,3H,6S,7C,11S,9C,6H,8D,12S,1D,13C,9D,12D,3D,7D,10H,3S

Während dieser Wettbewerb ein Code-Golf ist , bin ich besonders an zeiteffizienten Lösungen interessiert und werde geniale Lösungen wahrscheinlich mit Kopfgeldern belohnen. Trotzdem sind Lösungen, die astronomisch viel Zeit in Anspruch nehmen, immer noch akzeptabel (ich würde empfehlen, mit einem kleineren Deck zu testen, z. B. einem Deck mit 16 Karten und 4 Farben).

Python 3, 274 272 271 Bytes

2 Bytes gespart dank @orlp .

def g(p):
 q=lambda a:[[i,a]for i in range(len(p)-a)if p[i][:-1]==p[i+a][:-1]or p[i][-1]in p[i+a]]
 for n in q(1)+q(3):
  s=sum(n);c=p[:s]+p[s+1:];c[n[0]]=p[s]
  if g(c):return p[n[0]]+' <- '+p[s]+','+g(c)
 return' 'if len(p)<2else[]
print(g(input().split(','))[:-2]or'')

Das ist extrem langsam. Sie können es jedoch mit einem Memo versuchen . Dies hat ein paar extra list- tupleUmbauten, aber ansonsten gleichwertig.

import functools
@functools.lru_cache(maxsize=None)
def g(p):
 q=lambda a:[[i,a]for i in range(len(p)-a)if p[i][:-1]==p[i+a][:-1]or p[i][-1]in p[i+a]]
 for n in q(1)+q(3):
  s=sum(n);c=list(p[:s]+p[s+1:]);c[n[0]]=p[s]
  if g(tuple(c)):return p[n[0]]+' <- '+p[s]+','+g(tuple(c))
 return' 'if len(p)<2else[]
print(g(tuple(input().split(',')))[:-2]or'')

Sogar dieser ist mit bestimmten Eingaben astronomisch langsam.

Der Code verwendet Strings und keine Zahlen, daher unterstützt er auch Notationen wie KHanstelle von 13H.

Beispiel:

$ python accordion.py
5H,9C,11H,7S,7D,12D,6H,10S,3H,4D,12C,2S,3C,5C,7H,6S,1H,8S,2H,11S,4C,10D,12H,9H,2D,4H,6C,13H,11C,2C,10H,8C,1S,11D,3S,12S,7C,5D,13S,8D,4S,6D,13C,3D,8H,13D,1D,9D,9S,1C,5S,10C
7S <- 7D,7D <- 12D,3C <- 5C,12H <- 9H,11C <- 2C,3S <- 12S,13D <- 1D,1D <- 9D,9D <- 9S,2S <- 6S,7H <- 1H,6S <- 8S,1H <- 2H,8S <- 11S,2H <- 9H,10D <- 2D,9H <- 4H,4H <- 4C,5C <- 4C,4D <- 4C,4C <- 12C,10S <- 11S,11H <- 11S,6H <- 3H,12D <- 2D,12C <- 2C,2C <- 6C,6C <- 8C,12S <- 13S,5D <- 6D,6D <- 8D,8D <- 3D,4S <- 9S,13S <- 9S,11D <- 3D,7C <- 1C,1S <- 1C,1C <- 13C,8C <- 13C,13C <- 13H,13H <- 10H,2D <- 3D,3D <- 3H,3H <- 8H,8H <- 10H,11S <- 5S,5H <- 10H,5S <- 9S,10H <- 10C,10C <- 9C,9C <- 9S