Files
starcells e632fb4824 Rewrite the searcher: bit planes, and the last block searched backwards
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.
2026-11-05 23:35:56 +08:00
..