6
\$\begingroup\$

Let's introduce a simplified variant of the well known Spider Solitaire.

From Wikipedia:

The main purpose of the game is to remove all cards from the table, assembling them in the tableau before removing them. Initially, 54 cards are dealt to the tableau in ten piles, face down except for the top cards. The tableau piles build down by rank, and in-suit sequences can be moved together. The 50 remaining cards can be dealt to the tableau ten at a time when none of the piles are empty. A typical Spider layout requires the use of two decks. The Tableau consists of 10 stacks, with 6 cards in the first 4 stacks, with the 6th card face up, and 5 cards in the remaining 6 stacks, with the 5th card face up. Each time the stock is used it deals out one card to each stack.

An on-going game of Spider Solitaire

For the purpose of this challenge, you will receive a standard Spider Solitaire tableau with only a single suit and no extra stock, where you know the rank of all the cards, including the ones that normally could have been covered.

The task is to determine if a tableau is stale, i.e. the game can not be won/cleared from this position. This may happen because there are no moves, or there are moves, but they lead to repeating positions and do not ultimately end up with the whole rank sequence being taken off the board.

Examples

The following tableau is stale (0 - king, 1 - queen, 2 - jack, etc..., all down to the ace):

3 9 5 3 9 10
1 2 10 12 8 4
10 5 5 4 5
11 1 3 0 1 2
0 6 2 10 10 11 12
1 5 6 4 4 5
3 6 9 3 8
4 8
2 3 8 9 10
6 5 1 5 1 2

Not stale:

0 1 2  
3 4
11 
9
5
10
12
8
6
7

Not stale either:

0 1 2  
3 4
11 11
0 9 12
5 10
1 10 9
12 5
2 8 8
6 7
3 4 7 6

Scoring criterion

Code size in bytes in a particular language.

\$\endgroup\$
3
  • 4
    \$\begingroup\$ Please add more testcases, both stale and not stale \$\endgroup\$
    – tsh
    Nov 11 at 1:29
  • 2
    \$\begingroup\$ Please also clarify how to handle tableaux (like the one shown) that have a number of cards that isn’t a multiple of 13 - surely they’re all stale, but that situation wouldn’t arise in Spider where you have 104 cards total. \$\endgroup\$ Nov 11 at 8:43
  • \$\begingroup\$ @NickKennedy Fair point: In this scenario, the board is always stale. \$\endgroup\$ Nov 11 at 10:44

1 Answer 1

3
\$\begingroup\$

Jelly, 112 bytes

Iœr€1Ẉ‘rẈżị¥";@€"JȦƇẎW;ⱮṪẹ@¥ɗ€0ịⱮa‘$€Ɗ}Ẏɗ;pṆ€Tḣ1Ʋ}¥ɗị@œṖ@©ƭƒ@ḢWɗ1ị$}¦;€Fɼị@Wʋṛ¦ƭƒ€µœṣ13R¤F))Ṣ€
W©;Ç€ẎQ$ḟɗɼ$ÐLẸ€Ạ

Try it online!

A pair of links which are called monastically using a list of lists of integers as the starting tableau. Expects cards to be numbered from 1 (King) to 13 (Ace). Returns 1 if the tableau is stale and 0 if non-stale. Times out on TIO for more complex tableaux. This has taken a rather long time to get to this point but I will post an detailed explanation in due course. Removing the Ṣ€ at the end of the first link should also work and saves two bytes, but it times out on even simpler examples like the one in the TIO link.

Top-level explanation

  1. Start with a list of current tableaux (on first iteration will be a single one).
  2. For each tableau:
    • Work out which runs there are at the end of stacks.
    • Work out which of those runs can be moved to the end of another stack.
    • Also add the possibility of moving any run (including single cards) into the first empty stack.
    • Create new tableaux based on all of the moves identified above
  3. Join the new tableaux created in step 2 into a single list
  4. Remove any complete suits (from 1 to 13)
  5. Filter out any we’ve seen before
  6. Append to the list of all possibilities
  7. Stop when this list is unchanged (i.e. no new possible tableaux were generated); otherwise feed the new tableaux back into step 1.
  8. Determine whether all of the possible tableaux are non-empty
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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