#!/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";

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;
  }

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).

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);
  }));
}

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.

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);
}

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…

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);
}

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.

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.

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.

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.

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”.

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.

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.

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

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

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.

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

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.

#!/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.

#!/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.