Dart

Filling to find regions was easy. Counting areas was easy. Counting fences was okay. Counting sides caused me a lot of frustration as I tried and rejected a number of approaches, eventually arriving at a reasonably simple corner-counting approach. None of this was helped by all the examples lacking at least two important layouts, causing today to be the first day that I ran out of hints for wrong answers :-(.

(corners is where the magic happens)

import 'dart:math';
import 'package:collection/collection.dart';
import 'package:more/more.dart';

const List<Point> n4 = [Point(0, 1), Point(0, -1), Point(1, 0), Point(-1, 0)];
List<Point> n8 = n4 + [Point(1, 1), Point(1, -1), Point(-1, 1), Point(-1, -1)];
const List<Point> c4 = [Point(0, 0), Point(0, 1), Point(1, 0), Point(1, 1)];

(Map<Point, String>, Map<Point, List<Point>>) parse(ls) {
  var nodes = {
    for (var y in 0.to(ls.length))
      for (var x in 0.to(ls.first.length)) Point<num>(x, y): ls[y][x] as String
  };
  var nexts = Map.fromEntries(nodes.keys.map((n) => MapEntry(
      n,
      n4
          .map((d) => n + d)
          .where((d) => (nodes[d] ?? '') == nodes[n]!)
          .toList())));
  return (nodes, nexts);
}

(int, Set<Point>) survey(
    Point here, String target, Map<Point<num>, List<Point>> nexts,
    [Set sofar = const {}]) {
  seen.add(here);
  var fences = 4 - nexts[here]!.length;
  var area = {here};
  for (var f in nexts[here]!.where((e) => !seen.contains(e))) {
    var (fs, a) = survey(f, target, nexts, sofar.toSet()..add(f));
    fences += fs;
    area.addAll(a);
  }
  return (fences, area);
}

late Set<Point> seen;
List<(int, Set<Point<num>>)> costs(List<String> lines) {
  seen = {};
  var ret = <(int, Set<Point<num>>)>[];
  var (nodes, nexts) = parse(lines);
  var toVisit = nodes.keys.toSet();
  while (toVisit.isNotEmpty) {
    var here = toVisit.first;
    toVisit.remove(here);
    ret.add(survey(here, nodes[here]!, nexts));
    toVisit.removeAll(seen);
  }
  return ret;
}

Function eq = const ListEquality().equals;
int corners(Set<Point> points) {
  var border = points.map((e) => n8.map((n) => n + e)).flattenedToSet
    ..addAll(points);
  // A corner is where a 2x2 grid contains one/three in-shape points, or
  // two diagonally-opposite cells
  var corners = 0;
  for (var cell in border) {
    var count = c4.map((e) => points.contains(e + cell)).toList();
    if (count.count((e) => e) % 2 == 1) {
      corners += 1;
    } else {
      if (eq(count, [true, false, false, true]) ||
          eq(count, [false, true, true, false])) {
        corners += 2;
      }
    }
  }
  return corners;
}

part1(lines) => costs(lines).map((e) => e.first * e.last.length).sum;
part2(lines) => costs(lines).map((e) => corners(e.last) * e.last.length).sum;

Uiua

I thought this was going to be trivial to implement in Uiua, but I managed to blow the stack, meaning I had to set an environment variable in order to get it to run. That doesn’t work in Uiua Pad, so for any counts larger than 15 you need to run it locally. Built-in memoisation though so that’s nice.

# NB Needs env var UIUA_RECURSION_LIMIT=300
Next  ← ⍣([1] °0|[×2024] °1◿2⧻°⋕.|⍜°⋕(↯2_∞))
Count ← |2 memo(⨬(1|/+≡Count¤-1⊙Next)≠0.) # rounds, stone
≡(&p/+≡Count¤: ⊜⋕⊸≠@\s "125 17")[25 75]

Dart

I really wish Dart had memoising built in. Maybe the new macro feature will allow this to happen, but in the meantime, here’s my hand-rolled solution.

import 'package:collection/collection.dart';

var counter_ = <(int, int), int>{};
int counter(s, [r = 75]) => counter_.putIfAbsent((s, r), () => _counter(s, r));
int _counter(int stone, rounds) =>
    (rounds == 0) ? 1 : next(stone).map((e) => counter(e, rounds - 1)).sum;

List<int> next(int s) {
  var ss = s.toString(), sl = ss.length;
  if (s == 0) return [1];
  if (sl.isOdd) return [s * 2024];
  return [ss.substring(0, sl ~/ 2), ss.substring(sl ~/ 2)]
      .map(int.parse)
      .toList();
}

solve(List<String> lines) => lines.first.split(' ').map(int.parse).map(counter).sum;

That’s a lovely minimalist solution. I couldn’t even see where the solution was on my first read-through.

Uiua

Run it here!

How to read this

Uiua has a very helpful (still experimental) astar function built in which returns all valid paths that match your criteria, making a lot of path-finding stuff almost painfully simple, as you just need to provide a starting node and three functions: return next nodes, return heuristic cost to destination (here set to constant 1), return confirmation if we’ve reached a suitable target node (here testing if it’s = 9).

Data   ← ⊜≡⋕⊸≠@\n"89010123\n78121874\n87430965\n96549874\n45678903\n32019012\n01329801\n10456732"
N₄     ← ≡+[0_1 1_0 0_¯1 ¯1_0]¤
Ns     ← ▽:⟜(=1-:∩(⬚0⊡:Data))▽⊸≡(/×≥0)N₄. # Valid, in-bounds neighbours.
Count! ← /+≡(⧻^0⊙◌ astarNs 1 (=9⊡:Data))⊚=0Data
&p Count!(◴≡◇⊣)
&p Count!∘

Dart

I dug out the hill-climbing trail-walking code from 2022 Day 12, put it up on blocks, and stripped all the weirdness out of it.

Ended up with just a simple flood-fill from each trailhead, so it turns out I only actually used the Graph and Node classes which I then also stripped out…

import 'dart:math';
import 'package:collection/collection.dart';
import 'package:more/more.dart';

late Map<Point, int> nodes;
late Map<Point, List> nexts;

/// Parse the lines, build up nodes and nexts, return starts.
List<Point> parse(ls) {
  nodes = {
    for (var y in 0.to(ls.length))
      for (var x in 0.to(ls.first.length)) Point(x, y): int.parse(ls[y][x])
  };
  nexts = Map.fromEntries(nodes.keys.map((n) => MapEntry(
      n,
      [Point(0, 1), Point(0, -1), Point(1, 0), Point(-1, 0)]
          .map((d) => n + d)
          .where((d) => (nodes[d] ?? -1) - nodes[n]! == 1)
          .toList())));
  return nodes.keys.where((e) => nodes[e] == 0).toList();
}

/// Given a starting node, return all valid paths to any '9' on the grid.
Set paths(Point here, [Set sofar = const {}]) {
  if (nodes[here]! == 9) return {sofar};
  return nexts[here]!
      .where((e) => !sofar.contains(e))
      .fold({}, (s, f) => s..addAll(paths(f, sofar.toSet()..add(f))));
}

/// Finds all paths from each start, then apply the fn to each and sum.
count(lines, int Function(Set) fn) => parse(lines).map(paths).map<int>(fn).sum;

part1(lines) => count(lines, (e) => e.map((p) => p.last).toSet().length);
part2(lines) => count(lines, (e) => e.length);

Uiua

Just a port of my Dart solution from earlier really, and it shows, as it takes about 30 seconds on the live data.

(edit: I just noticed the little alien in the code (⋅⋅∘|⋅∘|∘) which is literally flipping the stack (╯°□°)╯︵ ┻━┻!)

How to read this

Try it live!

Data   ← "2333133121414131402"
FS     ← ↙⌊÷2⧻.▽≡⋕:♭⍉⊟⊃(⇡|↯:¯1)⧻.Data  # Build up a map of the FS.
MoveB  ← ⍜(⊡|⋅)⊃(⋅⋅∘|⋅∘|∘) ⊡¯1.:⊢⊚⌕¯1. # Find a space, move block into it.
MoveBs ← ⍢(⍢(↘¯1|=¯1⊣)↘¯1MoveB|>0⧻⊚⌕¯1)

TryMove ← ⨬(◌|∧⍜⊏⇌⍉)/×/>.
MoveFile ← (
  ⊃(⊚⌕↯:¯1⧻|∘)⊚⌕⊙.⊙.         # get posns from, start posn to.
  ⨬(◌◌|TryMove ⊟+⊙◌°⊏,⊢)>0⧻. # check posn to is good, swap.
)
Check ← /+/×⊟⇡⧻.↥0
&p Check MoveBs FS
&p Check ∧MoveFile⇌+1⇡/↥.FS

(edit: improved. Part1 is instant, part2 is about 17sec, but the alien has left)

Data   ← "2333133121414131402"
FS     ← ▽≡⋕:↙⧻:♭⍉⊟⊃(⇡|↯:¯1)⧻..Data # Build up a map of the FS.
Ixs    ← ⊃(⊚¬|⇌⊚)≥0                 # Get indices of space, and of blocks reversed.
SwapBs ← ▽⊸≡/>⍉⊟∩↙⟜:↧∩⧻,,           # Join them where space < block.

Files ← ⇌≡(□⊚)⊞=⇡+1/↥.
Move  ← ∧(⍜⊏⇌)⍉⊟+⇡⧻,⊢ # (tos, froms, fs)
MoveFile ← (
  ⊚⌕⊙,↯:¯1⧻.                # List of possible starts
  ⨬(◌◌|⨬(◌◌|Move)>∩⊢,,)>0⧻. # Only valid, leftwards starts 
)
Check ← /+/×⊟⇡⧻.↥0
&p Check ∧⍜⊏⇌SwapBs⊸Ixs FS
&p Check ∧◇MoveFile Files .FS

Haha, a little too close to home, though my homepage is actually HTML4.01 compliant, so that’s a miss.

Dart

I just mapped the filesystem onto a list holding value at each block (with -1 for spaces), and manipulated that.

It’s slow, but it’s honest work.

import 'dart:math';
import 'package:collection/collection.dart';
import 'package:more/more.dart';

List<int> parse(List<String> lines) => lines.first
    .split('')
    .map(int.parse)
    .mapIndexed((i, e) => List.filled(e, (i.isOdd ? -1 : i ~/ 2)))
    .reduce((s, t) => s + t);

part1(List<String> lines) {
  var fs = parse(lines);
  var i = 0;
  while ((i = fs.indexOf(-1)) >= 0) {
    while (fs.last == -1) {
      fs.removeLast();
    }
    fs[i] = fs.removeLast();
  }
  return fs.mapIndexed((i, e) => i * e).sum;
}

Function eq = const ListEquality().equals;
part2(List<String> lines) {
  var fs = parse(lines);
  for (var target in 1.to(fs.max + 1).reversed) {
    var index = fs.indexOf(target);
    var length = fs.sublist(index).takeWhile((e) => e == target).length;
    var sseq = List.filled(length, -1);
    var space = fs
        .indices()
        .where((e) => e < index)
        .firstWhereOrNull((i) => eq(fs.sublist(i, i + length), sseq));
    if (space == null) continue;
    // Copy the file, clear old location.
    fs.replaceRange(space, space + length, List.filled(length, target));
    fs.replaceRange(index, index + length, List.filled(length, -1));
  }
  return fs.mapIndexed((i, e) => i * max(e, 0)).sum;
}

Updated version

Massive speedup from implementing a modified Knuth–Morris–Pratt algorithm -> around 0.5sec runtime for part 2.

I really don’t understand why efficiently matching a sublist isn’t a builtin function. Implementing it manually was half an hour of unneeded head-scratching.

import 'dart:math';
import 'package:collection/collection.dart';
import 'package:more/more.dart';

List<int> parse(List<String> lines) => lines.first
    .split('')
    .map(int.parse)
    .mapIndexed((i, e) => List.filled(e, (i.isOdd ? -1 : i ~/ 2)))
    .flattened
    .toList();

part1(List<String> lines) {
  var fs = parse(lines);
  var i = 0;
  while ((i = fs.indexOf(-1)) >= 0) {
    while (fs.last == -1) {
      fs.removeLast();
    }
    fs[i] = fs.removeLast();
  }
  return fs.mapIndexed((i, e) => i * e).sum;
}

part2(List<String> lines) {
  var fs = parse(lines);
  for (var target in 1.to(fs.max + 1).reversed) {
    var index = fs.indexOf(target);
    var length = fs.skip(index).takeWhile((e) => e == target).length;
    int? space = findSpace(index, length, fs);
    if (space == null) continue;
    // Copy the file, clear old location.
    fs.setRange(space, space + length, List.filled(length, target));
    fs.setRange(index, index + length, List.filled(length, -1));
  }
  return fs.mapIndexed((i, e) => i * max(e, 0)).sum;
}

/// Knuth–Morris–Pratt algorithm
int? findSpace(int limit, int length, List<int> fs) {
  for (var si = 0; si < limit - length + 1; si++) {
    if (fs[si] != -1) continue;
    var match = true;
    for (var ssi in 0.to(length)) {
      if (fs[si + ssi] != -1) {
        si += ssi;
        match = false;
        break;
      }
    }
    if (match) return si;
  }
  return null;
}

deleted by creator

Glad it helped. I think the concatenation thing is because of the context it’s being called in rather than a bug, but I couldn’t work out exactly what was going on…

My pleasure. I’ve really enjoyed learning Uiua, and hope that I can encourage others to dip their toes in the water!

Maybe we’ve been good all year :-)

I had the opportunity many years ago to learn APL for work, but quickly dropped it because it scared me so much, so I found Uiua a very nice re-introduction to that world.

Thanks, you’ve reminded me that I didn’t actually explain the “why” of Uiua. I will add something.

Uiua

Getting closer to an elegant solution, but still a way to go…

How to read this

Try it live!

Grid      ← ⊜∘⊸≠@\n "............\n........0...\n.....0......\n.......0....\n....0.......\n......A.....\n............\n............\n........A...\n.........A..\n............\n............"
Pairs     ← ∧(⊂⧅≠2⊚⌕)⊙¤⊸(◴▽⊸≠@.♭)Grid[] # get pairs of nodes in grid (both ways round).
InGrid    ← ▽≡/××<⧻Grid:≥0..            # (posns) Keeps those in range.
AntiNodes ← ↯∞_2≡(+¤⊙(פ)⊃⊣/-):¤        # (range, pairs) Find antinodes by taking offset, mul by range, add to last node, check it's in grid.
&p ⧻InGrid◴ AntiNodes ↘1⇡2 Pairs
&p ⧻InGrid◴ AntiNodes ↘0⇡50 Pairs

Dart

This really does feel like a weekend break this year, maybe Eric and co have begun to realise that family time is more precious than work time :-)

import 'dart:math';
import 'package:more/more.dart';

solve(List<String> lines, int min, int max) {
  var map = ListMultimap<String, Point<int>>();
  for (var r in lines.indices()) {
    for (var ci in lines[r].split('').indexed()) {
      if (ci.value != '.') map[ci.value].add(Point(ci.index, r));
    }
  }
  var anti = <Point<int>>{};
  for (var k in map.keys) {
    for (var p in map[k].combinations(2, repetitions: false)) {
      var diff = p.last - p.first;
      for (var m in min.to(max)) {
        anti.addAll([p.first - diff * m, p.last + diff * m]);
      }
    }
  }

  return anti.count((e) =>
      e.x.between(0, lines.first.length - 1) &&
      e.y.between(0, lines.length - 1));
}

part1(List<String> lines) => solve(lines, 1, 2);

part2(List<String> lines) => solve(lines, 0, 50);

Here you go

Team Uiua in the house!

(╯°□°)╯︵ ┻━┻

Haha, sorry about that, it does seem quite smug :-) I went into it expecting it to be a nightmare of boxes and dimensions, but finding it something I could deal with was a massive relief. Of course once I had a working solution I reversed it back into a multi-dimensional nightmare. That’s where the performance gains came from: about 10x speedup from letting Uiua build up as many dimensions as it needed before doing a final deshaping.

I enjoyed reading a different approach to this, and thanks for reminding me that ⋕$"__" exists, that’s a great idiom to have up your sleeve.

Let me know if there’s any bits of my solution that you’d like me to talk you through.