• The lab writeup is at either of these two links. The content is the same at both locations.
  • BVZ: http://web.eecs.utk.edu/~bvz/cs140/Labs/Lab9/
  • Plank: http://web.eecs.utk.edu/~jplank/plank/classes/cs140/Labs/Lab9
• I call this a Free-form Lab. You are allowed to implement it in whatever way you wish (in C++...), as long as you solve the problem with recursion. We will check it.
• There are 2 parts to this lab: Enum and ShapeShifter. This help page is strictly for ShapeShifter.
• You will submit 2 files: enum.cpp and ss_solver.cpp
• This is a hard lab. And you are only given a week to do it. Start early.

Last semester, I made a video that visually shows how ShapeShifter works, and how to approach the recursion. You are advised to watch it before attempting to solve this problem on your own.

Quick Link: http://tinyurl.com/cool-shape-thing (Everyone remembers silly link names like these...)

Direct YouTube Embed:

Video Anomalies

• The shape must fit in the grid.
  • The video shows possible combinations where the shape goes out of the grid slightly on purpose to show you how the for-loop in your recursive function should work.
  • For each shape, loop through every X. And for every X, loop through each Y. Try to place the shape at that position. Obviously if the shape goes a bit out of the grid, it won't work.
• The video doesn't have audio. It was made for me to show in lab and talk about simultaneously. It also goes a bit fast. Hence why I pause it (and sometimes rewind) when explaining or answering questions in lab.

You have to understand, this lab is practice for writing programs entirely from scratch. But I did show a template of my implementation in lab. And, by request, I'll post it.

For those with UTK hydra access:

You can head over to ~ssmit285/public/code/ss_solver_template.cpp and copy it (Or download from my server here).

Normally I would supply a header file with the class prototype in it, and then a cpp that where you actually implement the code. But since I want your entire ShapeShifter to be in a single file for submission (ss_solver.cpp), we will declare the prototype at the top, and then the functions after... in the same file.

Includes

This is all you need.

//C++
#include <iostream>
#include <string>
#include <vector>
#include <list>
#include <map>
#include <algorithm>
#include <sstream>

//C
#include <stdio.h>
#include <stdlib.h>

using namespace std;

Header Portion

Notice that typedef right there. We are never going into the negatives in this lab, so all integer operations should be unsigned. Because unsigned int takes up a lot of space when typing this out, I made uint as a shorthand for it. You may replace it with int if you wish.

/*
 * Class for ShapeShifter. Has a grid of the initial setup that you will try to
 * put shapes into. Also has a struct called "shape" that stores a shape's
 * grid, width, and height.
 */
 
typedef unsigned int uint;

class ShapeShifter {
	struct shape {
		//Constructors
		shape();
		shape(const string&);
		
		//Variables
		vector< vector<bool> > grid;
		uint width, height;
		string text;
	};
		
	public:
		//Constructors
		ShapeShifter();
		ShapeShifter(const vector<string>&);
		
		//Dealing with shapes
		void add_shape(const string&);
		bool apply_shape(uint, uint, uint);
		
		//Solving functions
		bool all_one();
		bool find_solution(uint);
		void print_solution();
		
	private:
		//All shapes to be inserted into the grid
		vector<shape> shapes;
		
		//Game Grid
		vector< vector<bool> > grid;
		
		//(x, y) points for each shape when the solution is found.
		list< pair<uint, uint> > solution;
		
		//Game grid size
		uint width, height;
};

You may take the struct out of the class if you want. I put it in because I can't see myself using shape outside of ShapeShifter. It's good practice to think like this to prevent name collisions in C++.

Function Definitions

The file linked above has each function neatly typed out with nothing in it. Rest assured, it compiles on Hydra by default. But I think we need to go over what each of these functions do.

Shape struct

Before we even talk about the ShapeShifter class, let's talk about that struct inside it... Shape.

The shape struct has a 2D vector of bools. We will use this to store our shape. The shape's grid doesn't have to be the same size as the game grid. Each shape can vary in size.

Constructing the grid may not be obvious at first, because you are given data like this and it can be hard to understand without a reference:

111
110 011
1 1 1

Here's my take on it:

• Each line is its own shape (which means that example has 3 shapes).
• Each row is separated by spaces (first shape has 1 row only, second shape has 2 rows, etc).

More importantly, here's a visual way to think of it (with rows coloured differently):



Shape Variables

• vector< vector<bool> > grid - This is the grid that holds the shape. You may use it as either grid[row][col] or grid[x][y] (which is flipped).
• uint width, height - Width and height of the shape
• string text - Holds the original text used to make the image. This is so we can print out the shape when a solution is found.

Shape Functions

• shape() - This is a default constructor. Do nothing with it.
• shape(const string& line) - This takes a string and uses it to fill in the grid 2D vector of bools. You can try with this approach:
  1. The string passed in will be the entire shape (Each line read in via stdin is a shape. Each row is separated by a space.)
  2. Split the string by the spaces and put each row into a temporary vector (e.g. "110 011" is 2 rows. Split into "110" and "011").
  3. Loop through that temporary vector of strings and insert into grid either "true" or "false" depending on if the string character has "1" or "0".
  4. Set width and height accordingly.

That's really all there is to the shape struct.

ShapeShifter class

Now we can talk about the elephant in the room. This class will store all of the other variables, including your recursion function, as well as shapes. Let's talk about the variables first before getting to the functions.

Variables

• vector<shape> shapes - This will hold all of your shapes in one spot.
• vector< vector<bool> > grid - This will hold the initial grid that is given in argv. You will append shapes to this grid in your recursion function. Just like the shapes grid, you may use it as either grid[row][col] or grid[x][y] (which is flipped).
• list< pair<uint, uint> > solution - This one is a fun one. It stores the (x, y) coordinates of the solution (if found), so you can print out the coordinates when the solution is found. The reason for the pair is so we can store the x and y simultaneously. The reason for the list is because we will be pushing and popping from the back of the list as we search for the solution. Then, at the end, if a solution is found, we will go from the front to the end and print out the coordinates.
  • If you were in my lab section, I showed a template with deque. That isn't necessary unless you want to use solution[i] instead of iterators.
  • The second example in the lab writeup (and in my video) would have a solution list that looks like this:
    Pseudocode

    solution[0] = pair of (1, 1)
    solution[1] = pair of (1, 0)
    solution[2] = pair of (0, 1)

• uint width, height - Stores the width and height of the game grid.

Functions

• ShapeShifter() - Default constructor. Just do nothing.
• ShapeShifter(const vector<string>& rows) - Takes a vector of strings (make this vector in your main function) that have your rows in them as 0's and 1's. Your constructor will take this vector and parse it just like you did in your shape constructor.
• void add_shape(const string& line); - Make a shape using the given string here as the constructor, and do shapes.push_back(); on the new shape.
• bool apply_shape(uint shape_id, uint x, uint y); - Apply shape[shape_id] to the grid at position x, y (Given in the arguments). If you are unable to place the shape (i.e. the shape goes out of the grid) return false. Otherwise, return true.
  
  Here is an example of using it on shape index 0 in 2 positions. First is at the top left. Second is shifted down by 1.
  
  
  
• bool all_one() - Returns true if all of the indices in grid are 1. If any are 0, return false
• bool find_solution(uint shape_id) - This is the recursive function. See the next section for it. This one is the hard one.
• void print_solution() - Loop through solution list and print out all coordinates, along with each shapes[id].text.c_str().
  • In my solution, I store x and then y. To match the gradescript, you have to print out row and then column. Just switch them in the print statement.

Now for the real challenge. This function actually isn't that bad. But since you're likely new to recursion, you're going to likely spend most of your time on this.

For reference, if you're using my implementation from above, it's the bool find_solution(uint) function.

"How do I even start the recursion?"

So if you look at the video, posted above, the way to solve this problem is by pure brute-force. We will check every possible combination with every possible shape given. In your main() function, you will need to set up the grid and all shapes first. Then, you can call find_solution on the very first shape like so:

int main(int argc, char** argv) {
	bool solution_found;
	vector<string> rows;
	string line;
	
	/* Generate the rows vector with argv[1..N] */
	
	/* Set up the game. Pass "rows" in via the constructor. */
	ShapeShifter game(rows);
	
	/* Set up all shapes via stdin and game.add_shape() by using getline() */
	
	/* Play the game */
	solution_found = game.find_solution(0);
	
	/* If solution_found is "true", print out the shapes and the coordinates of the solution */
}

The function body

bool ShapeShifter::find_solution(uint shape_id) {
	/* code here */
}

Think for a moment about this...

• You are placing the shape in every possible spot that it can be put into.
• Call apply_shape(shape_id, x, y); to try to put the shape in place. Remember that I made the function return a boolean.
• Push a pair of x and y to the solutions list.
• After the shape is placed and it isn't the last shape, you go to the next shape (via find_solution(shape_id + 1);) and do the same.
• If you're at the last shape, apply:
  • Call all_one(); to check if the grid is all set to "1" (aka you solved it). If this returns true, return true.
• If you have exhausted all combinations then you need to go back to the previous shape, move it to the next spot, and try again.
  • Remember that you have to undo the changes you made to your ShapeShifter class...

I won't spoil the entire part of the recursion, but this is the kind of mentality you should have when trying to solve this function. If you write it correctly, the function should be around 15-30 lines. Mine was 15.

Just some tips.

• My approach is very object-oriented, as C++ should be. Make sure you understand what a "Shape" is and how it's applied to "ShapeShifter" before you go and copy-and-paste my template.
• When implementing your Shape and ShapeShifter structures, print out the grid after you've created and processed the 0's and 1's into them. You can't get the correct answer without correct data in read in!
• Put print statements in your recursion statement. This will help you understand what is going on when you're struggling. Something like this is perfectly valid for debugging:
  Output

  Trying to apply shape 1 at (0, 0)... Success!

  And when the recursion fails:
  Output

  Unable to insert shape. Undoing changes...

• Of course, don't include these print statements in your final submission...

You will submit a tar file that has enum.cpp and ss_solver.cpp in it. You may do that with this command:

tar -cf lab9.tar enum.cpp ss_solver.cpp

You may check the tar file to see if it has the files in it with the following:

tar -tf lab9.tar

It should print the file names out to stdout.