this post was submitted on 16 Dec 2024
12 points (100.0% liked)

NotAwfulTech

386 readers
4 users here now

a community for posting cool tech news you don’t want to sneer at

non-awfulness of tech is not required or else we wouldn’t have any posts

founded 1 year ago
MODERATORS
 

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
you are viewing a single comment's thread
view the rest of the comments
[–] [email protected] 3 points 5 days ago* (last edited 5 days ago) (2 children)

17!

p1 discussionSimultaneously 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 discussionI 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++) {}
}

[–] [email protected] 3 points 5 days ago* (last edited 5 days 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 p2Also 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 #

load more comments (1 replies)