CS 242 Fall 2009 : Assignment 1.1

This page last changed on Sep 09, 2009 by cemeyer2.

Assignment 1.1 – Generating a neighbour grid

This is the first part of a three part assignment that will span over the course of three weeks. It is important that you complete this assignment on time because the next assignment will build on it. If you have questions, please post them on the newsgroup since there is a good chance that other people will have the same question as you. Also, look over this page frequently for Update markers with clarifications or changes to the assignment.

Update: A solution is available at https://csil-projects.cs.uiuc.edu/svn/fa09/cs242/_public/solutions/Assignment1.1/

Reading: (only if you have the book, but will be very helpful): Code Complete Chapter 6 – Working Classes

Language: C or C++

Objectives:

  1. Create a program that can read terrain maps and generate neighbour grids from them
  2. learn or refresh your knowledge of IO

Goal: Read an ASCII input file and generate an output file representing a neighbour grid

As you will notice in this assignment and the ones that follow, they are indeed different ways for doing each one. This assignment does not list everything that you need to do to accomplish the task. When we do not specify a particular way of doing things, you can always do it in whatever way you see fit. We will ask for your justifications when you present your code in class. This is different from a regular machine problem where you have to follow rigid rules to facilitate grading.

Your program will read in input file such as (click here to download):

or

and generate an output file representing a neighbour grid. The format of the input file is as follows:

row_count
column_count
data

The row_count and column_count will both be positive integers, while the data will be a series of line with one line for each row and one character per line for each column. The data characters may be any of the following:

Character Terrain Type
g grass
d desert
j jungle
p plains
s swamps
r roads
w water
h hotrocks
f forest
m mountains
i ice

For this part of the assignment, we don’t care what each cell of the data portion of the map is, only its relation to its neighbours. Once you read in the input file, your program should generate an output file that has one byte per cell of data in the input file, which each bit of each byte representing that cell’s relation to its neighbours:

Bit 7 Bit 6 Bit 5 Bit 4 Bit 3 Bit 2 Bit 1 Bit 0
West South West South South East East North East North North West

A 1 for a particular bit signifies that that cell has a neighbour that is different from it, a 0 signifies that that is the same type of cell. So, for the second input file shown above, the grass element in the middle of hte map would have the 8 bits be 11011010.

A graphical representation of how the cells relate to each other for the second given map is as follows:

Update: You can download what one implementation of this assignment would generate for the given input file here.

In summary, here is what you have to do:

  1. read the input file into memory
  2. for each cell you read in, generate an 8 bit number that describes its relationship to its neighbours. Use a data type in your language of choice that is 8 bits. Unsigned char in C or byte in java work well. Do not write actual 1s and 0s as ASCII to your output file
  3. the collection of 8 bit numbers should be written out to disk in the same format as the input, with a line containing the number of rows, a line containing the number of columns, and then one line per row containing one 8 bit number per cell.

Update: For extra credit, have your program create a visualization of the neighbour grid in a similar fashion to the one above, for an example of a larger version, click here.

Recommendations:

  1. Modularize your code as much as possible. A sample decomposition is shown below.
  2. try to use the principle of information hiding, that is, make each module’s data structures only visible to that module, and have each module expose an interface to access its data
  3. do not put all of your code in one long main method
  4. comment your code so it is clear and easy to understand

Update: Here is a sample decomposition for your program:

input module (one class):

processor module (one class):

output module (one class):

and a controller module to coordinate all of the other modules together. Using this decomposition, none of the data structures are exposed outside of the modules in which they reside and any changes made would be local to that module.

Things to watch out for:

  1. What do you do when you reach the edge of a map? Should of have 0s or 1s for the edge neighbours of a cell?
  2. How do you handle invalid data (if the number of rows and columns don’t match what the file said they should be)?
  3. What if we changed the input format, how much work would need to be done to your code to accommidate the change? Try to make your program as flexible as possible.
  4. What if we changed the output format?
  5. How does your program scale to very large inputs? Hint: write a simple program that generates maps and test your code on a variety of sizes.

Update: This assignment is due by Wednesday, September 2nd at 8am in subversion at https://csil-projects.cs.uiuc.edu/svn/fa09/cs242/<netid>/Assignment1.1

Grading

Note: As is usual for CS242, only about 1/2 of the points will be given for having a program that accomplishes the given task. The rest will be for the style of your code and your participation in discussion section. That being said, you should still focus on completing all of the tasks you are given, but be aware that if you do not create good code, you will be heavily penalized.

Total 50 Points

visualization.txt (text/plain)

given.out (application/octet-stream)

given.in (application/octet-stream)
Document generated by Confluence on Feb 22, 2012 18:18

  1. No comments yet.

  1. No trackbacks yet.