CSE142

Homework #1

Circles in the Wheat

Electronic turn-in due: Sunday, April 8, 10:00pm

The task  CARR input format  Algorithm details  Supplied code and files  Your write-up  Guidelines, hints and help  Submission  Extras  Announcements

The year is 2153. You are the Computer Officer aboard the deep space ship Lead Zeppelin. You were sent on your mission one hundred and uh.. hm.. some-odd years ago (you're not so good at math in your head). Anyway, you were sent in 2038. Now, your ship has reached Alpha Centauri and found sentient life around the fourth planet! Following standard procedure, your captain intends to initiate communication with the newly discovered race by creating "crop circles" on the planet.  The mobile robot, CARR (Crop Ablation Remote Robot) will be sent down to land in a field where a crop of wheat is growing.  By remote control, CARR will move about, creating giant circles that the inhabitants are sure to notice (if they have any intelligence).  The CARR robot has a rather arcane interface.  Since the Captain doesn't understand robotics, you have been assigned the task of computing the numbers which will instruct CARR how to move once it has landed.  It's tricky and has to be done right.  Are you up to the challenge?

The Task

The CARR robot responds to a series of numbers ("commands"), and using this information it knows how to move.  As you'll see, the commands are not perfectly direct -- but they are the only thing which the robot understands.  

Your job: write a program which calculates the correct commands to give to CARR.  

The Captain has ordered that there will be two circles; their size and how many times they are retraced should  depend upon the total population of the planet (more details about this later).  The CARR robot should draw the circles as fast as it can.  Thus, your program will need to first find out the population and the maximum safe robot speed.  Then the program can make the calculations and issue the series of 3-number commands that CARR needs to follow.

CARR Input Format

1. speed (meters per second); this is linear motion, and is always positive; 0.0 means that the robot is not moving
2. rotational speed (rotations per second); a positive value means counterclockwise, and a negative value means clockwise; a value of 0.0 means the that robot moves in a straight line. 
3. time (seconds); this is the amount of time for which the robot should carry out the activity. 

For example:

  2.5 1.0 10

CARR reads one series of numbers per line of input. Given a set of three numbers, CARR will proceed forward at the given speed with the given rotational speed for the given period of time. CARR will cease processing a set of input when it reads a line with zero for all of speed, rotational speed, and time¹.

As an example, the following will make CARR draw a counterclockwise circle of perimeter 10 meters in 20 seconds, then draw two clockwise circles of the same perimeter but take 50 seconds (total). Finally, CARR would stop and await the next command file. Note that CARR is redrawing a circle on the second line (re-tamping the crops helps make the circles more obvious).

  0.5 0.05 20
  0.4 -0.04 50
  0  0  0

We calculated speed by finding the distance to travel (perimeter times number of circles) divided by the time to complete the action. The rotational speed is even simpler; it's just the number of circles divided by the time. Your calculations will differ slightly from these because you have different given values.

And of course, the program that you write will only generate a short sequence of commands (five, to be precise).  Generating a whole list of CARR commands would be useful, but we don't have the programming knowledge yet to do that.  Such a list could be considered a "file".  You can consider your program as one which generates a file for CARR.  Viewing it in that light, here is a picture of the process:

You are expected to design a program that will produce your CARR file, which includes a set of CARR commands,  given the appropriate specifications.

Algorithm details

Here are your instructions as they were transcribed from your boss's last e-mail from Earth:

For the last time you mathematically challenged ape²! First, measure the population of the planet. Then, query the robot for its maximum safe speed after transit. Now, going as fast as the robot can without exceeding 3/4 of maximum speed:

1. First, you'll make counterclockwise circles. Make one complete circle for every 25,000 "people" (or equivalent alien thingies) plus one extra. Make the perimeter of each circle equal to one plus the cube root of the total population³. Note that you are not to make any partial circles! Any leftover people will be accounted for in the next two steps.
2. Now, make clockwise circles of the same perimeter. You should make one of these circles for every 8,000 leftover people plus one extra circle. Again, make no partial circles!
3. Next, drive straight forward for an amount of time (in seconds) equal to exactly 0.1% of the leftover population. This may mean driving for a non-integral period of time.
4. Finally, do something to eat up another 20 seconds. You can perform any valid command (or any series of valid commands) you wish as long as you neither emit the "0 0 0" command during this time nor exceed 3/4 of maximum speed.
5. Stop the robot (with the "0 0 0" command).

You should be able to perform these five steps with one CARR command each. Indeed, we require that you perform all but the fourth with exactly one command. Moreover, even should your bioengineered super-primate brain contain knowledge of advanced programming constructs such as loops or conditionals, you are not to use these constructs for this assignment!

Supplied Code and Files

• hw1viz.exe executable
• example output from the sample solution
• fun mac related robot commands (rename robot.txt to use)
• neat picture with robot commands (rename robot.txt to use)

Oh, right, here's that sample code. This is basically just a small starter for your project which includes the input statements and a sample output statement. Get it as a self-extracting archive or just the starter .c file (only use this if you are not working on Windows).

To help you out with this program, we have provided a sample executable; use this as a reference, not as an alternative to the specification! It's only meant to help you debug. We will not provide sample executables on every future assignment! So, don't rely on it too much.

Guidelines, Hints, and Help

Coding style (following The Way) is vitally important for this assignment and all others. We will generally grade your code for three things: functionality (does it work?), style (is it readable, maintainable, and changeable?), and robustness (does it work well?). So, style will factor in heavily. Moreover, if your code does not work perfectly or is not perfectly robust, you will lose fewer points if we can understand the problem's cause... and good style will help us to read your code enormously. Finally, we might change our minds about the values of some of the constants in this assignment (e.g., the 3/4 safety factor on the speed or the 25,000 person blocks for circles). What does this mean in terms of style? You should ensure that any constants you use are defined in a flexible manner as symbolic constants!

The following advice should help greatly with your work. None of this is hard and fast rules, but they're handy tips.

• Start early. Despite the fact that it improves your life immensely, so many people ignore this advice. It always pays to get an early start.
• Read these instructions completely and carefully.
• Answer the pre-project questions before you start.
• Try running the sample executable with various input values.
• Before writing a single line of code, plan your solution on paper. Try thinking about what you would do to perform the computations yourself.
• Develop and test the program a bit at a time. Don't try to write the whole program and test it all at once. Instead, try getting a small part working (say, reading in the speed and population or calculating the number of circles for one of the directions). Then, test and add more pieces bit by bit until the whole job is done.
• Experiment with the MSVC debugger and printf statements to help you debug the project. Until your code is working, print every value of interest with a brief label. To help you sort these out in the output, you can preface debugging lines by printing something like a '#' character.
• Before turning in your work, test it thoroughly, comparing results with the sample executable. (But, keep in mind that you need not support negative or zero speeds.)
• When it comes to grading, there's nothing better than a happy TA. Make your TA a happy TA: Your code should be neat and readable, with sensible variable names.
• Start right now!
• No, really, start right this instant!

Your Writeup

• Your name
• Your student ID
• Your section
• Approximately how many hours you spent on the assignment
• Acknowledgment of any help you received on the assignment from any source other than the lectures/sections, the staff, or the course textbook. (Note that acknowledging activities which constitute cheating does not stop them from being cheating!)

Pre-project:

• What are the quantities you need to calculate? Which of them should be double values and which should be int values?
• Write out mathematical equations to calculate the important quantities. Don't try to make the equations look like C code; just use whatever mathematical notation comes most naturally.
• How can you make it so you can test each of the five parts separately?
• What are three sets of test input that will help to check if your code is working?

Post-project:

• What would happen if you entered a maximum safe speed of zero into your program? What do you think should happen in the program with a maximum safe speed of zero? What does this problem have to do with the requirement to make one extra circle in each of steps one and two and the "one plus" part of the perimeter? (Note that for this project you need only support positive, non-zero maximum safe speeds.)
• Are there any other bugs in your program or in the sample executable?
• What did you do for the fourth part (to eat up time)? Briefly describe what your robot does with the time.
• Imagine you were responsible for writing the code to run the robot based on CARR input files. What problems would you face given only the programming tools we've learned so far?
• What's the most insightful or interesting question you thought of, asked, or heard asked about this assignment? If it was a question you heard, make sure you attribute the source (e.g., "newsgroup post by wolf" or "personal communication with Martin Dickey")! Explain briefly why this was such a good question and what you think the (an?) answer is⁵.
• What did you enjoy about this assignment? What did you hate? Could we have done anything to make it better (either the assignment itself or the way we handled handing it out, clarifying it, or turnin procedure)?

• You know that part where you just have to eat up time for 20 seconds? Draw something cool during that! If you want to see your results on the robot, however, don't exceed 0.5 rotations per second! If you want in on the competition, you will have to submit your code on time, working correctly, with these enhancements in place.
• Do you know why entering a speed of zero is a problem? Well, see if you can fix it. Make it so your program either recognizes the difficulty and stops or fixes it and keeps going. You should not turn in this enhancement, however!
• Write a program to just go crazy drawing cool stuff. No constraints here.. it's just for your fun. Don't turn this in. We might be able to supply something soon to make this more fun. Keep your eyes peeled.

1. Perhaps CARR is bored by such a banal set of commands? The world may never know.
2. Did we mention that you were a genetically engineered super ape? You don't think they'd send a human on this incredibly dangerous (and -- for the first one hundred and um... something years -- boring) mission, do you?.
3. The cube root of a number x is x raised to the power of 1/3 (looks like x^1/3 if superscripts work on your browser). To calculate an exponent in C, use the pow function, which is of the form pow(<base>, <exponent>), where <base> and <exponent> are variables or constants. So, to find the cube root of the variable someValue and store it in the variable someResult, use the expression:

   someResult = pow(someValue, 1.0 / 3.0)

   The supplied code uses the command #include <math.h> to obtain access to the math library which includes pow.
4. Like the rest of your code, however. The debug_printf statements should be well written and make sense. In other words, don't write:

     debug_printf("# %d\n", number_of_circles);
   

   Write this instead:

     debug_printf("# Number of circles: %d\n", number_of_circles);
   

5. "Does my question have to be about the code?" Not necessarily! It could be about the lab setup or the cheating regulations or anything related to the assignment. "Does it have to be unique?" As long as you cite your source, the question needn't be unique, but the answer and explanation should be your own thought and words.