13
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ Do your rules mention that the moves can only be made in one direction? \$\endgroup\$ – feersum Aug 26 '15 at 5:07
  • 6
    \$\begingroup\$ 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. \$\endgroup\$ – Level River St Aug 26 '15 at 6:12
  • 1
    \$\begingroup\$ @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. \$\endgroup\$ – Level River St Aug 26 '15 at 7:33
  • 3
    \$\begingroup\$ 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. \$\endgroup\$ – Nathan Merrill Aug 26 '15 at 7:41
  • 4
    \$\begingroup\$ 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. \$\endgroup\$ – Nathan Merrill Aug 26 '15 at 7:50
5
\$\begingroup\$

Python 3, 274 272 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
\$\endgroup\$
  • \$\begingroup\$ Use functools.lru_cache instead of writing your own. \$\endgroup\$ – orlp Aug 26 '15 at 10:48
  • \$\begingroup\$ @orlp I would, but as list is unhashable it doesn't work. \$\endgroup\$ – PurkkaKoodari Aug 26 '15 at 11:15
  • \$\begingroup\$ Then use tuples. \$\endgroup\$ – orlp Aug 26 '15 at 11:16
  • \$\begingroup\$ @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. \$\endgroup\$ – PurkkaKoodari Aug 26 '15 at 11:17
  • \$\begingroup\$ You could do h=lambda p:lru_cache(None)(g)(''.join(p)). \$\endgroup\$ – orlp Aug 26 '15 at 11:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.