Accordion é um jogo de cartas de paciência que me deparei recentemente, onde quase todos os layouts são solucionáveis, mas incrivelmente difíceis. Você pode jogar aqui .

Regras

52 cartões de face são colocados com a face para cima em uma ordem aleatória. A cada turno, você substitui um cartão por um cartão posterior, onde os dois cartões :

• Compartilhe um terno ou número e
• Estão a uma distância de 1 (adjacente) ou 3 (duas cartas no meio).

O jogo é ganho quando restar apenas 1 carta . Você pode assumir que cada entrada é solucionável. O cartão substituído deve sempre preceder o cartão de substituição.

Exemplo

Como exemplo, considere o seguinte layout:

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

Existem 3 movimentos possíveis aqui:

1. Substitua o 2Hpelo adjacente 2S, para que acabemos com2S,1S,2D
2. Substitua o 2Spelo adjacente 1S, para que acabemos com2H,1S,2D
3. Substitua 2Hpor 2D(a uma distância de 3), para que acabemos com2D,2S,1S

Desses 3 lances, apenas o último tem a possibilidade de ganhar (você ganha substituindo 2D <- 2S, então 2S <- 1S).

Entrada / Saída

Seu trabalho é escrever um solucionador de acordeão . Você recebe uma lista de cartas e precisa retornar uma lista de jogadas para resolver o jogo.

Você recebe uma lista de cartões como uma sequência delimitada por vírgula, onde cada cartão é passado como um número inteiro representando seu valor numérico e, em seguida, como um caractere representando seu naipe.

Você deve retornar uma lista de substituições como uma sequência delimitada por vírgula, onde cada substituição está no formato Card <- Card(seguindo o formato do cartão descrito acima). A primeira carta de cada par é a carta que está sendo substituída.

Casos de teste:

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

Embora essa competição seja um código de golfe , estou particularmente interessado em soluções com eficiência de tempo e provavelmente recompensarei soluções engenhosas com recompensas. Dito isso, as soluções que levam tempo astronômico ainda são aceitáveis ​​(eu recomendaria testar com um baralho menor, como um baralho de 16 cartas e 4 naipes).

Python 3, 274 272 271 bytes

2 bytes salvos graças 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'')

Isso é extremamente lento. No entanto, você pode tentar com um memorando . Isto tem alguns extras list- tupleconversões, mas de resto é 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'')

Mesmo este é astronomicamente lento com certas entradas.

O código usa cadeias de caracteres, não números, então também suporta notação como em KHvez de 13H.

Exemplo:

$ 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