SnowWalkers

Dennis Shasha

Omniheurist Course

Computer Science


 

Description

Grid City is a small planned city laid out at a completely regular N by M grid with streets going north-south and east-west. There is one building per city block. Grid occasionally suffers major snow storms. The Grid City Snow Clearing Department (GridClear) wishes to make it possible to reach each city block but the effort to move the snow is so great that they resolve to make it possible to go from any block to any other through paved paths. This means that the path itself may snake through the city and may even loop through an intersection, but the plows won't double-back on a paved road for fear of running over the many pedestrians.

The head of GridClear consults you to help plan the path. You are told the path must start somewhere on the outside boundary of the grid, but you can choose where, because Grid City has many garages available. The goal is to ensure that for any two blocks that neighbor one another north-south or east-west, a resident will need to travel over only a few streets (or through a few buildings) along the cleared path. The "score" of a path is the worst case, i.e. the largest number of such streets/buildings. Crossing a plowed intersection costs nothing, but it is impossible to cross an unplowed intersection or street.

You may assume that each building block has an entrance at every corner and that walking through a building to any other corner (even to the diagonally opposite one) costs the same as walking one city block along a plowed street. You accept this simplication, because there is no ice inside the buildings.

In what follows, you may find it helpful to look at the very nice applet of Arefin Huq with whom I have worked on this puzzle.

Players will be told M and N (the dimensions of the grid), how many plows they have (up to and including 4), and be given an upper bound (worst case) of the score on the whole grid. They are to obtain that score in the shortest time cost possible, where the time cost is the maximum number of streets plowed by any single plow.

Here are some examples along with solutions in the human-solvable version of this puzzle

Architecture

The architecture group will extend Arefin Huq's applet to display the board, reorganize the game to allow TCP connections, keep track of the plow that takes the longest route.