Implementation notes There is a software solution to every annoyance. ---------------------------------------------------------------------- 0. Concept I found this flash-based sliding block puzzle game via some BBS one day. It's a variation of the "Hakoiri Musume" puzzle, also known as Klotski. I have seen puzzles like this before, but this one has a theme to it -- every block was a picture of some person, and the largest 2x2 block was this girl. The story was something like "free the girl" or "kidnap the girl". Of course it must have been the latter, because after wasting a bit of time solving this puzzle, it then turned into this interactive rape-the-girl-with-crazy-tentacles thing. And it complained to me that my solution was not optimal. I was pretty disappointed... when somebody complains that a solution obtained via human brute-force effort as non-optimal, I feel that it's begging me to do a software solution. Oh, the tentacle thing was disappointing too. Not quite related to tentacles, recently I have been hearing quite a bit about language X (for some value of X) being the successor of C++. Some proponents even went as far as saying X is the successor to C, which annoyed me to no ends. I mean, C++ succeeds C, and C++0x follows C++. Of all the contenders who claims to eclipse C++, at least "D" has both a familiar syntax and a familiar name, and not this "language X" that I shall not name. Determined to solve both annoyances at once, I set out to write some D code to solve these sliding block puzzles once and for all. ---------------------------------------------------------------------- 1. Puzzle solver My method of solving the puzzle is very straightforward -- examining what I have been doing to reach the tentacles bit, I see that I was basically doing backtracking: there are only so many blocks that can be shifted at any one time. If I reached either a dead-end or some previously seen configuration after shifting some blocks, I undo all the moves until I reach a point where there are multiple possible blocks to shift, and shift a different block that wasn't tried before. Doing the above as a human takes a long time because we are easily confused at the recurring block configurations. Computers will not be confused, so I wrote a version that did the same backtracking thing that I was doing, and this got me a solution quickly -- the code was trivial to implement, and the program terminated in a very short time. Unfortunately, the solution here wasn't optimal either. There are often multiple ways to reach the same configuration of blocks, and there is no telling that this backtracking algorithm will use the minimum number of moves to get there. But this is easily fixed by an updated algorithm that uses breadth-first search instead of depth-first search: Let a "node" be a block configuration state. Let queue = [starting node] while queue is not empty: pop the next node off the queue. If this node is the solution state, print path up to this node. Find all neighbors to this node, where a neighbor is another node that is reachable by shifting one block. Push all neighbors onto the queue To record the solution path, every time we push a neighbor node onto the queue, we store a pointer back to the current node. So when the solution node is reached, we follow those pointers back to the starting node, and output the intermediate nodes backwards. ---------------------------------------------------------------------- 2. Implementation Implementing this in D was fairly straightforward. After all, it's just like C++, although some of the pointer/reference differences took a bit of getting used to. The end result was a new disappointment though, it was just too slow. Profiling showed that associative arrays were slow, but I didn't feel like rewriting it. So then, I ported the D implementation to C++. The code size was about the same, but the executable was 3 times smaller and the binary runs 10 times faster. So much for that. See, there is C++, and everything else is just disappointing tentacles. ---------------------------------------------------------------------- 3. Layout At this point, I have decided to use Victorique (from the anime/manga/novel GOSICK) as the layout. I figured it's a fitting character for a puzzle solver. But then an idea came to mind... A lot of people have asked how I made these ASCII art programs, and I have always answered "I just type those things out in vi. Except the Perl ones." Even though there is a bit of method to making ASCII art, there really is very little automation to it. Most people don't believe me of course. Having solved two annoyances, I figured I might as well go for three. After I wrote the C++ solver above, I took a few months of break to write a VIM plugin for recording editing sessions, and a corresponding program for converting those recorded logs to JavaScript-embedded HTML for playback. The end result is here: http://uguu.org/arc_homura.html It really was a few months of break, GOSICK has long completed the TV broadcast during that time, and C++0x has been unanimously approved by the standards committee (maybe it should be called C++11 now?) And I have tested Homura with a few long text editing sessions, including ICFP 2011. Convinced that the tools are now all in good shape, I set out to do my ASCII art thing. The end result is edit.html ---------------------------------------------------------------------- 4. Finally... Victorique solved all my recent and not so recent annoyances :) Until next time...