Concepts of Computer Systems (CSCI250)
Project: Fall term, 20191
Due Dates:
Due: Monday Dec. 2
Early Submission (10% bonus): Friday Nov. 22
Late Submission (20% penalty): Tuesday Dec. 3
Goals and Objectives
The goal of this project is to write a complete MIPS program from scratch.
Overview
For this project you will be writing a MIPS assembly program to solve a Tents puzzle.
Unsolved puzzle
Solved puzzle
The Tents puzzle will be given to you as an ASCII text stream (which can be typed in on the command line or redirected from a file). You will print out the unsolved puzzle, then a solved version with all the tents placed.
For information about Tents puzzles, and how to solve them, go to BrainBashers.com. or dkmsoftware.com.
Rules of Tents
You have a grid of squares, some of which contain trees. Your aim is to place tents in some of the remaining squares, in such a way that the following conditions are met:
Each tree has exactly one tent attached to it.
Each tent is attached to one tree (so there are as many tents as there are trees).
The numbers across the bottom and down the side tell you how many tents are in the respective column or row.
A tent can only be placed horizontally or vertically adjacent to a tree.
Tents are never adjacent to each other, neither vertically, horizontally, nor diagonally.
A tree might be next to two tents, but is only connected to one.
Input Specification
The puzzle will be provided to you on STDIN (i.e., as if a user were typing it in at the console). The Input will contain multiple lines of ascii text (strings) where each line may have a different meaning.
Note, we guarantee that each line will always have the correct number of characters. We also guarantee that the number lines will only contain digit characters. We in no way promise that the digits are in the correct range, or that the characters are valid. Below we talk about the valid values for each input.
The first line entered will contain the board size (we will call the board size n from this point on). The legal range for the size is between 2 and 12 inclusively. If the board size is not within that range, your program should print the following error message and terminate.
Error message 1
Invalid board size, Tents terminating
The next line contains a string made up of n digits. These will be used as the row sums (the number of tents that need to be placed in each row), entered from top to bottom. Note, that the value for a row sum will always be a single digit number, since the max board size is 12, and there can only be (size+1)/2 (integer division) tents in a single row (since tents cant be next to each other). So, while reading row sum values, the number of tents in a row must be between 0 and (n+1)/2 inclusively, if not then your program should print the following error message and terminate.
Error message 2
Illegal sum value, Tents terminating
The next line contains a string made up of n digits. These will be used as the column sums (the number of tents that need to be placed in each column), entered from left to right. Again note, as above, that these will all be single digit numbers. The number of tents must be between 0 and (n+1)/2 inclusively. If a tent count for a column is not within this range, then your program should print Error message 2 above and terminate.
The next n lines will contain the rows of the board. Each row will contain n characters, which make up the initial value for each square on the board. The only legal possibilities for initial squares are grass, which will be represented by a period character (.) and a tree which will be represented by a capital t (T) If the character is not one of these two values, then your program should print the following error message and terminate.
Error message 3
Illegal board character, Tents terminating
Here is asample input file.
Input Processing Hint
Be aware that you wont be able to read the row/column sums as numbers because with 12 being the max size of a board, that could be a number in the 100s of billions, which is much to big to fit in a 32-bit int. So you will need to read some (all) of the numeric input as strings and then convert them to integers, by writing your own ascii-to-int function (remember you did something similar in lab 3).
Output Specification
Your program output will have the following parts:
1) The program banner
The first thing you should output is a blank line, then the program banner. It looks like the following:
******************
** TENTS**
******************
After the program banner, leave one (1) blank line.
Note, at this point your code should read all the input. If there is an error in the input, you program should terminate without printing anything but the error message.
2) The initial puzzle
Your program should print the words Initial puzzle followed by a blank line. Then print the puzzle, formatted to include a box around the whole puzzle. The output should look like this:
Initial Puzzle
+-+
| T . T . . . | 1
| . . . . . . | 1
| . . . . T . | 1
| . . . . T . | 2
| T T T . . . | 1
| . . . . . . | 1
+-+
2 1 1 1 1 1
Note that the boxes are made of plus signs ( + ) for corners, dashes ( ) for horizontal lines, and vertical bars ( | ) for vertical lines. For the content of the puzzle, trees are printed as capital Ts ( T ), and grass squares are printed as periods ( . ).
Also note that the row sums are placed to the right of the puzzle separated by a space. The column sums are below the puzzle lined up with the individual columns (you can assume the column sums will never be greater than 9). Also note that there are no extra spaces at the end of the lines. Ont last thing, if the input is correct, then your program should always print the initial puzzle, before you try to solve it.
After printing the unsolved input puzzle, leave one (1) blank line.
3) The solved puzzle
Your program should print Final puzzle followed by a blank line. Then print out the puzzle with all the tents added. The output should look like:
Final Puzzle
+-+
| T . T A . . | 1
| A . . . . . | 1
| . . . . T A | 1
| A . A . T . | 2
| T T T . A . | 1
| . A . . . . | 1
+-+
2 1 1 1 1 1
Note that the tents are printed out as capital As ( A ).
After printing the solved puzzle, leave one (1) blank line.
Example 1: complete program output
******************
** TENTS**
******************
Initial Puzzle
+-+
| T . T . . . | 1
| . . . . . . | 1
| . . . . T . | 1
| . . . . T . | 2
| T T T . . . | 1
| . . . . . . | 1
+-+
2 1 1 1 1 1
Final Puzzle
+-+
| T . T A . . | 1
| A . . . . . | 1
| . . . . T A | 1
| A . A . T . | 2
| T T T . A . | 1
| . A . . . . | 1
+-+
2 1 1 1 1 1
Here is a sample output file.
Error message
Your program must be able to detect one error condition, and that is if you find that the provided input puzzle can not be solved, in which case you should print the following message followed by a blank line, then your program should terminate.
Impossible Puzzle
An impossible puzzle occurs when you have tried every possible tent location and none of them are legal.
Algorithm
The simplest method for writing a solver is to use a brute force algorithm (backtracking). There are other algorithms for solving a Tents puzzle, but they generally require a more difficult algorithm, and such would be even more painful (than the brute force) to implement in assembly.
Briefly, a backtracking program would solve a puzzle by placing the value (a guess) in the first guess-able spot (a value can represent a grass square, or a tent attached to a specific tree adjacent to that spot) and checking if it is allowed to be there. If there are no violations (checking that its next to a tree, it not next to another tent, and it is under the max count of tents for the row and column) then the algorithm advances to the next guess-able spot, and makes a guess for that spot.
When checking for violations, if it is discovered that any guess you could make for the spot is not allowed, then the algorithm leaves that guess-able spot blank and moves back to the previous spot. The guess for that spot is then moved to the next possibility.
The algorithm is repeated until a legal value is found for all guess-able spots (the guesses you made previously then make up a valid solution) or you find that you cant make any guess for the first guess-able spot (which means that there is no solution to this puzzle)
The above algorithms were left vague about the definition of a guess-able spot on purpose because there are at least two ways to look at this puzzle.
1.From the board view, where you try to guess the value for each square on the board (grass or tent). Note in this view you may have to look at more than one possible way of placing a tent into a square, since it is possible to have two trees next to a tent (where the tent is connected to only one of those trees).
2.From the tree view, where you would need to guess in which direction around each tree the tent will go. Note that in this view you need to keep track of all the trees independently, and also keep track of the board (for row/column checking) as well as deal with the possibility of trying to place a tent off the board (trying to put the tent outward on a tree that is on the edge of the puzzle).
One more thing to keep in mind about backtracking is that the number of possible boards is huge (for a 1212 board, there is 2144 possiblilities). There is no way you can create each of these. So you will need to solve it with less, (it is possible to solve this puzzle using only a single board). In addition, to test all boards would take a long time, assuming you can test 1,000,000 boards/sec it would take you 729 years to test them all. So you will need to test and invalidate a board early (as soon as you know a guess is bad).
Activities
You may use any file names you wish for your solution, with the restriction that the file containing your main() function must be named tents.asm.
Because the purpose of this project is for you to write a complete assembly language program, from scratch, no starting materials will be made available to you. However, here is an input files to get you started.
sample1_in.txt
sample2_in.txt
sample3_in.txt
sample4_in.txt
sample5_in.txt
Note: To save these files (and the output files below) you should right-click on the link and use the Save Link As option.
If you open these input/output files in a browser then any leading and trailing blank lines will not be displayed. If you then select-all and copy/paste into a file, any leading and trailing blank lines will not be copied.
You can invoke your program on a data file by typing (using sample1_in.txt as an example input):
/home/fac/wrc/bin/rsim tents.out < sample1_in.txtRemember that the output generated when you re-direct input from a file will not echo the input (including the newlines typed by the user). If you redirect the output to a file: /home/fac/wrc/bin/rsim tents.out < sample1_in.txt > myout1.out
it should match the output found in:
sample1_out.txt
sample2_out.txt
sample3_out.txt
sample4_out.txt
sample5_out.txt
Make sure to spend the time making your output match the description above and provided in the sample file; we will be using diff to compare your output to ours, and diff looks for differences in whitespace and extra or missing blank lines as well as real output differences. You can check for differences yourself with the vimdiff program:
vimdiff myout1.out sample1_out.txt
You should also take the time to comment your program. This includes a file comment at the top of the program with your name, your section number, a description of the project and sections talking about the input and output of the program. In the code, make sure that you use block comments for each function you write, and other comments to describe what the code is doing. Refer to the previous experiments for examples of reasonable comments in front of functions and subprograms.
Submitting Your Code
Submit your solution using the following command:
try grd-250 project1 tents.asm other_files.asm
where other_files.asm includes any other assembly language source files containing parts of your solution.
Grading
This project is worth a total of 50 points. 40 points will be awarded based on functionality, and the remaining 10 points will be based on your programming design and style (functional decomposition, code organization, documentation, clarity of code, etc.)
Tips and Tricks
The entry point to your program must be a global symbol named main, or else your program wont link correctly into a load module and the simulator will refuse to run it.
To simplify assembling and linking your program, you can use the Makefile from experiment 5 as a template for creating a Makefile for this project by replacing all occurrences of that experiments object (.obj) and executable (.out) files with the ones for your solution.
Make intelligent use of functions e.g., write functions for reading input, writing output, reading/writing values from/to the grid, etc. If you write your output routines early, you can use them for debugging as you write the rest of your code.
Test early and often. Test functional units as soon as they are written. This includes your puzzle reading function, your square lookup and write functions, your change-position function, etc.
When you have a bug, use the simulators built-in debugger to step through your code. Run the simulator with the -d option to enable the debugger, and the -t option to turn on line-by-line tracing of instructions. Be sure to read the using rbug section in the RSIM Reference Manual to see what commands are available; in particular, breakpoints, single-stepping, and register commands will be useful.
You can, if you wish, put all of the functions implementing your solution in the tents.asm file. However, just as in programming using high-level languages, good programming practice would be to separate out the parts of your solution into major functional units, and to put the code for each unit in a separate source file.
Use the provided test input/output file(s) to check your text messages for correctness. You can run the diff or vimdiff programs yourself to see if there is any differences between your output and ours.
Last updated by paw Oct 17, 2019
Reviews
There are no reviews yet.