next up previous
Next: Project3: Where's My Bus? Up: W4444 Programming and Problem Previous: Project1: The Poker Market

Project2: Picture This

You start with an empty (black) square canvas, and your job is to paint it. You have all colors available, generated as combinations of red, green, blue: A color is an (r,g,b) triple where each value is between 0 and 255. Unfortunately, you have no paintbrushes. No spray cans. Not even Photoshop. What you do have is an automaton.

Your artistic mission is to generate ``beautiful'' pictures with as simple an automaton as possible. Simplicity of an automaton will be measured by the size of the automaton's code. The beauty of an image will be decided during a beauty contest, in which a panel of ordinary people chosen by the instructor will be asked to rate the images. In addition to ``beauty'' we will have other categories such as ``originality,'' ``geometricality,'' ``cute traversal,'' etc. Each group can make multiple submissions.

An automaton has access to the state of the pixel on which it sits. A pixel contains four 8-bit values. The first three are (r,g,b) values for the pixel. The fourth, which we'll call c, is a ``control'' value that can be used by the automaton to store some data about the pixel that doesn't show up in the image. All values for all pixels are initially zero. Collectively, we'll call the 32-bit (r,g,b,c) value the pixel-word, or $p$ for short. When the automaton moves, it loses access to the old $p$ value, and gets access to the $p$ value for the new pixel.

An automaton also has access to an 8-bit random number, uniformly generated between 0 and 255. This number will be called $n$. A new number is generated after each ``move'' (to be defined below). The automaton can keep four local 8-bit values in its state. Unless explicitly updated, these values remain unchanged when the automaton moves. For convenience, we'll also call the four values (r,g,b,c) and collectively we'll call this 32-bit state $w$.

The automaton's code is a sequence of statements of the form

if (condition) then (assignment)$*$ : (movement) ;

The sequence is scanned until some condition matches, at which time the corresponding assignment and movement operations are executed. Only the first matching statement is executed. Note the ``$*$'' in the specification above: zero or more assignments, each enclosed in parentheses, are allowed.

Scanning the instructions and executing the first matching instruction is called a ``move''. The random number $n$ does not change within the scan, so you can build constructs like case statements on the random value. In the event that no instruction matches, the automaton does nothing, but still continues to function. On the next scan, there will be a different random number, so perhaps a matching instruction will be found then.

In what follows, an ``l-value'' is one of w.r, w.g, w.b, w.c, p.r, p.g, p.b, p.c, and an ``r-value'' is either a constant between 0 and 255 inclusive, or one of w.r, w.g, w.b, w.c, p.r, p.g, p.b, p.c, n.

A condition is an expression of the form

V1 op V2 cp V3

Here, op is an operation from the following list: $+$ (addition), # (addition modulo 256), $-$ (subtraction), $*$ (multiplication), & (logical AND), | (logical OR), ^ (logical XOR). Note that these are operations on 8-bit unsigned values. A negative result will be replaced by zero, and a result above 255 will be replaced by 255. Note that a binary comparison can be simulated in several ways, such as V1 + 0 cp V2.

cp is a comparison operation, from the following list: $<$ (less than), $<=$ (less than or equal to), $>$ (greater than), $>=$ (greater than or equal to), $==$ (equal to), and $!=$ (not equal to).

Each of V1, V2, V3 is an r-value.

An assignment is an expression of the form

V4 := V5 op V6

where op is as above, and V4 is an l-value. When executed, the value of V4 is changed. If there are several assignment statements, they are executed in left-to-right order, with subsequent assignments seeing the new values for l-values in previous assignments.

A movement is an r-value V7. If V7 is the same as the left hand side of an assignment, then the new value of V7 (i.e., after the final assignment) is used. There are five (!) kinds of movement: (a) staying put, (b) moving one pixel in one of the eight primary compass directions, (c) moving a random number of pixels along one of the two orthogonal axes, (d) moving to one of the four edges of the picture, and (e) moving to a random pixel. The canvas wraps around when you move off an edge.

V7 is interpreted as follows: The low order 4 bits of V7 we'll call the NSWE bits in order, so that E is the lowest order bit. The high-order 4-bits of V7 are ignored. The four directions N, S, W, E, correspond to the bit patterns 1000, 0100, 0010, 0001, respectively. The four directions NW, NE, SW, SE correspond to the bit patterns 1010, 1001, 0110, 0101, respectively. In these eight cases, the automaton moves one pixel in the chosen direction. The pattern 0000 corresponds to no movement. The pattern 1100 corresponds to a random jump along the north/south axis, while the pattern 0011 corresponds to a random jump along the east/west axis. The pattern 1111 corresponds to a jump to a random pixel.

The remaining patterns, 1110, 1101, 1011, and 0111 are handled as follows. 1110 means move along the east/west axis to the west edge of the picture. 1101 means move along the east/west axis to the east edge of the picture. 1011 means move along the north/south axis to the north edge of the picture. 0111 means move along the north/south axis to the south edge of the picture. These are the only kinds of movement that are sensitive to the notion of ``edges'' since other kinds of movement wrap around. Note that one can move to a corner in two instructions by applying two of these movement operations in succession.

When programming your automaton, be careful to avoid getting stuck in a loop. For example, suppose that the automaton's first instruction is

if (w.c | p.c == 255) then (p.b := w.b + 0) : (0) ;
which assigns w.b to p.b under conditions depending only on w.c and p.c. Since there's no movement, and no change to either w.c or p.c, the statement will always be executed and no progress will be made. Similarly, a first statement of
if (w.c == 0) then (p.b := 255 + 0) : (15) ;
will jump from random pixel to random pixel, coloring everything blue, without yielding control to any other instructions. We might ``fix'' the second statement above by adding an extra assignment, such as
if (w.c == 0) then (p.b := 255 + 0)(w.c := w.c + 1) : (15) ;

What kind of statement as the first statement in a program would prevent all single-statement loops?

We will provide software for interpreting your automaton and generating an animation of its progress. The automaton always starts in the top-left corner of the image. The size of the image and the number of iterations of the automaton will be parameters set in the command line of this program. The automaton is unaware of these parameters. (How might you program your automaton to derive the size of the image?)


next up previous
Next: Project3: Where's My Bus? Up: W4444 Programming and Problem Previous: Project1: The Poker Market
Ken Ross 2001-09-28