Problem difficulty so far (up to day 16)

  1. Day 15 - Warehouse Woes: 30m00s
  2. Day 12 - Garden Groups: 17m42s
  3. Day 14 - Restroom Redoubt: 15m48s
  4. Day 09 - Disk Fragmenter: 14m05s
  5. Day 16 - Reindeer Maze: 13m47s
  6. Day 13 - Claw Contraption: 11m04s
  7. Day 06 - Guard Gallivant: 08m53s
  8. Day 08 - Resonant Collinearity: 07m12s
  9. Day 11 - Plutonian Pebbles: 06m24s
  10. Day 04 - Ceres Search: 05m41s
  11. Day 02 - Red Nosed Reports: 04m42s
  12. Day 10 - Hoof It: 04m14s
  13. Day 07 - Bridge Repair: 03m47s
  14. Day 05 - Print Queue: 03m43s
  15. Day 03 - Mull It Over: 03m22s
  16. Day 01 - Historian Hysteria: 02m31s
  • @swlabr
    link
    English
    3
    edit-2
    1 day ago

    17!

    p1 discussion

    Simultaneously very fun and also the fucking worst.

    Fun: Ooooh, I get to simulate a computer, exciting!

    Worst: Literally 8 edge cases where fucking up even just one can fuck up your hour.

    p2 discussion

    I did this by hand. sort of. I mean I didn’t code up something that found the answer.

    Basically I looked at the program in the input and wrote it out, and realised that A was essentially a loop variable, where the number of iterations was the number of octal digits A would take to represent. The most significant octal digits (octits?) would determine the tail end of the output sequence, so to find the smallest A you can do a DFS starting from the MS octit. I did this by hand.

    EDIT: code. Not gonna explain any of it.
    class Comp {
      List<int> reg;
      List<int> prog;
      int ip = 0;
    
      List<int> output = [];
      late List<(int, bool) Function()> ops;
    
      int get combo => prog[ip + 1] < 4 ? prog[ip + 1] : reg[prog[ip + 1] - 4];
    
      Comp(this.reg, this.prog) {
        ops = [
          () => (reg[0] = (reg[0] >> combo), false),
          () => (reg[1] ^= prog[ip + 1], false),
          () => (reg[1] = combo % 8, false),
          () => (reg[0] != 0) ? (ip = prog[ip + 1], true) : (0, false),
          () => (reg[1] ^= reg[2], false),
          () {
            output.add(combo % 8);
            return (0, false);
          },
          () => (reg[1] = (reg[0] >> combo), false),
          () => (reg[2] = (reg[0] >> combo), false)
        ];
      }
    
      compute() {
        output.clear();
        while (ip < prog.length) {
          if (!ops[prog[ip]]().$2) {
            ip += 2;
          }
        }
      }
    
      reset(int A) {
        ip = 0;
        reg[0] = A;
        reg[1] = 0;
        reg[2] = 0;
      }
    }
    
    void d17(bool sub) {
      List<String> input = getLines();
      Comp c = Comp(
          input.take(3).map((s) => s.split(" ").last).map(int.parse).toList(),
          input.last.split(" ").last.split(",").map(int.parse).toList())
        ..compute();
      print("Part a: ${c.output.join(",")}");
    
      if (!sub) return;
    
      List<int> sols = [];
      bool dfs(int cur) {
        bool found = false;
        sols.add(cur);
        int sol = sols.reduce((a, b) => 8 * a + b);
        c..reset(sol)..compute();
        if (c.prog
            .whereIndexed((i, e) => i >= c.prog.length - c.output.length)
            .foldIndexed(true, (i, p, e) => p && c.output[i] == e)) {
          if (found = c.output.length == c.prog.length) {
            print("Part b: $sol");
          } else {
            for (int i = 0; i < 8 && !(found = found || dfs(i)); i++) {}
          }
        }
    
        sols.removeLast();
        return found;
      }
    
      for (int a = 0; a < 8 && !dfs(a); a++) {}
    }
    
    
    • @geriksonOP
      link
      English
      31 day ago
      re: p1

      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.

    • @zogwarg
      link
      English
      3
      edit-2
      1 day ago

      EDIT: I have a sneaking suspicion that the computer will need to be re-used since the combo-operand 7 does not occur and is “reserved”.

      re p2

      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 #