swlabr

Part 1. A quick look at the data showed that the input length was short enough to perform an O(2^n^) search with some early exits. I coded it as a dfs.

Part 2. Adding concatenation just changes the base from 2 to 3, which, while strictly slower, wasn't much slower for this input.

void d7(bool sub) => print(getLines()
    .map((l) => l.split(RegExp(r':? ')).map(int.parse).toList())
    .fold<int>(
        0, (p, ops) => test(ops, ops[0], ops[1], 2, sub) ? ops[0] + p : p));

bool test(List<int> l, int cal, int cur, int i, bool sub) =>
    cur == cal && i == l.length ||
    (i < l.length && cur <= cal) &&
        (test(l, cal, cur + l[i], i + 1, sub) ||
            test(l, cal, cur * l[i], i + 1, sub) ||
            (sub && test(l, cal, cur.concat(l[i]), i + 1, sub)));

void d5(bool isPart2) {
  Map<int, Set<int>> ordering = {};
  int comp(int a, int b) => ordering[a]?.contains(b) ?? false ? -1 : 1;

  List<String> lines = getLines();
  int rulesEnd = lines.indexWhere((line) => line.isEmpty);

  lines
      .sublist(0, rulesEnd)
      .map((line) => line.split('|').map((e) => int.parse(e)).toList())
      .forEach((rule) => ordering.putIfAbsent(rule[0], Set.new).add(rule[1]));

  print(lines
      .sublist(rulesEnd + 1)
      .map((line) => line.split(",").map((s) => int.parse(s)).toList())
      .fold<int>(
          0,
          (p, e) =>
              p +
              (e.isSorted(comp) != isPart2
                  ? e.sorted(comp)[e.length >> 1]
                  : 0)));
}

As it turns out, that instinct was also correct. By drawing the sample data (or counting or printing it out), I noticed that every page number had a defined relation with every other page number. This meant that a total ordering (rather than a lattice) existed, meaning it was possible to construct a comparison function.

So, the algorithm for part 1 was to check if a list was sorted, and part 2 was to sort the list. There's probably a 1-3 line solution for both parts a and b, but that's for Mr. The Reader.

Context: I participated (and completed!) in AoC last year and pragmatically wrote my code as a set of utility modules for solving these pathological problems. So, I had about 80% of the boilerplate for this problem written, waiting for me to read and relearn.

Anyway, the analysis: P1. was pretty straightforward. Just walk along the map, turn right if you hit an obstacle, and stop when you leave the map. I guessed that there may be a case where one needs to turn in place more than once to escape an obstacle, but I never checked if that was true. Either way, I got the answer out. This is a worst-case O(n^2^) solution, which was fast for n = 130.

P2. I chose to brute force this, and it was fine. I iterated through the grid, placing a wall if possible, and checked if this produced a loop using an explored set. This is worst case O(n^4^), which, for n=130, takes a few seconds to spit out the answer. It's parallelisable, though, so there's that. If a faster solution existed, I'd love to know.