You have to understand, this lab is practice for writing programs entirely from scratch.
However, you can thank your fellow past classmates in Spring 2018
and Fall 2018, because they requested I make my template public, as
well as a give a rundown. So here you go.
Disclaimer: The lab writeup uses terms like "row" and "column".
In my guide, I flip it to be "x" and "y" since that makes more sense to me.
You are allowed to do it however you want.
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.
Code (C++)
//C++
#include <iostream>
#include <string>
#include <vector>
#include <deque>
#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.
Code (C++)
/*
* 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 = 0);
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.
deque< 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:
Text
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:
- 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.)
- 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").
-
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".
- 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).
-
deque< 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.
Then, at the end, if a solution is found, we will go from the front to the end and print out the coordinates.
-
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 deque 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.
