Expand description
§Radioisotope Thermoelectric Generators
Solves using a BFS from the starting position where each next state is the possible elevator moves either one floor up or down. This was faster than using A* with a heuristic.
A huge critical optimization is the observation that generator and chip pairs are fungible.
A configuration that starts with two pairs on floor one takes the same number of steps to
solve whether pair A or pair B is moved first (that is, the setup [-;-;AG,AM;BG,BM] while on
floor 2 is indistinguishable from [-;-;BG,BM;AG,AM] on floor 2 in terms of the final result).
However, the relative positions of pairs still matter (the setup [AM;AG;BG;BM] on floor two
can move BG up or down; but the setup [AM;BG;AG;BM] on floor two can only move AG up). To
maximize state sharing, represent each pair’s generator and microchip position as hex
digits, but merge all permutations by sorting those hex digit pairs during the hash
function. Including the elevator position, the hash value requires up to 30 useful bits
(2 + 7*4) if densely packed, although this uses a 64-bit struct with one-hot encodings.
Next, observe that adding a chip and generator pair on floor 1 adds 12 moves to the final solution; likewise, removing a pair from floor 1 (but only if there is still something else left on the floor) can be solved in 12 fewer moves. Tracking a smaller number of chip and generator pairs, then adjusting by the 12 times the number of ignored pairs, is inherently faster.
The rules for a valid floor are either:
- Any amount of microchips only with no generators.
- Any microchip on a floor with at least one generator must have its own generator on that floor.
This allows us to efficiently memoize previously seen states and reject any that we’ve seen before extremely quickly. Other optimizations:
- If we can move 2 items up, then skip only moving 1 item up.
- If we can move 1 item down, then skip moving 2 items down.
- Moving a microchip and generator together is only safe if they are the same type (if they are not from the same type, then the old floor will necessarily have the generator that pairs with the chip being moved, leaving that chip to be fried on its new floor).
- If floor 1 is empty then don’t move items back down to it, similarly if both floor 1 and floor 2 are empty then don’t move items to them.