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 ****************************************