Write a program or function that takes in three integers, a width
w, a height
h, and a step count
s. You will be drawing a non-self-intersecting random walk
s steps long on a
5*h pixel image where every 5 by 5 pixel cell is either empty (pure beige) or one of these twelve simple "pipes":
The image above is enlarged to show detail. Here are the pipes at actual size:
(The gray lines are just to separate the pipe types.)
The random walk will be a single continuous pipe path that starts at one pipe endpoint (one of the bottom four pipe types) and ends at another pipe endpoint.
Start with an empty
h grid and randomly choose one cell to be the starting point. Then randomly choose one of the four directions to start in and draw the corresponding pipe endpoint. This starting cell marks the first step in your walk and every time you draw a new cell or overwrite an existing one it counts as another step taken.
Now, repeatedly, randomly choose to go right, left, or straight, drawing the appropriate pipe cell if the direction chosen is valid. Backtrack and re-choose if a direction is not valid until the complete
s step path is formed. The path should end with a pipe endpoint, which might be anywhere on the grid, depending on the course the path took.
It is very important to note that only the two straight pipe cells can be overwritten, and only by the straight pipe cell of the opposite orientation, the result being an intersection cell. Otherwise, all pipes must be placed in empty cells.
When an intersection is drawn, the part of the path that is further along from the starting cell should be drawn on top.
It is up to you whether or not the grid has periodic boundary conditions (PBC), i.e. whether a pipe exiting one side of the grid will come out on the other side. Without PBC the grid boundary counts as a barrier that you can run into just like other pipes.
sis 0 no pipes should be drawn and the output should be a blank
5*himage (i.e. all beige).
sis 1 a single pipe stub
should be drawn at the randomly chosen starting cell.
- You may assume that
sis at most
w*hso a path will always be possible. (Though longer paths are possible due to intersections.)
hwill always be positive.
- All random choices must be uniformly random. e.g. you shouldn't avoid making intersections when they are possible even if it makes the problem easier. Pseudo-random number generators are allowed.
- Any three visually distinct colors may be used in place of the black, blue, and beige.
- Your output images may be enlarged so that they are really
kis a positive integer. (Enlarging any examples you post is advised even if your
- Any common lossless image file format may be used and the image may be saved to a file, displayed, or spewed raw to stdout.
The shortest code in bytes wins.
(All enlarged by 500%.)
If the input is
w=2, h=1, s=0 then the output will always be:
If the input is
w=2, h=1, s=1 then the output will be one of these images with equal chance:
If the input is
w=2, h=1, s=2 then the output will be
if the grid is assumed to have PBC.
Here are some possible outputs for
w=3, h=2, s=6, assuming PBC:
Here is a possible output for
w=3, h=3, s=9, assuming PBC:
Notice that the path didn't need to cover all the cells due to the intersection counting as two steps. Also, we can deduce that the corner endpoint was the starting cell since the intersection overpass must have been drawn afterwards. Thus we can infer the sequence of random choices that were made:
start at top left, facing east go straight go right go right go right go straight go left go right end
Finally, here are examples of
w=4, h=5, s=20 and
w=4, h=5, s=16: