We stayed in Sheerness (where this flight took place), and when my girlfriend saw this she immediately asked “Did pigs fly before women did?”. And the answer turned out to be no, women beat pigs by two weeks: “Sarah Van Deman … was the woman who flew with Wilbur Wright on October 27, 1909” source

What does “zoomed in to check which colour they re-used in the second chart so didn’t even realise there was a third one” count as?

Isn’t every video game just moving colourful blocks?

(Except Quake obviously)

i_understood_that_reference.jif

Dart

I'm cheating a bit by posting this as it does take 11s for the full part 2 solution, but having tracked down and eliminated the excessively long path for part 1, I can't be bothered to do it again for part 2.

I'm an idiot. Avoiding recursively adding the same points to the seen set dropped total runtime to a hair under 0.5s, so line-seconds are around 35.

Map, Set>> seen = {};

Map fire(List> grid, Point here, Point dir) {
  seen = {};
  return _fire(grid, here, dir);
}

Map, Set>> _fire(
    List> grid, Point here, Point dir) {
  while (true) {
    here += dir;
    if (!here.x.between(0, grid.first.length - 1) ||
        !here.y.between(0, grid.length - 1)) {
      return seen;
    }
    if (seen[here]?.contains(dir) ?? false) return seen;
    seen[here] = (seen[here] ?? >{})..add(dir);

    Point split() {
      _fire(grid, here, Point(-dir.y, -dir.x));
      return Point(dir.y, dir.x);
    }

    dir = switch (grid[here.y][here.x]) {
      '/' => Point(-dir.y, -dir.x),
      r'\' => Point(dir.y, dir.x),
      '|' => (dir.x.abs() == 1) ? split() : dir,
      '-' => (dir.y.abs() == 1) ? split() : dir,
      _ => dir,
    };
  }
}

parse(List lines) => lines.map((e) => e.split('').toList()).toList();

part1(List lines) =>
    fire(parse(lines), Point(-1, 0), Point(1, 0)).length;

part2(List lines) {
  var grid = parse(lines);
  var ret = 0.to(grid.length).fold(
      0,
      (s, t) => [
            s,
            fire(grid, Point(-1, t), Point(1, 0)).length,
            fire(grid, Point(grid.first.length, t), Point(-1, 0)).length
          ].max);
  return 0.to(grid.first.length).fold(
      ret,
      (s, t) => [
            s,
            fire(grid, Point(t, -1), Point(0, 1)).length,
            fire(grid, Point(t, grid.length), Point(0, -1)).length
          ].max);
}

Imagine you're looking at a grid with your path drawn out on it. On any given row, start from the left and move right, cell by cell. You're outside the area enclosed by your path at the start of the row. As you move across that row, you remain outside it until you meet and cross the line made by your path. Every non-path cell you now pass can be added to your 'inside' count, until you next cross your path, when you stop counting until you cross the path again, and so on.

In this problem, you can tell you're crossing the path when you encounter one of:

• a '|'
• a 'F' (followed by 0 or more '-'s) followed by 'J'
• a 'L' (followed by 0 or more '-'s) followed by '7'

If you encounter an 'F' (followed by 0 or more '-'s) followed by '7', you've actually just skimmed along the line and not actually crossed it. Same for the 'L'/ 'J' pair.

Try it out by hand on the example grids and you should get the hang of the logic.

Uiua

As promised, just a little later than planned. I do like this solution as it's actually using arrays rather than just imperative programming in fancy dress. Run it here

Grid ← =@# [
  "...#......"
  ".......#.."
  "#........."
  ".........."
  "......#..."
  ".#........"
  ".........#"
  ".........."
  ".......#.."
  "#...#....."
]

GetDist! ← (
  # Build arrays of rows, cols of galaxies
  ⊙(⊃(◿)(⌊÷)⊃(⧻⊢)(⊚=1/⊂)).
  # check whether each row/col is just space
  # and so calculate its relative position
  ∩(\++1^1=0/+)⍉.
  # Map galaxy co-ords to these values
  ⊏:⊙(:⊏ :)
  # Map to [x, y] pairs, build cross product, 
  # and sum all topright values.
  /+≡(/+↘⊗0.)⊠(/+⌵-).⍉⊟
)
GetDist!(×1) Grid
GetDist!(×99) Grid

There is a really simple approach that I describe in my comment on the megathread, but it's always good to have a nice visualisation so thanks for sharing!

Dart

Terrible monkey-coding approach of banging strings together and counting the resulting shards. Just kept to a reasonable 300ms runtime by a bit of memoisation of results. I'm sure this can all be replaced by a single line of clever combinatorial wizardry.

var __countMatches = {};
int _countMatches(String pattern, List counts) =>
    __countMatches.putIfAbsent(
        pattern + counts.toString(), () => countMatches(pattern, counts));

int countMatches(String pattern, List counts) {
  if (!pattern.contains('#') && counts.isEmpty) return 1;
  if (pattern.startsWith('..')) return _countMatches(pattern.skip(1), counts);
  if (pattern == '.' || counts.isEmpty) return 0;

  var thisShape = counts.first;
  var minSpaceForRest =
      counts.length == 1 ? 0 : counts.skip(1).sum + counts.skip(1).length + 1;
  var lastStart = pattern.length - minSpaceForRest - thisShape;
  if (lastStart < 1) return 0;

  var total = 0;
  for (var start in 1.to(lastStart + 1)) {
    // Skipped a required spring. Bad, and will be for all successors.
    if (pattern.take(start).contains('#')) break;
    // Includes a required separator. Also bad.
    if (pattern.skip(start).take(thisShape).contains('.')) continue;
    var rest = pattern.skip(start + thisShape);
    if (rest.startsWith('#')) continue;
    // force '.' or '?' to be '.' and count matches.
    total += _countMatches('.${rest.skip(1)}', counts.skip(1).toList());
  }
  return total;
}

solve(List lines, {stretch = 1}) {
  var ret = [];
  for (var line in lines) {
    var ps = line.split(' ');
    var pattern = List.filled(stretch, ps.first).join('?');
    var counts = List.filled(stretch, ps.last)
        .join(',')
        .split(',')
        .map(int.parse)
        .toList();
     ret.add(countMatches('.$pattern.', counts)); // top and tail.
  }
  return ret.sum;
}

part1(List lines) => solve(lines);

part2(List lines) => solve(lines, stretch: 5);

It's so humbling when you've hammered out a solution and then realise you've been paddling around in waters that have already been mapped out by earlier explorers!

If you're still stuck on part 2, have a look at my comment which shows an unreasonably easy approach :-)

Dart

Finally got round to solving part 2. Very easy once I realised it's just a matter of counting line crossings.

Edit: having now read the other comments here, I'm reminded me that the line crossing logic is actually an application of Jordan's Curve Theorem which looks like a mathematical joke when you first see it, but turns out to be really useful here!

var up = Point(0, -1),
    down = Point(0, 1),
    left = Point(-1, 0),
    right = Point(1, 0);
var pipes = >>{
  '|': [up, down],
  '-': [left, right],
  'L': [up, right],
  'J': [up, left],
  '7': [left, down],
  'F': [right, down],
};
late List> grid; // Make grid global for part 2
Set> buildPath(List lines) {
  grid = lines.map((e) => e.split('')).toList();
  var points = {
    for (var row in grid.indices())
      for (var col in grid.first.indices()) Point(col, row): grid[row][col]
  };
  // Find the starting point.
  var pos = points.entries.firstWhere((e) => e.value == 'S').key;
  var path = {pos};
  // Replace 'S' with assumed pipe.
  var dirs = [up, down, left, right].where((el) =>
      points.keys.contains(pos + el) &&
      pipes.containsKey(points[pos + el]) &&
      pipes[points[pos + el]]!.contains(Point(-el.x, -el.y)));
  grid[pos.y][pos.x] = pipes.entries
      .firstWhere((e) =>
          (e.value.first == dirs.first) && (e.value.last == dirs.last) ||
          (e.value.first == dirs.last) && (e.value.last == dirs.first))
      .key;

  // Follow the path.
  while (true) {
    var nd = dirs.firstWhereOrNull((e) =>
        points.containsKey(pos + e) &&
        !path.contains(pos + e) &&
        (points[pos + e] == 'S' || pipes.containsKey(points[pos + e])));
    if (nd == null) break;
    pos += nd;
    path.add(pos);
    dirs = pipes[points[pos]]!;
  }
  return path;
}

part1(List lines) => buildPath(lines).length ~/ 2;
part2(List lines) {
  var path = buildPath(lines);
  var count = 0;
  for (var r in grid.indices()) {
    var outside = true;
    // We're only interested in how many times we have crossed the path
    // to get to any given point, so mark anything that's not on the path
    // as '*' for counting, and collapse all uninteresting path segments.
    var row = grid[r]
        .indexed()
        .map((e) => path.contains(Point(e.index, r)) ? e.value : '*')
        .join('')
        .replaceAll('-', '')
        .replaceAll('FJ', '|') // zigzag
        .replaceAll('L7', '|') // other zigzag
        .replaceAll('LJ', '') // U-bend
        .replaceAll('F7', ''); // n-bend
    for (var c in row.split('')) {
      if (c == '|') {
        outside = !outside;
      } else {
        if (!outside && c == '*') count += 1;
      }
    }
  }
  return count;
}

Dart

Nothing interesting here, just did it all explicitly. I might try something different in Uiua later.

solve(List lines, {int age = 2}) {
  var grid = lines.map((e) => e.split('')).toList();
  var gals = [
    for (var r in grid.indices())
      for (var c in grid[r].indices().where((c) => grid[r][c] == '#')) (r, c)
  ];
  for (var row in grid.indices(step: -1)) {
    if (!grid[row].contains('#')) {
      gals = gals
          .map((e) => ((e.$1 > row) ? e.$1 + age - 1 : e.$1, e.$2))
          .toList();
    }
  }
  for (var col in grid.first.indices(step: -1)) {
    if (grid.every((r) => r[col] == '.')) {
      gals = gals
          .map((e) => (e.$1, (e.$2 > col) ? e.$2 + age - 1 : e.$2))
          .toList();
    }
  }
  var dists = [
    for (var ix1 in gals.indices())
      for (var ix2 in (ix1 + 1).to(gals.length))
        (gals[ix1].$1 - gals[ix2].$1).abs() +
            (gals[ix1].$2 - gals[ix2].$2).abs()
  ];
  return dists.sum;
}

part1(List lines) => solve(lines);
part2(List lines) => solve(lines, age: 1000000);

Lots and lots of print statements :-)

I even have time to knock out a quick Uiua solution before going out today, using experimental recursion support. Bleeding edge code:

# Experimental!
{"0 3 6 9 12 15"
 "1 3 6 10 15 21"
 "10 13 16 21 30 45"}
StoInt ← /(+×10)▽×⊃(≥0)(≤9).-@0
NextTerm ← ↬(
  ↘1-↻¯1..      # rot by one and take diffs
  (|1 ↫|⊢)=1⧻⊝. # if they're all equal grab else recurse
  +⊙(⊢↙¯1)      # add to last value of input
)
≡(⊜StoInt≠@\s.⊔) # parse
⊃(/+≡NextTerm)(/+≡(NextTerm ⇌))

Dart

I was getting a bad feeling when it explained in such detail how to solve part 1 that part 2 was going to be some sort of nightmare of traversing all those generated numbers in some complex fashion, but this has got to be one of the shortest solutions I've ever written for an AoC challenge.

int nextTerm(Iterable ns) {
  var diffs = ns.window(2).map((e) => e.last - e.first);
  return ns.last +
      ((diffs.toSet().length == 1) ? diffs.first : nextTerm(diffs.toList()));
}

List> parse(List lines) => [
      for (var l in lines) [for (var n in l.split(' ')) int.parse(n)]
    ];

part1(List lines) => parse(lines).map(nextTerm).sum;
part2(List lines) => parse(lines).map((e) => nextTerm(e.reversed)).sum;

Dart

Part 1 was easy enough. For Part 2 I took a guess that the cycles were all well behaved and I could get away with just calculating the LCM, and it paid off.

(List, Map) parse(List lines) => (
      lines.first.split(''),
      {
        for (var l in lines.skip(2).map((e) => e.split(RegExp(r'[^A-Z0-9]'))))
          l[0]: [l[4], l[6]]
      }
    );
int movesTo(pos, steps, rules) {
  var stepNo = -1;
  while (!pos.endsWith('Z')) {
    pos = rules[pos]![steps[(stepNo += 1) % steps.length] == 'L' ? 0 : 1];
  }
  return stepNo + 1;
}

part1(List lines) {
  var (steps, rules) = parse(lines);
  return movesTo('AAA', steps, rules);
}

// All cycles are independent of state of `steps`, and have
// first instance == cycle length which makes this verrry simple.
part2(List lines) {
  var (steps, rules) = parse(lines);
  return [
    for (var start in rules.keys.where((e) => e.endsWith('A')))
      movesTo(start, steps, rules)
  ].reduce((s, t) => s.lcm(t));
}
}

It's Uiua time!

It works, but even I can't understand this code any more as I'm well into my second beer, so don't put this into production, okay? (Run it here if you dare.)

{"32T3K 765"
 "T55J5 684"
 "KK677 28"
 "KTJJT 220"
 "QQQJA 483"}
StoInt ← /(+×10)▽×⊃(≥0)(≤9).-@0
ToHex ← ⊏:"  23456789abcde"⊗:"  23456789TJQKA"
ToHexJ ← ⊏:"  23456789a0cde"⊗:"  23456789TJQKA"
# A hand of "311" with one J will have same rank as "41"
# Dots indicate impossible hands.
Rankings ← {
  {"11111" "2111" "221" "311" "32" "41" "5"}   # 0
  {"..." "11111" ".." "2111" "221" "311" "41"} # 1
  {"..." "....." ".." "2111" "..." "221" "32"} # 2
  {"..." "....." ".." "...." "..." "311" "32"} # 3
  {"..." "....." ".." "...." "..." "..." "41"} # 4
  {"..." "....." ".." "...." "..." "..." "5"}  # 5
}
RankHand ← (
  +@0⊏⍖.⊕⧻⊛⊢⍉⇌⊕∘⍖...          # Count instances, sort desc, to string
  ⊗⊃⊢(⊔⊡:Rankings/+=@0⊢↘1)⊟∩□ # Use table to get ranking
)
ScoreHands! ← (
  ≡(⊐⊟⊓(⊐⊟RankHand.^1⊔)∘⍘⊟) # Rank every hand
  /+/×⊟+1⇡⧻.∵⊔≡(⊢↘1)⊏⍏≡⊢.   # Sort based on rankings
)
⍉⊟⊓∘(∵StoInt)⍘⊟⍉≡(⊐⊜∘≠@\s.) # Parse input
⊃(ScoreHands!ToHex)(ScoreHands!ToHexJ)

Dart

I'm glad I took the time to read the directions very carefully before starting coding :-)

Top Tip: my ranking of hand types relies on the fact that if you count instances of each face and sort the resulting list from high to low, you get a list that when compared with lists from other hands gives an exact correspondence with the order of the hand types as defined, so no need for a bunch of if/thens, just

  var type = Multiset.from(hand).counts.sorted(descending).join('');

Otherwise it should all be pretty self-explanatory apart from where I chose to map card rank to hex digits in order to facilitate sorting, so 'b' means 'J'!

int descending(T a, T b) => b.compareTo(a);
var cToH = "  23456789TJQKA"; // used to map card rank to hex for sorting.

handType(List hand, {wildcard = false}) {
  var type = Multiset.from(hand).counts.sorted(descending).join('');
  var i = hand.indexOf('b');
  return (!wildcard || i == -1)
      ? type
      : '23456789acde'
          .split('')
          .map((e) => handType(hand.toList()..[i] = e, wildcard: true))
          .fold(type, (s, t) => s.compareTo(t) >= 0 ? s : t);
}

solve(List lines, {wildcard = false}) => lines
    .map((e) {
      var l = e.split(' ');
      var hand =
          l.first.split('').map((e) => cToH.indexOf(e).toRadixString(16));
      var type = handType(hand.toList(), wildcard: wildcard);
      if (wildcard) hand = hand.map((e) => e == 'b' ? '0' : e);
      return (hand.join(), type, int.parse(l.last));
    })
    .sorted((a, b) {
      var c = a.$2.compareTo(b.$2);
      return (c == 0) ? a.$1.compareTo(b.$1) : c;
    })
    .indexed(offset: 1)
    .map((e) => e.value.$3 * e.index)
    .sum;

part1(List lines) => solve(lines);

part2(List lines) => solve(lines, wildcard: true);

Today was easy enough that I felt confident enough to hammer out a solution in Uiua, so read and enjoy (or try it out live):

{"Time:      7  15   30"
 "Distance:  9  40  200"}
StoInt ← /(+ ×10) ▽×⊃(≥0)(≤9). -@0
Count ← (
  ⊙⊢√-×4:×.⍘⊟.           # Determinant, and time
  +1-⊃(+1↥0⌊÷2-)(-1⌈÷2+) # Diff of sanitised roots
)
≡(↘1⊐⊜∘≠@\s.)
⊃(/×≡Count⍉∵StoInt)(Count⍉≡(StoInt⊐/⊂))