From 8c4f0c7d6020ca581b245012e687973a14a1947d Mon Sep 17 00:00:00 2001 From: Kamil Kaminski Date: Mon, 14 Mar 2011 00:59:13 -0500 Subject: Initial import --- Makefile | 35 ++++ grid.cpp | 58 ++++++ grid.h | 44 +++++ main.cpp | 614 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ main.h | 34 ++++ piece.cpp | 68 +++++++ piece.h | 48 +++++ 7 files changed, 901 insertions(+) create mode 100644 Makefile create mode 100644 grid.cpp create mode 100644 grid.h create mode 100644 main.cpp create mode 100644 main.h create mode 100644 piece.cpp create mode 100644 piece.h diff --git a/Makefile b/Makefile new file mode 100644 index 0000000..b9cbc01 --- /dev/null +++ b/Makefile @@ -0,0 +1,35 @@ +# Kamil Kaminski +# NetID: kkamin8 +# +# CS340 +# Project 3, Sliding Block Puzzles +# +# Makefile + +PROG = klotski +OBJS = main.o piece.o grid.o +CC = g++ +DBGFLAGS = -g -O0 +ifdef DEBUG + CFLAGS = $(DBGFLAGS) -D DEBUG -std=c++98 -pedantic-errors -Wall +else + CFLAGS = -O2 -std=c++98 -pedantic-errors -Wall +endif +LDFLAGS = -lm + +$(PROG): $(OBJS) + $(CC) $(LDFLAGS) $(OBJS) -o $(PROG) + +main.o: %.o: %.cpp %.h piece.h grid.h + $(CC) -c $(CFLAGS) $< + +piece.o: %.o: %.cpp %.h + $(CC) -c $(CFLAGS) $< + +grid.o: %.o: %.cpp %.h + $(CC) -c $(CFLAGS) $< + +.PHONY: clean + +clean: + rm -f ./$(OBJS) ./$(PROG) ./*.exe diff --git a/grid.cpp b/grid.cpp new file mode 100644 index 0000000..b069782 --- /dev/null +++ b/grid.cpp @@ -0,0 +1,58 @@ +/* + * grid.cpp + * + * + */ + +#include "grid.h" + +Grid::Grid(void) : rows(0), cols(0), numOfMoves(0), lastMoved(0), lastMoveDir(0), board(NULL) +{ +} + +#if 0 +Grid::Grid(const Grid &grid) : rows(grid.rows), cols(grid.cols), numOfMoves(grid.numOfMoves), + lastMoved(grid.lastMoved), lastMoveDir(grid.lastMoveDir), board(new string(*grid.board)) +{ + +} +#endif + +int *Grid::getRows(void) +{ + return &rows; +} + +int *Grid::getCols(void) +{ + return &cols; +} + +int *Grid::getNumOfMoves(void) +{ + return &numOfMoves; +} + +vector *Grid::getPieces(void) +{ + return &pieces; +} + +void Grid::setRows(int n) +{ + rows = n; +} + +void Grid::setCols(int n) +{ + cols = n; +} + +void Grid::addMove(string move) +{ + moves.push_back(move); +} + +void Grid::markPiecesPos(void) +{ +} diff --git a/grid.h b/grid.h new file mode 100644 index 0000000..23294f7 --- /dev/null +++ b/grid.h @@ -0,0 +1,44 @@ +#ifndef _GRID_H_ +#define _GRID_H_ + +#include "piece.h" +#include +#include +#include +#include + +using std::string; +using std::cout; +using std::endl; +using std::vector; + +class Grid +{ + private: + int rows; + int cols; + int numOfMoves; + int lastMoved; + int lastMoveDir; + vector pieces; + vector moves; + string *board; + + public: + Grid(void); + /* we do not need a copy constructor since the deault shallow copy will be fine */ + //Grid(const Grid &); + + int *getRows(void); + int *getCols(void); + int *getNumOfMoves(void); + vector *getPieces(void); + + void setRows(int); + void setCols(int); + void addMove(string); + + void markPiecesPos(void); +}; + +#endif diff --git a/main.cpp b/main.cpp new file mode 100644 index 0000000..90e56b8 --- /dev/null +++ b/main.cpp @@ -0,0 +1,614 @@ +/* Kamil Kaminski + * NetID: kkamin8 + * + * CS340 + * Project 3, Sliding Block Puzzles + * + * + */ + +#include "main.h" + +/* check if Z piece spans last column */ +bool checkSoln(Grid grid) +{ + Piece tmp(""); + for (vector::size_type ix = 0; ix != grid.getPieces()->size(); ++ix) + { + tmp = (*(grid.getPieces()))[ix]; + if (tmp.getName() == "Z") + break; + } + + if ( (tmp.getCol() + tmp.getW()) == (*(grid.getCols())+1) ) + return true; + + return false; +} + +/* validate piece */ +int checkPiece(int rows, int cols, Piece piece) +{ + /* wrong direction */ + if ( piece.getDir() != 'v' && piece.getDir() != 'h' && piece.getDir() != 'b') + { + return 2; + } + + /* out of bonds */ + if ( (piece.getRow() + piece.getH()) > rows+1 || (piece.getCol() + piece.getW()) > cols+1) + return 3; + + /* wrong dimensions */ + if ( (piece.getH() != 1) && (piece.getW() != 1) ) + return 1; + + return 0; +} + +/* take in a grid and return a string representation of it */ +string *fillBoard(Grid grid) +{ + int grid_h = *grid.getRows(); + int grid_w = *grid.getCols(); + string *board = new string[grid_h * grid_w + 1]; + int k; + for (k = 0; k < grid_h * grid_w; k++) + board[k] = "."; + + int i = 0; + Piece tmp(""); + string name; + int row; + int col; + int w; + int h; + char dir; + int offset; + + for (vector::size_type ix = 0; ix != grid.getPieces()->size(); ++ix, i++) + { + tmp = (*(grid.getPieces()))[ix]; + name = tmp.getName(); + row = tmp.getRow(); + col = tmp.getCol(); + w = tmp.getW(); + h = tmp.getH(); + dir = tmp.getDir(); + + int j; + offset = (grid_w * (row-1)) + col; + if (w == 1) + { + for (j = 0; j < h; j++) + board[offset + (j * grid_w) - 1] = name; + } + else if (h == 1) + { + for (j = 0; j < w; j++) + board[offset - 1 + j] = name; + } + else + cout << "oops in fillBoard(), height or width of a piece is not 1!\n"; + } + + board[grid_h * grid_w] = ""; + + return board; +} + +/* take 1D grid, create 1D representation of it, and print it */ +void printGrid(Grid grid) +{ + int grid_h = *grid.getRows(); + int grid_w = *grid.getCols(); + string padding = string(grid_w + 1, '*'); + string *board = new string[grid_h * grid_w]; + int k; + for (k = 0; k < grid_h * grid_w; k++) + board[k] = "."; + + int i = 0; + Piece tmp(""); + string name; + int row; + int col; + int w; + int h; + char dir; + int offset; + + for (vector::size_type ix = 0; ix != grid.getPieces()->size(); ++ix, i++) + { + tmp = (*(grid.getPieces()))[ix]; + name = tmp.getName(); + row = tmp.getRow(); + col = tmp.getCol(); + w = tmp.getW(); + h = tmp.getH(); + dir = tmp.getDir(); + + int j; + offset = (grid_w * (row-1)) + col; + if (w == 1) + { + for (j = 0; j < h; j++) + board[offset + (j * grid_w) - 1] = name; + } + else if (h == 1) + { + for (j = 0; j < w; j++) + board[offset - 1 + j] = name; + } + else + cout << "oops in printGrid(), height or width of a piece is not 1!\n"; + } + + cout << padding << "*\n*"; + for (int k = 1; k <= grid_h * grid_w; k++) + { + cout << board[k-1]; + if (k % grid_w == 0) + cout << "*\n*"; + } + cout << padding << endl << endl; + + delete [] board; +} + +/* load grid from a file */ +Grid loadGrid(char **argv) +{ + FILE *fname = fopen(argv[1], "r"); + if (fname == NULL) + { + perror("fopen"); + exit(EXIT_FAILURE); + } + + Grid grid; + Piece piece_tmp(""); + + /* used for line reading */ + size_t line_sz = 0; + char *line = NULL; + int matched_inputs = 0; + + if (getline(&line, &line_sz, fname) != -1) + sscanf(line, "%d %d\n", grid.getRows(), grid.getCols()); + + if (*grid.getRows() < 1 || *grid.getCols() < 1) + { + cout << "invalid grid dimensions, read in: " << *grid.getRows() << "h, " + << *grid.getCols() << "w" << endl; + exit(EXIT_FAILURE); + } + + /* parse grid's dimensions */ + int piece_row = -1; + int piece_col = -1; + int piece_w = -1; + int piece_h = -1; + char piece_dir = 0; + int line_cnt = 0; + string piece_name; + bool foundGoalPiece = false; + int ret; + int i; + + for (i = 0; getline(&line, &line_sz, fname) != -1; i++) + { + matched_inputs = sscanf(line, "%d %d %d %d %c\n", &piece_row, + &piece_col, &piece_w, &piece_h, &piece_dir); + + if (matched_inputs != 5) + { + cout << "failed to parse line " << i+2 << ", skipping: " << line; + continue; + } + else if (!foundGoalPiece) + { + piece_name = string("Z"); + piece_tmp = Piece(piece_name, piece_row, piece_col, piece_w, piece_h, piece_dir); + ret = checkPiece(*grid.getRows(), *grid.getCols(), piece_tmp); + if (ret != 0) + { + cout << "failed to parse line " << i+2 << ", " << err_msg[ret] << endl; + continue; + } + + grid.getPieces()->push_back(piece_tmp); + foundGoalPiece = true; + } + else + { + piece_name = string(piece_tag[line_cnt-1]); + piece_tmp = Piece(piece_name, piece_row, piece_col, piece_w, piece_h, piece_dir); + ret = checkPiece(*grid.getRows(), *grid.getCols(), piece_tmp); + if (ret != 0) + { + cout << "failed to parse line " << i+2 << ", " << err_msg[ret] << endl; + continue; + } + + grid.getPieces()->push_back(piece_tmp); + } + + line_cnt++; + } + + cout << "read in " << line_cnt << " pieces" << endl; + fclose(fname); + + return grid; +} + +/* can piece move to left? If so, have many spaces */ +int canMoveLeft(string board[], int row_sz, int col_sz, Piece piece) +{ + int ret = 0; + int offset = ( ((piece.getRow() - 1 ) * col_sz) + piece.getCol() ) - 1; + + if (piece.getH() == 1) + { + if (!offset || (offset % col_sz == 0)) + return 0; + + while (board[offset-1] == ".") + { + offset--; + ret++; + + if (offset % col_sz == 0) + break; + } + + return ret; + } + else if (piece.getW() == 1) + { + int offset2 = offset + col_sz; /* fix me later */ + + if (!offset || (offset % col_sz == 0)) + return 0; + +#if 0 /* XXX: unimplemented */ + int i; + while(1) + for (i = 0; i < piece.getH()) + { + + } +#endif + + while (board[offset-1] == "." && board[offset2-1] == ".") + { + offset--; + offset2--; + ret++; + + if (offset % col_sz == 0) + break; + } + + return ret; + } + else + cout << "oops in canMoveLeft(), height or width of a piece is not 1!\n"; + + return 0; +} + +/* can piece move to right? If so, have many spaces */ +int canMoveRight(string board[], int row_sz, int col_sz, Piece piece) +{ + int ret = 0; + int offset = ( ((piece.getRow() - 1 ) * col_sz) + piece.getCol() ) - 1; + + if (piece.getH() == 1) + { + offset += piece.getW(); + offset--; + + if (!offset || ((offset+1) % col_sz == 0)) + return 0; + + while (board[offset+1] == ".") + { + offset++; + ret++; + + if (offset % col_sz == 0) + break; + } + + return ret; + } + else if (piece.getW() == 1) + { + offset += piece.getW(); + offset--; + + int offset2 = offset + col_sz; /* fix me later */ + + if (!offset || ((offset+1) % col_sz == 0)) + return 0; + + while (board[offset+1] == "." && board[offset2+1] == ".") + { + offset++; + offset2++; + ret++; + + if (offset % col_sz == 0) + break; + } + + return ret; + } + else + cout << "oops in canMoveRight(), height or width of a piece is not 1!\n"; + + return 0; +} + +/* can piece move up? If so, have many spaces */ +int canMoveUp(string board[], int row_sz, int col_sz, Piece piece) +{ + int ret = 0; + int offset = ( ((piece.getRow() - 1 ) * col_sz) + piece.getCol() ) - 1; + + if (piece.getW() == 1) + { + if (!offset || offset < col_sz) + return 0; + + while (board[offset-col_sz] == ".") + { + offset -= col_sz; + ret++; + + if (offset-col_sz < 0) + break; + } + + return ret; + } + else if (piece.getH() == 1) + { + int offset2 = offset + piece.getW() - 1; /* fix me later */ + + if (!offset || offset < col_sz) + return 0; + + while (board[offset-col_sz] == "." && board[offset2-col_sz] == ".") + { + offset -= col_sz; + offset2 -= col_sz; + ret++; + + if (offset-col_sz < 0) + break; + } + + return ret; + } + else + cout << "oops in canMoveUp(), height or width of a piece is not 1!\n"; + + return 0; +} + +/* can piece move down? If so, have many spaces */ +int canMoveDown(string board[], int row_sz, int col_sz, Piece piece) +{ + int ret = 0; + int offset = ( ((piece.getRow() - 1 ) * col_sz) + piece.getCol() ) - 1; + + if (piece.getW() == 1) + { + if (piece.getH() != 1) + offset = col_sz * piece.getH(); + + if (offset + col_sz > row_sz * col_sz) + return 0; + + while (board[offset+col_sz] == ".") + { + offset += col_sz; + ret++; + + if (offset+col_sz > row_sz * col_sz) + break; + } + + return ret; + } + else if (piece.getH() == 1) + { + int offset2 = offset + piece.getW() - 1; /* fix me later */ + + if (offset + col_sz > row_sz * col_sz) + return 0; + + while (board[offset+col_sz] == "." && board[offset2+col_sz] == ".") + { + offset += col_sz; + offset2 += col_sz; + ret++; + + if (offset+col_sz > row_sz * col_sz) + break; + } + + return ret; + } + else + cout << "oops in canMoveDown(), height or width of a piece is not 1!\n"; + + return 0; +} + +/* fill in a queue with grids to be checked */ +int possibleMoves(Grid grid, queue &kway) +{ + Piece tmp(""); + Piece tmp2(""); + string *filled = fillBoard(grid); + char dir; + int ret; + char move[100]; + int howMany = 0; + + int i; + /* for all pieces in Grid grid */ + for (vector::size_type ix = 0; ix != grid.getPieces()->size(); ++ix) + { + tmp = (*(grid.getPieces()))[ix]; + dir = tmp.getDir(); + + /* check where piece can go and create a new graph */ + if (dir == 'h' || dir == 'b') + { + /* left */ + ret = canMoveLeft(filled, *grid.getRows(), *grid.getCols(), tmp); + howMany += ret; + + for (i = 0; i < ret; i++) + { + Grid new_grid = grid; + tmp2 = (*(new_grid.getPieces()))[ix]; + tmp2.setCol(tmp2.getCol() - (i+1)); + (*(new_grid.getPieces()))[ix] = tmp2; /* update position */ + + /* update movement */ + sprintf(move, "Piece %s left %d space(s)\n", tmp2.getName().c_str(), i+1); + new_grid.addMove(string(move)); + + cout << "pushing new grid, \"" << tmp2.getName() << "\"" + << " can move " << i+1 << " space(s)" << " to the left" << endl; + kway.push(new_grid); + } + + /* right */ + ret = canMoveRight(filled, *grid.getRows(), *grid.getCols(), tmp); + howMany += ret; + + for (i = 0; i < ret; i++) + { + Grid new_grid = grid; + tmp2 = (*(new_grid.getPieces()))[ix]; + tmp2.setCol(tmp2.getCol() + (i+1)); + (*(new_grid.getPieces()))[ix] = tmp2; /* update position */ + + /* update movement */ + sprintf(move, "Piece %s right %d space(s)\n", tmp2.getName().c_str(), i+1); + new_grid.addMove(string(move)); + + cout << "pushing new grid, \"" << tmp2.getName() << "\"" + << " can move " << i+1 << " space(s)" << " to the right" << endl; + kway.push(new_grid); + } + } + + if (dir == 'v' || dir == 'b') + { + /* up */ + ret = canMoveUp(filled, *grid.getRows(), *grid.getCols(), tmp); + howMany += ret; + + for (i = 0; i < ret; i++) + { + Grid new_grid = grid; + tmp2 = (*(new_grid.getPieces()))[ix]; + tmp2.setRow(tmp2.getRow() - (i+1)); + (*(new_grid.getPieces()))[ix] = tmp2; /* update position */ + + /* update movement */ + sprintf(move, "Piece %s up %d space(s)\n", tmp2.getName().c_str(), i+1); + new_grid.addMove(string(move)); + + cout << "pushing new grid, \"" << tmp2.getName() << "\"" + << " can move " << i+1 << " space(s)" << " up" << endl; + kway.push(new_grid); + } + + /* down */ + ret = canMoveDown(filled, *grid.getRows(), *grid.getCols(), tmp); + howMany += ret; + + for (i = 0; i < ret; i++) + { + Grid new_grid = grid; + tmp2 = (*(new_grid.getPieces()))[ix]; + tmp2.setRow(tmp2.getRow() + (i+1)); + (*(new_grid.getPieces()))[ix] = tmp2; /* update position */ + + /* update movement */ + sprintf(move, "Piece %s down %d space(s)\n", tmp2.getName().c_str(), i+1); + new_grid.addMove(string(move)); + + cout << "pushing new grid, \"" << tmp2.getName() << "\"" + << " can move " << i+1 << " space(s)" << " down" << endl; + kway.push(new_grid); + } + } + + } + + return howMany; +} + +int main(int argc, char *argv[]) +{ + /* seed rand() */ + srand((unsigned int ) time(NULL)); + + if (argc != 2) + { + cout << "usage: " << argv[0] << " " << endl; + return -1; + } + + Grid grid = loadGrid(argv); + printGrid(grid); + queue toCheck; + queue checked; + + /* kickstart the queue */ + possibleMoves(grid, toCheck); + + while (1) + { + while (!toCheck.empty()) + { + Grid popped = toCheck.front(); + toCheck.pop(); + checked.push(popped); + + if (checkSoln(popped)) + { + cout << "Solution: " << endl; + printGrid(popped); + exit(0); + } + else + { + cout << "The below was not a solution: " << endl; + printGrid(popped); + } + } + possibleMoves(checked.front(), toCheck); + checked.pop(); + } + +#if 0 + if (memcmp(&grid, ©, sizeof(Grid)) == 0) + cout << "victory" << endl; + else + cout << "else" << endl; +#endif + + cout << "\n\tBye!" << endl; + return 0; +} diff --git a/main.h b/main.h new file mode 100644 index 0000000..56cc773 --- /dev/null +++ b/main.h @@ -0,0 +1,34 @@ +#ifndef _MAIN_H_ +#define _MAIN_H_ + +#include +#include +#include +#include +#include + +#include "piece.h" +#include "grid.h" + +#define ANSI_COLOR_RED "\x1b[31m" +#define ANSI_COLOR_GREEN "\x1b[32m" +#define ANSI_COLOR_YELLOW "\x1b[33m" +#define ANSI_COLOR_BLUE "\x1b[34m" +#define ANSI_COLOR_MAGENTA "\x1b[35m" +#define ANSI_COLOR_CYAN "\x1b[36m" +#define ANSI_COLOR_RESET "\x1b[0m" +#define PRINT_COLOR(C, S) printf("%s%s%s", C, S, ANSI_COLOR_RESET) + +using std::vector; +using std::queue; + +string piece_tag[] = {"1", "2", "3", "4", "5", "6", "7", "8", "9", "a", "b", "c", + "d", "e", "f", "g", "h", "i", "j", "k", "l", "m", "n", "o", + "p", "q", "r", "s", "t", "u", "v", "w", "x", "y", "z", "A", + "B", "C", "D", "E", "F", "G", "H", "I", "J", "K", "L", "M", + "N", "O", "P", "Q", "R", "S", "T", "U", "V", "W", "X", "Y", + "Z"}; + +string err_msg[4] = {"piece is correct", "piece has wrong dimensions", "piece has wrong direction", "piece is out of bounds"}; + +#endif diff --git a/piece.cpp b/piece.cpp new file mode 100644 index 0000000..0d3eec1 --- /dev/null +++ b/piece.cpp @@ -0,0 +1,68 @@ +/* + * piece.cpp + * + * + */ + +#include "piece.h" + +Piece::Piece(string name_p, int row_p, int col_p, int w_p, int h_p, char dir_p) : name(name_p), + row(row_p), + col(col_p), + w(w_p), + h(h_p), + dir(dir_p) +{ +} + +string Piece::getName(void) +{ + return name; +} + +int Piece::getRow(void) +{ + return row; +} + +int Piece::getCol(void) +{ + return col; +} + +int Piece::getW(void) +{ + return w; +} + +int Piece::getH(void) +{ + return h; +} + +char Piece::getDir(void) +{ + return dir; +} + +/* mark the current position of the piece */ +void Piece::markPos(void) +{ + POINT curr = { row, col }; + haveBeen.push_back(curr); +} + +vector *Piece::gethaveBeen(void) +{ + return &haveBeen; +} + +void Piece::setRow(int row_p) +{ + row = row_p; +} + +void Piece::setCol(int col_p) +{ + col = col_p; +} diff --git a/piece.h b/piece.h new file mode 100644 index 0000000..52c2a5b --- /dev/null +++ b/piece.h @@ -0,0 +1,48 @@ +#ifndef _PIECE_H_ +#define _PIECE_H_ + +#include +#include +#include +#include + +using std::string; +using std::cout; +using std::endl; +using std::vector; + +typedef struct +{ + int row; + int col; +} POINT; + +class Piece +{ + private: + string name; + int row; + int col; + int w; + int h; + char dir; + vector haveBeen; + + public: + Piece(void); + Piece(string, int = 0, int = 0, int = 0, int = 0, char = 0); + + string getName(void); + int getRow(void); + int getCol(void); + int getW(void); + int getH(void); + char getDir(void); + void markPos(void); + vector *gethaveBeen(void); + + void setRow(int); + void setCol(int); +}; + +#endif -- cgit v1.2.3