Symbolic Algebra:
For this option, you will write a program that recursively parses a string for an arithmetic expression and returns the value of it. Examples would be 5+7 or 9*(5+7.5)/2. Your parser should do proper order of operations (things in parentheses bind highest, * and / before + and -, and go from left to right for the same level of priority).
The approach I want you to take for solving this problem is with a recursive algorithm that breaks the problem into pieces starting with the lowest priority operation. You will write a function parse(exp:String):Double. This function will return the value of the expression in the string exp. First it should find the lowest priority operator (it can't be in parentheses). If it finds one it recurses twice with the substrings on either side of that operator (use the substring method of String). If there isn't an operator that isn't in paretheses you can check if the string starts with '(' and pull the bounding parentheses off and recurse on what is left. If it doesn't start with '(' you know that part of the expression is just a number so use toDouble to get the value.
The user will give you a formula, that doesn't include any spaces, at the command line and you should simply print the value it evaluates to. So a potential invocation of your program might be as follows: "scala parser.scala 5+3*(70/5)". I'm not providing a sample output file because this would simply output 47.
This assignment will lead into another option in the last assignment.
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. It will do this through a recursive function.
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.
For extra credit, make it so your program has a GUI. It should load puzzles from file and use a Table to display the puzzle. They should be able to select a solve option to have other spaces filled in.
difficult input : difficult output
Text Adventure Items/XML:
This assignment is of most interest to you if you did the map assignment earlier. For this one I want you to convert your file to XML format and add in items. 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 can include an item tag in the room.
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 print 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 from an earlier assignment 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 that way 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 the earlier assignment where you type in a chemical equation. It should then print out the same output as in that assignment 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.
L-System Fractals (The Algorithmic Beauty of Plants):
L-systems are an interesting type of formal grammar originally developed by Aristid Lindenmayer to describe how plants grow. They can produce realistic looking grasses and trees. They also produce physiologically accurate fungi and can be used to generate certain types of fractals. This assignment will stretch into the last assignment in a way that will have you develop a program that can let the user edit and visualize these systems. For cool graphics on L-systems, go to AlgorithmicBotany.org.
For this first assignment you will work on basic generation capabilities and the graphical interpretation. You should write a program that will allow the user to evolve and visualize one L-system that is hard coded into the program. You can begin with any of the grammars from page 25 of "The Algorithmic Beauty of Plants". What I really care about is that you use a grammar that includes brackets as that will give you a reason to use recursion. You need to have a GUI that has a panel that shows the turtle interpretation of the string as well as a button that will advance the string to the next generation and refresh the drawing when the user clicks it.
If you pick this option, you will probably want to pick the follow-on in the last assignment. For that one, you will be adding menu options that allow the user to edit and save grammars so that they can play around with L-systems.