By the time you will turn this in you will have developed the ability to work with files and to use case classes to combine associated data elements into a single object. We are now getting to the point where you don't want to just start coding. You want to start by sitting down and thinking about what your code needs to do and how you are going to make it do it, paper and pen might even be helpful for this. I can almost promise that every minute spent really thinking about what you are going to be doing will save you at least 2 minutes of coding/recoding/debugging.
When you work on breaking your problem down into pieces, look for pieces that are reusable. If you find yourself writing the same code three or more times, that probably means that it should be put into a function. In addition, don't write functions that are so specific to the assignment you could never reuse them if there is an alternate function you could write that would be reusable. A specific function could call the reusable one. Also try to think of ways that you might make the functions more general, perhaps by passing in function arguments to them.
After each problem description I've given you sample input and output files. If you run the program and pipe in the input I give, you should get something pretty much identical to my output. I've told you for each one if you want to be piping data in or not. For example, the first one is a menu based application and you will probably want to be typing things in at the keyboard there, but piping data in could be helpful for some things.
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.
Standard Problem:
Mathematicians and computer scientists alike seem to have a certain fascination with prime numbers. They are a very vital component of the study of number theory. Interestingly, mathematicians studied number theory for centuries and many of them studied it in large part because it was completely unusable for anything productive. It was a fun intellectual pursuit and nothing more. That was before computers and cryptography, which have moved number theory into the lime light. We aren't going to get into any heavy number theory, but we should look at how we can play some games with numbers.
The program you are going to write is a menu based program that "plays" with numbers. The options on the menu are the following:
If they select 1 then the user enters a new number for the program to work with. It should start off as 2. If the number is <2 you should print a message saying it must be at least two and set it equal to 2. Keep in mind that n%10 will always give you the value of the ones digit of a number. Also, n/10 will give you a number where the ones digit has been removed. You will be working with integer types for this. Making the character string representation could be helpful for options 2, and 3.
For 4 you will go through a loop to see if the number is prime. You can look at the test answers for code that will do this if you have a hard time with it. Options 5 and 6 should give the same output, but get it in different ways. In 5 you will count from 2 up to the number and just print out all the ones that are prime using the function you wrote to check if a number is prime. For 6 you will improve on this. With a little thinking, you can see that given a number n, you don't have to check if n is divisible by every number less than n, or even every number less than or equal to sqrt(n). What you need to do is check against the prime numbers less than or equal to sqrt(n). So to speed things up you will keep a list of numbers that stores primes in it and when you check if each number is prime, you only divide by the primes before it. You might want to write an isPrime2 function that takes not only the number to check, but also a list of known primes less than it and the number of primes in that array. For option 7, just print the prime factorization of a number, so if the number is 588 you print 2*2*3*7*7.
This is not a program where you will typically want to be piping things in and out. Do play with it a bit and make sure that it works for different inputs the way that it should for all the options in it.
Physics Problem:
Now that you have arrays, you can do a bit more with the Keplerian simulator that some of you wrote in assignment #3. In that program all you had was one body in motion about a "central mass" that wasn't really moving at all. Now you can store and work with the positions and velocities of many bodies because you can store their component data in arrays or classes. That is to say you can have an array for x positions as well as y, vx and vy, or an array of some class that stores those values. This allows you to simulate the motions of many particles at the same time which is much more fun. Earlier you only had to calculate the acceleration due to the central particle. Now you want to calculate accelerations due to all interactions between all the particles. We can also make the central particle one of the particles in our array. (If we were doing galactic dynamics we wouldn't have a central body, but that's a different issue all together.)
With multiple particles, we need to have a nested loop (or a for loop with two generators) that calculates the accelerations on each particle from all the others and adds them all up. Keep in mind that if particle i pulls on particle j then particle j pulls back on i just as hard, but in the opposite direction. That doesn't mean the accelerations are the same though. The acceleration is proportional to the mass of the puller because the mass of the pullee is canceled out by its inertia. Earlier we had ax=-x/(r*r*r) and ay=-y/(r*r*r). When the particle doing the pulling isn't at the origin, r is the distance between the particles and x and y are the distances between them in x and y directions. We also need a factor of m for the mass of the puller. You want to add up the accelerations from all other particles on each one and store that into arrays so
ax(i)=sum(-(x(j)-x(i))*m(j)/(r*r*r))
There is a similar formula for y and note that I'm being a bit sloppy with the r's which need to be recalculated for every i,j pair. When you write your formula in the code, think a bit about it. This formula causes a problem if we really use r because particles can get too close to one another. I suggest you make r=sqrt(dx*dx+dy*dy)+something small. You can play with how small you want it to be because that depends on the scale of your problem. I also recommend that you have your integrator not use the normal Euler method which calculates accelerations, then updates positions, then velocities. Make sure that after it does the accelerations it does velocities before the positions. Keep in mind that you want to break this up into functions that fit together nicely and are helpful. It will hurt your brain more if you don't.
The input for the program will have a first line that is the number of bodies, timestep, stopping time, and the number of steps between outputs. This will be followed by lines with the x, y, vx, vy, and mass values for each particle. See the link below for an example. Note that the central mass has a mass of 1 and all the others are much smaller.
As output, I want you to write out the positions of all the particles in your simulation to a file once for every n steps where n is a value given on the first line of the input. In fact, there is a handy program you can look at it with called gnuplot. If you then you can run gnuplot and give it the command plot 'output' and it will make a little scatter plot showing you the paths of a particle in the simulation. Slightly different commands can be used to plot the others. You could also pull down my plotting package called SwiftVis and use that.
Graphics Problem:
When we draw graphics on computers, the most standard way of doing it is with what are called raster graphics. In this style of graphics, images are made of many rows and columns of "pixels". Depending on the type of display a pixel might be just on or off, or it could have a shade, or even color to it. Computer screens are raster type displays, as are most of the images that we work with (gif, jpg, and png formats are for raster type images). It is also possible to have vector images, but we aren't going to worry about those in this class. For this assignment I want you to write some functions that will basically implement a simple raster display. What you write here should be helpful in later assignments as we try to put more things together to build a little graphics package.
It should be noted that raster displays typically use a slightly different coordinate system than what is used in math. The x-axis still runs across, getting larger as you move right, but the y-axis runs down the screen. So the (0,0) location on screen is the top-left most pixel.
You will represent the raster as a 2-D arrays of integers. Each element of this array will represent a color in red, green, and blue that has been packed into the int. The lowest byte is the blue, the next one is green, and the third is red. For now we won't use the top byte for anything and it should always be zero. You will write two functions to pack colors into one int and to take them out. These functions will use bit-shifting to help you. I want you to think a bit about how to do this, but don't hesitate to ask me if you start to get hung on it.
Use some vals at the top of your code to tell the program how big the raster width and height is. For this assignment you should use values of 80 for both. Include the following functions in your code.
def packColor(red:Int,green:Int,blue:Int):Int - This function returns an Int with the red, green, and blue values packed into it. This should do some checking to make sure that the values fit in the one byte that are supposed to. That means they have to be between 0 and 255. If they aren't you should force them to be so.
def unpackColor(int rgb):(Int,Int,Int) - This function breaks a single Int RGB value into the three components and returns them as a tuple.
def drawPixel(raster:Array[Array[Int]],x:Int,y:Int,rgb:Int) - Sets the value of the pixel at x,y to be this rgb value.
def fillRectangle(raster:Array[Array[Int]],x1:Int,y1:Int,x2:Int, y2:Int,rgb:Int) - Sets all the pixels in the region bound by (x1,y1) and (x2,y2) to the given rgb value. Check to make sure they aren't trying to draw outside your raster, but draw what fits in the raster.
def fillCircle(raster:Array[Array[Int]],x:Int,y:Int,r:Int,rgb:Int) - Sets all the pixels in the region around (x,y) with radius r to the given rgb value. You get to think a bit about how to get this to happen. Efficiency is nice, but not required. Check to make sure they aren't trying to draw outside your raster, but draw what fits in the raster.
def simplePrintRaster(raster:Array[Array[Int]]) - This function prints out a very simple representation of the image in the raster. It prints each row of the raster to screen, one pixel at a time. If the pixel has a value of 0 (black) it prints a space. Otherwise it prints a '#'. Obviously this doesn't give you any sense of color, but you can see the geometry quickly.
void printRaster(raster:Array[Array[Int]],filename:String) - This will print something to a file that you can read in with the JAR file linked to below. The file should have the width and height on the first line, then a series of 6 characters for each pixel with white space between the pixels. The 6 characters are hex values for red, green, and blue much like what is used on web pages to represent colors. For example, if a pixel is black this will print 000000 for that pixel. If it is white it will print ffffff. If it is pure red you get ff0000, etc. All of this should be written to a file of the specified name.
For the main functionality of this program you will write a menu driven application that gives the user the following options:
When they choose one of the first three, you need to prompt the user for values related to the inputs of that function. Being a menu driven program, you won't normally want the operation to be done through piping in files, but you can do that to speed things up when you are debugging it.
input : output : raster file
JAR file - You will need to specify the RGB option for the format of file you are outputting here.
Chemistry Problem:
For this problem you will do some string parsing that has relationships to chemical formulas in chemistry. We are going to keep things fairly simple for this. The basic idea is that the user types in a string that is a chemical formula, and your program should parse that string and tell how many of each type of element are on each side of the equation. This is the first step in balancing a chemical equation. A later assignment should have you go through the process of doing the actual balancing.
The format of the chemical equation will look something like this: CH4+O2=H2O+CO2. This is a reaction for burning/oxidizing methane. Note that it isn't well balanced because there need to be coefficients in front of each term. Your program will assume a coefficient on each term in the equation as a lower case letter starting with 'a' in alphabetical order from left to right and output how many of each element there are. So for this input the output would be:
C: a*1=d*1
H: a*4=c*2
O: b*2=c*1+d*2
or if you want to clean it up a bit,
C: a=d
H: a*4=c*2
O: b*2=c+d*2
This gives us three linear equations that we could try to solve (actually we have 3 equations for 4 unknowns so the system is underconstrained, but that is often the case so we find the solution where a, b, c, and d have the smallest values possible and are all integers but you don't have to worry about that now). We won't be solving it in this assignment.
So to be more specific about the input, the input has a sequence of terms that are separated by + or =. Are the reagents are in terms on the left hand side of the = and the products are on the right hand side of the =. Each term can have one or more element names, each followed by the number of that element in the given molecule. The element names will all be 1 or 2 characters long and the first will always be capitalized and the second letter always lowercase. Also, the number of elements will be just one digit. If no number is present you assume there is only one. Allowing more is extra credit and you should have a big comment saying you can do this if you support it.
The output should have a separate line for each element that was present in the equation. It should list the symbol for the element followed by a colon and then the equation that tells what the coefficients have to satisfy for that element to be balanced on both sides of the equation. You can choose either format above.
For extra credit, make it so that you can deal with formulas that have numbers with more than one digit. This actually isn't too hard.
Map Traversal:
This is the first installment for you building your own text adventure. Your program will read in from a map file that you will write by hand and let the user run around in that map by using commands like "north" to move from one room to another. The map file will have a fairly simple format right now and you will create your own map file using vi. Make sure when you submit this program you turn in both the .c file and the map file so I can walk through your map.
The format of the map file should start with a line telling you the number of rooms then have something like the following. You can change this some if you want to use a slightly different format:
room_number room_name
long line of room description
number_of_links
direction1 destination1
direction2 destination2
...
This is repeated over an over. (The number of rooms at the top is helpful for storing things in an Array.) Each room should have a unique room number and it should start at 0. The reason is that you will be putting all the room information into arrays. I'm providing a sample map file below, but you don't have to stick perfectly to that format if you don't want to. You might deviate if you are thinking about other options you will add in later. Odds are good you will be refactoring your code later.
The interface for your program is quite simple. When you run the program it should read in the map file and keep all the map information stored in various collections. You will start the user in room 0 and print the description of that room and the different directions they can go as well as where they lead to, then follow that with a prompt. You could just use ">" as the prompt to start with. It might get more complex later on when you have real game functionality. So when the user starts the game it might look something like this if you read in the sample map file.
Halsell 228
You are standing in a room full of computers and comfy chairs with a giant air conditioning unit hanging from the ceiling. While the surroundings are serine enough, you can't help feeling a certain amount of dread. This isn't just a fear that the air conditioning unit is going to fall either. Something in you tells you that this room is regularly used for strange rituals involving torture. You can only wonder what happens here and why there isn't blood all over the place. Your uneasyness makes you want to leave quickly.
The hallway is east.
>
The user must type in either a direction to move or "quit". If anything else is entered you should print an appropriate error message.