Basic routing and halting
Routing and halting are two of the hardest walls when starting to write nontrivial Piet programs. The pointer moves in the unit of connected areas of the same color, and it chooses the next cell using the following variables:
- DP: Direction pointer. One of right, down, left, or up. Initially right.
- CC: Codel Chooser. One of left or right. Initially left.
Given the current area, DP, and CC, the next cell to move into is chosen as follows (hopefully more intuitive than the official doc):
- Imagine you are facing in the direction of DP.
- In the area you're stepping on, choose the cell(s) that are farthest from you.
- If there are multiple, choose the rightmost or leftmost cell out of them (in your view) based on CC.
- Walk to the chosen cell and move front once.
For example, if your current area looks like
x in the following and DP=right and CC=left,
Then the next cell is
a. The cells marked
h are the cells you might enter next, depending on the current DP and CC.
If the next cell is black, or out of bounds, then the pointer tries the next combination of DP and CC - first swap CC, then rotate DP once clockwise, repeat. If all 8 combinations are tried and fails, it halts. (See the previous example again: the cells marked
h are the cells that are tried in order.) Note that, by the spec, invalid commands (stack underflow and division by zero) are simply ignored and execution continues, so the only way to halt a program is via a trapped region.
So how to construct such a trapped region? The simplest ones I found are:
Can you see why each of these works? (It is impossible to trap in a 1-row program, or using areas of size 1 or 2.) And since these are the only trapping configuration of size 3, you will likely use one of these in every halting golfed program.
The turn-right-when-blocked behavior can be used to route in interesting ways. Some examples I found are:
# 2-row infinite loop
# 3-row finite loop with tail
# use conditional DP+ on `de` to turn right to move towards exit
# also can be used for a linear program; put `Push 1` on `cd` and `DP+` on `de`
# 2-row with small loops; use conditional DP+ on `de`
pool pool zz
# more rows with few black cells to eventually lead to infinite loop
# note that seemingly unused cells can be used to push constants
A note on DP+ and CC+ commands (looping and if-else)
There is a command that can change the direction of movement (essentially DP). It is called "pointer" (at hue +3, darkness +1) in the official doc, but I like to call it
DP+, as it directly adds the top value to the current DP (modulo 4). If you have a condition that evaluates to 0 or 1, you can use DP+ on that to turn right once based on a condition. This creates a branch in your program, and you can mainly use it to create a conditional loop. (If you somehow need to turn left instead, applying
*3 to the condition is the shortest method I can think of, which costs 4 more cells.)
There is CC+ ("switch" in official doc, hue +3, darkness +2) command too, which adds the top value to CC (modulo 2). This can be useful in creating if-else constructs: if you place CC+ at
ab in the following code
then the pointer follows the
cde path or the
uvw path based on the resulting CC. Then the
x block acts as the merging point: since CC=right path is blocked, CC is toggled and the execution continues through
xyz... with CC=left in both cases.