day 2

::: spoiler perl

#!/usr/bin/env perl

use strict;
use warnings;
use v5.010;
use List::Util qw/ max /;

# Parse the input

my %games = ();

for my $line (<>) {
    $line =~ /Game (\d+): (.+)/;
    my $game_id = $1;
    my $game_str = $2;

    my @segments = split '; ', $game_str;
    my @game = ();
    for my $segment (@segments) {
        my @counts = split ', ', $segment;

        my %colors = (red => 0, blue => 0, green => 0);
        for my $count (@counts) {
            $count =~ /(\d+) (\w+)/;
            $colors{$2} = $1;
        }

        push @game, { %colors };
    }

    $games{$game_id} = [ @game ];
}

# Part 1

my $part1 = 0;

game: for my $game_id (keys %games) {
    for my $segment (@{$games{$game_id}}) {
        next game if $segment->{red} > 12 || $segment->{green} > 13 || $segment->{blue} > 14;
    }

    $part1 += $game_id;
}

say "Part 1: $part1";

# Part 2

my $part2 = 0;

for my $game (values %games) {
    my ($red, $green, $blue) = (0, 0, 0);

    for my $segment (@$game) {
        $red = max $segment->{red}, $red;
        $green = max $segment->{green}, $green;
        $blue = max $segment->{blue}, $blue;
    }

    $part2 += $red * $green * $blue;
}

say "Part 2: $part2";

:::

Found this much easier than day 1 honestly...

lemme is an incredibly hungry little shit, it eats so much

// Where we're going we won't need regexes.

fuck yes

Perl: https://github.com/gustafe/aoc2023/blob/main/d01-Trebuchet.pl

::: spoiler thoughts

I found this really tough for a day 1 problem. Because I don't really know regex, I did not know the secret to finding overlapping patterns. I quickly figured out that "twone" was a possibility, because it was in the example, but then I had to find other examples and hardcode them into my split pattern.

This isn't general, my input doesn't have 'sevenine' for example.

:::

Nice, I’ll be reading :D

(Possibly have some dart coming up on a thing soon)

::: spoiler 1 a,b: as a professional software engineer, I know that googling regex syntax and getting it right will take longer than manually writing string comparisons, so... here's all you need to see of my final solution.

  int? check3(String line, int index) {
    if (line.length < index + 3) {
      return null;
    }

    String sub = line.substring(index, index + 3);
    return sub == "one"
        ? 1
        : sub == "two"
            ? 2
            : sub == "six"
                ? 6
                : null;
  }

:::

::: spoiler 4 a Not so bad today. I bit the bullet and tried to see if dart has tuples or similar. It does, by the name of "records". Now instead of pretending I'm writing in C/C++, I can pretend I'm writing in python.

Anyway, a) is a pretty straightforward job-interview style question, except AoC doesn't care about efficiency. Still, we all have our own versions of pride, so I did it with a set (Though whether or not dart's native Set is tree or hash based is not known to me right now).

:::

::: spoiler code

int matches(String line) {
  ({List wn, List n}) card = getNumbers(line);
  Set wn = Set.from(card.wn);

  return card.n.fold(0, (prev, e) => prev + (wn.contains(e) ? 1 : 0));
}

void day4a(List lines) {
  print(lines.fold(0, (acc, line) {
    int m = matches(line);
    return acc + (m != 0 ? (1 << (m - 1)) : 0);
  }));
}

:::

::: spoiler 4b b) was a little harder, and definitely a possible trap for overthinking. I think the easiest way to think about solving this is as if it is a dynamic programming problem (though it kinda isn't).

So the general approach is to formulate it like this:

T_n(total cards won by card n) = M_n(total matches for card n) + CW_n(total cards won by the copies that card n wins).

and

CW_n =

• 0 if M_n = 0
• sum of T_i, where i = n + 1 ... n + M_n

Caching T_n is the DP trick to making this performant (though once again, it does not need to be)

Anyway, the above approach is the top-down version of the DP; the bottom-up version is what I actually started with in my head. I gave up on that approach because I felt like the logic was too hard for me to figure out. ::: ::: spoiler code:

void day4b(List lines) {
  List totalMatches = lines.map((e) => matches(e)).toList();

  // total copies won, including copies won from copies.
  List cachedWins = List.filled(totalMatches.length, -1);
  int totalWins(int i) {
    // return cached result if it exists
    if (cachedWins[i] > 0) {
      return cachedWins[i];
    }

    int count = totalMatches[i];
    // count the copies won from the subsequent copied cards
    for (int j = 1; j <= totalMatches[i]; j++) {
      count += totalWins(i + j);
    }

    // cache the result
    cachedWins[i] = count;
    return count;
  }

  int totalCards = totalMatches.length; // count all the originals
  // count all the wins
  for (int i = 0; i < totalMatches.length; i++) {
    totalCards += totalWins(i);
  }
  print(totalCards);
}

:::

::: spoiler 3 a I read this wrong initially and thought that you only needed to check adjacency on the same line. Whoops! Then I wrote a bad algorithm that finds numbers THEN searches for symbols. That alg isn't inherently bad, except... :::

::: spoiler 3 b If I had chosen a symbol first approach, I would not have had as much pain as I did here. Also, I probably under and overthought this one. I went with my first idea, which was guaranteed to work.

The approach this time was:

1. iterate through the characters to find a * symbol
2. Search the characters around it for a digit.
3. Get the value of the number associated with that digit by searching backwards until you find the start of a number
4. Use union-find to track whether or not you've seen this number before (because you can't assume that the same value is the same number)

A simpler approach would consider that you only have two numbers on the same line for the same gear if the character in the gear column is a non-digit; otherwise, if a number is adjacent to a gear, there is only one on that row. Union-find is completely overkill, but I like using it even when I don't need to.

Anyway, upon reflecting on this, while the general approach is fine, I didn't think too hard about the implementation and just ended up with globs of overly memoized spaghetti. I probably should check if Dart has a python-like tuple object or similar. Whatever. Behold!

void day3s() {
  List lines = [
    for (String? line = stdin.readLineSync();
        line != null;
        line = stdin.readLineSync())
      line
  ];

  List> digs = [for (int i = 0; i < lines.length; i++) Map()];
  int? isDigitMem(int r, int c) {
    return digs[r].putIfAbsent(c, () => isDigit(lines[r][c]));
  }

  // first entry is parentc, second is size
  List>> uf = List.generate(
      lines.length, (i) => List.generate(lines[0].length, (j) => [j, 1, -1]));

  int find(int r, int c) {
    if (uf[r][c][0] != c) {
      uf[r][c][0] = find(r, uf[r][c][0]);
      return uf[r][c][0];
    }
    return uf[r][c][0];
  }

  void union(int r, int cp, int c) {
    cp = find(r, cp);
    c = find(r, c);

    if (c == cp) {
      return;
    }

    if (uf[r][cp][1] >= uf[r][c][1]) {
      uf[r][c][0] = cp;
      uf[r][cp][1] += uf[r][c][1];
    } else {
      uf[r][cp][0] = c;
      uf[r][c][1] += uf[r][cp][1];
    }
  }

  int stoi(int row, int col) {
    int acc = 0;
    for (int i = col; i < lines[0].length; i++) {
      int? d = isDigitMem(row, i);
      if (d != null) {
        acc = (acc * 10) + d;
        union(row, col, i);
      } else {
        break;
      }
    }
    return acc;
  }

  int? stoiSearch(int row, int col) {
    assert(row >= 0 && col >= 0 && row < lines.length && col < lines[0].length);
    if (isDigitMem(row, col) == null) {
      return null;
    }
    int i = col - 1;
    while (i >= 0) {
      if (isDigitMem(row, i) == null) {
        return stoi(row, i + 1);
      }
      i--;
    }
    return stoi(row, 0);
  }

  List> s2i = [for (int i = 0; i < lines.length; i++) Map()];
  int? stoiSearchMem(int row, int col) {
    return s2i[row].putIfAbsent(col, () => stoiSearch(row, col));
  }

  int count = 0;
  for (int i = 0; i < lines.length; i++) {
    for (int j = 0; j < lines[0].length; j++) {
      if (lines[i][j] != "*") {
        continue;
      }

      List gearVals = List.empty(growable: true);
      for (int x = -1; x <= 1; x++) {
        if (i + x < 0 || i + x > lines.length) {
          continue;
        }

        Set parents = {};
        for (int y = -1; y <= 1; y++) {
          if (j + y < 0 || j + y > lines[0].length) {
            continue;
          }

          int? cur = stoiSearchMem(i + x, j + y);

          int parent = find(i + x, j + y);
          if (parents.contains(parent)) {
            continue;
          }

          parents.add(parent);

          if (cur != null) {
            gearVals.add(cur);
          }
        }
      }

      if (gearVals.length == 2) {
        count += gearVals[0] * gearVals[1];
      }
    }
  }

  print(count);
}

:::

::: spoiler 2 a,b: This one is just a test of whether or not your language lets you split strings.

Only novel thing I did here was recognise that red, green and blue end in different letters, so no need to string match the whole world, just check the last letter of the colour. :::

7 Camel Cards

::: spoiler a, b I decided to write some classes and enums for this, which paid off a little in part b) when I could reuse most of my code. :::

::: spoiler 6 a,b Very easy today. You don't need any programming to solve this; it's a series of inequalities. That said, the brute force calculation is fast enough if you don't want to think and is quite honestly faster than solving this mathematically.

So that being said, here's the mathematic solution:

The inequality to solve is just: x = time holding the button

x^2 - tx + d < 0

which occurs when x is between (t/2) +/- (t^2 - 4d). The total ways are the total integers between those two numbers, exclusive.

Writing that all in code is a little tricky thanks to int/double rounding/truncation intricacies, so the brute force solution is "better". :::

1. Not my best work. No code in this comment, just check 5.dart if you want to see it in the github repo linked above.

::: spoiler General I used a class this time because it looked like it might be helpful. I don't think it turned out to be that useful. Still, you can see Dart's interesting constructor and getter syntax on display. :::

::: spoiler a. Pretty straightforward, though I didn't read the format correctly and had the destination/source data reversed. Oops! Luckily, my performance here will in no way affect my future career. :::

::: spoiler b. I didn't read the prompt correctly, which tripped me up. Also, while my solution is correct, it assumes that the input could be trickier than what the problem threw at me. Specifically, the edge case I had in mind was a range of values split into many subintervals and needing to track those mappings. I threw in some print statements to discover that intervals were never split beyond two subintervals, which was disappointing. Oh well- being correct is the best feeling you can have if you are otherwise empty inside.

Other than processing the input in the form of intervals, I don't think there were any notable tricks at play here, so this was more of an exercise in implementing code cleanly, which I struggle with. :::

8

::: spoiler Hint for b The brute solution will take ~100 hours on my machine. You will need (to fudge) some very basic number theory to make it faster. :::

::: spoiler a A straightforward implementation of the traversal was sufficient for performant code. :::

::: spoiler b As suggested by the hint, I tried running the brute force solution. The pseudocode is something like this:

count = 0
while(all ghosts not on endpoint):
   for (all ghosts):
    move ghost to next node
  count++

print count

I put a timestamp for every 100mil iterations, which ticked once every two seconds.

So, how do we solve it? As mentioned in my hint, some fudged number theory is required.

Long story short, each ghost will eventually reach an end node. They could reach K endpoints, where K is the total number of end nodes available. They will follow the same path in a loop if they traverse infinitely.

The fudge is this: assume each ghost only hits one end node repeatedly. In this case, the solution is just the LCM of the number of steps it takes for each ghost to reach its end node from the initial state.

If given a case where a ghost hits multiple unique endpoints, you can probably find the configuration of counts and LCMs to yield the smallest one, but that proof is left to the reader.

The answer that I got was in the magnitude of 10 trillion, close to 20 trillion. :::

9

::: spoiler a,b This was another implementation exercise, i.e., can you implement this algorithm as specified? So pretty easy. a) took me about 30 minutes or so to code up, b) took like a minute after that since the problem is so similar.

Interestingly, the problem itself is based on a method for finding closed-form general formulae for progressions of integers. You can use it to develop a formula for sums of squares, cubes, quartics etc. or any progression that doesn't seem to have an obvious closed form.

Anyway, there is probably a language where this problem can be solved with a one-liner, I got kinda close, see 9.dart. Check the commits if it's unreadable. :::

Perl solution, nothing special: https://github.com/gustafe/aoc2023/blob/main/d02-Cube-Conundrum.pl

Historically problems on Sat/Sun have been more challenging than weekdays. However given that the first 7 days are usually “warmup” problems, I’d say this years edition of AoC is more challenging than at least since 2019.

I liked today's puzzle. It was meaty but not frustrating.

::: spoiler discussion In retrospect that would have been far better for runtime, my dist function ended up being a tad expensive.

I substituted the rows/columns, with multiplication by the expansion rate if they were all numbers. And then for each galaxy pair do a running sum by going “down” the “right” and adding the distance for each row and column crossed.

https://github.com/zogwarg/advent-of-code/blob/main/2023/jq/11-b.jq

transpose is nice to have in that approach. :::

How about not fiddling with indices?

::: spoiler JQ Notfiddlingwithindexification https://github.com/zogwarg/advent-of-code/blob/main/2023/jq/14-a.jq

#!/usr/bin/env jq -n -R -f

# Dish to grid
[ inputs / "" ]

# Tilt UP
| transpose                       # Transpose, for easier RE use
| map(                            #
  ("#" + add) | [                 # For each column,   replace '^' with '#'
    scan("#[O.]*") | [            # From '#' get empty spaces and 'O' rocks
      "#", scan("O"), scan("\\.") # Let gravity do it's work.
    ]                             #
  ] | add[1:]                     # Add groups back together
 )                                #
| transpose                       # Transpose back

# For each row, count  'O'  rocks
| map(add | [scan("O")] | length)

# Add total load on "N" beam
| [0] + reverse | to_entries
| map( .key * .value ) | add

:::

Similarly tired with index fiddling, I was pretty happy with my approach, which led to satisfying transpose cancelling in part 2. Not the fastest code out there, but it works. Day 14 was actually my favorite one so far ^^.

Happy holidays!

Happy holidays to you too! I decided this morning that I'm not gonna work myself up missing days, so they are on hold until after xmas for me!

Get well soon!

I believe you've posted in the wrong thread. This is the awful systems thread, not the awesome systems thread.

Cleaned up version of code used to solve part 2 in jq.

::: spoiler Spoiler code section

#!/usr/bin/env jq -n -R -f

# Get LR instructions
( input / "" | map(if . == "L" then 0 else 1 end )) as $LR |
( $LR | length ) as $l |

# Make map {"AAA":["BBB","CCC"], ...}
(
  [
    inputs | select(.!= "") | [ scan("[A-Z]{3}") ] | {(.[0]): .[1:]}
  ] | add
) as $map |

# List primes for GCM test / factorization
[
  2, 3, 5, 7, 11, 13, 17, 19,
  23, 29, 31, 37, 41, 43, 47,
  53, 59, 61, 67, 71, 73, 79,
  83, 89, 97
] as $primes |

reduce (
  $map | keys[] | select(test("..A")) | { s: 0, i: 0, c: .} |

  # For each "..A" starting position
  # Produce visited [ "KEY", pos mod $l ], until loop is detected
  until (.i as $i | .[.c] // [] | contains([$i]);
    .s as $s | .i as $i | .c as $c        |
    $map[$c][$LR[$i]] as $next            | # Get next KEY
    .[$c] = (( .[$c] // [ $s ] ) + [$i] ) | # Append ( .s ≡ $l ) to array for KEY (first = .s non mod)
    .s = ( $s + 1 )  | .i = (.s % $l )    | # Update cursors, for next iteration
    .c = $next
  )
  | .[.c][0] as $start_loop_idx | (.s - $start_loop_idx) as $loop_size
  | [ to_entries[] | select(.key[-1:] == "Z") ]
  | if (
      length != 1                                           # Only one ..Z per loop
      or ( .[0].value[0] != $loop_size )                    # First ..Z idx = loop size
      or ( [ .[0].value[0] / $l ] | inside($primes) | not ) # loop_size = ( prime x $l )
      or ( .[0].value[0] / $l  > $l )                       # GCM(loop_sizes) = $l
    ) then "Input does not fit expected pattern" | halt_error else
      # Under these conditions, synched positions of ..Zs happen at:
      # LCM = Π(loop_size_i / GCM) * GCM

      # loop_size_i / GCM
      .[0].value[0] / $l
    end
) as $i (1; . * $i)

# Output LCM = first step where, all ghosts are on "..Z" nodes
| . * $l

:::

::: spoiler spoiler DP to me is when you use memoisation and sometimes recursion and you want to feel smarter about what you did.

I also struggle to think of the need for DP, even in a more “elegant” approach. Maybe if you wanted to do an O(n) memory solution instead of n^2, or something. Not saying this out of derision. I do like looking at elegant code, sometimes you learn something.

I feel like there’s an unreadable Perl one line solution to this problem, wanna give that a go, @gerikson? :::

okay yeah so

p1 part 1 submitted, runs fine. part 2 says "wrong answer for you but right for someone else". doing a debug-print-everything run on the intermediate stages of the data after my regex all seems correct, but it's also 23h50 and it's been a looooong week. so I guess I'll take a look a fresh look at that one in the morning over coffee

part1, badly:

::: spoiler spoiler

import re

pattern = '\d'
cmp = re.compile(pattern)

# extremely lazy, of the ungood kind
datapath = 'data'
lines = open(datapath, 'r').read().split('\n')
candidates = []
values = []
for l in lines:
    if l != '':
        r = cmp.findall(l)
        candidates.append(r)
        values.append(int(''.join([r[0], r[-1]])))

print(candidates)
print(values)
print(sum(values))

:::

(I really wasn't kidding about the badly)

part2:

::: spoiler spoiler missed the eightwo case

changes:

mapping = {...} # name/int pairs
pattern = f'(?=(\d|{"|".join(mapping.keys())}))'
lines = open(datapath, 'r').read().split('\n').remove('')
values = []
for l in lines:
    r = cmp.findall(l)
    equivs = [str(mapping.get(x, x)) for x in r]
    head, tail = [equivs[0], equivs[-1]]
    values.append(int(f"{head}{tail}"))
print(sum(values))

:::

This is the hardest problem of the year so far, based on leaderboard completion times. I'm busy wrapping up work for this year, and looking for a new job, so this will have to be put on the TODO pile

Only solved by receving heavy hints from other's solution, and it still took me forever. By far the hardest this year.

Update on B:

::: spoiler still no solve, however Through glancing at someone else's code, I was inspired to just try simulating the A problem beyond 64 steps and seeing the result.

Essentially it reaches a (bi stable?) steady state between two numbers, which makes sense- if you can only make single rook steps, then the reachable squares will alternate every cycle.

Don't know if I'll try solve this again tonight but mentally I have now understood the solution. :::

Update to the update: now fully recovered, I am now trying to finish the last problems.

Solved 21 B!

::: spoiler I spent way too much time on this but it’s fine So my approach to AOC has always been to write a pure coding solution, which finally broke down here.

First, the solve:

I call the unrepeated garden map the “plot”. Each repetition of the plot I call a “grid”. Hope that isn’t confusing.

1. Looking at the input data, it is a grid of 131x131 squares with the starting position in the center at 66,66 (indexed from 1)
2. If you imagine a chessboard pattern over the whole area, on each step the possible reachable squares alternate colors.
3. Row 66 and col 66 are unimpeded by stones, as well as the edges of each grid. This means that:

• starting from the initial grid, it takes 66 steps to enter a new grid. You enter a new grid on all sides.
• a grid is always initially entered from the middle of an edge, either on one or two sides based on its position relative to the grids that are currently being considered.
• each grid is independent of every other grid, except for the step where it is entered.

To see why that last point is true, consider that in order for another grid A to influence an adjacent grid B beyond the moment the adjacent grid is entered, there must be a reachable point further from the midpoint of the edge on the edge of A. However, because the middle row and column are free from rocks, this is never the case. Any influence from A reaches B too late, i.e. reachable squares on B from A will be reachable sooner from just travelling from the entry point on B.

1. The number of steps is 131x100x2023 + 65.

So putting all this together, the way I got the answer was like this:

1. Simulate the whole area for 65 + (5*131) steps (more than necessary)
2. Print the number of reachable squares in the grid at 65 + 131n for n = 0-5
3. Using pen and paper, determine some coefficients for some of the numbers that come up, add everything up in a calculator, and type that answer into AOC.

So I guess the answer I arrived at was what I’d been thinking I should be doing this whole time: a mix of simulating some of the problem and a decent amount of pen and paper work to get the solution out, rather than just pure coding. Fun! :::

::: spoiler a,b a: Just copied what I did for 10 b. and applied it to work here. Had to fiddle with it to make it work, but it worked. I implemented a line-crossing counting algorithm. If you slice up the area into rows, you can tell if you are inside the area if you cross an odd number of lines that vertically cross that row.

b. Pretty much just changed the input parsing and ran the same algorithm. Thought that it might be too slow, but I put in some stopwatch ticks and found out that it should take about 5 minutes to run my a) algorithm to get the answer.

The actual time elapsed was 5m50s.

I miiiiight try make a faster version but my head is too fucked up to care right now, hence me letting the slow algorithm run. :::

11 ::: spoiler a,b a: So, I've been in the habit of skipping the flavour text and glossing over the prompt. This time, it hurt me badly.

I read the problem as follows: for N galaxies, find N/2 pairings such that the sum of distances is minimal.

At this point, I was like, wow, the difficulty has ramped up. A DP? That will probably run out of memory with most approaches, requiring a BitSet. I dove in, eager to implement a janky data structure to solve this humdinger.

I wrote the whole damn thing. The bitset, the DP, everything. I ran the code, and WOAH, that number was much smaller than the sample answer. I reread the prompt and realised I had it all wrong.

It wasn't all for naught, though. A lot of the convenience stuff I'd written was fine. Also, I implemented a sparse parser, which helped for b.

b: I was hoping they were asking for what I had accidentally implemented for a. My hopes were squandered.

Anyway, this was pretty trivial with a sparse representation of the galaxies. :::

::: spoiler a,b, not much to say The hardest part has finding the right dart ascii library to use (by default dart treats everything as UTF-16, which is horrible for this sort of thing) and the right data structure (linked hash map, which is a map that remembers insertion order.) :::

1. After this problem, I will create a new reply in the OP if it is not there already, and will discuss under that thread.

::: spoiler a,b So, like many other problems from this year, this is one of those direct solution problems where there isn't much of a neat trick to getting the answer. You just have to implement the algorithm they specify and hope you can do it correctly.

a) I used a regex to do some parsing because I haven't looked at dart regex much and wanted to dip my toes a little.

I considered doing this "properly" with OO classes and subclasses for the different rules. I felt that it would be too difficult and just wrote something janky instead. In hindsight, this was probably the wrong choice, especially since grappling with all the nullable types I had in my single rule class became a little too complex for my melting brain (it is HOT in Australia right now; also my conjunctivae are infected from my sinus infection. So my current IQ is like down 40 IQ points from its normal value of probably -12)

b) There may have been a trick here to simplify the programming (not the processing). Again, I felt that directly implementing the specified algorithm was the only real way forward. In brief:

1. Start with an "open" set containing a part with 4 ranges from [1, 4001) and an "accepted" set that is empty.
2. Start at the workflow "in"
3. For each rule in the current workflow:

• If the rule accepts part of the ranges in the open set, remember those ranges in a closed set and remove them from the open set.
• Remove anything the rule rejects from the open set.
• If the rule redirects to a different workflow W, split off the applicable ranges and recurse at 3 with the current workflow as W.
• Keep in the open set anything the rule doesn't consider.

Because this is AOC, I assumed that the input would be nice and wouldn't have anything problematic like overlapping ranges, and I was right. I had a very stupid off by one error that took me a while to find as well. :::

The code I have up as of this comment is pretty long and boring, I might try clean it up later.

1. I have contracted some kind of sinus infection, so rn I have a -20 IQ debuff.

::: spoiler a,b part a: nothing to say here.

part b: Before diving into the discussion, I timed how long 1000 cycles takes to compute, and apparently, it would take 1643175 seconds or just over 19 days to compute 1 billion cycles naively. How fun!

So, how do you cut down that number? First, that number includes a sparse map representation, so you can tick that box off.

Second is intuiting that the result of performing a cycle is cyclical after a certain point. You can confirm this after you've debugged whatever implementation you have for performing cycles- run it a few times on the sample input and you'll find that the result has a cycle length of 7 after the second interaction.

Once you've got that figured out, it's a matter of implementing some kind of cycle detection and modular arithmetic to get the right answer without having to run 1000000000 cycles. For the record, mine took about 400 cycles to find the loop. :::

17, We’re in the back third now, folks! ::: spoiler a, b A and B were roughly the same difficulty.

So in my first year in university, in my intro DSA class, we learned A*. Have I learned any other ways to search since? Not really. So I used A* here.

It took way longer than it should have to solve, which I blame on my ongoing illness. The main sticking point was that I implemented a class to represent the search state, and since I was going to use it as a key to a map, I implemented a hashcode for it. The rest of the A* code freely flowed from my brain (really the wikipedia pseudocode).

Cue like 40 mins plus of wondering how the test input was searching over millions of states, wondering if I’d fucked up the A* implementation, wondering if the problem was too big for A*, and wondering if it was finally time to take a days break from all the aoc nonsense.

Anyway at some point I realised I forgot to implement the corresponding equals method to my hashcode. Once I had that my code ran in seconds and everything was fine. This sickness is the worst!!! :::

12

::: spoiler a,b Finally! a Dee Pee!!!

This problem was mainly testing:

• Are you a bad enough dude to formulate this DP correctly?
• Are you a bad enough dude to choose a good DP state storage schema?
• Is your computer a bad enough dude to store all the DP states if you choose a bad storage schema?

...which is true of all DP problems, honestly. So given you know and understand how to approach DP problems, this would be more an engineering issue than anything. :::

::: spoiler 16 So, as I've been doing the AoC things, I've been creating small libraries of convenience functions to reuse, hopefully. This time, I reused some things I wrote for problem 10, which was vindicating.

a. was a fun coding exercise. Not much more to say.

b. I lucked out by making a recursive traversal function for a), which let me specify the entry and direction of where my traversal would start. Besides that, similar to a., this was a fun coding exercise. I was surprised that my code (which just ran the function from a) on every edge tile) It only took 2s to run; I thought I might need to memoize some of the results. :::

10! ::: spoiler a, b a was relatively straightforward - again, an implementation test.

b was interesting- luckily, I remembered how to test if a point lives inside a curve. The line-crossing count algorithm was a little tricky to write from scratch, but I finally got there. Also, I screwed up for like an hour when I didn't realise you were supposed to count junk pipes as part of the territory. Code wise it got messy, and I've thrown something up on my github, but might try clean it up a little later. :::

::: spoiler a,b a. while you can brute force this one in time, one simple trick to make it faster is to treat the symbols as bits and interpret the grid as numbers. It then becomes a matter of locating the reflection point.

b. It's not much of a difference to solve b. The trick here is that if you did the bit stuff I suggested above, you'd quickly realise that a smudge interpreted as a binary number is a power of two. Finding a smudge is equivalent to if the bitwise XOR of two numbers is a power of 2, which can be done with some bitwise magic. :::

I'm having a hard time modeling the network at the moment, there's too much shit to keep track of. Objects might be the solution!

::: spoiler [Language: jq] https://github.com/zogwarg/advent-of-code/blob/main/2023/jq/20-b.jq

Completed when waiting for the second leg of my Christmas holidays flight. (It was a long wait, can I blame jet-lag?).

Have a more compact implementation of LCM/GCD, something tells me it will come in handy In future editions. (I’ve also progressively been doing past years)

:::

No-one should begrudge or judge you for taking a day off.

I liked the slight trickiness of part 2, that the naive implementation would never complete in time.

As always doing a JQ implementation:

::: spoiler Part 1

#!/usr/bin/env jq -n -R -f

# Get seeds
input | [ match("\\d+"; "g").string | tonumber ] as $seeds |

# Collect maps
reduce inputs as $line ({};
  if $line == "" then
    .
  elif $line | test(":") then
    .k = ( $line / " " | .[0] )
  else
    .[.k] += [[ $line | match("\\d+"; "g").string | tonumber ]]
  end
)

# For each map, apply transformation to all seeds.
# seed -＞ ... -＞ location
| reduce ( to_entries[] | select(.key != "k") .value) as $map ({s:$seeds};
  .s[] |= (
    # Only attempt transform if element is in one of the ranges
    [ . as $e | $map[] | select(. as  [$d,$s,$l] | $e ＞= $s and $e ＜ $s + $l) ] as $range |
    if ($range | length ) ＞ 0 then
      $range[0] as [$d,$s] |
      . - $s + $d
    else
      .
    end
  )
)

# Get lowest location
| .s | min

Some comments:

• A nice use of input first to get the seeds, then inputs to get remaining lines. :::

::: spoiler Part 2

#!/usr/bin/env jq -n -R -f

# Utility function
def group_of($n):
  ( length / $n ) as $l |
  . as $arr |
  range($l) | $arr[.*$n:.*$n+$n]
;

# Get all seed ranges
input | [ match("\\d+"; "g").string | tonumber ] | [group_of(2)] as $seeds |

# Collect maps
reduce inputs as $line ({};
  if $line == "" then
    .
  elif $line | test(":") then
    .k = ( $line / " " | .[0] )
  else
    .[.k] += [[ $line | match("\\d+"; "g").string | tonumber ]]
  end
)

# For each map, apply transformation to all seeds ranges.
# Producing new seed ranges if applicable
# seed -＞ ... -＞ location
| reduce (to_entries[] | select(.key != "k") .value) as $map ({s:$seeds};
  .s |= [
    # Only attempt transform if seed range and map range instersect
    .[] | [.[0], add, .[1] ] as [$ea, $eb, $el] | [
      $map[] | select(.[1:] | [.[0], add ] as [$sa,$sb] |
        ( $ea ＞= $sa and $ea ＜ $sb ) or
        ( $eb ＞= $sa and $eb ＜ $sb ) or
        ( $sa ＞= $ea and $sa ＜ $eb )
      )
    ] as $range |
    if $range | length ＞ 0 then
      $range[0] as [$d,$s,$l] |
      # ( only end ) inside map range
      if $ea ＜ $s and $eb ＜ $s + $l then
        [$ea, $s - $ea], [$d, $eb - $s ]
      # ( both start, end ) outside map range
      elif $ea ＜ $s then
        [$ea, $s - $ea], [$d, $l], [ $s + $l, $eb ]
      # ( only start ) inside map range
      elif $eb ＞ $s + $l then
        [$ea + $d - $s, $l - $ea + $s ], [$s + $l, $eb - $s - $l]
      # ( both start, end ) inside map range
      else
        [$ea + $d - $s , $el]
      end
    else
      .
    end
  ]
)

# Get lowest location
| [.s[][0]] | min

Some comments:

• Since iterating across all seeds naively would take forever, iterating over seed ranges instead.
• It's nice that JQ can neatly produce extra elements: [1,2,3] | [ .[] | if . == 2 then . * 10 + 1 , . * 10 + 2 else . end ] -> [1, 21, 22, 3]
• There is probably a more compact way of expressing all the conditions and produced outputs. :::

Replaced less-than (and greater-than for symmetry) symbols with full-width version, since lemmy apparently doesn't handle them well within a code block: replacing less than with &lt;

I have to punt on part 2 for now, generally shitty day precludes fun coding.

Update done, nothing special

https://github.com/gustafe/aoc2023/blob/main/d05-If-You-Give-A-Seed-A-Fertilizer.pl

congrats! I have officially checked out of the competition for the time being. Maybe if I get some spare energy later.

What problem had you stumped?

Comments and code: https://github.com/gustafe/aoc2023/tree/main#day-7-camel-cards

nice cleanser after yesterday

::: spoiler spoiler it would have taken me longer to figure out the algebra than to just mush the inputs together and get the solution that way (16s runtime) :::

::: spoiler Nice! Also, kudos for working with polygon area from the start. I was too invested in reusing my code as discussed elsewhere, but I came around in the end. :::

19 was a real pain in dart.

My part b code ran slower :(

A nice workaround to jq single threadedness, since this is maq reduce and safe to parallelize. 17m10s -> 20s !!! ::: spoiler Spoiler link to commit. https://github.com/zogwarg/advent-of-code/commit/fef153411fe0bfe0e7d5f2d07da80bcaa18c952c :::

Not really spoilery details: Revolves around spawing mutiple jq instances and filtering the inputs bassed on a modulo of number of instances:

  # Option to run in parallel using xargs
  # Eg: ( seq 0 9 | \
  #        xargs -P 10 -n 1 ./2023/jq/12-b.jq input.txt --argjson s 10 --argjson i \
  #      ) | jq -s add
  # Execution time 17m10s -> 20s
  if $ARGS.named.s and $ARGS.named.i then #
    [inputs] | to_entries[] | select(.key % $ARGS.named.s == $ARGS.named.i) | .value / " "
  else
    inputs / " "
  end

I use JQ at work, and never really needed this, i guess this trick is nice to have under the belt just in case.

::: spoiler spoiler

Oooh I should run my code without memoization. Or just add a cache hit count.

:::