CSCI 1320 - Assignment #9


This assignment is going to test your abilities to use the things that we have recently discussed in class. This includes dynamic memory, structures, etc.

As a side note, be sure to save the code from all the programs you do. It is quite possible that later in the semester other assignments will include things that overlap with them and your code will be reusable.

Sudoku:

This assignment is not connected to any other.

For this problem I want you to write a program that will solve 9x9 Sudoku puzzles. That's fairly easy to do alone. What will make it challenging is that I want it to find a solution quickly. This means that you can't just do brute force recursion (9^81 is a rather large number). So you will have to come up with a way to prune things down so you don't test every possible configuration.

The input will be 9 lines of text, each with 9 characters on it. The characters will either be a space or a single digit number. You should output a board with all the blanks filled in and put spaces between the numbers to keep it readable. See the sample files below. It turns out that most puzzles have more than one solution. That's true for the two I've given below which appear to have at least two solutions. I only need you to provide one.

easy input : easy output

difficult input : difficult output

Text Adventure Items:

This assignment is of most interest to you if you did the map assignment earlier. For this one I want you to add in items to your program. The items should be described in a separate file. So you will need both a map file and an item file. The item file should have item names and descriptions. You might also have identifying numbers for the items. It is possible that there will be extra information as well that you will need for your game. You can decide what that is. Your map file will need to be enhanced so that items can be "placed" in each room. You might list the items after the exits from a room in the map file.

You will also need to implement a few new commands so that the user can interact with items. Part of that interaction will also require that you implement an inventory to keep track of the things that the player has picked up. The following commands need to be added to your program.

get item - take the item with the given name and put it in the players inventory (probably removing it from the room as well). If the item isn't there, print a suitable message.

inv - this should print out the contents of the players inventory.

drop item - this will drop the specified item out of the players inventory and into the room the player is currently in.

look [item|direction] - this is probably the most complex of the new commands because what it does depends on the nature of the second argument. This command will print out a description of whatever the player says to look at. If they don't list something to look at, it should proint the description of the room they are currently in. If a name is specified the program should check to see if it matches the name of anything in the player's inventory. If a match is found, it should print the description of that item. If there is no match found in the inventory it will check the room for items in the room. If no items in the room match it should check if it matches a direction and if it does, print the description of the room that lies in that direction (you can choose not to implement this if it would cause issues for your game). If no match is found in any of those options then print a suitable message.

This should be added to the ability to walk around the map that you create. Note that for the last assignment you will add in an objective to your game and potentially other things to interact with. Basically though I will need you to put in some way to win or lose your text adventure.

Balancing Chemical Equations:

This path continues one of the options for assignment 4 where you had to figure out how many elements of each type were on the different sides of a chemical equation. You should recall that the output of that program was something like the following.

C: a*1=d*1
H: a*4=c*2
O: b*2=c*1+d*2

We want to treat this as a system of linear equations and solve it to find the proper values of a, b, c, and d. These particular formulas give you three equations for four unknowns. If you remember systems of equations, that's typically not a good thing as the system is underdetermined so there are an infinite number of solutions. The easy way to fix that is to assume that a certain number of the coefficients are 1 so that you are left with equal numbers of equations and unknowns.

The form given above would be fine for solving this equation by hand, but for solving it on a computer we will want to move things around a bit. The idea is that we want to get it into the form Ax=y, where A is a matrix giving the explicit numbers in the equations, x is a vector with the variables we are solving for, and y is a vector with whatever constants wind up being on the right side of the equal sign. Let's make this more explicit by rearranging the equations above into something more like the form we want.

1*a-1*d=0
4*a-2*c=0
2*b-1*c-2*d=0

Now we have to pick a coefficient to set to 1 so we get down to equal numbers of equations and coefficients. Any will do equally fine, but programmatically you will probably find it is easiest to set the last coefficient to a constant value (so everything is still zero indexed in your code). In this case that is d. If we do that and move constants to the right side we get the following equations.

1*a=1
4*a-2*c=0
2*b-1*c=2

This can be transformed into Ax=y if A={{1,0,0},{4,0,-1},{0,2,-1}} and y={{1},{0},{2}}. (I'm using C notation for these things because putting matrices into HTML is a pain and would probably confuse things. Both x and y are column vectors here so they have a single column and multiple rows. In C you won't bother making them 2-D arrays. I'm making it look at thway here so it is explicit they are columns for the math aspect.) Remember that x={{a},{b},{c}} and that is what we want to solve for. The way you will do this is through a process called Gaussian elimination. It turns out that there are many methods of doing this that have different numerical properties. Gaussian elimination isn't the best, but it is the simplest to describe so we will go with it. Gaussian elimination is also exactly what you would do if you were solving this problem on paper so hopefully it will make sense.

What we do in Gaussian elimination is multiply and add together rows in A and y to remove coefficients and turn A into a triangular matrix. We might also have to swap rows at certain times. In fact, we will do that generally to improve numerical stability. To begin with, we want to remove the a term from everything but the first row. We could do this with A as it is, but for numerical reasons it is best if we keep the largest coefficient. You'll see other reasons for this when we remove b. So the first thing we do is we note that the largest coefficient of a is 4 and it is in the second row so we swap the first and second rows. Note that we swap them in both A and y. This gives the following values.

A={{4,0,-1},{1,0,0},{0,2,-1}} and y={{0},{1},{2}}

Now we eliminate the a terms in the second and third rows by multiplying their values appropriately so that when we subtract them from the top column we don't have anything left. If the a term is already zero in a row we can leave it alone. In this case we will remove the a term from the middle row by multiplying it by 4 and subtracting the top row from it. We'll do nothing with the bottom row. This gives the following values.

A={{4,0,-1},{0,0,1},{0,2,-1}} and y={{0},{4},{2}}

Now the top row is set so I look at the smaller nested matrix ignoring the first row and column. I want to eliminate the b coefficients from that. Here it really matters that I swap up the row with the largest coefficient because what is there right now has a zero coefficient and that will do bad things. We do the swap and since the last row already has a zero in the b coefficient we won't do anythign else. That leaves us with the following values.

A={{4,0,-1},{0,2,-1},{0,0,1}} and y={{0},{2},{4}}

This we can solve by working out way up the matrix. The bottom row tells us that c=4. We plug that into the next row and get 2*b-4=2 and find b=3. It's easy for us to say that, but we should probably examine how the computer will find these values. For the first one the computer simply does c=y[2]/A[2][2]. Then as we move up we have to do some loops to subtract things off before we do the division. In this case b=(y[1]-c*A[1][2])/A[1][1]. Note that we are always dividing by the component on the diagonal and we subtract off all the terms to the right of the diagonal. Now we are down to our top equation which is a=c/4 so a=1. In the program that will be a=(y[0]-c*A[0][2]-b*A[0][1])/A[0][0]. The y[0] and A[0][1] are both zero but the math in the program will include them and it won't matter.

Your program should take an input just like assignment #4 where you type in a chemical equation. It should then print out the same output as in assignment #4 and follow that with a solution. In this case it would print out "a=1 b=3 c=4 d=1" as the last line of output. There might be some decimal points in there as well. This example was well behaved and gave us integer results. However, our procedure doesn't gaurentee that. I'm not requiring you scale things up so they are all integers.

Speed Test Problem:

For this assignment I want you to do speed testing on the different sorts that we did. You should write the three sorts (yes, you have the in class code, but you should at least try to write them yourself first). You will make two versions of each. One will sort ints like we did in class and the other will sort large structures. The large structures will have one int and an array of 100 doubles. Sorting those will show you the difference of having time consuming copies vs. short copies.

So to get this to work you need to have some numbers to sort. To do this you will use the rand function and fill an array with random numbers. So that your tests are "even" I want you to have one array with 100,000 integers that you fill with random numbers by calling rand. Then have another array of ints and an array of your structures. Copy the ints from your first array into the other arrays and sort them. Do this once using only 100 of the numbers, then 1000, then 10000, and last the full 100000 (this last one might require dynamic memory for the structures). Use the clock command in time.h to keep track of how long the sorts take. Use man clock to look up the description. Put comments at the top of your submitted code with your results.

Some notes on this. It does not matter what values are in the doubles in the structs. You just sort by the ints. The doubles are only there to make the copies take longer. You should only have a total of 3 arrays, two of ints and one of structs. One int one is your "backup copy" so that after you sort some numbers you can restore the original sequence. The second int array is the one that you will use for sorting. While it will be 100,000 elements in size, you can easily tell the sort method to sort a smaller number of those elements, which is what you should do. You will have to copy from your backup array to the sort array before every sort. The struct array should be a dynamic array because 100,000 of those structures would take over 80MB of space and the stack won't be happy with that. A simple malloc at the beginning and free at the end will suffice. You must copy the numbers from your backup array into the int fields of the struct array before each sort of these.

If you pick this option you must also turn into me a plot of the timing results.

Graphics Problem:

One problem that existed in what you did for assignment 7/8 is that while you told it how far the triangles are from you, you didn't use that information for much of anything. Most importantly, you didn't check to see if one triangle was behind another (at least you didn't have to). Now you can fix this. I want you to add one more option to your menu. When this option is selected you should sort the triangles based on the point that is closest to the viewer (smallest z value). Do this so that when you draw the triangles you draw the ones that are furthest first. That means you want the array to start with the traingle that has the largest z value (again you are only considering the point in the triangle with smallest z-value). This way, when you draw it, things will look correct as long as the triangles don't actually intersect one another (which is a much harder problem to deal with).