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

NotAwfulTech

385 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
top 20 comments
sorted by: hot top controversial new old
[–] [email protected] 1 points 3 days ago (3 children)

22!

spoilers!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.

[–] [email protected] 3 points 3 days ago

so many off by one errors

also first time I had to run the code on a desktop machine because my VPS was too slow

[–] [email protected] 2 points 2 days ago* (last edited 2 days ago)

22-2 commentaryI got a different solution than the one given on the site for the example data, the sequence starting with 2 did not yield the expected solution pattern at all, and the one I actually got gave more bananas anyway.

The algorithm gave the correct result for the actual puzzle data though, so I'm leaving it well alone.

Also the problem had a strong map/reduce vibe so I started out with the sequence generation and subsequent transformations parallelized already from pt1, but ultimately it wasn't that intensive a problem.

Toddler's sick (but getting better!) so I've been falling behind, oh well. Doubt I'll be doing 24 & 25 on their release days either as the off-days and festivities start kicking in.

[–] [email protected] 2 points 3 days ago* (last edited 3 days ago) (1 children)

Hacky Manual parallelization22-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

[–] [email protected] 2 points 2 days ago* (last edited 2 days ago) (1 children)

If nothing else, you've definitely stopped me forever from thinking of jq as sql for json. Depending on how much I hate myself by next year I think I might give kusto a shot for AOC '25

[–] [email protected] 1 points 2 days ago

That's still mostly what it is ^^, though I'd say it's more "awk+sed" for JSON.

[–] [email protected] 3 points 4 days ago

21 (wip)

2 meme 2 memeious

[–] [email protected] 3 points 5 days ago (2 children)

20: currently a WIP but:

memeWait, so it’s all grids? 🧑🏿‍🚀🔫🧑🏿‍🚀

[–] [email protected] 5 points 5 days ago (1 children)

Skipping this for now, there are only so many grid maps I can take.

[–] [email protected] 4 points 5 days ago

Understandable, have a nice day

[–] [email protected] 3 points 5 days ago

ok discoIt took me too long to read the prompt and see that without the shortcuts, it's a single path. I wasted too much time on search algorithms.

P1: Here's what I did: Walk the path. Every time you hit a new grid, check if the two shortcuts you can take will save you 100 ps.

To calculate the shortcut saving:

If you index every grid position on the main path from 0, then it takes X ps to reach position X, The time it takes to travel from start to X, then a shortcut to Y, then from Y to the end, is X + 1 + (main path length - Y). The time saved is then just Y - X - 1, modulo maybe like 5 fence post errors.

P2. The prompt wasn't really clear about whether or not cheating meant you can only travel through one set of walls before your cheat ends, or if it meant you could just move through walls for 20ps to wherever you could reach. Turns out, it's the latter.

The above formula is then a special case of Y - X - manhattan distance(X, Y).

[–] [email protected] 3 points 6 days ago* (last edited 6 days ago)

Day 19! (the cuervo gold....)

disc and codeOk so my path to this answer was circuitous and I now hate myself a little.

P1: Ok, a repeated dfs on suffixes. that shouldn't be too hard. (it was not hard)

P2: Ok, a repeated dfs is a little too slow for me, I wonder how I can speed it up?

forgets about memoisation, a thing that you can do to speed this sort of thing up

I guess the problem is I'm doing an O(mn) match (where m is the number of towels, n is the max towel length) when I can do O(n). I'll build a prefix tree!

one prefix tree later

Ok that still seems to be quite slow. What am I doing wrong?

remembers that memoisation exists

Oh I just need to memoise my dp from part 1. Oops.

Anyway posting the code because I shrunk it down to like two semicolons worth of lines.

(

List<String> input = getLines();
Set<String> ts = Set.from(input.first.split(', '));
Map<String, int> dp = {};

int dpm(String s) => dp.putIfAbsent(
    s,
    () => s.isNotEmpty
        ? ts
            .where((t) => t.matchAsPrefix(s) != null)
            .map((t) => dpm(s.substring(t.length)))
            .fold(0, (a, b) => a + b)
        : 1);

void d19(bool sub) {
  print(input
      .skip(2)
      .map((s) => dpm(s))
      .map((i) => sub
          ? i
          : i > 0
              ? 1
              : 0)
      .reduce((a, b) => a + b));
}

[–] [email protected] 4 points 1 week ago (2 children)

16!

p1I used A*, though mathematically I would have been fine with Dijkstra's. Also, here's how I remember how to spell Dijkstra: ijk is in alphabetical order.

p2If you've implemented path/back tracking on a search algo before, this wasn't too bad, though instead of tracking best parent you need to track equivalently best parents. Woke AOC trying to normalise families with more than two parents, SMH

[–] [email protected] 3 points 1 week ago

16 commentaryDFS (it's all dfs all the time now, this is my life now, thanks AOC) pruned by unless-I-ever-passed-through-here-with-a-smaller-score-before worked well enough for Pt1. In Pt2 in order to get all the paths I only had to loosen the filter by a) not pruning for equal scores and b) only prune if the direction also matched.

Pt2 was easier for me because while at first it took me a bit to land on lifting stuff from Djikstra's algo to solve the challenge maze before the sun turns supernova, as I tend to store the paths for debugging anyway it was trivial to group them by score and count by distinct tiles.

[–] [email protected] 3 points 1 week ago

Fun fact, dijk means dike (the land/water barrier) in Dutch.

[–] [email protected] 4 points 1 week ago (1 children)

day 18

bit of a breather episode

As long as you ensure A* / Dijkstra's (is there a functional difference if the edge weights are constant?) you'll get the shortest path. Part 2 was just simulation for me, if I started in the state of part 1 it took a minute to run through the rest of the bytes.

[–] [email protected] 2 points 1 week ago

yesWhat is this, day 16?

[–] [email protected] 3 points 1 week ago* (last edited 1 week 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 1 week 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.

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