mykdavies/index.html

## index.html
<!DOCTYPE html>

<html>
<head>
    <meta charset="utf-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <meta name="scaffolded-by" content="https://github.com/dart-lang/sdk">
    <title>aoc2022_day12</title>
    <link rel="stylesheet" href="styles.css">
    <script defer src="main.dart.js"></script>
</head>

<body>

  <div id="output">
  </div>
  <div id="wrapper">
    <canvas id="canvas" width="1050" height="246"/>
  </div>

</body>
</html>

## main.dart
import 'dart:html';
import 'dart:async';
//import 'package:more/more.dart';
import 'package:collection/collection.dart';

late CanvasElement canvas;
late CanvasRenderingContext2D ctx;
const int cellSize = 6;

void drawCell(Point<int> coords, String color) {
  ctx
    ..fillStyle = color
    ..strokeStyle = "white";

  final int x = coords.x * cellSize;
  final int y = coords.y * cellSize;

  ctx
    ..fillRect(x, y, cellSize, cellSize)
    ..strokeRect(x, y, cellSize, cellSize);
}

void clear() {
  ctx
    ..fillStyle = "white"
    ..fillRect(0, 0, canvas.width!, canvas.height!);
}

var colors = [
  '#003E00',
  '#005E11',
  '#017C26',
  '#08883D',
  '#129255',
  '#1D9A6C',
  '#27AA39',
  '#63B932',
  '#B4C73F',
  '#D3A352',
  '#DD6F66',
  '#E67A98',
  '#EE8FDE',
];

class Runner {
  static const num speed = 50;
  num _lastTimeStamp = 0;
  late Model model;

  Runner() {
    init();
  }
  List<Point<int>> path = [];
  int index = 0;

  void init() {
    model = Model()..init();
    var p = end;
    while (true) {
      path.insert(0, p);
      if (!cameFrom.containsKey(p)) break;
      p = cameFrom[p]!;
    }
    index = 0;
    print('width: $width \t height: $height');
  }

  void update(num delta) {
    final num diff = delta - _lastTimeStamp;

    if (diff > speed) {
      _lastTimeStamp = delta;
      clear();
      for (var n in model.g.nodes.keys) {
        var c = colors[model.g.nodes[n]!.height ~/ 2];
        drawCell(n, c);
      }
      var c = "red";
      for (var i in 0.to(index)) {
        drawCell(path[i], c);
      }
      index += 1;
      if (index >= path.length) return;
    }

    // keep looping
    run();
  }

  Future run() async {
    update(await window.animationFrame);
  }
}

class Model {
  var bluePoint = Point(10, 10);
  var redPoints = [Point(20, 20), Point(30, 30)];
  late Graph g;
  late Map<Point, int> path;
  init() {
    g = buildGraph(lines.split('\n'));
    // Add edges, building the other way round.
    buildEdges(g, (hh, hn) => hh - hn <= 1);

    path = dijkstra(g, start, end);
  }
}

void main() {
  querySelector('#output')?.text = 'AOC 2022 Day 12 - Hill Climbing Algorithm';
  canvas = document.querySelector('#canvas') as CanvasElement;
  ctx = canvas.getContext('2d') as CanvasRenderingContext2D;

  Runner().run();
}

//import 'package:more/more.dart';
// Hack for missing `more` library
extension IntegerRangeExtension on int {
  List<int> to(int end) => List.generate(end - this, (i) => i + this);
}

class Node {
  Point<int> id;
  int height;
  Node(this.id, this.height);
}

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

class Graph {
  var nodes = <Point<int>, Node>{};
  var edges = <String, Edge>{};
  //var connected = SetMultimap<Point, Point>();
  var connected = <Point, Set<Point<int>>>{};
  Graph();

  Node ensure(Node n) => nodes.putIfAbsent(n.id, () => n);

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

  List<Point<int>> neighboursOf(Point node) => connected[node]!.toList();

  // Yuk :-)
  Edge? edgeBetween(Point node1, Point node2) => edges["$node1/$node2"];
}

// Can be used to trace path back (not used in 2022 Day 12)
var cameFrom = <Point<int>, Point<int>>{};
// Returns map of Points examined and their distances from the start.
Map<Point, int> dijkstra(Graph graph, Point<int> start, Point<int> end) {
  cameFrom = {start: Point<int>(-1, -1)};
  var costSoFar = {start: 0};
  var frontier = PriorityQueue<Point<int>>(
      (a, b) => (costSoFar[a]!).compareTo((costSoFar[b]!)));
  frontier.add(start);
  while (frontier.isNotEmpty) {
    var current = frontier.removeFirst();
    if (current == end) break;
    // could use this shortcut here if the Part 2 search takes too long
    // if (graph.nodes[current].height = 0) 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;
}

late int width, height;
Graph buildGraph(List<String> lines) {
  var g = Graph();
  width = lines.first.length;
  height = lines.length;
  var points = [
    for (var y in 0.to(lines.length))
      for (var x in 0.to(lines.first.length)) Point(x, y)
  ];
  //Add the nodes.
  for (var p in points) {
    var c = lines[p.y].substring(p.x, p.x + 1);
    if (c == 'S') {
      start = p;
      c = 'a';
    } else if (c == 'E') {
      end = p;
      c = 'z';
    }
    var h = c.codeUnitAt(0) - 'a'.codeUnitAt(0);
    g.ensure(Node(p, h));
  }
  return g;
}

typedef HeightTest = bool Function(int x, int y);
var dirs = [Point(0, 1), Point(0, -1), Point(1, 0), Point(-1, 0)];

void buildEdges(Graph g, HeightTest edgeTest) {
  for (var h in g.nodes.keys) {
    var hh = g.nodes[h]!.height;
    dirs
        .map((d) => h + d)
        .where((n) => g.nodes.containsKey(n))
        .where((n) => edgeTest(g.nodes[n]!.height, hh))
        .forEach((n) => g.addEdge(h, n, 1));
  }
}

late Point<int> start, end;
part1(List<String> lines) {
  Graph g = buildGraph(lines);
  // Add edges where this height test is valid
  buildEdges(g, (hh, hn) => hh - hn <= 1);

  var path = dijkstra(g, start, end);
  return path[end];
}

// Just solve the same path in reverse, knowing that this will pick
// up any nearer end-points that exist, then examine them.
part2(List<String> lines) {
  Graph g = buildGraph(lines);
  // Add edges, building the other way round.
  buildEdges(g, (hh, hn) => hn - hh <= 1);

  var path = dijkstra(g, end, start);
  return path.entries
      .where((e) => g.nodes[e.key]!.height == 0)
      .map((e) => e.value)
      .min;
}

// Replace the following data within triple quotes with your live data
var lines =
'''Sabqponm
abcryxxl
accszExk
acctuvwj
abdefghi''';

## styles.css
@import url(https://fonts.googleapis.com/css?family=Roboto);

html, body {
  width: 100%;
  height: 100%;
  margin: 0;
  padding: 0;
  font-family: 'Roboto', sans-serif;
}

#output {
  padding: 20px;
  text-align: center;
}
#wrapper {
  width: 1032px;
  height: 246px;
  margin: auto;
  border: solid thin black;
}
	<!DOCTYPE html>

	<html>
	<head>
	<meta charset="utf-8">
	<meta http-equiv="X-UA-Compatible" content="IE=edge">
	<meta name="viewport" content="width=device-width, initial-scale=1.0">
	<meta name="scaffolded-by" content="https://github.com/dart-lang/sdk">
	<title>aoc2022_day12</title>
	<link rel="stylesheet" href="styles.css">
	<script defer src="main.dart.js"></script>
	</head>

	<body>

	<div id="output">
	</div>
	<div id="wrapper">
	<canvas id="canvas" width="1050" height="246"/>
	</div>

	</body>
	</html>
	import 'dart:html';
	import 'dart:async';
	//import 'package:more/more.dart';
	import 'package:collection/collection.dart';

	late CanvasElement canvas;
	late CanvasRenderingContext2D ctx;
	const int cellSize = 6;

	void drawCell(Point<int> coords, String color) {
	ctx
	..fillStyle = color
	..strokeStyle = "white";

	final int x = coords.x * cellSize;
	final int y = coords.y * cellSize;

	ctx
	..fillRect(x, y, cellSize, cellSize)
	..strokeRect(x, y, cellSize, cellSize);
	}

	void clear() {
	ctx
	..fillStyle = "white"
	..fillRect(0, 0, canvas.width!, canvas.height!);
	}

	var colors = [
	'#003E00',
	'#005E11',
	'#017C26',
	'#08883D',
	'#129255',
	'#1D9A6C',
	'#27AA39',
	'#63B932',
	'#B4C73F',
	'#D3A352',
	'#DD6F66',
	'#E67A98',
	'#EE8FDE',
	];

	class Runner {
	static const num speed = 50;
	num _lastTimeStamp = 0;
	late Model model;

	Runner() {
	init();
	}
	List<Point<int>> path = [];
	int index = 0;

	void init() {
	model = Model()..init();
	var p = end;
	while (true) {
	path.insert(0, p);
	if (!cameFrom.containsKey(p)) break;
	p = cameFrom[p]!;
	}
	index = 0;
	print('width: $width \t height: $height');
	}

	void update(num delta) {
	final num diff = delta - _lastTimeStamp;

	if (diff > speed) {
	_lastTimeStamp = delta;
	clear();
	for (var n in model.g.nodes.keys) {
	var c = colors[model.g.nodes[n]!.height ~/ 2];
	drawCell(n, c);
	}
	var c = "red";
	for (var i in 0.to(index)) {
	drawCell(path[i], c);
	}
	index += 1;
	if (index >= path.length) return;
	}

	// keep looping
	run();
	}

	Future run() async {
	update(await window.animationFrame);
	}
	}

	class Model {
	var bluePoint = Point(10, 10);
	var redPoints = [Point(20, 20), Point(30, 30)];
	late Graph g;
	late Map<Point, int> path;
	init() {
	g = buildGraph(lines.split('\n'));
	// Add edges, building the other way round.
	buildEdges(g, (hh, hn) => hh - hn <= 1);

	path = dijkstra(g, start, end);
	}
	}

	void main() {
	querySelector('#output')?.text = 'AOC 2022 Day 12 - Hill Climbing Algorithm';
	canvas = document.querySelector('#canvas') as CanvasElement;
	ctx = canvas.getContext('2d') as CanvasRenderingContext2D;

	Runner().run();
	}

	//import 'package:more/more.dart';
	// Hack for missing `more` library
	extension IntegerRangeExtension on int {
	List<int> to(int end) => List.generate(end - this, (i) => i + this);
	}

	class Node {
	Point<int> id;
	int height;
	Node(this.id, this.height);
	}

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

	class Graph {
	var nodes = <Point<int>, Node>{};
	var edges = <String, Edge>{};
	//var connected = SetMultimap<Point, Point>();
	var connected = <Point, Set<Point<int>>>{};
	Graph();

	Node ensure(Node n) => nodes.putIfAbsent(n.id, () => n);

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

	List<Point<int>> neighboursOf(Point node) => connected[node]!.toList();

	// Yuk :-)
	Edge? edgeBetween(Point node1, Point node2) => edges["$node1/$node2"];
	}

	// Can be used to trace path back (not used in 2022 Day 12)
	var cameFrom = <Point<int>, Point<int>>{};
	// Returns map of Points examined and their distances from the start.
	Map<Point, int> dijkstra(Graph graph, Point<int> start, Point<int> end) {
	cameFrom = {start: Point<int>(-1, -1)};
	var costSoFar = {start: 0};
	var frontier = PriorityQueue<Point<int>>(
	(a, b) => (costSoFar[a]!).compareTo((costSoFar[b]!)));
	frontier.add(start);
	while (frontier.isNotEmpty) {
	var current = frontier.removeFirst();
	if (current == end) break;
	// could use this shortcut here if the Part 2 search takes too long
	// if (graph.nodes[current].height = 0) 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;
	}

	late int width, height;
	Graph buildGraph(List<String> lines) {
	var g = Graph();
	width = lines.first.length;
	height = lines.length;
	var points = [
	for (var y in 0.to(lines.length))
	for (var x in 0.to(lines.first.length)) Point(x, y)
	];
	//Add the nodes.
	for (var p in points) {
	var c = lines[p.y].substring(p.x, p.x + 1);
	if (c == 'S') {
	start = p;
	c = 'a';
	} else if (c == 'E') {
	end = p;
	c = 'z';
	}
	var h = c.codeUnitAt(0) - 'a'.codeUnitAt(0);
	g.ensure(Node(p, h));
	}
	return g;
	}

	typedef HeightTest = bool Function(int x, int y);
	var dirs = [Point(0, 1), Point(0, -1), Point(1, 0), Point(-1, 0)];

	void buildEdges(Graph g, HeightTest edgeTest) {
	for (var h in g.nodes.keys) {
	var hh = g.nodes[h]!.height;
	dirs
	.map((d) => h + d)
	.where((n) => g.nodes.containsKey(n))
	.where((n) => edgeTest(g.nodes[n]!.height, hh))
	.forEach((n) => g.addEdge(h, n, 1));
	}
	}

	late Point<int> start, end;
	part1(List<String> lines) {
	Graph g = buildGraph(lines);
	// Add edges where this height test is valid
	buildEdges(g, (hh, hn) => hh - hn <= 1);

	var path = dijkstra(g, start, end);
	return path[end];
	}

	// Just solve the same path in reverse, knowing that this will pick
	// up any nearer end-points that exist, then examine them.
	part2(List<String> lines) {
	Graph g = buildGraph(lines);
	// Add edges, building the other way round.
	buildEdges(g, (hh, hn) => hn - hh <= 1);

	var path = dijkstra(g, end, start);
	return path.entries
	.where((e) => g.nodes[e.key]!.height == 0)
	.map((e) => e.value)
	.min;
	}

	// Replace the following data within triple quotes with your live data
	var lines =
	'''Sabqponm
	abcryxxl
	accszExk
	acctuvwj
	abdefghi''';
	@import url(https://fonts.googleapis.com/css?family=Roboto);

	html, body {
	width: 100%;
	height: 100%;
	margin: 0;
	padding: 0;
	font-family: 'Roboto', sans-serif;
	}

	#output {
	padding: 20px;
	text-align: center;
	}
	#wrapper {
	width: 1032px;
	height: 246px;
	margin: auto;
	border: solid thin black;
	}