Programming Assignment 3 - Accordion Solitaire

Advanced Programming II, Spring 2003

Due Date

This assignment is due by 2:00 p.m. on Wednesday, 5 March.

See the assignment turn-in page (last modified on 21 January 2003) for instructions on turning in your assignment.

Background

Accordion is a solitaire card game played with a standard 52-card deck. Play starts with a single card dealt face up. Play continues by repeatedly making any of the following moves:

  1. Move the top card in a pile to the top of the pile to its immediate left if the top cards on both piles match. Two cards match if both have the same suit (clubs, diamonds, hearts, spades) or the same rank (ace through king). If the two adjacent cards don't match, this move can't be made.

  2. Move a card pile on top of the card pile to its immediate left if the top cards on both piles match. If the two adjacent cards don't match, this move can't be made. The gap left by the moved pile is ignored.

  3. Move the top card in a card pile to the top of the card pile two to its immediate left if the top cards on both card piles match. If the two cards don't match, this move can't be made. This move is similar to move 1, except the card jumps the in between pile.

  4. Move a card pile on top of the card pile two to its immediate left if the top cards on both piles match. If the two cards don't match, this move can't be made. This move is similar to move 2, except the card pile jumps the in between card pile.

  5. Deal a new right-most card face up from the deck.

You are not required to make any of the moves 1 through 4 as soon as they are possible; when more than one move is possible, you may choose any one of them. Play ends when all the cards have been dealt. You win if there's a single pile of cards left.

The Problem

Write a program that checks a game of Accordion solitaire to see if 1) the game is legal and 2) the game is the best possible game that could result.

Input

A card is represented by a two-character sequence giving the card's suit (club, diamond, heart, or spade) and its rank (ace, 2 through 9, ten, jack queen king). For example 3H is the Three of Hearts. Because the characters for suit and rank are different, the card characters may be in either order; for example both sq and QS represent the Queen of Spades (letter case also doesn't matter). Because every card has two characters, one card need not be separated from the next by non-newline space characters.

The first non-blank line the program reads from std-in is the sequence of cards dealt, with the left-most card being the first card dealt and the right-most card being the last dealt. This line must contain 52 cards.

The remaining 1 <= n <= 52 non-blank lines the program reads from std-in represent the tableau at the end of the game, in left to right order (that is, the second line read from std-in is the leftmost pile and the nth line read from std-in is the right-most pile. Within each line representing a pile, the left-most card is the card on the top of the pile and the right-most card is the card at the bottom of the pile. Here is an example input: 

ad2d3d4d5d6d7d8d9dtdjdqdkd as2s3s4s5s6s7s8s9stsjsqsks ac2c3c4c5c6c7c8c9ctcjcqckc ah2h3h4h5h6h7h8h9hthjhqhkh

ad2d3d4d5d6d7d8d9dtdjdqdkd as2s3s4s5s6s7s8s9stsjsqsks 

ac2c3c4c5c 6c7c8c9ctcjcqckc 

ah2h3h4h5h6h7h8h9hthjhqhkh

Any input that doesn't follow this format is syntactically invalid and should terminate the program with an informative error message.

Output

If the given tableau cannot be derived from given deals, the program should output "impossible" to std-out.

A tableau is winning if it contains the smallest number of piles possible for the given deal; a tableau that contains more than the smallest number of piles possible is a losing tableau. If the given tableau can be derived from the given deals but is a losing tableau, the program should output to std-out a winning tableau. If the given tableau is both derivable and winning, the program should output nothing.

Testing

The gen-game program in /export/home/class/cs-509/pa3 generates some input you can use to test your program. The command format is

gen-game [ -b ]

By default, gen-game writes to std-out a correct but not necessarily optimal output. The -b command-line option causes gen-game to write incorrect output.

This page last modified on 4 March 2003.