211 Plot the Shape

Description

Kvetha Rubyists,

This week’s quiz was submitted by Alan on the suggestions page

Somewhere on a 10x20 grid is a 10 block shape. The shape parts are all adjacent, either horizontally, vertically or diagonally.

Write a simple algorithm that will list the co-ordinates of the 10 parts of the shape. Try to minimize lookups to the grid.

Here is an example shape to get started:

 0123456789ABCDEFGHIJ
0....................
1....................
2.........@@.........
3........@...........
4........@@@@@.......
5.............@......
6............@.......
7....................
8....................
9....................

Have Fun!

Summary

There were many good solutions to this week’s quiz, but Chris Howe’s solution stands out as the best.

Chris’s solution consists of two parts: a Shape class that handles creating the shape and tracking lookups to the grid and a ShapePlot class that handles the guesses.

Chris also provides a mode that draws the board as it is searched. The ’@’ characters represent the parts of the shape that have been discovered so far, the ‘x’ characters represent misses, and the ’.’ characters represent neighbors to the discovered shapes: the places that the program will search next.

+-------------------+
|            x      |
|                   |
|                   |
|                   |
|    . x x .        |
|x x x @ @ .        |
|x @ @ @ x .        |
|x x @ x x          |
|  . x .       x    |
|    x              |
+-------------------+

As you can see the two ‘x’s off to the side are random choices that missed. The program continues to guess randomly a location with part of the shape is found. A piece of the shape was then discovered near the bottom left and the program began searching the neighbors of the already discovered pieces to find the rest of it.

The default output of the program is to display one game in drawing mode, and then run 999 more games to generate the statistics for the average number of lookups. After 1000 plays the average number of lookups is around 31.7.

Thank you Brabuhr, Chris Cacciatore, Chris Howe, Kendal Gifford, and Sandro Paganotti for your solutions this week!

Plot the Shape (#211) - Solutions


Sunday, June 28, 2009