Baby Mathematica:
For this problem you will use your equation parser from assignment #6 to build a little program that can be used to do some simple function evaluation. You will then give it the ability to output text files that are plots of your functions and can be plotted up using gnuplot. You should also give it the ability to read files that have functions defined in them.
You can define 3 functions: f, g, and h. They are all functions of a single variable x. They are definied in terms of numbers, x, and the other functions. You only have to have the four basic operators (+, -, *, /), but you can add extra ones if you want extra credit. If you do this, there needs to be a big comment at the top of the code telling me what you did so I can try it and give you the extra credit.
Options:
This program won't use a numeric menu. Instead, it will be more command line like, similar to what we wrote in class for the text editor. You can read in a string for the command and check the first character to see what they picked. Use the strings shown above after each option. See the sample input file for an idea of how this would work.
The define option lets the user define a function. The format for that should look something like this "define f=x*x" or "def g=f(x-1)+2". After the keyword (beginning with 'd') you have the function letter ('f', 'g', or 'h'), followed by an equals sign and the string for the function. I recommend that you store the functions in an array of 3 strings.
The evaluate option allows the user to evalutate one of the functions at a particular value. So they could type in something like "evaluate f(4)" or "eval h(5+3)". To get this to work, you will add a bit to your parse function from assignment #6. Earlier it needed three arguments, a string for the equation and two ints for start and end. You will need to add two more arguments to that. The first is a double for the value of x. The second is a 2D array of chars that holds the three strings defining f, g, and h. You need that because the functions can call other functions. The second example in this paragraph and the second one in the define paragraph might scare you a bit, but don't let them. Instead think about the power of your parse function and how you can use that to make evaluating those expressions easier.
In addition to adding the two extra arguments to parse, you will also add some extra possible cases in the function. Where you earlier just called atof, now you will need to check for 3 possibilities and all can be easily distinguished by the value of str[start] (or whatever name you use for the string argument. If it is an 'x' then you need to return the value that was passed in for x. If it begins with an f, g, or h, you need to parse the argument and then use that as the x value for a call to parse on the proper function definition string.
The view option just prints out the formulas that have been entered in case you forget them.
The read and write options are fairly straight forward. You need to write some code that will read in definitions for your three functions from a file or write out to it. In both cases, the use needs to specify a file name. For example "read forms.txt" or "w cooleqs.txt". You can choose your own format for this as long as it works for reading and writing when you don't have all of them defined. Consider that using something close to what I have asked you to do for define might be helpful because you could call a single function for define and for the read function.
The last option is to plot. You aren't going to write the graphics code, but you will write a file that has x and y values in it so that it can be plotted with gnuplot. See the description of the physics problem in assignment #4 for information on that. For this to work, they need to specify which function, a minimum x, a maximum x, and a file name. Your code should evaluate the function at 100 evenly spaced points between the min and max and write 100 lines where each has the x value followed by the y value on it. For example, they might give the command "plot f(x) 2.3 6.7 funcPlot.txt".
If you choose this option you might want to look at the strcmp and strcpy functions in string.h using the man pages or your text. You can certainly write those functions yourself, but calling those will make your code shorter.
Just as a side note, I think this might be the most exciting problem of all the ones I've given so far this year (for me). It can really show you the power of a simple recursive algorithm and once it is done, you will have written a program that is far more powerful than what most people in a PAD1 class would even dream of doing. That doesn't mean it is harder though, just more powerful.
If you want to do this option and you didn't do the symbolic algebra options on assignment #5, let me know and I can e-mail you code for it, mainly the parse function.
input file : output file : function file : plot file : plot2 file
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.
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.
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).
X11 Fractals:
This option is related to the fractal option from the previous assignment. You will still be generating a Mandelbrot fractal with the command line options, but instead of writing out a file, this version will actually open a window and display the graphic image of the fractal. Use the X11 libraries for displaying the fractal. Here's a link to help you with X11.