Snow Walkers

Snow Walker Applet launch button would be displayed here if Java were enabled.

Quick Start

  1. Read the puzzle description.
  2. Launch the applet by clicking on the button above.
  3. Ensure you have keyboard focus.
  4. Hit Enter to toggle plowing, use the arrow keys to move around.
  5. Configure the puzzle as desired.

The Applet

The applet requires Java 1.5 or higher. It is known to work on Windows XP and Vista under Internet Explorer, Mac OS X Leopard under Safari, and Ubuntu Linux under Firefox.

The applet has a Control Panel on the left for configuring the parameters of the puzzle and has a representation of Grid City in the pane on the right. Each block is depicted along with its four entrances. The plow is represented by a small colored square. The plow is initially green and in the top left corner of Grid City.

As paths are plowed the number inside each block is updated to show its score - that is, the farthest that a pedestrian must walk from that block to get to a neighboring block (north, east, south or west).

Keyboard Focus

In order for you to use the keyboard the Grid City pane must have keyboard focus, which means it is receiving the keystrokes that are being entered. Moving the mouse onto the Grid City pane should be enough to accomplish this, however you may need to cajole the applet to get keyboard focus. One thing that usually works is to click in an edit field in the Control Panel (e.g. the field for editing the number of blocks Grid City has going across) and then move the mouse over to the Grid City pane.

When the Grid City pane has keyboard focus it will be drawn with an interior border, as shown in the image below.

Closeup of Grid City pane with interior border indicating keyboard focus.

Plowing a Path

  1. Move the plow to the desired starting position using the arrow keys.
  2. Hit Enter to turn the plow red and start plowing.
  3. Plow a path using the arrow keys.
  4. Hit Enter to end plowing.

If you have more than one plow (as specified by the "Plowing Rules") you can now position the next plow in its starting position and plow a second path.

The plow is green when it is not plowing and red when it is plowing.

Plowing a path. Tiny indicator arrows point to "offending blocks".

Indicators

When the maximum distance from a block to any of its neighbors is not zero, indicator arrows will point to the "offending" block or blocks - that is, the block or blocks that account for the maximum distance. To avoid clutter, no indication will be shown if the distance to all neighbors is infinity.

Indicator arrows can be seen in the image above.

Inspect Mode

Click on a block in Grid City to enter "Inspect Mode". The selected block will be shaded and red lines will be drawn to show the shortest paths (if any) to its adjacent blocks. Click on the block again to exit "Inspect Mode".

Inspect mode. Paths from the gray block to each neighbor are shown in red.

Configuration

Dimension (blocks across and blocks down)
These set the size of Grid City as shown in the right pane.
Building entrances on corners/sides
This determines the location of the entrances. A corner entrance is accessible when the adjacent intersection has been plowed; a side entrance is accesible only when the adjacent street has been plowed.
Walk through buildings
When this is set, pedestrians are allowed to enter a building through one entrance and exit through another for the purposes of getting to another building. The cost (distance) involved in doing so is determined by the values in the "Configure Costs" dialog.
Configure Costs dialog
This allows you to set the distances involved in walking through a building from one entrance to another.
Max # plows
The total number of plows available. 0 indicates an unlimited number of plows. Plows are assumed to work in parallel even though their paths are specified one after the other.
Max total streets
The total number of streets that can be plowed by all of the plows. 0 indicates no limit.
Only start on boundary
When this is set, plowing must begin at an edge of Grid City. Otherwise plowing can begin anywhere in Grid City.
Allow retrace
Retracing is when a plow that is plowing moves over a street that has already been plowed. This is not allowed by default because it is assumed that pedestrians are walking on these streets.

Output

Score
The score is the farthest anyone would have to travel to get to an adjacent block. It is the maximum of the scores shown on each block.
Time
Plowing a street takes 20 minutes. Moving without plowing takes a negligible amount of time. (Moving without plowing either happens when a plow is moved to its initial position before plowing starts, or when "Allow Retrace" is set and a plow is retracing a street that has already been plowed.) When multiple plows are involved they are assumed to plow in parallel. Therefore the total time reported is the maximum amount of time any plow takes to complete its plowing route.
Max # Streets
The most streets that have been plowed by any one plow.
# Streets
The number of streets that have been plowed by each plow.
Plows Used
The number of plows that have been used, including the current plow if it is currently plowing.
Plows Left
If "Max # plows" has been set, this shows the number of plows remaining.
Streets Plowed
The total number of streets that have been plowed by all plows.
Streets Left
When "Max total streets" has been set, this shows the number of streets that can still be plowed.

Miscellaneous

Scripting

It is possible to specify an entire puzzle configuration in one go using the "Set Puzzle" dialog (bottom of the Control Panel). It is also possible to run a script (a sequence of key commands) using the "Run Script" dialog (also at the bottom of Control Panel). The dialog will come up with the key commands that have been entered so far.

Because of Java applet security restrictions it is currently not possible to copy from or paste to these dialogs.

Speed

The applet should be reasonably responsive for small grid sizes (up to 8 x 10). For larger grid sizes the applet will become noticeably slow and may take several seconds to respond to an action. Currently the applet is not set up to show a busy cursor (e.g. hourglass) to indicate when it is performing a slow computation.

The Algorithm

This section discusses the algorithm that is used internally to compute the shortest paths. The shortest paths have to be recomputed every time a street is plowed or any time a change is made to the configuration. Ideally this recomputation should occur within a few hundred milliseconds so that the user delay is minimal and the applet doesn't feel sluggish.

To compute the shortest paths between blocks I construct a graph where every intersection and every entrance is a vertex, and then I connect:

So with an 8x10 grid there are 99 intersections and 320 entrances for 419 vertices in total. If, for example, every street is plowed that makes 178 edges connecting intersections (9*10 for the north-south streets and 8*11 for the east-west streets). Each intersection can service up to four entrances (regardless of whether entrances are on corners or sides), yielding another 396 (=99*4) edges at most. If "Walk through buildings" is checked there are 480 (=80*choose(4,2)) edges connecting entrances within the blocks. So in the worst case there are 1054 edges (=178+396+480) for an 8x10 grid.

To compute the shortest paths I run Dijkstra's algorithm from each entrance vertex. Originally I used BFS which is much faster but Dijkstra's algorithm supports arbitrary nonnegative weights (e.g. for walking through buildings) and allows for a much more natural graph construction. The internal MIN-QUEUE inside Dijkstra is a naive linear implementation, so the total running time is O(V^3), that is, cubic in the number of vertices.

I considered all-pairs shortest paths algorithms but these are typically cubic or at best O(V^2 lg V) and for a graph this small I felt the extra overhead of the more complicated algorithm would offset the improvement in going from V to lg V. I also considered a binary MIN-QUEUE implementation so that finding the min would happen in log rather than linear time, but again for this number of vertices I felt the considerable overhead of managing the heap and keeping the handles in sync would not yield much improvement.

Optimizations

I did introduce a few optimizations that made a substantial difference in the response time of the applet.


Written by Arefin Huq
Comments? Email me at arefin@gmail.com