1046fbae45 2012-07-16 kinaba: -------------------------------------------------------------------------------- 3e683f8768 2012-07-14 kinaba: Team: 3e683f8768 2012-07-14 kinaba: Dark Integers 1046fbae45 2012-07-16 kinaba: 6293256fec 2012-07-14 kinaba: Member: dbff34ac59 2012-07-14 kinaba: Kazuhiro Inaba (www.kmonos.net / kiki@kmonos.net) 1046fbae45 2012-07-16 kinaba: 1046fbae45 2012-07-16 kinaba: Programming Language: dbff34ac59 2012-07-14 kinaba: D Programming Language (dlang.org) 1046fbae45 2012-07-16 kinaba: -------------------------------------------------------------------------------- 1046fbae45 2012-07-16 kinaba: 1046fbae45 2012-07-16 kinaba: Three types of solvers are combined. 1046fbae45 2012-07-16 kinaba: 1046fbae45 2012-07-16 kinaba: 1. Solver "Forest" 1046fbae45 2012-07-16 kinaba: It does breadth first search every turn for taking the game's dynamism 1046fbae45 2012-07-16 kinaba: into account. Basically it tries to rush to the nearest lambda or open 1046fbae45 2012-07-16 kinaba: lift, but if there is no route found, it tries other various options. 1046fbae45 2012-07-16 kinaba: Pushing rocks, digging earth around rocks, wait a while... 1046fbae45 2012-07-16 kinaba: It is slow, but relatively more clever. 1046fbae45 2012-07-16 kinaba: 1046fbae45 2012-07-16 kinaba: 2. Solver "Wind" 1046fbae45 2012-07-16 kinaba: It does breadth first search and memorize the computed path. As far as 1046fbae45 2012-07-16 kinaba: possible, it tries to follow the precomputed route. If some obstacle is 1046fbae45 2012-07-16 kinaba: found, it redoes the BFS. It is dumb but fast. So it is used for large 1046fbae45 2012-07-16 kinaba: maps. 1046fbae45 2012-07-16 kinaba: 1046fbae45 2012-07-16 kinaba: 3. Solver "Fire" 1046fbae45 2012-07-16 kinaba: It is a kind of "higher-order" solver, that takes another solver and 1046fbae45 2012-07-16 kinaba: creep into it to make it more careful. Precisely speaking, this higher 1046fbae45 2012-07-16 kinaba: order solver runs the subsolver as a 10-20 step lookahead. While no 1046fbae45 2012-07-16 kinaba: problem is found in the lookahed, it behaves exactly as same as the 1046fbae45 2012-07-16 kinaba: sub solver. If there was a problem (i.e., subsolver dead or stuck), 1046fbae45 2012-07-16 kinaba: it tries all the possible perturbations to the lookahead window, and 1046fbae45 2012-07-16 kinaba: re-runs subsolvers many times and chooses the best one. 1046fbae45 2012-07-16 kinaba: 1046fbae45 2012-07-16 kinaba: Fire<Forest> is used for W*H<=1600 instances. Fire<Wind> is used for any 1046fbae45 2012-07-16 kinaba: instances. For smaller maps, the better result of the two is used as the 1046fbae45 2012-07-16 kinaba: final output. In addition, all these outputs are guarded by a sentinel 1046fbae45 2012-07-16 kinaba: who aborts by force the output sequence at the best score position (so 1046fbae45 2012-07-16 kinaba: that left-over run does not make the score worse). 1046fbae45 2012-07-16 kinaba: 1046fbae45 2012-07-16 kinaba: 6293256fec 2012-07-14 kinaba: 1046fbae45 2012-07-16 kinaba: For the added features, not quite much effort is paid. So if there came a 1046fbae45 2012-07-16 kinaba: map that fully exploits the characteristics of the gadgets, I'll lose :(. 6293256fec 2012-07-14 kinaba: 1046fbae45 2012-07-16 kinaba: Flood: 1046fbae45 2012-07-16 kinaba: Almost nothing is done for it. The "fire" solver locally takes care 1046fbae45 2012-07-16 kinaba: of it, and it is inclided to use "U" during perturbation. Also, "wind" 1046fbae45 2012-07-16 kinaba: solver's BFS is made to like "U" direction in larger maps. 1046fbae45 2012-07-16 kinaba: Trampoline: 1046fbae45 2012-07-16 kinaba: Just treated as one BFS edge. 1046fbae45 2012-07-16 kinaba: Beard: 1046fbae45 2012-07-16 kinaba: No clue. If there is nothing else to do, goes to the place where many 1046fbae45 2012-07-16 kinaba: Wadler's are around, and uses the shaver. 1046fbae45 2012-07-16 kinaba: Higher-order Rocks: 1046fbae45 2012-07-16 kinaba: Tries to push them somehow randomly. 6293256fec 2012-07-14 kinaba: 1046fbae45 2012-07-16 kinaba: 6293256fec 2012-07-14 kinaba: 1046fbae45 2012-07-16 kinaba: Thanks for organizing the contest! I've enjoyed!