mykl

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