Assignment 6
CSCI 3136: Principles of Programming Languages
Due March 26, 2021
Assignments are due on the due date before 23:59. Plagiarism in assignment answers will not be tolerated. By submitting their answers to this assignment, the authors named above declare that its content is their original work and that they did not use any sources for its preparation other than the class notes, the textbook, and ones explicitly acknowledged in the answers. Any suspected act of plagiarism will be reported to the Faculty’s Academic Integrity Officer and possibly to the Senate Discipline Committee. The penalty for academic dishonesty may range from failing the course to expulsion from the university, in accordance with Dalhousie University’s regulations regarding academic integrity.
Rush Hour
Rush Hour is an entertaining puzzle game. You are given a 6 × 6 grid with cars (horizontal or vertical 3 × 1 or 2 × 1 rectangles) placed on it. From here on, I call this grid the board because the original Rush Hour game was a board game. The board is enclosed by walls, but there is an opening on the right side of the third row:
Horizontal cars are allowed to move left and right but only as far as they can go without hitting other cars or the wall. (“Hit” means “occupy the same grid cell as”.) Vertical cars are allowed to move up and down subject to the same rules. By moving cars out of the way, you create new possible moves for other cars. The third row has a single horizontal 2 × 1 car on it. In the example above, this car is red. Your goal is to find the shortest sequence of moves that allows the red car to move through the gap on the right of the third row. A single move moves a single horizontal car left or right or a single vertical car up or down. Whether you move this car by 1, 2, 3 or 4 positions is unimportant; it still counts as only one move as long as the move is legal (does not hit the wall or other cars). Since the board is a 6 × 6 grid and every car is at least 2 cells long, no car can legally move by more than 4 positions.
To simplify the computational modelling of the problem, we will consider the red car to be free if it is in the 5th and 6th columns, that is, its right end is right next to the opening in the wall. Clearly, if we can move the red car to this position, we can also move it through the opening without any additional moves. The following is a possible solution state reachable from the state above:
Your goal in the next two programming assignments is to implement Haskell code that can find a shortest sequence of legal moves—an optimal solution—that frees the red car. As part of this assignment, I provide you with a skeleton of this project, which includes
• A database of all possible starting positions for the Rush Hour puzzle (rush_no_walls.txt).
• A solution checker for the Rush Hour puzzle (rush_hour_check.py).
• A skeleton of a Haskell project that takes care of reading a puzzle from the database and writing
the results to screen.
1
Your finished Rush Hour solver takes the number of the Rush Hour puzzle in the database to be solved as an argument. It solves the puzzle and then prints the sequence of moves to stdout:
$ cd
$ stack run — 84386
BBHooKFoHoJKFAAoJLoGCCoLoGoIDDEEoIoo
(3,1)+2
(3,3)-1
(2,3)+1
(1,2)+3
(3,3)-1
(3,2)+2
(5,2)-3
(3,4)-1
(4,4)-1
(6,4)-2
(5,6)-3
(3,5)+2
(4,4)+1
(4,6)+1
(3,3)+3
The first 36-character string is the textual encoding of the puzzle in the database. Since this puzzle takes 15 moves to solve, this line is followed by 15 lines, each storing one move in the optimal move sequence. Each move is represented in the form (row,col)±offset. Both row and col are integers between 1 and 6 and refer to the position of the rightmost (bottommost) square of a horizontal (vertical) car to be moved. For a horizontal car, a negative offset means the car is moved offset positions to the left; a positive offset means the car is moved offset positions to the right. For a vertical car, a negative offset means move up; a positive offset means move down.
The solution checker, rush_hour_check.py, can both check that the produced solution for a given puzzle is correct and produce a visual representation of the solution. Since the solution checker reads its input from a file, you need to collect the output of your solver in a file, which you then pass as an argument to rush_hour_check.py. Once again, it is important that you run rush_hour_check.py from the same directory that contains rush_no_walls.txt because the path to this file is hardcoded into rush_hour_check.py.
2
$ cd
$ ./rush_hour_check.py
Optimal moves = 15
Moves in solution = 15
Search space size = 308818
The computed solution is optimal.
the project> 84386.sol 84386.sol
In this example, rush_hour_check.py is happy with its input and reports that the solution is optimal. It also prints the sequence of board states produced from the start state by the sequence of moves in the so- lution. The first state (top left) is the start state encoded by the string “BBHooKFoHoJKFAAoJLoGCCoLoGoI DDEEoIoo”. The last state (bottom right) is the solved state reached at the end of the sequence of moves. Each state is obtained from the previous state to its left by moving one car to the left, to the right, up or down as instructed by the output of your solver.
If the first string in the input file of rush_hour_check.py is not a puzzle in the database, a move is not a valid move, the final state is not a solution state (the car in the third row is not in the rightmost position) or the number of moves is not optimal, rush_hour_check.py will print an error message.
One useful piece of information you see in the output is the search space size. This is the total number of board states that are reachable from the initial state. The largest search space is the one of puzzle 84385, which has over 500,000 states in it. The general rule of thumb is that a larger search space size means the puzzle is harder to solve, at least for a computer. I recommend that you use puzzles with small search space sizes for your initial tests and move to bigger search spaces only once and if you are ready to test the efficiency of your code. If have implementations of Rush Hour solvers in various programming languages. My Rust implementation solves any puzzle in the database in 0.08s or less on my laptop. My Haskell implementation takes less than 2s for any puzzle in the database on my laptop. This should translate into no more than 3–4s on timberlea. Your implementation may not match this performance because my implementation includes some advanced performance optimizations, but if it takes minutes to solve some puzzles, chances are your algorithm is wrong.
To find out which puzzles have small search spaces, look at the database file rush_no_walls.txt. The 3
puzzle number refers to the line in this file that the puzzle is stored on, starting from 0 for the first line. Each line has 3 fields: the optimal number of moves to solve it, the 36-character string encoding the puzzle, and the size of the search space.
Submission Instructions
Submit your assignment in a single ZIP-file named in the form Banner_LastName_FirstName.zip, where Banner, Lastname, and FirstName are your banner number, last name, and first name. The file should contain the follow directory structure:
Compiling and Running Your Code
Since I did not teach you how to work in the IO monad, which is necessary to read files and write to stdout, I am providing a skeleton project within which to embed your code. This skeleton project is provided as part of this assignment. If you look inside the src folder of this project, it already contains a file RushHour.hs. This is the file where you need to add your code. To submit it following the instructions above, copy it into a separate folder Banner_LastName_FirstName outside the skeleton project and submit it. To compile and run your code, you need the RushHour.hs file to be inside the src folder of the project I provided.
You compile the code and check for any compilation errors you encounter using
$ stack build
This command works anywhere inside the rush hour project directory and any of its subdirectories. To run the code, use
$ stack run —
.
Banner_LastName_FirstName
RushHour.hs
4
The Skeleton Project
The skeleton project contains a number of files, including configuration files that instruct stack how to build your project. You shouldn’t need to worry about them. The only file you do need to be interested in is src/RushHour.hs. As I said before, this is where you need to place your code. The other file that may be interesting is app/Main.hs. Together, these two files contain the whole source code of your program. app/Main.hs contains all the code to read command line arguments, load the puzzle from the database, and write the solution to stdout. This conde relies on a single function exported by src/RushHour.hs:
solvePuzzle :: [(Int, Int, Int, Bool)] -> Maybe [(Int, Int, Int)]
This function is currently a stub. Your task is to implement it over the next two programming assign- ments.
The argument of solvePuzzle is a list of quadruples. Each quadruple represents a piece (car) on the board. The first piece is always the horizontal piece in row 3, the one you need to free. Each piece is represented by the following four pieces of information, in this order:
• The row containing the starting cell of the piece.
• The column containing the starting cell of the piece.
• The length of the piece (2 or 3).
• False if the piece is horizontal and True if the piece is vertical.
The “starting” cell of a horizontal piece is the leftmost cell occupied by the piece. For a vertical piece, it is the topmost cell occupied by the piece. Rows and columns are numbered top to bottom, left to right, starting from 1.
As an example, the starting position on top of page 1 would be provided to solvePuzzle as the list
The ordering of the tuples in this list may be different. Only the first tuple is guaranteed to be the first tuple because it represents the car to be freed.
The return value of solve is a list of triples representing the moves your solution performs to free the piece in row 3, wrapped in Just. Each move is represented by the following three values:
• The row containing the ending cell of the moved piece.
• The column containing the ending cell of the moved piece.
• The offset by which the piece is moved. A negative offset means move left or up, depending
on the orientation of the piece. A positive offset means move right or down, depending on the orientation of the piece.
[ (3,2,2,False), (1,1,2,False), (1,3,2,True), (1,6,2,True), (2,1,2,True)
, (2,5,2,True), (3,6,2,True), (4,2,2,True), (4,3,2,False), (5,4,2,True)
, (5,5,2,False), (6,1,2,False)
]
5
The “ending” cell of a horizontal piece is the rightmost cell occupied by the piece. For a vertical piece, it is the bottommost cell occupied by the piece. If there is no solution, your function should return Nothing.
As an example, the solution on page 2 would be represented as the list
Two comments:
• The type of the solvePuzzle function would normally not be a good choice. You would probably define custom data types Piece and Move and then define a function
solvePuzzle :: [Piece] -> Maybe [Move]. Since I needed to make my Main.hs code interface with your code no matter how you define these types, I opted for a generic representation of pieces and moves as tuples.
• Note that in the argument list of solvePuzzle, each piece’s position is indicated by its starting cell. In the result list of moves, each moved piece is referenced by its ending cell. The former is natural. The latter is an idiosyncracy of rush_hour_check.py, which I had no time to change.
Just [ (3,1, 2), (3,3,-1), (2,3, 1), (1,2,3), (3,3,-1), (3,2,2), (5,2,-3), (3,4,-1) , (4,4,-1), (6,4,-2), (5,6,-3), (3,5,2), (4,4, 1), (4,6,1), (3,3, 3)
]
6
This Assignment:
Implement the Data Types for Your Rush Hour Solver and “I/O” Functions
In this assignment, you have four tasks:
• Design data types that represent the state of your solver code.
• Implement functions that convert the argument of solvePuzzle into your internal representation of the board state, and your internal representation of the list of moves into the list of tuples to be returned by solvePuzzle.
• Implement a stub
of a function that takes your representation of the board state as input and returns your repre- sentation of the list of moves. This is the actual solver of a rush hour puzzle. Implementing this function is your task in the next assignment.
• Implement solvePuzzle in terms of the above three functions.
At the end of this assignment, your code should compile without errors. It obviously won’t run yet
because your actual solver function is undefined. The Types You Need
An efficient implementation of the search for an optimal solution (a minimum-length sequence of moves that frees the red car) will use breadth-first search through the space of board positions, starting at the initial board state.1 The first level of your search contains the start configuration. Then you proceed level by level. To generate the (i + 1)st level from the ith level, you inspect every state s on the ith level, generate its neighbours, states that can be reached from s by (legally) moving a single piece, and then level i + 1 contains all these neighbour states tat aren’t already included in levels 1 through i. Once your current level contains a state where the red car is free, you have found a solution. At this point, you need to record the sequence of moves you performed to reach this state. Thus, for each state in the current level, you also need to record the sequence of moves you followed to reach this state from the start configuration. The data types you need to design in this assignment should support this approach to solving the rush hour puzzle:
• You need a State type that stores the positions of all pieces on the board. There are many different ways you can represent this, and I leave the choice up to you. My Python code uses a very compact representation of the board state as 3 bit vectors. My initial Haskell implementation did the same, but this turned out to be rather slow in Haskell. My fast Haskell implementation opts for a much more direct representation, explicitly storing the board as a Vector (a more
1An implementation using depth-first search and iterative deepening may also be efficient, but I haven’t tested that. 7
functionName :: FunctionType
functionName = undefined
restricted but faster version of an Array) of piece positions.2 You are expected to use a more descriptive representation of pieces and of the State than as a list of tuples.
• Move and Path types. A Move represents moving a single piece. Given the output your code is expected to produce, it is most prudent to represent a move using the bottom-right cell occupied by the moved piece and the offset by which the piece was moved (negative for left/up movements, positive for right/down movements). A Path represents a sequence of moves, exactly what you are expected to report at the end. It is okay to represent the Path as a list of moves, but a move should be represented using a more descriptive data type than a tuple.
• Frontier and ExploredSet. There are two ways to implement breadth-first search. One uses a queue of states to be explored. It adds a newly discovered state at the end of the queue and removes the next state whose neighbours to explore from the beginning of the state. This is a rather imperative way of doing things. The second view of breadth-first search is more suited for a functional implementation. You maintain a Frontier of states at the current level in your search. Your initial frontier, the first level in your search, contains only the start state. Given the current frontier, the next level consists of all neighbours of states in the current frontier that you haven’t seen before. So you need a data type that represents this frontier. You also need a data type to keep track of states you have seen before. That’s your ExploredSet. It is probably best to implement this as an actual Set. Search for Data.Set on Hoogle. Any data type you want to store in a set must have an ordering defined on it (because a Set is essentially implemented as a binary search tree). Since you want to store board states in your ExploredSet, you either need to make your State type an instance of the Eq and Ord type classes, or you need to implement a conversion of State into a type that is already an instance of these type classes. For example, you could represent your state as a list of character positions, each represented as an Int.
Note: We will discuss how to define custom data types on Wednesday, and how to define instances of type classes on Monday. You can also read the relevant chapters of Real World Haskell or Learn You a Haskell to get a head start.
The Functions You Need
As stated above, you are expected to implement three functions and provide a stub for a fourth, to be populated in the next assignment:
makeBoard :: [(Int, Int, Int, Bool)] -> State
This takes the list of piece positions in the argument of solvePuzzle and converts it into a value of type State representing the initial state of the board.
formatSolution :: Path -> [(Int, Int, Int)]
2I do in fact split this into a static part shared by all board positions and a dynamic part that changes between board positions. The length of a piece, the column containing a vertical piece, and the row containing a horizontal piece don’t change. That’s the static part. The only thing that changes is the position of each piece within its row or column. That’s the dynamic part.
8
This takes your representation of a Path, a sequence of moves, and converts it into the representation of the list of moves that solvePuzzle needs to return.
myMagicSolver :: OfSomeType
This is the stub of your actual solver code, to be implemented in the next assignment.
solvePuzzle :: [(Int, Int, Int, Bool)] -> Maybe [(Int, Int, Int)]
This function is the one that the code in app/Main.hs calls to compute a solution to a given puzzle. If you defined the type of myMagicSolver correctly, you should be able to implement solvePuzzle in terms of makeBoard, formatSolution, and myMagicSolver. The logic should be that solvePuzzle takes its input, converts it into a State using makeBoard, passes this board to myMagicSolver to compute a solution for this board, and finally converts the result of myMagicSolver into the list of move tuples to be returned by solvePuzzle using formatSolution.
9