chiark / gitweb /
Apply some optimisation to Undead's get_unique() function, which was
authorSimon Tatham <anakin@pobox.com>
Fri, 12 Apr 2013 16:28:52 +0000 (16:28 +0000)
committerSimon Tatham <anakin@pobox.com>
Fri, 12 Apr 2013 16:28:52 +0000 (16:28 +0000)
commitfe6da52b26f14e539183d5eb71e2132a8bf9fa8f
tree6686f5daab9bcabc0f75a04546716c22ee801fa9
parent120f6de605b9a431e3b084bfc34d7cf33b6c9905
Apply some optimisation to Undead's get_unique() function, which was
not only enumerating all possible arrangements of monsters along a
sight-line in O(3^n) time, but also allocated memory for them all and
then does a quadratic-time loop over that list to find arrangements
with a unique visibility count from both ends. Spotted by the new
'make test', which observed that 7x7dn#517035041807425 took 45 seconds
to generate.

This revised version still does the initial O(3^n) enumeration, which
can probably be got rid of as well with a bit more thought, but it now
doesn't allocate nearly so much memory and it spots uniques
efficiently. The above random seed now generates the same game ID in
less than a second, which drops this puzzle off the 'make test' hit
list of things most obviously needing speedup.

[originally from svn r9826]
undead.c