• 2 Posts
  • 58 Comments
Joined 1 year ago
cake
Cake day: July 4th, 2023

help-circle
  • Hacky Manual parallelization

    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 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;
    
    ( # 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/22-b.jq input.txt \
    # --argjson s 10 --argjson i {} > out-{}.json'
    # cat out-*.json | ./2024/22-b.jq --argjson group true
    # rm out-*.json
    #
    # Speedup from naive ~50m -> ~3m
    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
    



  • Day 14, got very lucky on this one, but too tired to think about why part 2 still worked.

    spoiler
    #!/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:




  • Day 11

    Some hacking required to make JQ work on part 2 for this one.

    Part 1, bruteforce blessedly short
    #!/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)
    
    Part 2, some assembly required, batteries not included
    #!/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
    



  • re:10

    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
    


  • Day 8

    Al lot of grid index shuffling these past few days! Not too difficult yet though, will this year be gentler or much harsher later?

    Part 2 code in JQ
    #!/usr/bin/env jq -n -R -f
    
    [ inputs / "" ] | [.,.[0]|length] as [$H,$W] |
    
    #----- In bound selectors -----#
    def x: select(. >= 0 and . < $W);
    def y: select(. >= 0 and . < $H);
    
    reduce (
      [
        to_entries[] | .key as $y | .value |
        to_entries[] | .key as $x | .value |
        [ [$x,$y],. ]  | select(last!=".")
      ] | group_by(last)[] # Every antenna pair #
        | combinations(2)  | select(first < last)
    ) as [[[$ax,$ay]],[[$bx,$by]]] ({};
      # Assign linear anti-nodes #
      .[ range(-$H;$H) as $i | "\(
        [($ax+$i*($ax-$bx)|x), ($ay+$i*($ay-$by)|y)] | select(length==2)
      )"] = true
    ) | length