I decided to write a blog post based on the Kakuro puzzle solver problem from this thread:
http://squishythinking.com/2015/11/02/optimizing-kakuro-in-julia/ On Wednesday, October 21, 2015 at 7:08:35 PM UTC-4, Jason Merrill wrote: > > I got interested in trying to optimize this problem even further. Here are > the results: > > https://gist.github.com/jwmerrill/5b364d1887f40f889142 > > I was able to get the benchmark down to a few microseconds (or ~100 > microseconds if you count the time to build a look up table). Either way, > it's a pretty good improvement over 1+ seconds :-) > > The main trick is to represent a set of digits 1-9 as a binary integer. > There are only 2^9=512 such sets, so you can pack any of them into an > Int16. Then you can precompute the sum of each set and store those in a > look up table, so that finding the ways to decompose a given number is just > a table lookup. > > I think this is a pretty nice example of how Julia's dispatch system let > you have complex views and operations over a very simple data structure (in > this case, a single integer), with essentially 0 overhead. > > On Monday, October 19, 2015 at 7:39:03 AM UTC-4, Patrick Useldinger wrote: >> >> Hello >> true but no summand may appear twice, and only numbers 1 to 9 may be >> used. For example, (10, 3) yields >> >> Array[Int16[2,3,5],Int16[1,4,5],Int16[1,3,6],Int16[1,2,7]] >> >> Regards, >> -Patrick >> >
