AoC 2024, day 11 (dc)

# Command: echo 75 | dc -finput -fdc-p12.dc

?st

[ 1+        ] s+    # increment
[ *1+ q     ] sZ    # return(1): clear frame (depth==0) * value + 1
[ _4R++s. q ] sM    # return(memo), clear frame (three items)

[ +s. A0 0  ] sH    # replace hashes with impossible ones (no hash ends in two 0s)


# Even (stack: value depth-1 hash)
[
    dZ 2/Ar^        # 10^(len(value)/2) value depth-1 hash
    ~               # rhs lhs depth-1 hash
    3Rd             # depth-1 depth-1 rhs lhs hash
    3R r lRx        # recurse(depth-1 rhs) depth-1 lhs hash
    _3R             # tuck result
    lRx             # recurse(depth-1 lhs) result-rhs hash
    +               # result-sum hash
    d 3R:m q        # memo(hash)=result, return result
] sE

# recurse: depth value -> count
[
    d 0=Z           # return (1) if (depth == 0)

    d1-3Rd          # value value depth-1 depth
    A0*4R+          # hash=100*value+depth value depth-1

    dd 9d^<H        # cancel hash if > max; stack: hash-write hash-read value depth
                    # max hash is actually 2^31 - 1, 9d^ is short and big enough

    _4R             # tuck hash-write
    ;m d0<M         # memo check hash-read; return if in memo

                    # stack: 0 value depth-1 hash-write
    r dZ2% 3R=E     # if (0==len(value)%2) do Even; stack: value depth-1 hash

    2024*           # 2024*value depth-1 hash
    d 0=+           # 2024*value|1 depth-1 hash
    r lRx           # recurse(depth-1 2024*value|1) hash
    d 3R:m          # memo(hash)=rec; stack: rec (return value)
] sR

0                   # sum=0 input1 input2 ...
[
    r
    lt lRx+          # sum += recurse(25, input1) input2 ...

    z1<L
] dsLx

p