CS302 -- Project 3 -- Superball!

• CS302 -- Data Structures and Algorithms II
• Spring, 2019
• courtesy of Dr. James S. Plank
• The original file: http://www.cs.utk.edu/~plank/plank/classes/cs302/Labs/Lab5/

What you hand in

Brent was pretty insistent we keep the CS302 Superball! challenge... and Dr. Plank wants me to use all of his labs/notes (if I want), so here it is.

As in the Fall (and previous iterations), this project must be done alone.

You need to submit the source code for two programs: sb-analyze.cpp and sb-play.cpp as a tar/zip on Canvas (as you have for Challenges).

Also

Every year, someone asks Dr. Plank for the source to sb-player. He does not give it out since its "too easy" in his words to solve the lab with it. There are, however, various implementations (see below) and Brent can ask Dr. Plank to try and make an sb-player binary for your machine. Let us know.

There is an sb-player binary for macs in sb-player-mac.

Plus, in 2015, Alex Teepe wrote a multiplatform Superball player to share. Neither Dr. Plank nor I have not tried it, but please do. Thanks, Alex!

https://drive.google.com/file/d/0B4rzPrfwFCsKbUpwd21pMlgtc1E/view.

There is a README here.

Disjoint Sets

Use the disjoint sets code from the lecture note directory. That means you should include disjoint.h, and then compile with disjoint-rank.cpp. When you instantiate your disjoint set instance, use "new DisjointSetByRankWPC". Since you don't use the other implementations, you don't need to compile with them.

If you don't understand how to compile your program correctly, please ask the TA's or ask on Piazza. DO NOT COPY THE DISJOINT SET CODE AND INCLUDE IT WITH YOUR PROGRAM.

Superball

• P - Purple: worth 2 points.
• B - Blue: worth 3 points.
• Y - Yellow: worth 4 points.
• R - Red: worth 5 points.
• G - Green: worth 6 points.

• You may swap two cells. After the swap, five new random cells will be filled with a random colors.
• You may "score" a cell. To score a cell, the cell must be one of the "goal" cells, and there are sixteen of these, in rows 2-5, columns 0, 1, 8 and 9. (Everything is zero indexed). Moreover, there must be at least five touching cells of the same color, one of which must be the goal cell that you want to score. When you score, you get the sum of the cells connected to the cell that you are scoring, and then all of those cells leave the board, and three new random ones are added.

Dr. Plank has a tcl/tk/shell-scripted Superball player at /home/plank/Superball. Simply copy that directory to your home directory:

UNIX> cp -r /home/plank/Superball $HOME

Then you can play it with ~/Superball/Superball. The high score probably won't work -- you'll have to change the open command in the file hscore to the name of your web browser.

Let's look at some screen shots. Suppose we fire up Superball:

The "goal" cells are marked with asterisks, and there are five non-empty cells. Our only legal action is to swap two cells -- Dr. Plank swaps cells [3,6] and [5,8] below. This will make those two blue cells contiguous. In the game, we can do that by clicking on the two cells that we want to swap. Afterwards, five new cells are put on the screen. Here's the screen shot:

Dr. Plank does a bunch more swaps and ends up with the following board:

We can score the green cells by clicking on cell [2,1], [3,0], [3,1] or [4,0] and then clicking "Collect". This will score that group of eight green squares, which gets us 48 points (8*6), and three new cells will be added:

There are no cells to score here (the blues ones in the lower right-hand part of the board only compose a group of four). So Dr. Plank now reverts to swapping. Suppose we keep doing this until we reach:

We're in trouble. Dr. Plank has now got these beautiful groups of red, green and purple cells, but he can't score any of them because they are not connected to a goal. Dang. We can only score those two groups of blue cells. When Dr. Plank does that, he is only left with four open squares, and we can't score anything:

Perhaps Dr. Plank should have been a little more thoughtful while playing the game. Regardless, he is stuck. We simply swap two random squares and end the game:

Oh well -- should have done that swap a little sooner....

• rows - the number of rows on the game board. Although the tcl/tk version has that set to eight, our programs will handle any number.
• cols - the number of columns on the game board.
• min-score-size - the number of contiguous cells that have to be together in order to score them. This is 5 in the tcl/tk version
• colors - this must be a string of distinct lower-case letters. They represent that the colors that a cell can have. The point value of the first of these is 2, and each succeeding character is worth one more point. To have the same values as the tcl/tk game, this parameter should be "pbyrg".

Dr. Plank has written an interactive game player. Call it as shown below:

UNIX> cd /home/plank/cs302/Labs/Lab5/
UNIX> sb-player
usage: sb-player rows cols min-score-size colors player interactive(y|n) output(y|n) seed
UNIX> sb-player 8 10 5 pbyrg - y y -
Empty Cells: 75     Score: 0

..........
..........
**b....b**
**....b.**
**.g....**
**......**
..........
..g.......

Your Move: 

You can type two commands:

SWAP r1 c1 r2 c2
SCORE r c

In the board above, you can't score anything, so you'll have to swap. We'll swap the blue cell in [2,2] with the green one in [7,2]:

Your Move: SWAP 2 2 7 2

Empty Cells: 70     Score: 0

.r........
..........
**g....b**
**....b.**
**.g....*Y
**......*P
.....rr...
..b.......

Your Move: 

It's incredibly tedious -- play along with us:

Empty Cells: 70     Score: 0

.r........
..........
**g....b**
**....b.**
**.g....*Y
**......*P
.....rr...
..b.......

Your Move: SWAP 0 1 7 2  

Empty Cells: 65     Score: 0

.b........
..........
**g....bB*
**....b.**
P*.g....RY
**......*P
.....rr...
.gry......

Your Move: SWAP 7 3 4 8

Empty Cells: 60     Score: 0

.b.......p
....g.....
**g.p..bB*
**r...b.*R
P*.g....YY
**......*P
.....rr...
.grr......

Your Move: SWAP 3 2 7 1

Empty Cells: 55     Score: 0

.b..r...pp
....g...b.
**g.p..bB*
**g...b.*R
P*.g....YY
**.g....*P
.....rr...
rrrr......

Your Move: SWAP 3 9 0 1

Empty Cells: 50     Score: 0

.r..rgy.pp
....g...b.
**g.p..bB*
**g...b.*B
P*.g....YY
**.g....*P
p...rrr...
rrrr.p....

Your Move: SWAP 6 0 0 1

Empty Cells: 45     Score: 0

.p..rgy.pp
.g..g...b.
**g.p..bB*
**g...b.*B
P*.g..y.YY
**.g..yp*P
r...rrr...
rrrr.py...

Your Move: SWAP 5 9 7 6

Empty Cells: 40     Score: 0

.p..rgy.pp
.g..g...b.
**g.p.pbB*
R*g...by*B
P*.g..y.YY
P*.g..yp*Y
r...rrrb..
rrrr.pp...

Your Move: SWAP 5 0 0 4

Empty Cells: 35     Score: 0

.p..pgy.pp
.g..g.r.b.
G*g.p.pbB*
R*g...by*B
P*.g..y.YY
R*.g..yp*Y
r..grrrb..
rrrrbppy..

Your Move: SWAP 7 4 1 6

Empty Cells: 30     Score: 0

.p..pgy.pp
.g.pg.b.b.
G*g.p.pbB*
R*g.r.by*B
P*pg..y.YY
R*.g.bypBY
r..grrrb..
rrrrrppy..

Your Move: SCORE 5 0

Empty Cells: 37     Score: 50

.p..pgy.pp
.g.pg.b.by
G*g.p.pbB*
R*g.r.byGB
P*pg..y.YY
**.g.bypBY
...g...b..
.p...ppy..

Your Move: 

You'll note, we could have scored cell [5,0] when there were 35 empty cells, but Dr. Plank really wanted to make that patch of red cells bigger.

Program #1: Sb-read

May be represented by the following text (in input-1.txt):

...yyryy.p
y.rg.yppyp
**gg.yrpPP
GGgbgybp**
R*bg.yrp*P
G*gygyypY*
yyybpby.pb
.pgg.yp.bb

When we run sb-read on it, we get the following:

UNIX> sb-read 8 10 5 pbyrg < input-1.txt
Empty cells:                    20
Non-Empty cells:                60
Number of pieces in goal cells:  8
Sum of their values:            33
UNIX> 

You should take a look at sb-read.cpp. In particular, look at the Superball class:

class Superball {
  public:
    Superball(int argc, char **argv);
    int r;
    int c;
    int mss;
    int empty;
    vector <int> board;
    vector <int> goals;
    vector <int> colors;
};

Mss is min-score-size. Empty is the number of empty cells in the board. Board is a vector of r * c integers. The element in [i,j] is in entry board[i*c+j], and is either '.', '*' or a lower case letter. goals is another array of r * c integers. It is equal to 0 if the cell is not a goal cell, and 1 if it is a goal cell. Colors is an array of 256 elements, which should be indexed by a letter. Its value is the value of the letter (e.g. in the above example, colors['p'] = 2).

sb-read does all manner of error checking for you. It is a nice program from which to build your other programs.

Program #2: Sb-analyze

You are to write this one.

With sb-analyze, you are to start with sb-read.cpp as a base, and augment it so that it prints out all possible scoring sets. For example, in the above game board (represented by input-1.txt), there are two scoring sets -- the set of 10 purple cells in the upper right-hand corner, and the set of 6 green cells on the left side of the screen. Here is the output to sb_analyze:

UNIX> sb-analyze
usage: sb-analyze rows cols min-score-size colors
UNIX> sb-analyze 8 10 5 pbyrg < input-1.txt
Scoring sets:
  Size: 10  Char: p  Scoring Cell: 2,8
  Size:  6  Char: g  Scoring Cell: 3,0
UNIX> 

UNIX> sb-analyze 8 10 5 pbyrg < input-1.txt
Scoring sets:
  Size:  6  Char: g  Scoring Cell: 3,1
  Size: 10  Char: p  Scoring Cell: 2,9
UNIX> 

Think about how you would use the disjoint sets data structure to implement this -- it is a straightforward connected components application. We would recommend augmenting your Superball class with a DisjointSet, and then having a method called analyze_superball() that performs the analysis.

Here's another example:

This is in the file input-2.txt:

yyggyryybp
ggrgpyppyp
RBgggyrpPP
GGgggybpPP
RGygryrpBP
YGyygyypYB
yyybpbyppb
ppggyypbbb

UNIX> sb-analyze 8 10 5 pbyrg < input-2.txt
Scoring sets:
  Size: 14  Char: g  Scoring Cell: 5,1
  Size: 15  Char: p  Scoring Cell: 4,9
  Size:  7  Char: y  Scoring Cell: 5,0
  Size:  5  Char: b  Scoring Cell: 5,9
UNIX> 

Program #3: Sb-play

If you have fewer than five pieces and cannot score any, you will lose the game -- you should do that by swapping two legal pieces so that the game can end.

The sb-player program takes as its 5th argument the name of a program that it will use for input. Dr. Plank also also provided three programs - sb-play, sb-play2 and sb-play3 in that directory. sb-play simply swaps two random cells until there are fewer than five empty, then it scores a set if it can. The other two are smarter, but are by no means the best one can do.

Here's sb-player running on sb-play2 (note, sb-player creates a temporary file, so you must run it from your own directory):

UNIX> /home/plank/cs302/Labs/Lab5/sb-player 8 10 5 pbyrg /home/plank/cs302/Labs/Lab5/sb-play2 y y -
Empty Cells: 75     Score: 0

g.........
..........
**......**
*Pr.....**
**......**
**..p...**
........b.
..........

Type Return for the next play

Move is: SWAP 5 4 3 2

Empty Cells: 70     Score: 0

g........g
.......y..
**......**
*Pp.....**
**......G*
**..r...**
..g.....b.
........g.

Type Return for the next play

Move is: SWAP 6 8 0 0

Empty Cells: 65     Score: 0

b........g
.......y..
**..b...**
*Pp.g...**
**.....gG*
**..r...**
..g.....g.
.p...p..g.

Type Return for the next play

UNIX> /home/plank/cs302/Labs/Lab5/sb-player 8 10 5 pbyrg /home/plank/cs302/Labs/Lab5/sb-play2 n y -
Empty Cells: 75     Score: 0

..........
..........
**......**
**y..y..**
**......**
*P......**
..........
......p.g.

Move is: SWAP 3 5 3 2

Empty Cells:  1     Score: 505

yyrrgggpyy
grrbppg.yg
GYbgygggPB
GBggpgbpPB
PPgggggrYB
YBbybgpbYR
pprrrggggr
byyrppppgg

Move is: SWAP 0 1 7 5

Game over.  Final score = 505
UNIX> 

If you run with the 7th argument as n, it will only print out the end result, and the last argument can specify a seed (it uses the current time if that argument is "-"), so that you can compare multiple players on the same game:

UNIX> /home/plank/cs302/Labs/Lab5/sb-player 8 10 5 pbyrg /home/plank/cs302/Labs/Lab5/sb-play n n 1
Game over.  Final score = 0
UNIX> /home/plank/cs302/Labs/Lab5/sb-player 8 10 5 pbyrg /home/plank/cs302/Labs/Lab5/sb-play2 n n 1
Game over.  Final score = 855
UNIX> /home/plank/cs302/Labs/Lab5/sb-player 8 10 5 pbyrg /home/plank/cs302/Labs/Lab5/sb-play3 n n 1
Game over.  Final score = 2572
UNIX> 

Shell Script to Run Multiple Times

UNIX> sh run_multiple.sh 
usage: sh run_multiple.sh r c mss colors player nruns starting_seed
UNIX> sh run_multiple.sh 8 10 5 pbyrg sb-play 10 1
Run   1 - Score:     38  - Average     38.000
Run   2 - Score:      0  - Average     19.000
Run   3 - Score:      0  - Average     12.667
Run   4 - Score:     57  - Average     23.750
Run   5 - Score:      0  - Average     19.000
Run   6 - Score:      0  - Average     15.833
Run   7 - Score:     89  - Average     26.286
Run   8 - Score:     15  - Average     24.875
Run   9 - Score:      0  - Average     22.111
Run  10 - Score:     20  - Average     21.900
UNIX> sh run_multiple.sh 8 10 5 pbyrg sb-play2 10 1
Run   1 - Score:    855  - Average    855.000
Run   2 - Score:    979  - Average    917.000
Run   3 - Score:    650  - Average    828.000
Run   4 - Score:    833  - Average    829.250
Run   5 - Score:    832  - Average    829.800
Run   6 - Score:   3326  - Average   1245.833
Run   7 - Score:   1507  - Average   1283.143
Run   8 - Score:   3643  - Average   1578.125
Run   9 - Score:    610  - Average   1470.556
Run  10 - Score:    862  - Average   1409.700
UNIX> sh run_multiple.sh 8 10 5 pbyrg sb-play3 10 1
Run   1 - Score:   2572  - Average   2572.000
Run   2 - Score:   2708  - Average   2640.000
Run   3 - Score:    745  - Average   2008.333
Run   4 - Score:    424  - Average   1612.250
Run   5 - Score:   1888  - Average   1667.400
Run   6 - Score:   7140  - Average   2579.500
Run   7 - Score:   3475  - Average   2707.429
Run   8 - Score:   1701  - Average   2581.625
Run   9 - Score:   2699  - Average   2594.667
Run  10 - Score:   2291  - Average   2564.300
UNIX> 

Obviously, to get a meaningful average, many more runs (than 10) will be required.

Oh, and make your programs run in reasonable time. Roughly 5 seconds for every thousand points, and if you are burning all that time, your program better be killing Dr. Plank's....

The Superball Challenge

We will run a Superball tournament with all of your players with extra lab points going to the winners:

• 1st place: 30 extra lab points.
• 2nd place: 15 extra lab points.
• 3rd place: 5 extra lab points.

• CS140 in 2007.
• CS302 in 2010.
• CS302 in 2011.
• CS302 in 2012.
• CS302 in 2013.
• CS302 in 2014.
• CS302 in 2015.
• CS302 in 2018.

Hints