Re: Looking for help with a Stack Overflow error
Hi, Brad (and Karsten). I solved the problem with core.logic, to try out its CLP(FD) features. It took about 220-230ms to find a solution. It took about 400ms to find all solutions. Here it is for you to peek at after you try it: https://gist.github.com/leifp/b4af5f4cd7289c38b55a The code looked very similar to the problem statement, no careful hand-crafting required. The one minor irritation is that there is no way to easily specify equations involving vectors of logic vars. I think I could've done it in this case with macros, but I wouldn't want to do that if I had hundreds or thousands of variables. Maybe I'm just not experienced enough with core.logic, experts chime in if so. --Leif On Friday, May 16, 2014 3:31:26 PM UTC-4, 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.
Re: Looking for help with a Stack Overflow error
I've seen David Nolen talk a bit about core.logic and I admit it seems interesting. Since I'm new to Clojure I didn't think to look into it. I'll take a look at your solution Leif. Thanks for the suggestions everyone. On Sunday, May 18, 2014 6:28:15 PM UTC-5, Leif wrote: Hi, Brad (and Karsten). I solved the problem with core.logic, to try out its CLP(FD) features. It took about 220-230ms to find a solution. It took about 400ms to find all solutions. Here it is for you to peek at after you try it: https://gist.github.com/leifp/b4af5f4cd7289c38b55a The code looked very similar to the problem statement, no careful hand-crafting required. The one minor irritation is that there is no way to easily specify equations involving vectors of logic vars. I think I could've done it in this case with macros, but I wouldn't want to do that if I had hundreds or thousands of variables. Maybe I'm just not experienced enough with core.logic, experts chime in if so. --Leif On Friday, May 16, 2014 3:31:26 PM UTC-4, 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.
Re: Looking for help with a Stack Overflow error
Hi Brad, I can't help you with your solution, but just wanted to mention that the core.logic library might be a great tool for this kind of problem (plus I'd be v.interested in seeing a solution using this myself... :) K. On 16 May 2014 22:15, Brad Kurtz bkurtz@gmail.com 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.
Re: Looking for help with a Stack Overflow error
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.
Re: Looking for help with a Stack Overflow error
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
Looking for help with a Stack Overflow error
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.
Re: Looking for help with a Stack Overflow error
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.
