Day 6: Guard Gallivant

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
    2·
    21 days ago

    Dart

    Oof, simple rules can really trip you up if you don’t pay attention.

    This takes seconds to run so it’s clearly not the right approach, but it get the right answers, so…

    (edit) There’s an interesting range of times from others as well, so it probably only requires a little more attention to get the time down, but maybe not today…

    Click to reveal 60 lines of solution. 
    import 'dart:math';
import 'dart:math';
import 'package:more/more.dart';

var d4 = [Point(0, -1), Point(1, 0), Point(0, 1), Point(-1, 0)];

String safeGet(Point<int> p, List<List<String>> grid) =>
    (p.y.between(0, grid.length - 1) && p.x.between(0, grid.first.length - 1))
        ? grid[p.y][p.x]
        : '!';

Point<int> findGuard(List<List<String>> grid) {
  for (var row in grid.indices()) {
    for (var col in grid.first.indices()) {
      if (grid[row][col] == '^') return Point(col, row);
    }
  }
  return Point(-1, -1); //!
}

Set<Point<int>> getTrack(Point<int> guard, List<List<String>> grid) =>
    checkPath(guard, grid).first.map((e) => e.first).toSet();

// Check the path, returning ({(point, dir)}, did it end in a loop).
(Set<(Point<int>, int)>, bool) checkPath(
    Point<int> guard0, List<List<String>> grid,
    {Point<int>? block}) {
  if (block != null) grid[block.y][block.x] = '#';
  var dir = 0;
  var guard = guard0;
  var track = <(Point<int>, int)>{};
  var isLoop = false;
  while (safeGet(guard, grid) != '!') {
    if (track.contains((guard, dir))) {
      isLoop = true;
      break;
    }
    track.add((guard, dir));
    var check = guard + d4[dir];
    if (safeGet(check, grid) == '#') {
      dir = (dir + 1) % 4;
    } else {
      guard += d4[dir];
    }
  }
  if (block != null) grid[block.y][block.x] = '.';
  return (track, isLoop);
}

part1(List<String> lines) {
  var grid = lines.map((e) => e.split('')).toList();
  return getTrack(findGuard(grid), grid).length;
}

part2(List<String> lines) {
  var grid = lines.map((e) => e.split('')).toList();
  var guard = findGuard(grid);
  return getTrack(guard, grid)
      .count((e) => checkPath(guard, grid, block: e).last);
}