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

Well it’s not a grid! My chosen language does not have bitwise operators so it’s a bit slow. Have to resort to manual parallelization.

Ok it probably works because it isn’t bang center but a bit up of center, most other steps most be half half noise vertically, and the reason it doesn;t minimize on an earlier horizontal step (where every step is mostly half half), is because the middle points on the trunk, that don’t contribute to the overall product therefore minimizing it even lower.

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

#     Board size     # Our list of robots positions and speed #
[101,103] as [$W,$H] | [ inputs | [scan("-?\\d+")|tonumber] ] |

#     Making the assumption that the easter egg occurs when   #
#           When the quandrant product is minimized           #
def sig:
  reduce .[] as [$x,$y] ([];
    if $x < ($W/2|floor) and $y < ($H/2|floor) then
      .[0] += 1
    elif $x < ($W/2|floor) and $y > ($H/2|floor) then
      .[1] += 1
    elif $x > ($W/2|floor) and $y < ($H/2|floor) then
      .[2] += 1
    elif $x > ($W/2|floor) and $y > ($H/2|floor) then
      .[3] += 1
    end
  ) | .[0] * .[1] * .[2] * .[3];

#           Only checking for up to W * H seconds             #
#   There might be more clever things to do, to first check   #
#       vertical and horizontal alignement separately         #
reduce range($W*$H) as $s ({ b: ., bmin: ., min: sig, smin: 0};
  .b |= (map(.[2:4] as $v | .[0:2] |= (
    [.,[$W,$H],$v] | transpose | map(add) 
    | .[0] %= $W | .[1] %= $H
  ))) 
  | (.b|sig) as $sig |
  if $sig < .min then
    .min = $sig | .bmin = .b | .smin = $s 
  end | debug($s)
)

| debug(
  #    Contrary to original hypothesis that the easter egg    #
  #  happens in one of the quandrants, it occurs almost bang  #
  # in the center, but this is still somehow the min product  #       
  reduce .bmin[] as [$x,$y] ([range($H)| [range($W)| " "]];
    .[$y][$x] = "█"
  ) |
  .[] | add
)

| .smin + 1 # Our easter egg step

And a bonus tree:

Although saying “minimum” was a bit evil when all of the systems had exactly 1 solution (not necessarily in ℕ^2), I wonder if it’s puzzle trickiness, anti-LLM (and unfortunate non comp-sci souls) trickiness or if the puzzle was maybe scaled down from a version where there are more solutions.

If you somehow wanted your whole final array it would also require over 1 Peta byte ^^, memoization definetely reccomended.

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

last(limit(1+25;
  [inputs] | recurse(map(
    if . == 0 then 1 elif (tostring | length%2 == 1) then .*2024 else
      tostring | .[:length/2], .[length/2:] | tonumber
    end
  ))
)|length)

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

reduce (inputs|[.,0]) as [$n,$d] ({};     debug({$n,$d,result}) |
  def next($n;$d): # Get next           # n: number, d: depth  #
      if $d == 75                    then          1
    elif $n == 0                     then [1          ,($d+1)]
    elif ($n|tostring|length%2) == 1 then [($n * 2024),($d+1)]
    else #    Two new numbers when number of digits is even    #
      $n|tostring| .[0:length/2], .[length/2:] | [tonumber,$d+1]
    end;

  #         Push onto call stack           #
  .call = [[$n,$d,[next($n;$d)]], "break"] |

  last(label $out | foreach range(1e9) as $_ (.;
    # until/while will blow up recursion #
    # Using last-foreach-break pattern   #
    if .call[0] == "break" then break $out
    elif
      all( #     If all next calls are memoized        #
          .call[0][2][] as $next
        | .memo["\($next)"] or ($next|type=="number"); .
      )
    then
      .memo["\(.call[0][0:2])"] = ([ #                 #
          .call[0][2][] as $next     # Memoize result  #
        | .memo["\($next)"] // $next #                 #
      ] | add ) |  .call = .call[1:] # Pop call stack  #
    else
      #    Push non-memoized results onto call stack   #
      reduce .call[0][2][] as [$n,$d] (.;
        .call = [[$n,$d, [next($n;$d)]]] + .call
      )
    end
  ))
  # Output final sum from items at depth 0
  | .result = .result + .memo["\([$n,0])"]
) | .result

Mwahaha I’m just lazy and did are “unique” (single word dropped for part 2) of start/end pairs.

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

([
     inputs/ "" | map(tonumber? // -1) | to_entries
 ] | to_entries | map( # '.' = -1 for handling examples #
     .key as $y | .value[]
   | .key as $x | .value   | { "\([$x,$y])":[[$x,$y],.] }
)|add) as $grid | #           Get indexed grid          #

[
  ($grid[]|select(last==0)) | [.] |    #   Start from every '0' head
  recurse(                             #
    .[-1][1] as $l |                   # Get altitude of current trail
    (                                  #
      .[-1][0]                         #
      | ( .[0] = (.[0] + (1,-1)) ),    #
        ( .[1] = (.[1] + (1,-1)) )     #
    ) as $np |                         #   Get all possible +1 steps
    if $grid["\($np)"][1] != $l + 1 then
      empty                            #     Drop path if invalid
    else                               #
    . += [ $grid["\($np)"] ]           #     Build path if valid
    end                                #
  ) | select(last[1]==9)               #   Only keep complete trails
    | . |= [first,last]                #      Only Keep start/end
]

# Get score = sum of unique start/end pairs.
| group_by(first) | map(unique|length) | add