Author: Marie Huynh
Submission in response to Challenge #1 on http://www.quora.com/challenges
This problem boils down to a Hamiltonian path counter for an undirected graph, with each node having a max of 4 edges in the 2-D grid. I achieved a runtime of about 2.03 seconds on a 1.6 GHz Pentium M for the given 7x8 grid. Run on a 2.53 GHz Intel Core 2 Duo:
$ time ./pathcounter < input/78.in
301716
real 0m0.958s
user 0m0.955s
sys 0m0.002s
The source can be found here and some of my more interesting test files can be found here. A tarball of everything can be found here.
Optimizations focused on improvements in algorithm more than the canonical C optimizations, as this is an exponential problem and pruning a single path early can cut vast swathes of useless plying. In fact, some of those optimizations done by hand conflict with -O2 and increase runtime.
The function explore() recursively searches for viable paths with checks that prune these cases:
Two dynamically allocated two dimensional arrays represent the rooms. The primary array keeps track of the current path being explored and has an extra one-room wide border on all sides (filled with 1s) to eliminate the need to check for overflow off the edges of the board; I make use of C's short- circuit evaluation to eliminate the need for a wider border. The floodfill functions use the second one to avoid repeated allocations when checking for impossible paths. Both are allocated once in main() and are [re]used as needed.
I implemented the check for disjoint sets with a floodfill-type algorithm. To reduce the cost of floodfills, I created three-point and two-point versions. Most cases require a two-point check, which searches starting from one side of the possible pinch-off point until it finds the other side (or runs out of accessible nodes to check). If the other side is not found, it is not in the same set, which means the search must backtrack to find another possible path. The three-point version is used for cases in which diagonal blocks could divide the remaining rooms into three disjoint sets with the addition of a proposed room. Instead of using the two-point module twice, which might have a large overlap in areas checked, the three-point version keeps track of what points have been found and continues until it verifies that all three points are in the same set or has exhausted all nodes in the starting set. The two-point version could have been absorbed into the three- point version but redundant checks would have made it less efficient.
A full path is determined to have been found when the depth of rooms searched matches the total number of rooms. The check for cutoff of the exit ensures that so long as a full path has not been found, there will be at least one empty space next to the exit, as that is necessary for the completion of a path.
The formation of 1-wide corridors is prevented by not allowing moves in a direction that would create an adjacent, parallel pit that is 1 room wide and 2 rooms deep. Single-room pits are fine only so long as they are filled in immediately after formation, as there are no viable paths that can fill the pit in later. This check for corridors does not ensure that the pit will be filled in however, so a complementary check ensures the only options are to fill in the pit or backtrack.
In the end, I decided it was worth sacrificing a small amount of time for the sake of robustness in checking inputs, freeing mallocs, etc.
For larger grids, it may be worth scanning the board for islands, caves, and other features of the terrain that would determine what other modifications to the search would be productive. For a sufficiently large board, the exploration of a smaller area (such as a cave with a 2-wide opening) may be precomputed if these features are commonly found and all paths need to start/end at that opening. This can potentially save a lot of time.
In the current state of the program, there are some cases that are not checked for due to the overhead possibly overshadowing the gains for smaller boards. This likely includes the currently unimplemented check for bottlenecked pockets of rooms that are still connected, but only by one room and do not contain the exit, which means they can not be entered and backed out of to continue looking for the exit. The checks for the 1-room wide corridors can ensure that those are not created from the beginning, but it is not possible to check for these bottlenecks until they are formed. If such pockets are created but not explored immediately, time can be wasted as the rest of the board is explored despite there being no solutions that can come of this exploration. For smaller boards, the formation of the pocket doesn't leave much space in the rest of the board that would unnecessarily be explored, but for larger boards, many more pockets can happen, and with much more dead space left to explore. Checking for this can be done by sealing off the neck and checking for connectivity, which I'd probably do by floodfilling. A smarter algorithm might check for even/odd paths into a space without the exit, and backtrack when it finds an odd number, but again, it's overkill for this problem.
The full wet grid is reinitialized every time before it is used, but if the area that is used for floodfill is a small portion of the full grid, we can use the locations saved in floodedge[] to clear only what was used.
Reordering the pruning checks based on the pruning probability will result in fewer evaluations of conditionals.
The location of the proposed room is passed to the floodfill functions but wouldn't be necessary if it's marked off on the main board and unmarked when backtracking, but it is unclear if this change has any effect on runtime. Changing this would make the functions more versatile and usable for the bottleneck check, but the functions that call them a lot would be messier.
currx+/-1 and curry+/-1 are used often enough in some functions that it may be worth calculating them once instead of each time while indexing. I'm not sure if -O2 takes care of that or if the precomputed values can chill in registers without being pushed into cache. Recomputing is sometimes faster than pulling precomputed things out of the cache so this this is a fairly low priority item since it's not obvious if this will do any good.
1.6.1
