22-b.jq

Massive time gains with parallelization + optimized next function (2x speedup) by doing the 3 xor operation in “one operation”, Maybe I prefer the grids ^^:

#!/usr/bin/env jq -n -f

#────────────────── Big-endian to_bits ───────────────────#
def to_bits:
  if . == 0 then [0] else { a: ., b: [] } | until (.a == 0;
      .a /= 2 |
      if .a == (.a|floor) then .b += [0]
                          else .b += [1] end | .a |= floor
  ) | .b end;
#────────────────── Big-endian from_bits ────────────────────────#
def from_bits: [ range(length) as $i | .[$i] * pow(2; $i) ] | add;

( # Get index that contribute to next xor operation.
  def xor_index(a;b): [a, b] | transpose | map(add);
  [ range(24) | [.] ]
  | xor_index([range(6) | [-1]] + .[0:18] ; .[0:24])
  | xor_index(.[5:29] ; .[0:24])
  | xor_index([range(11) | [-1]] + .[0:13]; .[0:24])
  | map(
      sort | . as $indices | map(
        select( . as $i |
          $i >= 0 and ($indices|indices($i)|length) % 2 == 1
        )
      )
    )
) as $next_ind |

# Optimized Next, doing XOR of indices simultaneously a 2x speedup #
def next: . as $in | $next_ind | map( [ $in[.[]] // 0 ] | add % 2 );

#  Still slow, because of from_bits  #
def to_price($p): $p | from_bits % 10;

# Option to run in parallel using xargs, Eg:
#
# seq 0 9 | \
# xargs -P 10 -n 1 -I {} bash -c './2024/jq/22-b.jq input.txt \
# --argjson s 10 --argjson i {} > out-{}.json'
# cat out-*.json | ./2024/jq/22-b.jq --argjson group true
# rm out-*.json
#
# Speedup from naive ~50m -> ~1m
def parallel: if $ARGS.named.s and $ARGS.named.i  then
   select(.key % $ARGS.named.s == $ARGS.named.i)  else . end;

#════════════════════════════ X-GROUP ═══════════════════════════════#
if $ARGS.named.group then

# Group results from parallel run #
reduce inputs as $dic ({}; reduce (
      $dic|to_entries[]
  ) as {key: $k, value: $v} (.; .[$k] += $v )
)

else

#════════════════════════════ X-BATCH ═══════════════════════════════#
reduce (
  [ inputs ] | to_entries[] | parallel
) as { value: $in } ({};  debug($in) |
  reduce range(2000) as $_ (
    .curr = ($in|to_bits) | .p = to_price(.curr) | .d = [];
    .curr |= next | to_price(.curr) as $p
    | .d = (.d+[$p-.p])[-4:]  | .p = $p # Four differences to price
    | if .a["\($in)"]["\(.d)"]|not then # Record first price
         .a["\($in)"]["\(.d)"] = $p end # For input x 4_diff
  )
)

# Summarize expected bananas per 4_diff sequence #
| [ .a[] | to_entries[] ]
| group_by(.key)
| map({key: .[0].key, value: ([.[].value]|add)})
| from_entries

end |

#═══════════════════════════ X-FINALLY ══════════════════════════════#
if $ARGS.named.s | not then

#     Output maximum expexted bananas      #
to_entries | max_by(.value) | debug | .value

end

It took me too long to read the prompt and see that without the shortcuts, it’s a single path. I wasted too much time on search algorithms.

P1: Here’s what I did: Walk the path. Every time you hit a new grid, check if the two shortcuts you can take will save you 100 ps.

To calculate the shortcut saving:

If you index every grid position on the main path from 0, then it takes X ps to reach position X, The time it takes to travel from start to X, then a shortcut to Y, then from Y to the end, is X + 1 + (main path length - Y). The time saved is then just Y - X - 1, modulo maybe like 5 fence post errors.

P2. The prompt wasn’t really clear about whether or not cheating meant you can only travel through one set of walls before your cheat ends, or if it meant you could just move through walls for 20ps to wherever you could reach. Turns out, it’s the latter.

The above formula is then a special case of Y - X - manhattan distance(X, Y).

What is this, day 16?

Also did this by hand to get my precious gold star, but then actually went back and implemented it Some JQ extension required:

#!/usr/bin/env jq -n -rR -f

#─────────── Big-endian to_bits and from_bits ────────────#
def to_bits:
  if . == 0 then [0] else { a: ., b: [] } | until (.a == 0;
      .a /= 2 |
      if .a == (.a|floor) then .b += [0]
                          else .b += [1] end | .a |= floor
  ) | .b end;
def from_bits:
  { a: 0, b: ., l: length, i: 0 } | until (.i == .l;
    .a += .b[.i] * pow(2;.i) | .i += 1
  ) | .a;
#──────────── Big-endian xor returns integer ─────────────#
def xor(a;b): [a, b] | transpose | map(add%2) | from_bits ;

[ inputs | scan("\\d+") | tonumber ] | .[3:] |= [.]
| . as [$A,$B,$C,$pgrm] |


# Assert  #
if  [first(
        range(8) as $x |
        range(8) as $y |
        range(8) as $_ |
        [
          [2,4],  # B = A mod 8            # Zi
          [1,$x], # B = B xor x            # = A[i*3:][0:3] xor x
          [7,5],  # C = A << B (w/ B < 8)  # = A(i*3;3) xor x
          [1,$y], # B = B xor y            # Out[i]
          [0,3],  # A << 3                 # = A(i*3+Zi;3) xor y
          [4,$_], # B = B xor C            #               xor Zi
          [5,5],  # Output B mod 8         #
          [3,0]   # Loop while A > 0       # A(i*3;3) = Out[i]
        ] | select(flatten == $pgrm)       #         xor A(i*3+Zi;3)
      )] == []                             #         xor constant
then "Reverse-engineering doesn't neccessarily apply!" | halt_error
 end |

#  When minimizing higher bits first, which should always produce   #
# the final part of the program, we can recursively add lower bits  #
#          Since they are always stricly dependent on a             #
#                  xor of Output x high bits                        #

def run($A):
  # $A is now always a bit array                    #
  #                 ┌──i is our shift offset for A  #
  { p: 0, $A,$B,$C, i: 0} | until ($pgrm[.p] == null;

    $pgrm[.p:.p+2] as [$op, $x]       | # Op & literal operand
    [0,1,2,3,.A,.B,.C,null][$x] as $y | # Op &  combo  operand

    # From analysis all XOR operations can be limited to 3 bits  #
    # Op == 2 B is only read from A                              #
    # Op == 5 Output is only from B (mod should not be required) #
      if $op == 0 then .i += $y
    elif $op == 1 then .B = xor(.B|to_bits[0:3]; $x|to_bits[0:3])
    elif $op == 2
     and $x == 4  then .B = (.A[.i:.i+3] | from_bits)
    elif $op == 3
     and (.A[.i:]|from_bits) != 0
                  then .p = ($x - 2)
    elif $op == 3 then .
    elif $op == 4 then .B = xor(.B|to_bits[0:3]; .C|to_bits[0:3])
    elif $op == 5 then .out += [ $y % 8 ]
    elif $op == 6 then .B = (.A[.i+$y:][0:3] | from_bits)
    elif $op == 7 then .C = (.A[.i+$y:][0:3] | from_bits)
    else "Unexpected op and x: \({$op,$x})" | halt_error
    end | .p += 2
  ) | .out;

[ { A: [], i: 0 } | recurse (
    #  Keep all candidate A that produce the end of the program,  #
    #  since not all will have valid low-bits for earlier parts.  #
    .A = ([0,1]|combinations(6)) + .A | # Prepend all 6bit combos #
    select(run(.A) == $pgrm[-.i*2-2:] ) # Match pgrm from end 2x2 #
    | .i += 1
    # Keep only the full program matches, and convert back to int #
  ) | select(.i == ($pgrm|length/2)) | .A | from_bits
]

| min # From all valid self-replicating intputs output the lowest #

I literally created different test inputs for all the examples given and that found a lot of bugs for me. Specifically the difference between literal and combo operators.

DFS (it’s all dfs all the time now, this is my life now, thanks AOC) pruned by unless-I-ever-passed-through-here-with-a-smaller-score-before worked well enough for Pt1. In Pt2 in order to get all the paths I only had to loosen the filter by a) not pruning for equal scores and b) only prune if the direction also matched.

Pt2 was easier for me because while at first it took me a bit to land on lifting stuff from Djikstra’s algo to solve the challenge maze before the sun turns supernova, as I tend to store the paths for debugging anyway it was trivial to group them by score and count by distinct tiles.