Great read.
On Tuesday, November 3, 2015 at 6:43:24 AM UTC+1, Jason Merrill wrote: > > 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 >>> >>
