|
The
Campus Match
is in the form of a game called Herbert. Herbert requires you to solve a series
of levels by writing small programs to control a robot. The simpler and more elegant
your solution, the more points you get.
|
|
Herbert challenges your ability to see patterns and create algorithms to produce
these patterns.
This
Campus Match
consists of
25
levels. On each level there are some white buttons; to "solve" a level you must
press all the white buttons. To press the buttons, you have at your disposal a programmable
robot named Herbert. You must program Herbert, in a language called “h”, to press
all the white buttons while avoiding obstacles such as walls and gray buttons (walls
block Herbert's path and gray buttons will reset any previously pressed white buttons
to their unpressed state). You are only allotted a certain number of "bytes" (a
unit of program size) per level; your program must use no more than this number
of bytes. This last restriction is not too stringent for the earlier levels where
the goal is to simply write a program that works. However, you will find that your
program must be small and cleanly designed in order to complete the higher levels.
On each level, points are awarded for each white button pressed, a bonus is awarded
for solving the level, and extra points are awarded for those solutions that use
less than the allotted maximum number of bytes.
|
|
Herbert is programmed in a simple but powerful language called “h”. “h” contains
elements of traditional high-level languages: statements, procedures, parameters,
arguments, and recursion. However, “h” is syntactically more simple, and contains
some concepts (procedural arguments) that are not found in traditional languages.
Here are the basic elements of “h”:
|
Element |
|
Syntax |
|
Examples |
|
|
Statement |
s (go straight), r (turn right),
or l (turn left), a procedure call, or a procedural parameter. |
s |
|
Procedure definition |
x[(P1,P2,...,Pk)]:y1y2y3...yn
where x is any lowercase letter (except s,
r, or l), Pi is a
parameter, yi is any statement, 0 <= k <=15,
and n >= 0. If k = 0 (no parameters) then the
parentheses are not used. |
a:ssssr
b(C,D):sra(C)D |
|
Parameter |
X where X is any uppercase letter. |
A |
|
Expression |
[-] X [(+ or -) X [(+ or -) X
[(+ or -) X ... ]]] where each X is either a numeric parameter
or a number. |
5
A-5
-A-B-C+1 |
|
Argument |
Any number, expression, or sequence of zero or more statements. |
4
rsr
A-1 |
|
Procedure call |
x[(a1,a2,...,ak)]
where x is the name of a procedure and ai is
an argument (one for each parameter). If k = 0 (no parameters)
then the parentheses are not used. No call is made if any numeric argument is 0
or less. |
a(1,B-1,srs)
b |
|
Recursion |
x[(P1,P2,...,Pk)]:y1y2y3...ymx[(a1,a2,a3,..,ak)]ym+1ym+2ym+3...yn
where x is any lowercase letter (except s,
r, or l), Pi is a
parameter, ai is an argument, yi
is any statement, 0<= k <= 15, m >= 0,
and n >= 0.
|
a(A):sa(A-1)
b:sssrb |
|
Main Procedure |
y1y2y3...yn
where yi is any statement and n >= 1. |
sa(1,rsr)r |
|
Program |
<procedure definition>
:
:
<main procedure>
|
a:ssssra
sssa |
|
Byte |
Any lowercase or uppercase letter, or any number |
s
A
123 |
|
|
Here is a short tutorial to get you familiar with “h” and with Herbert.
First, make sure that your system is able to run Herbert with all of its functionality.
See help for more information on minimum systems requirements
and required security settings.
Next, click here to run a
practice version of Herbert.
You can now follow along in the tutorial by both writing programs yourself, and
checking them against the examples given, or by copying and pasting the examples
from this page into Herbert to see how they work.
In this tutorial we'll learn how to program in "h" by writing a program that makes
Herbert go around in a square. We'll start out with a simple solution and then show
how procedures and parameters can be used to simplify and/or generalize the solution.
Our first task is to program Herbert to go around in a square 5 units per edge,
and then end in the same position and facing the same direction in which he started.
The tutorial consists of a single level (level 0) which is free of buttons and obstructions.
Go to the Options menu, turn on "Trace", and make sure "Path" is enabled, so you
can better see what your program is doing. At any time during this tutorial, feel
free to adjust Herbert's speed by using the scroll bar on the bottom of the Herbert
window. To watch a program more carefully, you may halt it at any time by choosing
"Halt" from the "Run" menu, pressing the Halt (Pause) toolbar button, or simply
clicking anywhere in the text area. You can also place a vertical bar "|" (a breakpoint)
at the point in the program where you want it to stop. Once the program is halted,
you can start stepping through the program one command at a time ("Step" in the
"Run" menu or on the toolbar), resume execution ("Resume"), or reset Herbert to
his starting position ("Reset").
Type the following into the program text area:
sssssrsssssrsssssrsssssr
Now choose "Go" from the "Run" menu. Note that "s" makes Herbert go forward one
unit, while "r" makes him turn one-quarter turn to the right. As you might guess,
"l" (the letter "ell") would make him turn one-quarter turn to the left. These three
commands are the only ones Herbert understands.
Now reset Herbert by choosing "Reset" from the "Run" menu (or simply go ahead and
edit the program; Herbert will be automatically reset on your first edit) and try:
a:sssssr
aaaa
Here you've defined a procedure called "a", which does "sssssr" whenever called.
By calling it four times in a row, this is effectively the same as the first example,
but it's a smaller program; 11 bytes versus 24. Any single lowercase letter is legal
as a procedure name (except for "s", "r", and "l" which already mean something to
Herbert).
Even simpler is:
a:sssssra
a
Here "a" does "sssssr" as before, and then calls itself (which then does "sssssr"
and calls itself ...). When a procedure calls itself, this is called "recursion".
This example is an infinite recursion; Herbert doesn't stop when he's done with
the square. There is no problem with this in itself, since Herbert has an infinite
stack, but you can stop him if you want by choosing "Halt" on the "Run" menu. You
may wish to limit the depth of the recursion in the program itself if, for instance,
you wanted him to do something else after he's gone around in a square. To do this
you must use a parameter:
a(A):sssssra(A-1)
a(4)
Parameters are always single uppercase letters. When a procedure with parameters
is called, you must supply "arguments" for each parameter (here the argument for
"A" is initially 4, then 3, then 2, etc.). The rule with arguments in "h" is that
if any numeric argument in a procedure call evaluates to 0 or less, the call is
not made.
You can also use a second parameter to vary the size of the square.
a(A,B):f(B)ra(A-1,B)
f(A):sf(A-1)
a(4,5)
Now change the "5" to "8" and see what happens. Study the procedure "f" here (we've
used the letter "f" to stand for "forward"). This procedure is a very important
one and will appear time and time again in your solutions.
Parameters can be supplied with "procedural" arguments as well as numeric ones.
Try:
a(A,B,C):f(B)Ca(A-1,B,C)
f(A):sf(A-1)
a(4,5,r)
Then, try changing the "r" to an "l" (ell).
That's all there is to it! For more practice with "h", try the following variations
of our square program. What does each one do?
a(A,B,C):f(B)Ca(A-1,B,C)
b(A):a(4,5,r)lb(A-1)
f(A):sf(A-1)
b(4)
a(A,B,C):f(B)Ca(A-1,B,C)
b(A):a(4,A,r)b(A-1)
f(A):sf(A-1)
b(10)
a(A,B,C):f(B)Ca(A-1,B,C)
b(A):a(2,11-A,r)b(A-1)
f(A):sf(A-1)
b(10)
a(A,B,C):f(B)Ca(A-1,B,C)
f(A):sf(A-1)
a(4,5,rslsr)
|
Herbert is a pretty capable robot, but he does have his limits:
- "h" programs can be a maximum of 999 characters (including special characters and
digits). Your program can have a maximum of 15 lines, and each line can have a maximum
of 127 characters (excluding the function prototype; that is, including everything
after the ":").
- Numbers are limited to the range between -28 and +28 - 1 (-256
to 255). You will receive a runtime error if a numeric argument evaluates to a number
outside this range.
- Herbert's stack is circular and is 64K. For a procedure call, the size of each stack
frame is 4 * (1 + number of arguments). For evaluating procedural arguments, a stack
frame of size 8 is used. What this means in practice is that programs that recur
infinitely, without returning, and without nested procedural arguments, can run
forever. Other programs are limited to a maximum call depth of approximately 2,000
calls (depending on the number of arguments being passed). You will receive a runtime
error if you attempt to return from a call stack which exceeds this size.
- There is no inherent time limit to running Herbert programs. Keep in mind, however,
that your score will be based on the number of buttons pressed (and score uploaded)
by the end of the match.
- Level 0, in both the tutorial and full version of Herbert, is a practice level.
Programs left on this level are not saved or restored across program sessions.
|