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

  • mykl@lemmy.world
    3·
    5 hours ago

    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;