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
<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
<mailto: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.
