Aaron N. Tubbs bio photo

Aaron N. Tubbs

Dragon chaser.

Twitter Facebook Google+ LinkedIn Github

It’s been three months since I last solved a programming challenge from the book. I took some time to do some Project Euler problems, but there’s no real excuse why I’ve sucked at this. In any event, did another one:

10181 – “15-Puzzle Problem”

My solution is a bag of hell. It makes about three billion copies of vectors, and then goes one step further and uses vectors as indices into sets and maps. It uses a priority queue, and rather than being elegant about it, I just let the thing grow unbounded, inserting duplicate puzzles (with different weights) into the queue without even thinking about things. But it solves the challenge in 2.5 seconds, and, again, winning is all that really matters.

I had to cheat a lot on the Internet to figure out how to do parity calculations on the puzzle to determine whether or not one could be solved. The forum boffins seemed to want to use IDA*, but I just decided to use vanilla A*. I don’t see how the memory advantages of IDA* are really necessary, especially when my solution is bleeding memory out its ass and isn’t running into the memory barrier on the judge.

Careful tuning of the heuristic scaling factor was necessary. Some quick modeling determined that deviation from the factor I arrived at by as little as 1% could double runtime. Removing the linear conflict hint also doubled runtime for my test suite, and made things far worse in some contrived scenarios.