Send Beginners mailing list submissions to
[email protected]
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
[email protected]
You can reach the person managing the list at
[email protected]
When replying, please edit your Subject line so it is more specific
than "Re: Contents of Beginners digest..."
Today's Topics:
1. Re: Lions, Wolves and Goats (Tim Perry)
2. Re: Lions, Wolves and Goats (Tim Perry)
----------------------------------------------------------------------
Message: 1
Date: Mon, 16 Jun 2014 16:15:19 -0700
From: Tim Perry <[email protected]>
To: The Haskell-Beginners Mailing List - Discussion of primarily
beginner-level topics related to Haskell <[email protected]>
Subject: Re: [Haskell-beginners] Lions, Wolves and Goats
Message-ID:
<CAFVgASU23qq1N9La1xjG=9p3yapjkmvchk5og--3za--qx4...@mail.gmail.com>
Content-Type: text/plain; charset="utf-8"
I tried a set-based solution and it can process ~1600 items in 25 seconds
on this i7. Seems really slow compared to the times posted here:
http://unriskinsight.blogspot.co.at/2014/06/fast-functional-goats-lions-and-wolves.html
I'm curious if anyone spots any major flaw. If not, I'll profile it tonight
-- I can't afford to spend more time on this at work
Tim
On Fri, Jun 13, 2014 at 8:54 AM, Elric <[email protected]> wrote:
> Thank You Bob,
>
> I learnt quite a bit from your solution. I have been restricting myself to
> Lists so far. I think I will have to start exploring other data structures
> like Sets in Haskell as well. :)
>
> Thank You,
> Elric
>
>
> On 06/08/2014 03:41 PM, Bob Ippolito wrote:
>
> Here's another approach that more closely models what's going on in the
> C++ version. I defined an ordNub rather than using nub as nub is O(n^2) as
> it only requires Eq.
>
> https://gist.github.com/etrepum/5bfedc8bbe576f89fe09
>
> import qualified Data.Set as S
> import Data.List (partition)
> import System.Environment (getArgs)
>
> data LWG = LWG { _lion, _wolf, _goat :: {-# UNPACK #-} !Int }
> deriving (Show, Ord, Eq)
>
> lionEatGoat, lionEatWolf, wolfEatGoat :: LWG -> LWG
> lionEatGoat (LWG l w g) = LWG (l - 1) (w + 1) (g - 1)
> lionEatWolf (LWG l w g) = LWG (l - 1) (w - 1) (g + 1)
> wolfEatGoat (LWG l w g) = LWG (l + 1) (w - 1) (g - 1)
>
> stableState :: LWG -> Bool
> stableState (LWG l w g) = length (filter (==0) [l, w, g]) >= 2
>
> validState :: LWG -> Bool
> validState (LWG l w g) = all (>=0) [l, w, g]
>
> possibleMeals :: LWG -> [LWG]
> possibleMeals state =
> filter validState .
> map ($ state) $ [lionEatGoat, lionEatWolf, wolfEatGoat]
>
> ordNub :: Ord a => [a] -> [a]
> ordNub = S.toList . S.fromList
>
> endStates :: [LWG] -> [LWG]
> endStates states
> | not (null stable) = stable
> | not (null unstable) = endStates (concatMap possibleMeals unstable)
> | otherwise = []
> where (stable, unstable) = partition stableState (ordNub states)
>
> main :: IO ()
> main = do
> [l, w, g] <- map read `fmap` getArgs
> mapM_ print . endStates $ [LWG l w g]
>
>
>
> On Sat, Jun 7, 2014 at 11:33 PM, Francesco Ariis <[email protected]> wrote:
>
>> On Sat, Jun 07, 2014 at 08:04:09PM -0400, Elric wrote:
>> > Hi,
>> >
>> > I came across this article:
>> http://unriskinsight.blogspot.co.at/2014/06/fast-functional-goats-lions-and-wolves.html
>> > a couple of days ago. This compares performance of solving a problem
>> > (which I will get to) using the functional constructs alone in
>> > languages like C++11 and Java 8.
>> > Since, Haskell is my first foray into FP, I thought I should try
>> > solving this in Haskell.
>> >
>>
>> Hello Elric,
>> I gave a go at the problem, managed to get a result (23).
>> I attach the .hs file (not my best Haskell, but hopefully clear enough).
>>
>> The crucial point in my solution lies in this lines:
>>
>> carnage :: [Forest] -> [Forest]
>> let wodup = nub aa in
>> -- etc. etc.
>>
>> Which means after every iteration I call |nub| on my list of possible
>> states; nub is a function from |Data.List| and removes duplicate
>> elements from a list.
>>
>> If I omit that nub call, the program doesn't reach a solution (as it
>> is computationally quite inefficient). I think that's the problem
>> with your versions.
>>
>> Let me know if this helps
>>
>>
>>
>>
>>
>>
>>
>> _______________________________________________
>> Beginners mailing list
>> [email protected]
>> http://www.haskell.org/mailman/listinfo/beginners
>>
>>
>
>
> _______________________________________________
> Beginners mailing
> [email protected]http://www.haskell.org/mailman/listinfo/beginners
>
>
>
> _______________________________________________
> Beginners mailing list
> [email protected]
> http://www.haskell.org/mailman/listinfo/beginners
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://www.haskell.org/pipermail/beginners/attachments/20140616/3d9c29ff/attachment-0001.html>
------------------------------
Message: 2
Date: Mon, 16 Jun 2014 16:16:30 -0700
From: Tim Perry <[email protected]>
To: The Haskell-Beginners Mailing List - Discussion of primarily
beginner-level topics related to Haskell <[email protected]>
Subject: Re: [Haskell-beginners] Lions, Wolves and Goats
Message-ID:
<CAFVgASVzDaUS5Q+rLpAB6=wmyyrat6ffv9+y12jiuh5pygg...@mail.gmail.com>
Content-Type: text/plain; charset="utf-8"
Oops, I forgot the gist location.
https://gist.github.com/anonymous/99bc650c41e07364764c
I tried a set-based solution and it can process ~1600 items in 25 seconds
on this i7. Seems really slow compared to the times posted here:
http://unriskinsight.blogspot.co.at/2014/06/fast-functional-goats-lions-and-wolves.html
I'm curious if anyone spots any major flaw. If not, I'll profile it tonight
-- I can't afford to spend more time on this at work
On Mon, Jun 16, 2014 at 4:15 PM, Tim Perry <[email protected]> wrote:
> I tried a set-based solution and it can process ~1600 items in 25 seconds
> on this i7. Seems really slow compared to the times posted here:
>
> http://unriskinsight.blogspot.co.at/2014/06/fast-functional-goats-lions-and-wolves.html
>
> I'm curious if anyone spots any major flaw. If not, I'll profile it
> tonight -- I can't afford to spend more time on this at work
>
> Tim
>
>
>
> On Fri, Jun 13, 2014 at 8:54 AM, Elric <[email protected]> wrote:
>
>> Thank You Bob,
>>
>> I learnt quite a bit from your solution. I have been restricting myself
>> to Lists so far. I think I will have to start exploring other data
>> structures like Sets in Haskell as well. :)
>>
>> Thank You,
>> Elric
>>
>>
>> On 06/08/2014 03:41 PM, Bob Ippolito wrote:
>>
>> Here's another approach that more closely models what's going on in the
>> C++ version. I defined an ordNub rather than using nub as nub is O(n^2) as
>> it only requires Eq.
>>
>> https://gist.github.com/etrepum/5bfedc8bbe576f89fe09
>>
>> import qualified Data.Set as S
>> import Data.List (partition)
>> import System.Environment (getArgs)
>>
>> data LWG = LWG { _lion, _wolf, _goat :: {-# UNPACK #-} !Int }
>> deriving (Show, Ord, Eq)
>>
>> lionEatGoat, lionEatWolf, wolfEatGoat :: LWG -> LWG
>> lionEatGoat (LWG l w g) = LWG (l - 1) (w + 1) (g - 1)
>> lionEatWolf (LWG l w g) = LWG (l - 1) (w - 1) (g + 1)
>> wolfEatGoat (LWG l w g) = LWG (l + 1) (w - 1) (g - 1)
>>
>> stableState :: LWG -> Bool
>> stableState (LWG l w g) = length (filter (==0) [l, w, g]) >= 2
>>
>> validState :: LWG -> Bool
>> validState (LWG l w g) = all (>=0) [l, w, g]
>>
>> possibleMeals :: LWG -> [LWG]
>> possibleMeals state =
>> filter validState .
>> map ($ state) $ [lionEatGoat, lionEatWolf, wolfEatGoat]
>>
>> ordNub :: Ord a => [a] -> [a]
>> ordNub = S.toList . S.fromList
>>
>> endStates :: [LWG] -> [LWG]
>> endStates states
>> | not (null stable) = stable
>> | not (null unstable) = endStates (concatMap possibleMeals unstable)
>> | otherwise = []
>> where (stable, unstable) = partition stableState (ordNub states)
>>
>> main :: IO ()
>> main = do
>> [l, w, g] <- map read `fmap` getArgs
>> mapM_ print . endStates $ [LWG l w g]
>>
>>
>>
>> On Sat, Jun 7, 2014 at 11:33 PM, Francesco Ariis <[email protected]> wrote:
>>
>>> On Sat, Jun 07, 2014 at 08:04:09PM -0400, Elric wrote:
>>> > Hi,
>>> >
>>> > I came across this article:
>>> http://unriskinsight.blogspot.co.at/2014/06/fast-functional-goats-lions-and-wolves.html
>>> > a couple of days ago. This compares performance of solving a problem
>>> > (which I will get to) using the functional constructs alone in
>>> > languages like C++11 and Java 8.
>>> > Since, Haskell is my first foray into FP, I thought I should try
>>> > solving this in Haskell.
>>> >
>>>
>>> Hello Elric,
>>> I gave a go at the problem, managed to get a result (23).
>>> I attach the .hs file (not my best Haskell, but hopefully clear enough).
>>>
>>> The crucial point in my solution lies in this lines:
>>>
>>> carnage :: [Forest] -> [Forest]
>>> let wodup = nub aa in
>>> -- etc. etc.
>>>
>>> Which means after every iteration I call |nub| on my list of possible
>>> states; nub is a function from |Data.List| and removes duplicate
>>> elements from a list.
>>>
>>> If I omit that nub call, the program doesn't reach a solution (as it
>>> is computationally quite inefficient). I think that's the problem
>>> with your versions.
>>>
>>> Let me know if this helps
>>>
>>>
>>>
>>>
>>>
>>>
>>>
>>> _______________________________________________
>>> Beginners mailing list
>>> [email protected]
>>> http://www.haskell.org/mailman/listinfo/beginners
>>>
>>>
>>
>>
>> _______________________________________________
>> Beginners mailing
>> [email protected]http://www.haskell.org/mailman/listinfo/beginners
>>
>>
>>
>> _______________________________________________
>> Beginners mailing list
>> [email protected]
>> http://www.haskell.org/mailman/listinfo/beginners
>>
>>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://www.haskell.org/pipermail/beginners/attachments/20140616/9044a118/attachment.html>
------------------------------
Subject: Digest Footer
_______________________________________________
Beginners mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/beginners
------------------------------
End of Beginners Digest, Vol 72, Issue 15
*****************************************
