I'd suggest taking a look at the following blog post: http://programming-puzzler.blogspot.be/2013/03/logic-programming-is-overrated.html
(The ensuing discussion between David and Mark is also worth reading.) On 17 May 2014 14:49, Rob Day <r...@rkd.me.uk> wrote: > A better approach might be to break it down into three groups: > > * The first three numbers (rows 1 and 2), constrained by rule D > * The middle three numbers (row 3), constrained by rule A > * The last four numbers (row 4), constrained by rule E > > There are only 10!/7! or 10!/6! initial possibilities for each group, so > it's much quicker to apply the constraints, and the constraints reduce the > problem space significantly - only 53 of the original 720 possibilities > satisfy rule D, 4 of the original 720 satisfy rule A, and ~3000 of the > initial 5040 satisfy rule E. At this point, you've run less than 7000 > checks, but you've reduced your pool of possible solutions from 10! > (~3,600,000) to ~600,000. > > You can then combine those three groups together (to get the possible > arrangements of all 10 balls), and run a filter to verify that no numbers > are repeated (e.g. that you aren't combining a solution to the first three > balls that uses 1 with a solution to the last four balls that uses 1 - this > step takes it down to about 900 possible answers). Then just filter on rules > B and C to get the answer. I've got this running in about 160ms (though > admittedly in Haskell). > > There's probably a name for this technique - constraint propagation? - but > I'll leave it to the formally trained to comment. The slowest step is almost > certainly discarding repeated solutions - that runs over 600,000 possible > permutations and discards 599,000 of them - so if anyone has ideas on how to > not generate so many duplicate numbers, that would be great. > > On 17/05/14 00:15, Brad Kurtz wrote: > > I have since fixed the original stack overflow error I was getting, it was a > result of not using "recur". However, I'm still trying to find the best way > to actually iterate through the permutations to find the result... > > On Friday, May 16, 2014 2:31:26 PM UTC-5, Brad Kurtz wrote: >> >> I'm pretty new to Clojure so I'm trying out simple examples to see if I >> can get myself in the functional programming/Lisp mindset. My team lead >> sends out puzzles from his Mensa calendar, and every once in a while I find >> one that seems fun to solve as a Clojure program. >> >> With this particular puzzle, I've tried a couple of different ways of >> "solving" the puzzle, and I decided to try a recursive function. I'm fairly >> certain that what I've done here is not anywhere near ideal, and I'm looking >> for insight into how to better write this solution. >> >> Also, with my latest attempt I seem to be getting a stack overflow error, >> and I'm not quite sure why. I'm pretty sure it has to do with the >> permutation sequence (it's basically 10 factorial, or around 3 million >> sequences), but I don't really know how to better represent this problem in >> Clojure. Can anyone help? Thanks! >> >> https://github.com/bradkurtz/clojure-puzzles/tree/master/billiards > > -- > You received this message because you are subscribed to the Google > Groups "Clojure" group. > To post to this group, send email to clojure@googlegroups.com > Note that posts from new members are moderated - please be patient with your > first post. > To unsubscribe from this group, send email to > clojure+unsubscr...@googlegroups.com > For more options, visit this group at > http://groups.google.com/group/clojure?hl=en > --- > You received this message because you are subscribed to the Google Groups > "Clojure" group. > To unsubscribe from this group and stop receiving emails from it, send an > email to clojure+unsubscr...@googlegroups.com. > For more options, visit https://groups.google.com/d/optout. > > > -- > You received this message because you are subscribed to the Google > Groups "Clojure" group. > To post to this group, send email to clojure@googlegroups.com > Note that posts from new members are moderated - please be patient with your > first post. > To unsubscribe from this group, send email to > clojure+unsubscr...@googlegroups.com > For more options, visit this group at > http://groups.google.com/group/clojure?hl=en > --- > You received this message because you are subscribed to the Google Groups > "Clojure" group. > To unsubscribe from this group and stop receiving emails from it, send an > email to clojure+unsubscr...@googlegroups.com. > For more options, visit https://groups.google.com/d/optout. -- You received this message because you are subscribed to the Google Groups "Clojure" group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en --- You received this message because you are subscribed to the Google Groups "Clojure" group. To unsubscribe from this group and stop receiving emails from it, send an email to clojure+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/d/optout.
