13
3
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:
- Replace the
2H
with the adjacent2S
, so we end up with2S,1S,2D
- Replace the
2S
with the adjacent1S
, so we end up with2H,1S,2D
- Replace the
2H
with the2D
(at a distance of 3), so we end up with2D,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 code-golf, 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? – feersum – 2015-08-26T05:07:34.980
Yes. "The replaced card must always precede the replacing card" – Nathan Merrill – 2015-08-26T05:11:10.527
6Every 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. – Level River St – 2015-08-26T06:12:39.977
Counting the number of possible game states instead of paths I get a smaller number: around 4^52 = 2E30. Still, this is too large to search exhaustively – Level River St – 2015-08-26T06:24:42.907
@steveverrill I have a golfable Python program that solves the test cases in about 2 seconds. I believe this shouldn't be too bad as a code-golf if the program is required to terminate in a reasonable about of time. – PurkkaKoodari – 2015-08-26T06:28:04.957
@Pietu1998 Can your program be mathematically demonstrated to be capable of solving all possible test cases? If not, then by my interpretation of the current rules it's an invalid (but interesting) entry. They suspected that Rubik's cube could always be solved in 20 moves once they had analysed all symmetrical positions. But it wasn't proved until decades later, when all positions were exhaustively searched. If the requirement is to solve the test cases that should be stated, but it would make the question vulnerable to hardcoding. With that approach, a wider set of test cases would help – Level River St – 2015-08-26T06:39:41.740
An alternative for exhaustive searches (which is what the current rules appear to require) would be to use a reduced deck of 16 cards, giving a search space of 4^16 = 2^32, which can be fully searched in a few minutes. – Level River St – 2015-08-26T06:43:07.270
@steveverrill Well, my program just does a depth-first search through all possibilities. I assume that'd mean a trivial test case might take 1000 years. – PurkkaKoodari – 2015-08-26T06:43:15.337
@steveverrill There are unsolvable accordion games. For example KC QD JH TS 9C 8D 7H 6S 5C 4D 3H 2S AC KD QH JS TC 9D 8H 7S 6C 5D 4H 3S 2C AD KH QS JC TD 9H 8S 7C 6D 5H 4S 3C 2D AH KS QC JD TH 9S 8C 7D 6H 5S 4C 3D 2H AS. But the question assumes a solvable input. – orlp – 2015-08-26T06:44:53.003
@orlp indeed CDHS repeated 13 times is not solvable. The question does not currently state that the input will be solvable, nor is there any bound on how difficult it might be to solve. That's why I think this question as it stands is too broad, unless someone can come up with a decent mathematical analysis. I like the question though. (As an example of the issue I am trying to highlight, consider that there are implementations of quicksort which work great on random input, but run at a snail's pace when fed an already sorted input.) – Level River St – 2015-08-26T06:55:04.207
@steveverrill The question does state that: " You can assume that each input is solvable. " And for fun: https://github.com/orlp/pdqsort .
– orlp – 2015-08-26T06:59:45.020Orlp: Oops, I missed that. Given that @Pietu1998 says he has found a reasonable average time complexity (which is an important discovery), maybe the question is OK as it is, despite the fact that the worst case time complexity may be astronomical. – Level River St – 2015-08-26T07:12:36.270
@steveverrill Well, my solution is astronomically slow without memoization, but by adding a memoizer it's rather quick. – PurkkaKoodari – 2015-08-26T07:28:18.737
1@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. – Level River St – 2015-08-26T07:33:35.800
@steveverrill Well, I could submit both versions. The memoizer [sic] does not change the behavior of the program, so I believe I can still claim the byte count of the golfed program while testing with the memoizer. – PurkkaKoodari – 2015-08-26T07:36:34.053
3I'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. – Nathan Merrill – 2015-08-26T07:41:33.133
4Furthermore, 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. – Nathan Merrill – 2015-08-26T07:50:30.573
@NathanMerrill With that clarification, I've retracted my close vote, and upvoted the question. I suggest you edit those points into the question. Note that according to my analysis, 16 cards in worst case might still take several minutes. – Level River St – 2015-08-26T07:56:31.967