AOC2021 Day23

/// Turn 3x3x3 blocks of light on and off as instructed.
/// First limited to -50 to 50 in each direction.
/// Then it most definitely isn't :-(

// ignore_for_file: unused_import

import 'dart:io';
import 'dart:math';
import 'dart:typed_data';
import 'package:more/more.dart';
import 'package:collection/collection.dart';

// late Map<String, int> store;
// setScore(String pos, int score) => store[pos] = score;
// getScore(String pos) => store[pos] ?? 0;

setup() {
  // store = {};
}

late Graph graph;
int buildPaths1(String start) {
  setup();
  graph = Graph();
  var end = '00AA0BB0CC0DD00AABBCCDD';
  aStarSearch(graph, start, end);
  print('route');
  String? here = end;
  var cost = 0;
  while (here != null) {
    print(here);
    var there = here;
    here = cameFrom[here];
    if (here != null) cost += graph.edgeBetween(here, there)!.weight;
  }
  return cost;
}
// buildPaths() {
//   setup();
//   var queue = ['00BA0CD0BC0DA00'];
//   graph = Graph();
//   while (queue.isNotEmpty) {
//     if (queue.length % 100 == 0) print(queue.length);
//     var here = queue.removeLast();
//     // graph.nodes[here] = Node();

//     for (var next in validMoves(here)) {
//       var n = next.first;
//       var c = next.second;
//       // if (!graph.nodes.containsKey(n)) {
//       //   graph.nodes[n] = Node();
//       // }
//       // graph.addEdge(here, n, c);
//       queue.add(n);
//     }
//   }
// }

var homes = '..AA.BB.CC.DD..AABBCCDD';
// Use Points as they use ==.
var links = {
  Point(0, 1): 1,
  Point(1, 2): 2,
  Point(1, 4): 2,
  Point(2, 3): 1,
  Point(2, 4): 2,
  Point(3, 15): 1,
  Point(15, 16): 1,
  Point(4, 5): 2,
  Point(4, 7): 2,
  Point(5, 6): 1,
  Point(5, 7): 2,
  Point(6, 17): 1,
  Point(17, 18): 1,
  Point(7, 8): 2,
  Point(7, 10): 2,
  Point(8, 9): 1,
  Point(8, 10): 2,
  Point(9, 19): 1,
  Point(19, 20): 1,
  Point(10, 11): 2,
  Point(10, 13): 2,
  Point(11, 12): 1,
  Point(11, 13): 2,
  Point(12, 21): 1,
  Point(21, 22): 1,
  Point(13, 14): 1
};
// Roughly where they are in the diagram except alternating arms are moved
// upward to make the manhattan distance more convincing.
var posLocs = <int, Point<int>>{
  0: Point(0, 2),
  1: Point(1, 2),
  2: Point(2, 1),
  3: Point(2, 0),
  4: Point(3, 2),
  5: Point(4, 3),
  6: Point(4, 4),
  7: Point(5, 2),
  8: Point(6, 1),
  9: Point(6, 0),
  10: Point(7, 2),
  11: Point(8, 3),
  12: Point(8, 4),
  13: Point(9, 2),
  14: Point(10, 2),
  15: Point(2, -1),
  16: Point(2, -2),
  17: Point(4, 5),
  18: Point(4, 6),
  19: Point(6, -1),
  20: Point(6, -2),
  21: Point(8, 5),
  22: Point(8, 6)
};

var weights = {'A': 1, 'B': 10, 'C': 100, 'D': 1000};
var neighbours = {
  0: [1],
  1: [0, 2, 4],
  2: [1, 3, 4],
  3: [2, 15],
  4: [1, 2, 5, 7],
  5: [4, 6, 7],
  6: [5, 17],
  7: [4, 5, 8, 10],
  8: [7, 9, 10],
  9: [8, 19],
  10: [7, 8, 11, 13],
  11: [10, 12, 13],
  12: [11, 21],
  13: [10, 11, 14],
  14: [13],
  15: [3, 16],
  16: [15],
  17: [6, 18],
  18: [17],
  19: [9, 20],
  20: [19],
  21: [12, 22],
  22: [21]
};

Iterable<Tuple2<String, int>> validMoves(String pos) sync* {
  for (var i in 0.to(pos.length)) {
    if (!'ABCD'.contains(pos[i])) continue;
    for (var ni in neighbours[i]!) {
      if (ni < 0 || ni >= pos.length) continue;
      // Only move into empty cells
      if (pos[ni] != '0') continue;
      // We cannot move from an open space into the wrong home.
      if (homes[i] == '.' && homes[ni] != '.' && homes[ni] != pos[i]) continue;
      var l = links.keys
          .firstWhereOrNull((e) => (e == Point(i, ni) || (e == Point(ni, i))));
      if (l == null) continue;
      // All good.
      var ret =
          pos.replaceRange(i, i + 1, pos[ni]).replaceRange(ni, ni + 1, pos[i]);
      yield Tuple2(ret, links[l]! * weights[pos[i]]!);
    }
  }
}

class Node {
  int distance;
  String? previous;

  Node([this.distance = 99999999999999999, this.previous]);
}

class Edge {
  String from, to;
  int weight;
  Edge(this.from, this.to, this.weight);
}

class Graph {
  // Use String keys for nodes and edges to make look-up easier.
  var nodes = <String, Node>{};
  var edges = <String, Edge>{};
  var connected = SetMultimap<String, String>();
  Graph();

  // Building algo means that both directions get created separately.
  addEdge(from, to, weight) {
    edges["$from/$to"] = Edge(from, to, weight);
    connected.add(from, to);
    return "$from/$to";
  }

  // Proper version of this function.
  // List<String> neighboursOf(String node) => connected[node].toList();
  List<String> neighboursOf(String node) {
    if (nodes[node] != null) return connected[node].toList();
    nodes[node] = Node();
    var ret = <String>[];
    for (var v in validMoves(node)) {
      if (edgeBetween(node, v.first) == null) addEdge(node, v.first, v.second);
      ret.add(v.first);
    }
    return ret;
  }

  Edge? edgeBetween(String node1, String node2) => edges["$node1/$node2"];
}

// `cameFrom` is global to allow callers to query it.
var cameFrom = <String, String?>{};
dijkstra(Graph graph, start, end) {
  cameFrom = <String, String?>{};
  var costSoFar = <String, int>{};
  cameFrom[start] = null;
  costSoFar[start] = 0;
  var frontier = PriorityQueue<String>(
      (a, b) => (costSoFar[a]!).compareTo((costSoFar[b]!)));
  frontier.add(start);
  while (frontier.isNotEmpty) {
    var current = frontier.removeFirst();
    if (current == end) break;
    for (var next in graph.neighboursOf(current)) {
      var newCost =
          costSoFar[current]! + graph.edgeBetween(current, next)!.weight;
      if (!costSoFar.containsKey(next) || newCost < costSoFar[next]!) {
        costSoFar[next] = newCost;
        frontier.add(next);
        cameFrom[next] = current;
      }
    }
  }
  return costSoFar;
}

// Crude distance to the end point. Used by A* algorithm.
// Must be underestimate.
int heuristic(String locA, String locB) {
  //locB is always 'end', which has distance zero :-) so ignore.

  var dist = 0;
  for (var i in 0.to(locA.length)) {
    //look at each non-zero.
    if (locA[i] == '0') continue;
    // if it's in a home, then dist = 0
    if (locA[i] == homes[i]) continue;
    // else get posloc of its location and its home
    var hi = homes.indexOf(locA[i]);
    var pp = posLocs[i]!;
    var hp = posLocs[hi]!;
    //and calc manhattan distance.
    var md = (pp.x - hp.x).abs() + (pp.y - hp.y).abs();
    // Apply weight for the type.
    dist += (weights[locA[i]]! * md);
  }
  return dist;
}

aStarSearch(Graph graph, String start, String end) {
  var costSoFar = <String, int>{};
  // Build a lookup table of priorities for cells.
  var _heur = <String, int>{};
  var frontier =
      PriorityQueue<String>((a, b) => _heur[a]!.compareTo(_heur[b]!));
  frontier.add(start);
  cameFrom = <String, String?>{};
  cameFrom[start] = null;
  costSoFar[start] = 0;
  while (frontier.isNotEmpty) {
    if (frontier.length % 100 == 0) {
      print(frontier.length);
      print(frontier.first);
    }
    // print(frontier.length);
    var current = frontier.removeFirst();
    if (current == end) {
      break;
    }
    for (var next in graph.neighboursOf(current)) {
      var newCost =
          costSoFar[current]! + graph.edgeBetween(current, next)!.weight;
      if (!costSoFar.containsKey(next) || newCost < costSoFar[next]!) {
        costSoFar[next] = newCost;
        _heur[next] = newCost + heuristic(next, end);
        frontier.add(next);
        cameFrom[next] = current;
      }
    }
  }
  return costSoFar;
}

main() {
  // var lines = File('data/data22_01.txt').readAsLinesSync();
  // var t = DateTime.now();
  // print('${DateTime.now().difference(t).inMilliseconds} milliseconds');
}