The BFS used to walk the whole 1<<CELL_SIZE table for every edge, keep the
states in an unordered_set and the parents in a second unordered_map. For
the six plane full adder layer 4 is 642729 states, and layer 5 never
finished (75s, heading for GBs).
A state is now CELL_SIZE bit planes, each a truth table over only the
inputs that influence the answer, so a state is CELL_SIZE * 2^K bits --
48 bits for every adder-shaped problem -- and a block is a handful of
64-bit ops. The instruction list also lost its duplicated encodings
(378 instead of 762 for six planes).
The bigger win is not expanding the last layer at all. A block clears its
own plane, so for the goal to be its target goal[s] must be 0; the
preimages of the goal under each such block are enumerated exactly and
looked up in the BFS table. For full_add that is 9.3e3 lookups instead of
7.4e9 edges, which turns "unreachable" into "5 blocks, proven shortest,
7 seconds".
Results (r8veritas<6>, max_depth 5, MSVC /O2):
copy 2 33 states
clb_and 3 3398
clb_half_add 4 32898
half_add 4 32898
full_add_S 4 656528
full_add_Co 5 20388515
full_add 5 20388515 7.2s
All of those lengths are proven minimal, and the old bit_raw_add needed
eight blocks for the same slice.
Richer instruction sets were tried as well -- per destination OR/XOR, and
adding set_0 on top (6144 blocks) -- and neither admits a four-block full
adder, so five is not an artifact of the model.
CELL_SIZE stays a template parameter; the truth table compression picks K
at run time and dispatches on it. CMake flags got the same fix as r8asm:
stop clobbering CMAKE_CXX_FLAGS so Debug keeps /RTC1 and MSVC keeps /EHsc.