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. Re: suggestions for optimizing sudoku solver (Lyndon Maydwell)
2. Re: suggestions for optimizing sudoku solver (KC)
3. Heathrow to London from lyahgg - infinite loop
(Siddharth Karandikar)
4. Re: Heathrow to London from lyahgg - infinite loop
(Brandon Allbery)
5. Re: Heathrow to London from lyahgg - infinite loop
(Siddharth Karandikar)
----------------------------------------------------------------------
Message: 1
Date: Wed, 4 Jan 2012 11:25:47 +0800
From: Lyndon Maydwell <maydw...@gmail.com>
Subject: Re: [Haskell-beginners] suggestions for optimizing sudoku
solver
To: KC <kc1...@gmail.com>
Cc: peter.h...@memorphic.com, beginners@haskell.org
Message-ID:
<cam5qztzyyzwkztnqw9-sfl6jtpcxzuwz+e-6nmfxccg2zoq...@mail.gmail.com>
Content-Type: text/plain; charset=UTF-8
I was about to recommend Bird's solution as well.
An incredibly eye-opening pearl. I believe that he sticks with lists
as the data-structure the entire way through, so that should give an
indication that acceptable performance can be achieved without
requiring mutable data-structures, etc.
The only issue with this approach is that unless you're aware of other
invariants available you'll just end up copying Bird's solution...
I certainly wasn't aware of some of the invariants used in the paper,
and can't think of any others.
On Wed, Jan 4, 2012 at 11:01 AM, KC <kc1...@gmail.com> wrote:
> Bird begins with the specification (without regard to efficiency):
>
> solve = filter valid . expand . choices
>
> And ends up with this third version of solve
>
> solve = search . choices
>
> search m
> ?| not (safe m) = []
> ?| complete m' = [map (map head) m']
> ?| otherwise = concat (map search (expand1 m'))
> ?| where m' = prune m
>
> Note: some functions are missing
>
> The interesting idea is how he uses equational reasoning to reach this solve.
>
>
>
>
> On Sun, Jan 1, 2012 at 7:27 PM, Peter Hall <peter.h...@memorphic.com> wrote:
>> I set myself a learning task of writing a sudoku solver.
>> (https://github.com/peterjoel/sudoku/blob/master/src/Sudoku.hs)
>> It works pretty well, but struggles with some of the harder grids.
>> e.g. data/hard4.txt and data/hard5.txt take around 18 seconds to
>> solve. Obviously there's a limit, but I feel like I should be able to
>> make this faster.
>>
>> I think the main issue is reading/writing to the cells in the grid,
>> since (!!) is O(n). Even though it never has to go beyond index 8, it
>> will add up over the millions of times it has to do it. I imagine it
>> could be a lot faster if I use a static, non-list data structure, but
>> I was hoping to keep it a bit more flexible.
>>
>> Also, I'm struggling to get started with performance profiling. Can
>> someone point me to some good resources?
>>
>> Peter
>>
>> _______________________________________________
>> Beginners mailing list
>> Beginners@haskell.org
>> http://www.haskell.org/mailman/listinfo/beginners
>
>
>
> --
> --
> Regards,
> KC
>
> _______________________________________________
> Beginners mailing list
> Beginners@haskell.org
> http://www.haskell.org/mailman/listinfo/beginners
------------------------------
Message: 2
Date: Tue, 3 Jan 2012 19:44:43 -0800
From: KC <kc1...@gmail.com>
Subject: Re: [Haskell-beginners] suggestions for optimizing sudoku
solver
To: Lyndon Maydwell <maydw...@gmail.com>
Cc: peter.h...@memorphic.com, beginners@haskell.org
Message-ID:
<CAMLKXynfChDaZjkS-L=scfnxnskjmhnczq83jdjd4tqpr+v...@mail.gmail.com>
Content-Type: text/plain; charset=windows-1252
I'm amazed at the invariants he comes up with for all the problems in the book.
At the end of Bird's solution:
"Final Remarks
We tested the solver on 36 puzzles recorded at the website
http://haskell.org/haskellwiki/Sudoku. It solved them in 8.8s (on a
1GHz Pentium 3 PC). We also tested them on six minimal puzzles (each
with 17 non-blank entries) chosen randomly from the 32 000 given at
the site. It solved them in 111.4s. There are about a dozen different
Haskell Sudoku solvers at the site. All of these, including a very
nice solver by Lennart Augustsson, deploy coordinate calculations.
Many use arrays and most use monads. Ours is about twice as slow as
Augustsson?s on the nefarious puzzle (a particularly hard puzzle with
the minimum 17 non-blank entries), but about 30 times faster than Yitz
Gale?s solver on easy puzzles. We also know of solvers that reduce the
problem to Boolean satisfiability, constraint satisfaction, model
checking and so on. I would argue that the one presented above is
certainly one of the simplest and shortest. And at least it was
derived, in part, by equational reasoning."
On Tue, Jan 3, 2012 at 7:25 PM, Lyndon Maydwell <maydw...@gmail.com> wrote:
> I was about to recommend Bird's solution as well.
>
> An incredibly eye-opening pearl. I believe that he sticks with lists
> as the data-structure the entire way through, so that should give an
> indication that acceptable performance can be achieved without
> requiring mutable data-structures, etc.
>
> The only issue with this approach is that unless you're aware of other
> invariants available you'll just end up copying Bird's solution...
>
> I certainly wasn't aware of some of the invariants used in the paper,
> and can't think of any others.
>
> On Wed, Jan 4, 2012 at 11:01 AM, KC <kc1...@gmail.com> wrote:
>> Bird begins with the specification (without regard to efficiency):
>>
>> solve = filter valid . expand . choices
>>
>> And ends up with this third version of solve
>>
>> solve = search . choices
>>
>> search m
>> ?| not (safe m) = []
>> ?| complete m' = [map (map head) m']
>> ?| otherwise = concat (map search (expand1 m'))
>> ?| where m' = prune m
>>
>> Note: some functions are missing
>>
>> The interesting idea is how he uses equational reasoning to reach this solve.
>>
>>
>>
>>
>> On Sun, Jan 1, 2012 at 7:27 PM, Peter Hall <peter.h...@memorphic.com> wrote:
>>> I set myself a learning task of writing a sudoku solver.
>>> (https://github.com/peterjoel/sudoku/blob/master/src/Sudoku.hs)
>>> It works pretty well, but struggles with some of the harder grids.
>>> e.g. data/hard4.txt and data/hard5.txt take around 18 seconds to
>>> solve. Obviously there's a limit, but I feel like I should be able to
>>> make this faster.
>>>
>>> I think the main issue is reading/writing to the cells in the grid,
>>> since (!!) is O(n). Even though it never has to go beyond index 8, it
>>> will add up over the millions of times it has to do it. I imagine it
>>> could be a lot faster if I use a static, non-list data structure, but
>>> I was hoping to keep it a bit more flexible.
>>>
>>> Also, I'm struggling to get started with performance profiling. Can
>>> someone point me to some good resources?
>>>
>>> Peter
>>>
>>> _______________________________________________
>>> Beginners mailing list
>>> Beginners@haskell.org
>>> http://www.haskell.org/mailman/listinfo/beginners
>>
>>
>>
>> --
>> --
>> Regards,
>> KC
>>
>> _______________________________________________
>> Beginners mailing list
>> Beginners@haskell.org
>> http://www.haskell.org/mailman/listinfo/beginners
--
--
Regards,
KC
------------------------------
Message: 3
Date: Wed, 4 Jan 2012 09:51:26 +0530
From: Siddharth Karandikar <siddharth.karandi...@gmail.com>
Subject: [Haskell-beginners] Heathrow to London from lyahgg - infinite
loop
To: beginners@haskell.org
Message-ID:
<CAC6xauMdQU7BW4UK1QM-e2A=ykrjjjkjrq0eq1tyt2tkn-4...@mail.gmail.com>
Content-Type: text/plain; charset=UTF-8
Hi all,
I am trying out Heathrow to London problem given in Learn You a Haskell book.
There is optimization tip given by author to avoid computing priceA =
sum $ map snd pathA every time. I was trying to implement that like
following -
roadStep :: (Path, Path, Int, Int) -> Section -> (Path, Path, Int, Int)
roadStep (pathA, pathB, cA, cB) (Section a b c) =
let forwardPriceToA = cA + a
crossPriceToA = cB + b + c
forwardPriceToB = cB + b
crossPriceToB = cA + a + c
(newPathToA, cA) = if forwardPriceToA <= crossPriceToA
then ((A, a):pathA, forwardPriceToA)
else ((C, c):(B, b):pathB, crossPriceToA)
(newPathToB, cB) = if forwardPriceToB <= crossPriceToB
then ((B, b):pathB, forwardPriceToB)
else ((C, c):(A, a):pathA, crossPriceToB)
in (newPathToA, newPathToB, cA, cB)
But whenever I run this function -
roadStep ([], [], 0, 0) (Section 50 10 30)
its going in infinite loop! I am not able to figure out whats causing
this .. any thoughts?
Thanks,
Siddharth
------------------------------
Message: 4
Date: Wed, 4 Jan 2012 01:04:29 -0500
From: Brandon Allbery <allber...@gmail.com>
Subject: Re: [Haskell-beginners] Heathrow to London from lyahgg -
infinite loop
To: Siddharth Karandikar <siddharth.karandi...@gmail.com>
Cc: beginners@haskell.org
Message-ID:
<CAKFCL4WpTcFMZ6FOs7=pn=omeuk9mddkaeqxzimr4pcsc53...@mail.gmail.com>
Content-Type: text/plain; charset="utf-8"
On Tue, Jan 3, 2012 at 23:21, Siddharth Karandikar <
siddharth.karandi...@gmail.com> wrote:
> I am trying out Heathrow to London problem given in Learn You a Haskell
> book.
> There is optimization tip given by author to avoid computing priceA =
> sum $ map snd pathA every time. I was trying to implement that like
> following -
>
> roadStep :: (Path, Path, Int, Int) -> Section -> (Path, Path, Int, Int)
> roadStep (pathA, pathB, cA, cB) (Section a b c) =
> let forwardPriceToA = cA + a
> crossPriceToA = cB + b + c
> forwardPriceToB = cB + b
> crossPriceToB = cA + a + c
> (newPathToA, cA) = if forwardPriceToA <= crossPriceToA
>
Haskell's let is recursive; you bind cA (a second time, which is often not
wise) there, but forwardPriceToA also uses cA --- which, because you have
introduced a local binding for cA, is going to be that local binding and
not the one from the parameters. (I think.) So you get a binding that
self-recurses forever. Likewise for cB in the next binding.
The solution should be to introduce new names for those bindings (by
convention cA' and cB', but you can call them anything as long as they're
different from the other names in use).
--
brandon s allbery allber...@gmail.com
wandering unix systems administrator (available) (412) 475-9364 vm/sms
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://www.haskell.org/pipermail/beginners/attachments/20120104/941ed59a/attachment-0001.htm>
------------------------------
Message: 5
Date: Wed, 4 Jan 2012 13:06:35 +0530
From: Siddharth Karandikar <siddharth.karandi...@gmail.com>
Subject: Re: [Haskell-beginners] Heathrow to London from lyahgg -
infinite loop
To: Brandon Allbery <allber...@gmail.com>
Cc: beginners@haskell.org
Message-ID:
<cac6xaunoptmue5llz74ondepfh3hvhmwd_4+xb9cdkyylzx...@mail.gmail.com>
Content-Type: text/plain; charset=UTF-8
On Wed, Jan 4, 2012 at 11:34 AM, Brandon Allbery <allber...@gmail.com> wrote:
> On Tue, Jan 3, 2012 at 23:21, Siddharth Karandikar
> <siddharth.karandi...@gmail.com> wrote:
>>
>> I am trying out Heathrow to London problem given in Learn You a Haskell
>> book.
>> There is optimization tip given by author to avoid computing priceA =
>> sum $ map snd pathA every time. I was trying to implement that like
>> following -
>>
>> roadStep :: (Path, Path, Int, Int) -> Section -> (Path, Path, Int, Int)
>> roadStep (pathA, pathB, cA, cB) (Section a b c) =
>> ? ? ? ? let forwardPriceToA = cA + a
>> ? ? ? ? ? ? crossPriceToA = cB + b + c
>> ? ? ? ? ? ? forwardPriceToB = cB + b
>> ? ? ? ? ? ? crossPriceToB = cA + a + c
>> ? ? ? ? ? ? (newPathToA, cA) = if forwardPriceToA <= crossPriceToA
>
>
> Haskell's let is recursive; you bind cA (a second time, which is often not
> wise) there, but forwardPriceToA also uses cA --- which, because you have
> introduced a local binding for cA, is going to be that local binding and not
> the one from the parameters. ?(I think.) ?So you get a binding that
> self-recurses forever. ?Likewise for cB in the next binding.
>
> The solution should be to introduce new names for those bindings (by
> convention cA' and cB', but you can call them anything as long as they're
> different from the other names in use).
>
Yes, you are right. I am accidentally creating a recursive binding.
I introduced a new name, and it worked!
-Wall showed all the shadowing warnings. Better to keep -Wall always on. :)
Thanks!
------------------------------
_______________________________________________
Beginners mailing list
Beginners@haskell.org
http://www.haskell.org/mailman/listinfo/beginners
End of Beginners Digest, Vol 43, Issue 6
****************************************
