Send Beginners mailing list submissions to
beginners@haskell.org
To subscribe or unsubscribe via the World Wide Web, visit
http://www.haskell.org/mailman/listinfo/beginners
or, via email, send a message with subject or body 'help' to
beginners-requ...@haskell.org
You can reach the person managing the list at
beginners-ow...@haskell.org
When replying, please edit your Subject line so it is more specific
than "Re: Contents of Beginners digest..."
Today's Topics:
1. Peer review of an attempt to solve the golf-tee puzzle?
(Scott Thoman)
2. Re: Peer review of an attempt to solve the golf-tee puzzle?
(Brent Yorgey)
3. Re: Peer review of an attempt to solve the golf-tee puzzle?
(Scott Thoman)
4. Re: merge two files in to one file (Erik de Castro Lopo)
----------------------------------------------------------------------
Message: 1
Date: Wed, 5 Oct 2011 11:02:24 -0400
From: Scott Thoman <sc...@thoman.org>
Subject: [Haskell-beginners] Peer review of an attempt to solve the
golf-tee puzzle?
To: beginners@haskell.org
Message-ID:
<cafs7dscpacm1wwemwbgwqtj8s+6aggojpzbzfztncq_abzg...@mail.gmail.com>
Content-Type: text/plain; charset="utf-8"
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)
I'll attach the three files here.
Thanks in advance for any feedback...
/stt
-------------- next part --------------
A non-text attachment was scrubbed...
Name: TeeBoard.hs
Type: text/x-haskell
Size: 4404 bytes
Desc: not available
URL:
<http://www.haskell.org/pipermail/beginners/attachments/20111005/cbae43ad/attachment-0003.hs>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: TriangleTeeBoard.hs
Type: text/x-haskell
Size: 2108 bytes
Desc: not available
URL:
<http://www.haskell.org/pipermail/beginners/attachments/20111005/cbae43ad/attachment-0004.hs>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: solver.hs
Type: text/x-haskell
Size: 597 bytes
Desc: not available
URL:
<http://www.haskell.org/pipermail/beginners/attachments/20111005/cbae43ad/attachment-0005.hs>
------------------------------
Message: 2
Date: Wed, 5 Oct 2011 13:44:09 -0400
From: Brent Yorgey <byor...@seas.upenn.edu>
Subject: Re: [Haskell-beginners] Peer review of an attempt to solve
the golf-tee puzzle?
To: Scott Thoman <sc...@thoman.org>, beginners@haskell.org
Message-ID: <20111005174409.ga3...@seas.upenn.edu>
Content-Type: text/plain; charset=us-ascii
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
------------------------------
Message: 3
Date: Wed, 5 Oct 2011 20:25:23 -0400
From: Scott Thoman <sc...@thoman.org>
Subject: Re: [Haskell-beginners] Peer review of an attempt to solve
the golf-tee puzzle?
To: Brent Yorgey <byor...@seas.upenn.edu>
Cc: beginners@haskell.org
Message-ID:
<CAFS7DSdjmk=s2wpe24ahtcp3ftmxaxbsfwhcbkrux+du9wb...@mail.gmail.com>
Content-Type: text/plain; charset=UTF-8
On Wed, Oct 5, 2011 at 1:44 PM, Brent Yorgey <byor...@seas.upenn.edu> wrote:
> 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
>
Brent,
Thank you very much for your comments. I didn't realize that Show was
for producing valid Haskell so that's good to know. I think I got
stuck on the board containing Ints since I was in the mindset of
folding the board mathematically but everything would be more clear
with Bools. I'll probably switch that and use 'elems' since I didn't
realize that existed. I'll be sad to see the array fold
implementation go :) but I'll rather use the standard fold.
I was talking with the guy who started this little challenge and our
conversations were heading in the "how do I auto-generate the valid
moves for various boards" direction. I think you may be onto
something with your suggestion - the data itself making the valid
moves easy to figure out. The valid moves list was tedious to write
down but it was worth it to prove the algorithm worked.
/stt
------------------------------
Message: 4
Date: Thu, 6 Oct 2011 12:43:59 +1100
From: Erik de Castro Lopo <mle...@mega-nerd.com>
Subject: Re: [Haskell-beginners] merge two files in to one file
To: beginners@haskell.org
Message-ID: <20111006124359.2712b9bd798be28649f68...@mega-nerd.com>
Content-Type: text/plain; charset=US-ASCII
kolli kolli wrote:
> how to sort the values according to column or by date or by time or by
> alphabetical order
>
> * 3616 * 3556 2 11:49:43 /usr/bin/ps
> *3332* 2676 1 Jul 18 /usr/bin/bash
> *500* 2832 0 Jul 18 /usr/bin/bash
Unfortunately, that seems rather poorly formated and I susect
that rather than parsing that as text you would want to use
functions in System.Directory to read the directory into a
list of structs and then sort that.
Erik
--
----------------------------------------------------------------------
Erik de Castro Lopo
http://www.mega-nerd.com/
------------------------------
_______________________________________________
Beginners mailing list
Beginners@haskell.org
http://www.haskell.org/mailman/listinfo/beginners
End of Beginners Digest, Vol 40, Issue 6
****************************************
