Solve a game of Accordion

Accordion is a solitaire card game I recently came across where nearly every layout is solvable, but incredibly hard. You can play it here.

Rules

52 face cards are placed face-up in a random order. Each turn, you replace a card with a later card, where the two cards:

• Share a suit or number and
• Are at a distance of 1 (adjacent) or 3 (two cards in between).

The game is won when there is only 1 card remaining. You can assume that each input is solvable. The replaced card must always precede the replacing card.

Example

As an example, consider the following layout:

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


There are 3 possible moves here:

1. Replace the 2H with the adjacent 2S, so we end up with 2S,1S,2D
2. Replace the 2S with the adjacent 1S, so we end up with 2H,1S,2D
3. Replace the 2H with the 2D (at a distance of 3), so we end up with 2D,2S,1S

Of those 3 moves, only the last one has the possibility of winning (You win by replacing 2D <- 2S, then 2S <- 1S).

Input/Output

Your job is to write an Accordion solver. You are passed a list of cards, and you need to return a list of moves to solve the game.

You are passed a list of cards as a comma-delimited string, where each card is passed as an integer representing their numeric value, then a character representing their suit.

You must return a list of replacements as a comma-delimited string, where each replacement is in the format Card <- Card (following the card format described above). The first card in each pair is the card being replaced.

Test cases:

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


While this competition is a , I am particularly interested in time-efficient solutions, and am likely to reward ingenious solutions with bounties. That said, solutions that take astronomical amounts of time are still acceptable (I'd recommend testing with a smaller deck, such as a 16-card, 4 suit deck).

• Do your rules mention that the moves can only be made in one direction? Aug 26, 2015 at 5:07
• Every card on the table has on average about 0.25 + 0.25 = 0.5 legal moves. Therefore the search space is about 52! * 0.5 = 4E67. The challenge as written (with code golf tag) can only be interpreted as being required to search this entire space and report any solution (or "none" if exhausted), which leaves little room for ingenuity and requires astronomical timescales. I suggest you make this a code challenge, considering success rate and time, and either reduce the influence of code length on the score or eliminate it altogether. Aug 26, 2015 at 6:12
• @Pietu1998 and therein lies the problem. I assume the memorizer is costing you bytes, so you should submit the version without the memorizer as the golfed version, but then it becomes impossible to test on a 52 card deck. Codegolf doesn't work well as a scoring system on problems with large search spaces. Aug 26, 2015 at 7:33
• I'm ok with astronomical runtimes for those wanting to be code-golf competitive. However, people are certainly able (and encouraged) to post answers that aren't competitive, and are about run-time. Aug 26, 2015 at 7:41
• Furthermore, if you are wanting to test a code-golf solution, a 52-card deck is not needed. A 16-card (4 suit) deck should provide short runtimes, and verify correctness. Aug 26, 2015 at 7:50

Python 3, 274272 271 bytes

2 bytes saved thanks to @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'')


This is extremely slow. However, you can try it with a memoize. This has a few extra list-tuple conversions, but is otherwise equivalent.

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


Even this one is astronomically slow with certain inputs.

The code uses strings, not numbers, so it also supports notation like KH instead of 13H.

Example:

\$ 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

• Use functools.lru_cache instead of writing your own.
– orlp
Aug 26, 2015 at 10:48
• @orlp I would, but as list is unhashable it doesn't work. Aug 26, 2015 at 11:15
• Then use tuples.
– orlp
Aug 26, 2015 at 11:16
• @orlp OK, but that would require changes to the code (e.g. str.split returns list). I'd prefer the two programs to be functionally equivalent. Aug 26, 2015 at 11:17
• You could do h=lambda p:lru_cache(None)(g)(''.join(p)).
– orlp
Aug 26, 2015 at 11:20