pa01 : Card game using Binary Search Trees

num ready? description assigned due
pa01 true Card game using Binary Search Trees Thu 11/02 09:00AM Wed 11/15 11:59PM

Collaboration policy

Introduction

Goal of this assignment

Instructions

Starter code and required files

Refer to lab01 for instructions on how to set up a GitHub repository and pull the starter code for this lab. Obtain the starter code from this repo: https://github.com/ucsb-cs24-f23/STARTER-pa01

Check that you have the following files:

Create the following files:

The game

Alice and Bob are playing a game a bit like Go Fish, although neither of them is very good at it. The players are dealt two sets of cards which are provided in two separate files as inputs to your program. Although the cards in each player’s hand is unique, duplicates exist in the other player’s hand.

Once you have the sets of cards, the game begins. Alice and Bob take turns playing the game. Alice iterates forward through her hand in increasing order of the card values (see next section on how cards are ordered), checking whether Bob has that card. Once a matching card is found, your program should print the line “Alice picked matching card <card value as a number/character>". The card should then be removed from both players hands.

The process then repeats, except this time, Bob looks through his cards starting with the largest card and working towards the smallest card. This means that while the first card Alice finds should be the first shared card (in order), the first card Bob finds should be the last shared card (in order). The game ends once they do not have any cards in common and you should print out the final hands of both players. Note that players do not draw any new cards during this process.

The ordering of cards is described in the next section.

Card ordering

The ordering of cards is determined first by its suit and then by the value:

  1. The ordering least to greatest is: clubs, diamonds, spades, hearts. Thus a club of any value is less than a diamond of any value.

  2. The ordering within each suit is determined by the value from least to greatest as follows: ace, 2, 3, . . . 10, jack, queen, king.

Based on the above two rules, the ordering of the following cards

h 9, c k, s 3, c a, h j, d 3

from smallest to largest would be

c a, c k, d 3, s 3, h 9, h j

Your approach

At the start of the program, you will read in Alice and Bob’s starting hands from two files. The names of these files are provided as command line arguments with Alice’s file in argv[1] and Bob’s in argv[2]. The starter code opens the files for you as ifstream objects, which you can treat much like cin. You should read Alice and Bob’s cards into two binary search trees. You must implement the binary search trees yourself. Don’t worry about balancing the binary search trees (though you can try and optimize this if you like). Your binary search tree class should obey the card ordering rules given above. While implementing this, you may find it helpful to overload the operators ==, <, and > on your card class so that you can easily choose which branches to go down on your binary tree. Note that you need to correctly handle the case of cards with the value 10 (which has two characters) and separately compare the value and suit, so storing the cards as strings is probably not the best approach.

Once you have the sets of cards, the game begins as described before.

As before, you should write your own Makefile for this lab so that running make builds an executable called game.

Before you begin

An additional requirement is that you write a set of unit tests for your binary search tree. These should be in a file called tests.cpp, which you will submit, and you should write your Makefile so that running make test compiles and runs these tests. Note that there will be no Gradescope tests for these unit tests, so you can have the output in whatever format you find most helpful. You should test each of the functions on your binary search tree, which will include, at the very least, find(), delete(), insert(), successor(), and predecessor(). You should write these tests BEFORE implementing the full game to ensure that your binary search tree works correctly. Debugging one set of code is much easier than debugging two at the same time. This will also ensure that your are correctly separating your binary tree class from the rest of your program logic.

Example run of the program

Contents of alice_cards.txt:

h 3
s 10
c a
c 3
s 5
h 10
d a

Contents of bob_cards.txt:

c 2
d a
h 10
c 3
d j
s 10
h a

Correct output after running make && ./game alice_cards.txt bob_cards.txt:

Alice picked matching card c 3
Bob picked matching card h 10
Alice picked matching card d a
Bob picked matching card s 10

Alice's cards:
c a
s 5
h 3

Bob's cards:
c 2
d j
h a

Note: a=ace, k=king, q=queen, j=jack

Requirements

For this lab, you will have a lot of flexibility on your implementation (which just means we won’t be providing a code framework for you to fill in). However, there are a few requirements that your mentor will check for when they look at your code. Keep these in mind as you think about your solution:

Submission instructions

You and your partner only need to make a single submission. Add your partner to Gradescope before you submit (or before the deadline). Submit your code on Gradescope. You must organize your program in the files: main.cpp, cards.cpp, tests.cpp, cards.h, utility.cpp and utility.h

In addition you must create a Makefile that compiles your program to an executable called game.

Note

Gradescope will grade 55 points out of the allocated 75 points before the deadline. After the deadline has passed we will run hidden test cases worth 20 points and update the results. Make sure that you have thought about all possible edge cases and memory leaks / invalid memory access scenarios to avoid segmentation fault.