advent-of-code

commit cff8a8f417c906500cd267920d5934c4b15c60bd
parent e6b3b458e6ab8decdef578d6974c0ad85a2c0289
Author: finwo <finwo@pm.me>
Date:   Mon, 12 Dec 2022 10:49:26 +0100

2022/12 solution

Diffstat:
A
2022/day-12/index.js
 | 
149
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
A
2022/day-12/sample
 | 
5
+++++

2 files changed, 154 insertions(+), 0 deletions(-)
diff --git a/2022/day-12/index.js b/2022/day-12/index.js
@@ -0,0 +1,149 @@
+const fs            = require('fs');
+const through       = require('through2');
+const line_for_line = require('../common/line-for-line');
+
+String.prototype.startsWith = function(subject) {
+  return this.substr(0, subject.length) === subject;
+};
+
+const grid = [];
+let   dst  = [0,0];
+let   src  = [0,0];
+const x    = 0;
+const y    = 1;
+
+function h(start, goal) {
+  return Math.abs(start[x] - goal[x]) + Math.abs(start[y] - goal[y]);
+};
+
+function reconstruct_path(map, goal, start) {
+  const charmap = new Array(map.length).fill(0).map(() => new Array(map[0].length).fill('.'));
+  charmap[goal[y]][goal[x]] = 'E';
+
+  let current = [...goal];
+  let steps = 0;
+  while(map[current[y]][current[x]]) {
+    const previous = map[current[y]][current[x]];
+    // update graphic
+    if (previous[x] < current[x]) charmap[previous[y]][previous[x]] = '>';
+    if (previous[x] > current[x]) charmap[previous[y]][previous[x]] = '<';
+    if (previous[y] < current[y]) charmap[previous[y]][previous[x]] = 'v';
+    if (previous[y] > current[y]) charmap[previous[y]][previous[x]] = '^';
+
+    current = previous;
+    steps++;
+  }
+
+  process.stdout.write(
+    charmap
+      .map(l => l.join(''))
+      .join('\n')
+    + '\n\n'
+  );
+
+  return steps;
+}
+
+function A_star(grid, src, dst) {
+  const openSet  = [src];
+  const cameFrom = new Array(grid.length).fill(0).map(() => new Array(grid[0].length).fill(false));
+  const fScore   = new Array(grid.length).fill(0).map(() => new Array(grid[0].length).fill(Infinity));
+  const gScore   = new Array(grid.length).fill(0).map(() => new Array(grid[0].length).fill(Infinity));
+  fScore[src[y]][src[x]] = h(src, dst);
+  gScore[src[y]][src[x]] = 0;
+
+  while(openSet.length) {
+
+    // node = the openSet entry with lowest fScore
+    let current = [-1,-1];
+    let currentScore = Infinity;
+    for(let test of openSet) {
+      if (fScore[test[y]][test[x]] < currentScore) {
+        currentScore = fScore[test[y]][test[x]];
+        current      = test;
+      }
+    }
+
+    // if current = goal -> reconstruct_path
+    if ((current[x] == dst[x]) && (current[y] == dst[y])) {
+      return reconstruct_path(cameFrom, current, src);
+    }
+
+    // openSet.Remove(current)
+    openSet.splice(openSet.indexOf(current), 1);
+
+    const neighbours = [
+      [current[x] - 1, current[y]    ],
+      [current[x]    , current[y] - 1],
+      [current[x] + 1, current[y]    ],
+      [current[x]    , current[y] + 1],
+    ].filter(pos => {
+      // Filter out-of-grid possible neighbours
+      if (pos[x] < 0) return false;
+      if (pos[y] < 0) return false;
+      if (pos[x] >= grid[0].length) return false;
+      if (pos[y] >= grid.length) return false;
+      // Filter obstacles
+      if (grid[pos[y]][pos[x]] - grid[current[y]][current[x]] > 1) {
+        return false;
+      }
+      return true;
+    });
+
+    for(const neighbour of neighbours) {
+      const tentative_score = gScore[current[y]][current[x]] + 1;
+      if (tentative_score < gScore[neighbour[y]][neighbour[x]]) {
+        // This path to the neighbour is better than the previous one
+        cameFrom[neighbour[y]][neighbour[x]] = current;
+        gScore[neighbour[y]][neighbour[x]] = tentative_score;
+        fScore[neighbour[y]][neighbour[x]] = tentative_score + h(neighbour, dst);
+        openSet.push(neighbour);
+      }
+    }
+  }
+
+  return -1;
+}
+
+fs.createReadStream('input')
+  .pipe(line_for_line())
+
+  // Turn into paragraphs
+  .pipe(through(function(line, enc, cb) {
+    line = line.toString();
+
+    const elevations = line
+      .split('')
+      .map((char,i) => {
+        if (char == 'S') {
+          src  = [i, grid.length];
+          char = 'a';
+        }
+        if (char == 'E') {
+          dst  = [i, grid.length];
+          char = 'z';
+        }
+        return char.charCodeAt(0) - 97;
+      });
+    grid.push(elevations);
+    cb();
+  }))
+
+  .on('finish', () => {
+    const phase_1 = A_star(grid, src, dst);
+
+    let phase_2 = Infinity;
+    for(let i=0; i<grid.length; i++) {
+      for(let j=0; j<grid[i].length; j++) {
+        if (grid[i][j]) continue;
+        const steps = A_star(grid, [j,i], dst);
+        if (steps < 0) continue;
+        if (steps < phase_2) phase_2 = steps;
+      }
+    }
+
+    console.log({ phase_1, phase_2 });
+
+
+
+  });
diff --git a/2022/day-12/sample b/2022/day-12/sample
@@ -0,0 +1,5 @@
+Sabqponm
+abcryxxl
+accszExk
+acctuvwj
+abdefghi