AOC2022 day22

main.dart

// AOC 2022, Day 22: Monkey Map
// Navigate your way around a grid.
// 1) Following instructions.
// 2) But first, wrap it round a cube.
// https://dartpad.dev/?id=12713657a02660c09fe3c9e548e7d7e9

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

extension MathNumberExtension on num {
  bool between(num min, num max) => min <= this && this <= max;
}

const headings = [Point(0, -1), Point(1, 0), Point(0, 1), Point(-1, 0)];

late int width, height;
late List<List<String>> grid;
late Point<int> pos;
late int heading;

void buildGrid(List<String> lines) {
  lines.removeLast();
  width = lines.map((e) => e.length).max;
  height = lines.length;
  grid = lines.map((e) => e.padRight(width).split('')).toList();
}

void runRules(String navRules, {required void Function(int) moveFunction}) {
  heading = 1;
  var nr = navRules.replaceAll('R', ' R ').replaceAll('L', ' L ').split(' ');
  for (var r in nr) {
    if (r == 'L') {
      heading = (heading - 1) % headings.length;
      continue;
    }
    if (r == 'R') {
      heading = (heading + 1) % headings.length;
      continue;
    }
    // Otherwise move forward.
    moveFunction(int.parse(r));
  }
}

void moveForward(int step) {
  var h = headings[heading];
  while (step > 0) {
    var np = pos + h;
    np = Point(np.x % width, np.y % height);
    while (grid[np.y][np.x] == ' ') {
      np += h;
      np = Point(np.x % width, np.y % height);
    }
    if (grid[np.y][np.x] == '#') break;
    pos = np;
    step -= 1;
  }
}

/// Our ideal cube is laid out like this:
///
///     T
/// W - S - E - N
///     B
///
/// `transforms` shows what you will see in each direction from the cube as
/// laid out above. NOTE !!!! 0 = N, 1 = E...
/// SO 'S':0 shows that North of S is a T in the same orientation.

var transforms = {
  'S': {0: Tf('T', 0), 1: Tf('E', 0), 2: Tf('B', 0), 3: Tf('W', 0)},
  'E': {0: Tf('T', 1), 1: Tf('N', 0), 2: Tf('B', 3), 3: Tf('S', 0)},
  'N': {0: Tf('T', 2), 1: Tf('W', 0), 2: Tf('B', 2), 3: Tf('E', 0)},
  'W': {0: Tf('T', 3), 1: Tf('S', 0), 2: Tf('B', 1), 3: Tf('N', 0)},
  'B': {0: Tf('S', 0), 1: Tf('E', 1), 2: Tf('N', 2), 3: Tf('W', 3)},
  'T': {0: Tf('N', 2), 1: Tf('E', 3), 2: Tf('S', 0), 3: Tf('W', 1)},
};

class Face {
  String name;
  int orientation;
  Point<int> origin;
  Face(this.name, this.orientation, this.origin);

  @override
  int get hashCode => name.hashCode;
  @override
  bool operator ==(Object other) => other is Face && other.name == name;
}

class Tf {
  String name;
  int rotation;
  Tf(this.name, this.rotation);
}

late Face face;
late int faceSize;
late Map<String, Face> faces;

void moveForwardOnCube(int step) {
  while (step > 0) {
    var np = pos + headings[heading];

    //HERE COMES THE MAGIC. We're moving to another face -- recalibrate!!!
    if (!np.x.between(face.origin.x, face.origin.x + faceSize - 1) ||
        !np.y.between(face.origin.y, face.origin.y + faceSize - 1)) {
      var tf = transforms[face.name]![(heading - face.orientation) % 4]!;
      var nf = faces[tf.name]!;

      // Base case -- the point relative to the old face
      var tnp = Point(np.x % faceSize, np.y % faceSize);
      var relOrient = (nf.orientation - face.orientation - tf.rotation) % 4;
      var theading = (heading + relOrient) % 4;
      if (relOrient == 0) {
        // Same orientation, so nothing to do
      } else if (relOrient == 1) {
        tnp = Point(faceSize - 1 - tnp.y, tnp.x);
      } else if (relOrient == 2) {
        tnp = Point(faceSize - 1 - tnp.x, faceSize - 1 - tnp.y);
      } else if (relOrient == 3) {
        tnp = Point(tnp.y, faceSize - 1 - tnp.x);
      }
      // now index it relative to the new face.
      tnp = tnp + nf.origin;
      // is it about to hit a '#' on the new face? Stop on this face instead.
      if (grid[tnp.y][tnp.x] == '#') break;

      //Otherwise make the move.
      face = faces[tf.name]!;
      np = tnp;
      heading = theading;
    }

    if (grid[np.y][np.x] == '#') break;
    // Just a normal move.
    pos = np;
    step -= 1;
  }
}

/// READ THE ACTUAL GRID:
/// find a face, call it `T`, push its neighbours into a queue with their
/// directions and transforms
void buildFaces(
    int x, int faceSize, int width, int height, List<List<String>> grid) {
  var queue = [Face('T', 0, Point(x, 0))];
  faces = <String, Face>{};
  //var dirs = [Point(0, -1), Point(1, 0), Point(0, 1), Point(-1, 0)];
  while (queue.isNotEmpty) {
    var face = queue.removeAt(0);
    if (faces.containsKey(face.name)) continue;
    faces[face.name] = face;
    for (var n in [1, 2, 3]) {
      // right, down, left
      var d = face.origin + headings[n] * faceSize;
      if (d.x < 0 || d.x + faceSize > width || d.y + faceSize > height) {
        continue;
      }
      if (grid[d.y][d.x] == ' ') continue;
      var nextFace = transforms[face.name]![(n - face.orientation) % 4]!;
      var nextName = nextFace.name;
      var nextOrient = (nextFace.rotation + face.orientation) % 4;
      var nextOrigin = d;
      queue.add(Face(nextName, nextOrient, nextOrigin));
    }
  }
}

part1(List<String> ls) {
  var lines = ls.toList();
  var navRules = lines.removeLast();
  buildGrid(lines);

  var x = [grid.first.indexOf('.'), grid.first.indexOf('#')].min;
  pos = Point(x, 0);

  runRules(navRules, moveFunction: moveForward);
  return 1000 * (pos.y + 1) + 4 * (pos.x + 1) + (heading - 1);
}

part2(List<String> ls) {
  var lines = ls.toList();
  var navRules = lines.removeLast();
  buildGrid(lines);

  faceSize = (width > height) ? width ~/ 4 : width ~/ 3;
  var x = [grid.first.indexOf('.'), grid.first.indexOf('#')].min;
  pos = Point(x, 0);
  buildFaces(x, faceSize, width, height, grid);

  //Now have all the faces in `faces` with the origin and required tranforms
  //Define the topmost face to be T, and work from there.
  face = faces['T']!;

  runRules(navRules, moveFunction: moveForwardOnCube);
  return 1000 * (pos.y + 1) + 4 * (pos.x + 1) + ((heading - 1) % 4);
}

var testdata = [
  "        ...#",
  "        .#..",
  "        #...",
  "        ....",
  "...#.......#",
  "........#...",
  "..#....#....",
  "..........#.",
  "        ...#....",
  "        .....#..",
  "        .#......",
  "        ......#.",
  "",
  "10R5L5R10L4R5L5"
];

void main(List<String> args) {
  var dt = DateTime.now();
  assert(part1(testdata) == 6032);
  assert(part2(testdata) == 5031);
  var rt = DateTime.now().difference(dt).inMilliseconds;
  print('tests succeeded in $rt ms');
}