AOC 2022 Day 22

/// Navigate your way around a grid.
/// 1) Following instructions.
/// 2) But first, wrap it round a cube.
///
import 'dart:math';
import 'package:more/more.dart';

var headings = [Point(0, -1), Point(1, 0), Point(0, 1), Point(-1, 0)];
var arrows = ['^', '>', 'v', '<'];

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

  var navRules = lines.removeLast();
  lines.removeLast();
  var width = lines.map((e) => e.length).max();
  var height = lines.length;
  var grid = lines.map((e) => e.padRight(width).split('')).toList();

  var pos = Point(lines[0].indexOf('.'), 0);
  var heading = 1;

  navRules = navRules.replaceAll('R', ' R ').replaceAll('L', ' L ');
  var nr = navRules.split(' ');
  for (var r in nr) {
    if (r == 'L' || r == 'R') {
      heading = (heading + ((r == 'R') ? 1 : -1)) % headings.length;
      continue;
    }
    var step = int.parse(r);

    while (step > 0) {
      var np = pos + headings[heading];
      np = Point(np.x % width, np.y % height);
      while (grid[np.y][np.x] == ' ') {
        np = np + headings[heading];
        np = Point(np.x % width, np.y % height);
      }

      if (grid[np.y][np.x] == '#') {
        break;
      }
      grid[pos.y][pos.x] = arrows[heading];
      pos = np;
      step -= 1;
    }
  }
  return 1000 * (pos.y + 1) + 4 * (pos.x + 1) + (heading - 1);
}

/// OKAY

/// 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);
}

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

  var navRules = lines.removeLast();
  lines.removeLast();
  var width = lines.map((e) => e.length).max();
  var height = lines.length;
  var grid = lines.map((e) => e.padRight(width).split('')).toList();

  // I think this must be true....
  var faceSize = (width > height) ? width ~/ 4 : width ~/ 3;

  var x = [grid.first.indexOf('.'), grid.first.indexOf('#')].min();
  Map<String, Face> faces = 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.
  var face = faces['T']!;
  var pos = Point(x, 0);
  var heading = 1;

  navRules = navRules.replaceAll('R', ' R ').replaceAll('L', ' L ');
  var nr = navRules.split(' ');
  for (var r in nr) {
    if (r == 'L' || r == 'R') {
      // print('turn $turn');
      heading = (heading + ((r == 'R') ? 1 : -1)) % headings.length;
      continue;
    }
    // print(pos);
    var step = int.parse(r);
    // print('step $step');

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

      //HERE COMES THE MAGIC. We're moving to another face -- recalibrate!!!
      if (np.x < face.origin.x ||
          np.x >= face.origin.x + faceSize ||
          np.y < face.origin.y ||
          np.y >= face.origin.y + faceSize) {
        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 '#'? Stop on this face instead and break.
        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.
      grid[pos.y][pos.x] = arrows[heading];
      pos = np;
      step -= 1;
    }
    //grid[pos.y][pos.x] = '*';
    //grid.forEach((e) => print(e.join()));
  }

  // change the sum
  return 1000 * (pos.y + 1) + 4 * (pos.x + 1) + ((heading - 1) % 4);
}

// READ THE ACTUAL GRID
// find a face. call it `T`. push its neighbours into a queue with their
// directions and transforms
Map<String, Face> buildFaces(
    int x, int faceSize, int width, int height, List<List<String>> grid) {
  var queue = [Face('T', 0, Point(x, 0))];
  var 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 + dirs[n] * faceSize;
      if (d.x < 0 || d.x + faceSize > width || d.y + faceSize > height) {
        continue;
      }
      if (grid[d.y][d.x] != ' ') {
        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));
      }
    }
  }
  return faces;
}