CS61C 2010Sp Performance Competition: Bits on Ice

Dan Garcia, 2010-04-27. Last updated 2010-05-06 @ 02:00.

Updates

Background

Bits on IceWhen we're not looking, the ON bits in our bitmap images play a fun game (ala Toy Story toys coming to life). Imagine that all the OFF bits form a frictionless plane of ice. One ON bit at a time, that ON bit first picks a direction (North, South, West, or East) and then slides as far as it can over OFF bits until it hits another ON bit, at which point it stops. The ON bit it hits is unaffected. This continues until the bits are tired of the game, or there are no more moves to make. The same bit could move many times in a row if it would like, or other bits can decide they want to move. No bit is allowed to slide off the screen. As is standard with images, we label each slot <x> <y> with (0,0) in the upper-left corner (which might be initially confusing, since increasing y moves "down"), and shorten the compass direction names to their capitalized first letter (N,S,W, or E). The example below will hopefully help clarify things.

Example

In the following examples, we will use multiple equivalent representations for OFF and ON states:

State OFF ON
Pixel color white black
Value 0 1
Graphic empty filled

If we begin with the start bitmap below, with four ON bits, as in Figure 1 below:

0 1 2 3 4
 0  1 1
1 1
2 1
Figure 1. The start bitmap, start.pbm

There are only two available moves. The bit on (0,0) could move East, or the bit on (3,0) could move West. There's no other directions these bits could move (or any other bits for that matter) because the bits would slide off. After move "3 0 W", in which the right bit on the top row slides as far as it can to the West, we get the board below:

0 1 2 3 4
 0  1 1
1 1
2 1
Figure 2. The bitmap after the bit at position (3, 0) moved West.

There are only two moves from Figure 2: (1,0) could move South, or (1,2) could move North. The bit on the bottom wants to get into the action and slides up, which is denoted by "1 2 N"

0 1 2 3 4
 0  1 1
1 1 1
2
Figure 3. The end bitmap, end.pbm

Then the bits become bored and decide to stop the game, even though there are still moves available.

The Challenge

For this project, you'll write a C program ice to be run on the lab Macs that takes the filenames of two bitmap images (start and end) on the command line, and prints to STDOUT (typically via printf) a sequence of these moves (one on each line) that the ON bits on start would take so that the image looked like end, or declare that it was impossible to get from start to end, by printing IMPOSSIBLE. Here is an example of interaction with the computer (you type the text shown in bold):

lab_computer% ./ice start.pbm end.pbm
3 0 W
1 2 N
lab_computer% ./ice end.pbm start.pbm
IMPOSSIBLE 
lab_computer%
Figure 4. Example interaction with ice ; there's no way to get from end.pbm to start.pbm, so ice prints out IMPOSSIBLE.

Your ice C program can call other programs (you wrote) running on other lab machines to help it if you wish. The bottom line is your program should be as fast as possible and always return a correct answer. We say "a" correct answer, because there may be other solutions, possibly involving fewer moves -- but we don't care how many moves it takes, just as long as your moves are correct and take the start image to the end image. We will devise lots of interesting test cases, for images of varying sizes, and your program should handle all of these gracefully, quickly, and correctly.

Fortunately, we've provided a vanilla PBM reader, ice.c, that you're welcome to use as a starting point. Feel free to use it, rewrite-and-optimize it or ignore it. Our PBM parser will choke if you have extra spaces at the end of lines (instead of just a newline), so watch out for that if you're authoring your own PBM test files.

Error Handling

Don't worry about input error handling. You may assume you're always given two filename arguments to files that are valid, identically-sized, readable, PBM files. Spend your time optimizing your code for speed, not worry about annoying PBM parse errors.

Portable Bitmap Format

An image in Portable Bitmap Format (PBM) is a text file where each line (after the first line) is a row of the image as a string of "0"s and "1"s separated by a space (but no space at the end of a line). The man page says whitespace between bits is ignored, but the parser we gave to everyone in ice.c assumes a space, so let's stay with that. The first line indicates the format and size of the image in the form "P1 width height". So, for example, the 5-pixel-by-3-pixel image in Figure 1 would be represented by a text file like this:

P1 5 3
1 0 0 1 0
0 0 0 0 1
0 1 0 0 0

Python GUI

iceGUI screenshot
Figure 5. Screenshot of the Python GUI

We've authored a Python GUI for you. Just download (or copy) the file iceGUI.py, type chmod 755 iceGUI.py and run it as shown below. The GUI takes three arguments: two bitmap images (start and end), and the size (in pixels) of one "bit". Hopefully it's intuitive to use -- it displays red (or green, depending on whether the bit is over an 'end' bit location) arrows for all the available moves, blue movable start bit circles, and fixed black end bit squares. Click on an arrow to make a move -- you'll notice the GUI spits out the move to STDOUT and keeps track of the total steps, and updates the arrows accordingly. If you run out of moves or solve the puzzle, the GUI says so in its status window. Have fun creating neat puzzles for each other; feel free to share them on the newsgroup!

lab_computer% ./iceGUI.py start61C.pbm end61C.pbm 50
3 2 E
2 2 E
3 0 E
4 2 N
1 2 E
4 4 E
3 4 E
14 4 E
14 0 E
13 0 E
13 4 E
8 4 E
7 4 E
10 1 S
10 0 S 
lab_computer%
Figure 6. Example interaction with iceGUI.py ; it prints out the moves you make. If you're stuck (no moves left), the GUI displays STUCK! in its status window. If you've solved it, it displays SOLVED! in its status window.

Files provided to you

The following files are in the code subdirectory:

Submission

Submit your solution by creating a directory named ice that contains all the files you need. We should be able to type make from that directory and run ./ice, just like in the example above. Include a README.txt file that lists your partner and anything else we need to know about your submission.