Patience, Patience

[AngelB]

My first stab at a programming puzzle:

A variation of the card game patience is played according to the following rules:

Four cards are dealt face up on the table.
If two (or more) of the cards share the same face value, then the card furthest to the right is picked up and placed face up on the card of the same value. Once all possible movements have been made, four new cards are dealt face up on the existing piles (or any spaces created by card movements).

Still with me? OK...

Once the deck is exhausted, the four piles are picked up and piled together starting from the right hand side, so the far right hand pile ends up at the bottom and the far left hand pile at the top. The object of the game is to finish with the deck arranged into 13 groups of four (they do not have to be in numerical order).

The questions therefore are:

1. From a randomly shuffled deck, is there a maximum number of moves required to finish the game?
2. Is it possible to finish every game?

Let me know if anything needs explaining better (I'm betting it will need it!)


Geraint

Let's think the unthinkable, let's do the undoable, let's prepare to grapple with the ineffable itself, and see if we may not eff it after all

 

[LFI]

Well, it's certainly possible that a game could not be finished. In the most unlikely example, if the cards were pre-arranged in this fashion:
A 2 3 4 A 2 3 4 A 2 3 4 A 2 3 4 5 6 7 8 5 6 7 8 5 6 7 8 5 6 7 8 9 10 J Q 9 10 J Q 9 10 J Q 9 10 J Q K K K K

...then the stack would end up the same at the end of each "round" as it started.

Of course, the shortest game would be if the deck were pre-arranged similar to:
AAAA2222333344445555666677778888999910101010JJJJQQQQKKKK

Counting three moves for every four cards, 39 moves is the minimum.

Every game therefore would take from 39 to an infinite number of moves.

Who ever thought logic would be so useless! I know this is not really what you were after. Nevertheless, it's nice to know the bounding conditions!

Dav

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
...east is east and west is west and if you take cranberries and stew them like applesauce
they taste much more like prunes than rhubarb does

 

[AngelB]

LFI
OK, I'm with you on the shortest possible game and agree with your numbers. However, your example of an unsolvable game is not quite there. If the deck were in the order you stated then after being dealt, the 4 stacks would look like this:
A 2 3 4
A 2 3 4
A 2 3 4
A 2 3 4
5 6 7 8
5 6 7 8
5 6 7 8
5 6 7 8
9 10 J Q
9 10 J Q
9 10 J Q
9 10 J Q
K K K K

The kings would all move over to the far left hand stack and when picked up, the card would be in the following order:

A A A A 5 5 5 5 9 9 9 9 K K K K 2 2 2 2 6 6 6 6 10 10 10 10 3 3 3 3 7 7 7 7 J J J J 4 4 4 4 8 8 8 8 Q Q Q Q

after which the game is done. I've yet to have a go at a programming solution, but I'm hoping to have a go at it sometime this week.


Geraint

Let's think the unthinkable, let's do the undoable, let's prepare to grapple with the ineffable itself, and see if we may not eff it after all

 

[Sheco]

Maybe spread that last set around?

A 2 3 [red]K[/red]
A 2 3 4
A 2 3 4
A 2 3 4
5 6 7 [red]K[/red]
5 6 7 8
5 6 7 8
5 6 7 8
9 10 J [red]K[/red]
9 10 J Q
9 10 J Q
9 10 J Q
K [red]4 8 Q[/red]

 

[LFI]

I was under the impressiong that after you lay down the first four cards, you make all the moves you can, THEN consolidate the piles BEFORE laying down the next set of four. I see that I got that wrong.

I'll have to re-think...

Dave


~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
...east is east and west is west and if you take cranberries and stew them like applesauce
they taste much more like prunes than rhubarb does

 

[AngelB]

Sorry Dave, I knew there would be a hole in my explanation somewhere!

Sheco, sorry not really following you. What outcome do you expect from swapping those cards around? A quick shuffle of cells in Excel shows that the deck after one round would look like:

A A A A 5 5 5 5 9 9 9 9 K 2 6 10 3 3 7 7 J J 4 4 4 4 8 8 8 8 Q Q Q Q 2 2 2 6 6 6 10 10 10 3 3 7 7 J J K K K

which is not a finished game, nor does it prove that the game is unwinable.


Geraint

Let's think the unthinkable, let's do the undoable, let's prepare to grapple with the ineffable itself, and see if we may not eff it after all

 

[Sheco]

Ah, I seemd to have misunderstood the sequence picking the cards back up.

 

[LFI]

Question: if I lay down the cards in the following order:

A 2 3 4
A 2 3 4
4 2 3 4

...then the 4 from the last pile gets moved to the first pile, revealing another 4. Is THAT "new" 4 fair game to be moved to the first pile as well? ...and then the 4 beneath that?

Dave


~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
...east is east and west is west and if you take cranberries and stew them like applesauce
they taste much more like prunes than rhubarb does

 

[LFI]

Here's an example of a deck that will never win. Can you see why? NOTE: "T" = "10":

888A2345679TJQKA2345679TJQKA2345679TJQKA2345679TJQK8

Well, I've made it a bit obvious, but in short, that last '8' will always be the last card of the deck. It will never move left because the other three 8's will always be played together at the beginning. In other words, all four 8's are rooted to their spots. The other cards will keep moving around, but you will never get the 8's together.

Now, here's the gas... The top card in this game NEVER MOVES! If another card matches it, it's placed on top of it, but it is always there and, once the cards are re-stacked, is always played first, so the only way to win is to be able to move all the cards OF THAT NUMBER to the top of the deck. If the deck was...

5A23TQK...

...then 5's must move to the top. And, if, by chance, you manage to do that and have something like...

5555AJT96...

...then A's must be next because that A that's the fifth card is now "stuck" there.

What you'll find (for reasons I haven't worked out yet) is that, typically on the first card (e.g., the 5's), whatever board you start with will migrate into a 3-cards at the "top" and one-at-the-bottom configuration. If it doesn't happen on the first card, it will frequently happen on the second. The most groups I've ever gotten to rise to the top (before getting "stuck") was five.

I believe it IS possible to win, just extremely unlikely. Since most games will go unfinished, you cannot determine a maximum number of moves. I made a mistake on the minimum number of moves before, however. I guess it depends on what you call a "move", but I think the minimum number is 78. If the deck is pre-arranged in the winning configuration to begin with, then you lay down the top four cards, it will take 6 moves to place all the cards onto the first stack (given the right-most card moves, first, to the closest matching stack to its left, etc.).

Does this make sense? Is it right!?!

Dave

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
...east is east and west is west and if you take cranberries and stew them like applesauce
they taste much more like prunes than rhubarb does