Advent of Code, Day 9 part 1, handcoded in brainfuck

day9a.b

[day9a.b -- 2022 Advent of Code Day 9 Part 1
(c) 2022 Daniel B. Cristofani
http://brainfuck.org/
This program is licensed under a Creative Commons Attribution-ShareAlike 4.0
International License (http://creativecommons.org/licenses/by-sa/4.0/).]

[This program solves Advent of Code 2022, Day 9, Part 1.
(https://adventofcode.com/2022/day/9/)

Basic data layout is, roughly:
0 0 X x X x y y y y 0 0 0 0 0 0 0 0 0 H D C N n N n S S? S? 0 0 0 z z z z

We maintain a list of 4-byte numbers representing locations of T. Left two bytes
of each are vertical coordinate, most significant byte to left; right two bytes
are horizontal coordinate. Coordinates increase down and right. We keep this
list sorted in descending order. This program firmly assumes cells are bytes.

We place one border value of (65280,65280) at the left end, then an arbitrary
starting value of (768,768); the implicit right border of (0,0) doesn't need
initializing. We keep a moving window of 22 cells in the middle of the list, to
do calculations in. At any time, the y cells (the number just left of the
window) are the "current" location of T.

H is a value from 1 to 9 representing the current location of H relative to T.
D is the direction to move in, and C is the count of how many more times we need
to move H in that direction. I represent these with capital letters to note that
they can be relied on to be nonzero when navigating past our chunk of data.

After getting D and C from each line of input, we (C times) use D and H as
inputs into a hardcoded table: for each of the 36 combinations, this produces
a new value for H, a direction to move T in (if it needs to move), and also
restores the value of D.

The direction to move T in is a value from 0 to 10 in a custom encoding:
  5  4  6
  1  0  2
  9  8 10
The merit of this is that if we break this down in binary, it decomposes into
four booleans for the different components of movement, making it easy to update
T. Of course, if it's 0 then T doesn't need changing and we can skip to the next
movement of H. If we are updating T, we can also easily figure out which
direction we'll need to scan, to find where to insert the new T into the list.

If we are updating T, we copy the current T from the Y cells into the N cells,
increment or decrement the coordinates as needed, and then set up a little call
stack using the S cells. This technique of using a simple call stack to save
code duplication is explained at http://brainfuck.org/function_tutorial.b .
Here we use it for the code to insert the new T in the right place in the list.

Most of these functions are fairly straightforward, and several just call other
functions. All of them use a stack frame consisting only of their own numerical
identifier, except the "process results" functions 4 and 5, which use a frame of
(1 4) and (1 5); the 1 is to receive a return value from function 3 (comparison)
which may set it to 2 or 3 depending whether y or n is greater.

This program has not been obsessively optimized for concision, and could surely
be made much shorter.]

>>->>->>+++>>+++> >>>>>>>>>>+++++>>,[initialize; while a line of input:
  <,++[>--<-]+>[<+>--------[<+>------[<+>---]]] get direction: D1 L2 R3 U4
  >,----------[++<----[>++++++++++<-]>[<+>-],----------]<[get count; while count
    <-[<+++++++++>-]combine direction and H to compute new H and update for T
    +<<++++>-[<+>-[<+>-[<+>-[<+>-[<+>-[<<+++++++++>->-[<<->>-[<<++>>-[
    <<----->---->>+<-[<<[-]>--->-[<+>-[<<+>++>-[<<->>-[<+>-[<<+++++++++>->-[
    <<[-]>+++>-[<+>-[
    <[-]++>>+<-[<+>-[<<++++++>+++>-[<<[-]>->-[<+>-[<<++>>-[<<-->++>-[<+>-[
    <<++++++++++>--->-[
    <<----->---->>+<-[<<->>-[<<++>>-[<<[-]>->-[<+>-
    ]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]<[>+<-]<[ if T needs updating
      <<<++++[ copy current (Y) to make new N (next T)
        -<<<<<[>>>>+<<<<-]>>>>[<<<<+>>>>>>>>>>>>>>>>+<<<<<<<<<<<<-]>[<+>-]<
      ]>>>>>>>[[<]++[->]<] break down update of T into tasks
      <[->>++>>>>>>>[-<[<<]>]<[->-<[<<]]] decrement horiz
      <[->>>+>>>>>>>+[<[<<]]<[+[<<]<]] increment horiz
      <[->>>>[-]++>>>>>[-<[<<]]<[->-<[<<]<]<] decrement vert
      <[->>>>>[-]+>>>>>+[<[<<]]<[+[<<]<]<<] increment vert
      >>>>>[>>>>>>>>+<<<<<<<<-]>[[>]>]<< move scan direction to stack
      [ while function on stack
        >+<-[-[-[-[-[-[-[-[-[- skip to the appropriate function     
        >10  wipe new and terminate
          -<<[-]<[-]<[-]<[-]>
        ]>[9  place new as Y and terminate
          -<++++[-<[<<<<<<<<<<<<<<<<+>>>>>>>>>>>>>>>>-]>[<+>-]<]>>
        ]<]>[8 move data right and move right (Z) to become current (Y)      
          ->>>++++[->[<<<<<<<<<<<<<<<<<<<<<<+>>>>>>>>>>>>>>>>>>>>>>-]<[>+<-]>]
          <<<<<<<<<[[[>>>>+<<<<-]<]<]>>>>>>>[>>]
        ]<]>[7 move data left and current (Y) to right (Z)
          -<<[[<]<]>>[[[<<<<+>>>>-]>]>]<<<<<<[[<]<]
          <<<++++[-<[>>>>>>>>>>>>>>>>>>>>>>+<<<<<<<<<<<<<<<<<<<<<<-]>[<+>-]<]
          >>>>>>>>>[[>]>]
        ]<]>[6 move right half of list right to make room for new value
          ->>>[>>]<<[[>>>>+<<<<-]>[>>>>+<<<<-]<<<]<
        ]<]>[5 process results (scanning right)
          ->+<<<--[-[++>]>] switch/case based on comparison results
          >[-<<<++++++++++>] 1 (new equals current)
          >[-<<<++>++++++++>] 3 (new greater than current)
          >[-<<<+++>++++>+++++++>] 2 (new less than current; tricky shortcut)
          <<[>]>
        ]<]>[4 process results (scanning left)
          ->+<<<---[+[+>]>] switch/case based on comparison result
          >[-<<<++++++++++>] 1 (new equals current)
          >[-<<<+>+++++++>] 2 (new less than current)
          >[++[<<<+++>++>++>-]<<++>>] 3 (new greater than current)
          <<[>]>        
        ]<]>[3 comparison
          -<<<[<<]<+<+<+<+[for up to 4 bytes
            -<<<<<<<<[>>>>>+<+<<<<-]>>>>[<<<<+>>>>-]copy pair of bytes
            >>>>>>>>>>>>[<<<<<<<<<<+>>+>>>>>>>>-]<<<<<<<<[>>>>>>>>+<<<<<<<<-]
            <<[<[->]<]compare
            >>[[-]>>>[->]>>>>>>>>+[<<]<] N greater than Y
            <<<[[-]>>>>[->]>>>>>>>>++[<<]<<<<]>>>> Y greater than N
          ]>>[>>]>
        ]<]>[2 scan right
          <+>++++>+++>>
        ]<]>[1 scan left
          <+>+++>+++>>
        ]<<
      ]<<<<< end while function on stack
    ]>>>>- end if T changed
  ]<[-]>, end (while num)
]end while input
>>>>>>>>>>>[>>]+[count locations: for each value back to start:
  <<[-]>>-[[-] clear space; if not 0 (data gap)    
    >>>>>>+[[-]+>>---------[++++++++++<<[<<<<]-<<]>>+]<<increment
  ]>>+[>>[<<<<+>>>>-]>>]<<<<-<<<<[<<<<]<<+ move count left 4 cells
]>>>>++>>-----[>>>>]+[+++++[<<++++++++>>-]<<.<<] output count