Accordion es un juego de cartas solitario que encontré recientemente donde casi todos los diseños son solucionables, pero increíblemente difícil. Puedes jugarlo aquí .

Reglas

52 cartas de cara se colocan boca arriba en un orden aleatorio. Cada turno, reemplaza una carta con una carta posterior, donde las dos cartas :

• Comparte un traje o número y
• Están a una distancia de 1 (adyacente) o 3 (dos cartas en el medio).

El juego se gana cuando solo queda 1 carta . Puede suponer que cada entrada es solucionable. La tarjeta reemplazada siempre debe preceder a la tarjeta reemplazada.

Ejemplo

Como ejemplo, considere el siguiente diseño:

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

Hay 3 movimientos posibles aquí:

1. Reemplaza el 2Hcon el adyacente 2S, así terminamos con2S,1S,2D
2. Reemplaza el 2Scon el adyacente 1S, así terminamos con2H,1S,2D
3. Reemplace el 2Hcon el 2D(a una distancia de 3), por lo que terminamos con2D,2S,1S

De esos 3 movimientos, solo el último tiene la posibilidad de ganar (Ganas reemplazando 2D <- 2S, entonces 2S <- 1S).

De entrada y salida

Su trabajo es escribir un solucionador de acordeón . Se te pasa una lista de cartas y necesitas devolver una lista de movimientos para resolver el juego.

Se le pasa una lista de tarjetas como una cadena delimitada por comas, donde cada tarjeta se pasa como un número entero que representa su valor numérico, luego un personaje que representa su palo.

Debe devolver una lista de reemplazos como una cadena delimitada por comas, donde cada reemplazo está en el formato Card <- Card(siguiendo el formato de tarjeta descrito anteriormente). La primera carta de cada par es la carta que se reemplaza.

Casos de prueba:

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

Si bien esta competencia es un código de golf , estoy particularmente interesado en soluciones que ahorren tiempo y es probable que recompense soluciones ingeniosas con recompensas. Dicho esto, las soluciones que toman cantidades astronómicas de tiempo aún son aceptables (recomendaría probar con una baraja más pequeña, como una baraja de 16 cartas y 4 palos).

Python 3, 274 272 271 bytes

2 bytes guardados gracias a @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'')

Esto es extremadamente lento. Sin embargo, puedes probarlo con un memorizar . Esto tiene unos extra list- tupleconversiones, pero por lo demás equivalente.

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'')

Incluso este es astronómicamente lento con ciertas entradas.

El código usa cadenas, no números, por lo que también admite notación como en KHlugar de 13H.

Ejemplo:

$ 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