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!