Lab46 Wiki

To gain an understanding of pointer-based stack data structures and their use in algorithms.

The intent of this project is to explore the use of pointer-based stack data structures through the implementation of a FreeCell-based card game.

If you are not familiar, please reference the Wikipedia article on FreeCell.

Your task (either individually or in groups), is to implement a specific card game in a particular language. I am going to require diversity amongst card games implemented and programming languages used. So whatever path you decide to embark upon, I must be made aware and approve.

You must:

• Implement an accurate one player game of the above card games on Lab46
• You may work individually or in groups of at most CLASS_SIZE % 4
• EACH group must do a unique implementation in a unique programming language
• ALL solutions must utilize “pointer”-based dynamic stacks (lists of nodes, NOT arrays)
• EACH group must have a wiki page providing general user documentation, explanation of rules, and some exploration of particular implementation challenges, insights, etc. Focus should be paid to the concept of stacks
• ALL group members must contribute to the wiki page
• ALL group members must participate in the programming and be familiar with the code base
• Source code must be well documented
• Groups should make use of a version control system, such as subversion, to develop and ultimately make available the final implementation version control system optional for this project
• Implementations should consist of a minimum of 3 sources files, and utilize a Makefile for automated building
• In the base of your implementation directory, have an all-caps file called “README” which has the essential information for building, running, and using your implementation

• FreeCell
• Eight Off
• Forty Thieves
• Baker's Game

The reason I have chosen these games is that they involve a level of memory allocation, which has similarity to how the actual computer's hardware works. There may be additional games that fall under this category. If you find one and would like to implement it, let me know and I can ascertain if it is appropriate.

• C
• Object-Oriented C++ (must use objects and classes)
• Java
• Python

Technically I'd allow any language that allows for linked data structures; but the above four are the most common students at CCC are likely to have encountered.

A caveat, I am only officially supporting C and C++, as those are the languages I will be using in class (predominantly C).

Borrowed from Wikipedia:

• One standard 52-card deck is used.
• There are four open cells and four open foundations. Some alternate rules use between one to ten cells.
• Cards are dealt into eight cascades, four of which comprise seven cards and four of which comprise six. Some alternate rules will use between four to ten cascades.

• The top card of each cascade begins a tableau.
• Tableaux must be built down by alternating colors.
• Foundations are built up by suit.

• Any cell card or top card of any cascade may be moved to build on a tableau, or moved to an empty cell, an empty cascade, or its foundation.
• Complete or partial tableaus may be moved to build on existing tableaus, or moved to empty cascades, by recursively placing and removing cards through intermediate locations. While computer implementations often show this motion, players using physical decks typically move the tableau at once.

• The game is won after all cards are moved to their foundation piles.

A card game is an excellent example of stack usage. When moving cards, I want to see push/pop operations taking place with respect to the various “storage locations” the cards can reside (foundations, cells, etc.)

To better understand the impact of stacks on these card games, be sure to play some games. Once you are familiar with the rules, specifically take notice of the functionality the stacks enable for the playing of the game.

To facilitate the readability of your code, when preparing your code for submission, I'd like for you to make sure certain qualifications are met:

• you use consistent indentation
  • multiple levels of code see proper indentation
  • there are no “mostly there” inconsistent indentations
  • no stray statements with 0 indentation
  • all selection, iteration, and function statements receive uniform formatting

If you'd like, I have configured a facility on Lab46 to enable you to conveniently beautify your code to the ANSI/Allman style of coding. This is my preferred coding style, and would help me to better read your code.

So, if you aren't already consistent at code formatting (some have well-established coding habits and their code, although styled slightly different than mine, is still far more readable because it is consistent), please go through the following exercise for all your source files.

In this example, I will assume your files are called: main.c, list.c, and freecell.h

lab46:~$ cd src
lab46:~/src$ indent main.c
lab46:~/src$ indent list.c
lab46:~/src$ indent freecell.h
lab46:~/src$ 

You will find that a backup of your original formatted source code is saved in files called main.c~, list.c~, and freecell.h~. But the plain .c files are now nicely formatted.

If you find yourself tracking down elusive bugs and have experienced an unbalanced curly brace… you may want to consider passing your code through indent so as to save yourself some work and time. You'd be amazed what a little code beautification will do for you.

• Stack Wikipedia Article
• FreeCell Wikipedia Article
• Web/Flash version of Forty Thieves
• Pointer Fun with Binky Educational Video
• Pointer Basics
• Linked List Basics
• Stanford Summary on the C Programming Language
• Stanford Introduction of UNIX Programming Tools