CSCI 1320 - Assignment #4


Before this is due, we will have expanded your abilities so that you can make extensive use of arrays in your code. Pick one of the options below to complete. 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 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.

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:

  1. Enter new number
  2. Print number reversed
  3. Check if number is a palindrome
  4. Check if number is prime
  5. Print all primes up to number (slow)
  6. Print all primes up to number (fast)
  7. Print the prime factorization of the number
  8. Quit

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. At this time you should also create a string that stores the string representation of that number. There are a few ways to do this, but I'd rather you write your own code for it. When trying to do that 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 will 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 for 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 large array 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 an array 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.

input : output

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. That is to say you can have an array for x positions as well as y, vx and vy. 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 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. Don't make one huge main for this. It will hurt your brain more that way.

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 print out the positions of all the particles in your simulation once for every n steps where n is a value given on the first line of the input. This could be quite a bit of output, but you should pipe it out to a file so that you can look at it. In fact, there is a handy program you can look at it with called gnuplot. If you run your program with a line like this "a.out < input > output" 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.

input : output

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 #defines 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 function in your code.

int packColor(int red,int green,int blue); 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.

void unpackColor(int rgb, int *red,int *green,int *blue); This function breaks a single int RGB value into the three components.

void drawPixel(int raster[][HEIGHT],int x,int y,int rgb); Sets the value of the pixel at x,y to be this rgb value.

void fillRectangle(int raster[][HEIGHT],int x1,int y1,int x2,int y2,int rgb); 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.

void fillcircle(int raster[][HEIGHT],int x,int y,int r,int rgb); 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.

void simplePrintRaster(int raster[][HEIGHT]); 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(int raster[][HEIGHT],char *filename); This will print something to a file that you can read in with the JAR file linked to below. It's similar to the one you used for assignment #3 if you did the graphics option. As with assignment 3, it should first print the width and height on a line, then print 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:

  1. Draw Pixel
  2. Fill Rectangle
  3. Fill Circle
  4. Simple Print Raster
  5. Print Display Raster
  6. Quit

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.

The input equation will not be more than 1000 characters long, it will not involve more than 200 terms or have more than 100 elements in it. These values are important for picking the size of static arrays.

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, you can use the atoi function that is in stdlib.h to help make it even easier.

input : output