[Haskell-beginners] Peer review of an attempt to solve the golf-tee puzzle?

[Brent Yorgey]

On Wed, Oct 05, 2011 at 11:02:24AM -0400, Scott Thoman wrote:
> Hi,
>
> I'm looking to see of anyone is interested in a quick code review.  I
> coded a quick solution to the golf-tee puzzle (like you see a places
> like Cracker Barrel, 15 piece triangle where you hop the pegs in order
> to get down to one left).  My solution seems to work, seems to perform
> ok, and seems to come up with a very large number of distinct
> solutions.
>
> I'm looking for some feedback as far as:
> - am I "getting" it? :)
> - is the approach general enough?
> - does it look anything like idiomatic haskell?
> - any places to make things simpler or more point-free-ish?
> - any types are overkill, too restrictive (I added the Board type so
> maybe it could be an instance of Show to display the triangle but
> didn't go that far)

Hi Scott,

It seems like a nice general solution to me.  It looks like it would
also be applicable to a puzzle I remember from my childhood which had
the same rules (jump one piece over another to remove the jumped
piece, try to end up with only a single piece) but had a board with a
starting configuration that looked like this:

  XXX
  XXX
XXXXXXX
XXX XXX
XXXXXXX
  XXX
  XXX

Some comments interspersed below.

> -- | A module of functions around solving the "tee board" type
> --   puzzles.  The main example of this is the 15 piece puzzle
> --   found at places like Cracker Barrel.
> --   The board is modeled as an immutable array where indexes
> --   are Ints and the elements are also Ints.  The contents are
> --   expected to be 0 for an empty spot and 1 for a full spot.

Why use Int? Wouldn't Bool be more appropriate?

> -- | Our representation of a board - an indexable array
> --   of Ints (slots are 0 -> empty, 1 -> full).
> newtype Board = Board (Array Int Int)
>     deriving (Show, Eq)
> --type Board = Array Int Int

You mentioned making a Show instance for Board to display the puzzle
but I wouldn't do that.  Show is intended to produce valid Haskell
expressions, i.e. you should really only use the automatically derived
Show instance.  If you want to print out the board nicely I would just
make a function  displayBoard :: Board -> String.

>
> -- | Make board of the given size filled with the given value
> populateBoard :: Int -> Int -> Board
> populateBoard s v = board s $ map (\x -> (x, v)) $ range (1, s)
>
> -- | Make an empty board of the given size
> emptyBoard :: Int -> Board
> emptyBoard = (flip populateBoard) 0
>
> -- | Make a full board of the given size
> fullBoard :: Int -> Board
> fullBoard = (flip populateBoard) 1

The fact that you had to use 'flip' to define emptyBoard and fullBoard
suggests that the order of parameters to populateBoard should be switched.

> -- | Test whether a move is valid on the given board.
> isValidMove :: Board -> Move -> Bool
> isValidMove b (s,j,e) = (b `atSpot` s == 1) && (b `atSpot` j == 1) && (b `atSpot` e == 0)

If the board stored Bools you could just write (b `atSpot` s) && (b
`atSpot` j) && (not (b `atSpot` e)).

> -- | Simple foldl for our Board (array) that folds up the
> --   values on the board.
> --   (This one knows about the internal board implementation.)
> foldBoard :: (Int -> Int -> Int) -> Int -> Board -> Int
> foldBoard f a (Board b) =
>     let hi = snd $ bounds b
>         doit a i = if (i > hi) then
>                         a
>                    else
>                         doit (f a (b ! i)) (i + 1)
>     in
>         doit a 1

This is an ugly and fiddly way to fold over the values in the array.
Instead, use the 'elems' function to get a list of the array elements
and then do a fold over that.

> -- | The specifics for the 15 piece "tee board" puzzle.  This module
> --   contains the details about valid moves, etc. on this board layout.
> --   The board layout is labled like the following:
> --                    01
> --                  02  03
> --                04  05  06
> --              07  08  09  10
> --            11  12  13  14  15
> module TriangleTeeBoard where
> import TeeBoard
> import Data.Array
>
> -- | The valid moves on the 15 piece triangle "tee board".
> --   This is just a list of (start, jumped, end) tuples and can be
> --   used when called TeeBoard.solutions.
> validTriangleMoves :: [(Int, Int, Int)]
> validTriangleMoves = [
>             (1,2,4),
>             (1,3,6),
>             (2,4,7),

Ugh! I wonder if you could figure out a way to generate this list
instead of just writing it down by hand.  Although I realize that
might be tricky.  It might become easier if you choose a different
representation for locations.  For example you could represent a
location as a triple (Int, Int, Int), representing the
distances from the bottom, left, and right edges respectively. Like
so:

                (4,0,0)
        (3,0,1)         (3,1,0)
(2,0,2)         (2,1,1)         (2,2,0)

and so on. Notice that the sum of the values is constantly one less
than the size of the puzzle.  Then from any location you can easily
compute the adjacent locations like so:

          (+1,-1,0)  (+1,0,-1)
     (0,-1,+1)   (i,j,k)   (0,+1,-1)
          (-1,0,+1)  (-1,+1,0) 

which should make generating valid moves a snap.  Of course, it would
be nice to still store the board in an array indexed by Int: to convert
one of these triple-locations (i,j,k) to a unique integer index you can do

  locToIndex (i,j,k) = (4-i)*(4-i+1) `div` 2 + j

Just a fun idea.

-Brent