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@awful.systems
    link
    fedilink
    English
    arrow-up
    0
    ·
    edit-2
    5 days 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.

    • zogwarg@awful.systems
      link
      fedilink
      English
      arrow-up
      0
      ·
      5 days ago
      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 #
      
    • gerikson@awful.systemsOP
      link
      fedilink
      English
      arrow-up
      0
      ·
      5 days 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.