Day 12: Garden Groups
Megathread guidelines
- Keep top level comments as only solutions, if you want to say something other than a solution put it in a new post. (replies to comments can be whatever)
- You can send code in code blocks by using three backticks, the code, and then three backticks or use something such as https://topaz.github.io/paste/ if you prefer sending it through a URL
FAQ
- What is this?: Here is a post with a large amount of details: https://programming.dev/post/6637268
- Where do I participate?: https://adventofcode.com/
- Is there a leaderboard for the community?: We have a programming.dev leaderboard with the info on how to join in this post: https://programming.dev/post/6631465
You are viewing a single thread.
View all comments 
3 points
*
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)
70 or so lines, half a second to run, so that's fine for today.
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;
