Advent of Code 2022 - Day 12: Hill Climbing Algorithm Solution

Part 1

Since each step has the same cost of 1, we could use BFS instead of other shortest-path finding algorithms

Implementation

1const fs = require("fs")
2
3const readData = () => {
4  const data = fs
5    .readFileSync("./input", "utf-8")
6    .split(/\r?\n/)
7    .map(s => s.split(""))
8    .filter(Boolean)
9
10  const [numberOfRows, numberOfCols] = [data.length, data[0].length]
11
12  let start, end
13
14  for (let row = 0; row < numberOfRows; row++) {
15    for (let col = 0; col < numberOfCols; col++) {
16      if (data[row][col] === "S") {
17        start = [row, col]
18        data[row][col] = "a"
19      } else if (data[row][col] === "E") {
20        end = [row, col]
21        data[row][col] = "z"
22      }
23    }
24  }
25
26  return { grid: data, start, end, numberOfRows, numberOfCols }
27}
28
29const main = () => {
30  const { grid, start, end, numberOfRows, numberOfCols } = readData()
31
32  const posToStr = ([row, col]) => `${row} ${col}`
33  const isPosInGrid = ([row, col]) =>
34    row >= 0 && row < numberOfRows && col >= 0 && col < numberOfCols
35  const isAtMostOneHigher =
36    currentElevation =>
37    ([row, col]) =>
38      grid[row][col].charCodeAt(0) - currentElevation.charCodeAt(0) <= 1
39
40  const DIRS = [
41    [-1, 0],
42    [1, 0],
43    [0, -1],
44    [0, 1],
45  ]
46
47  const bfs = start => {
48    const queue = [[start, 0]]
49    const visited = new Set([posToStr(start)])
50    let res = Number.POSITIVE_INFINITY
51
52    while (queue.length) {
53      const [pos, steps] = queue.shift()
54
55      if (posToStr(pos) === posToStr(end)) {
56        res = steps
57        break
58      }
59
60      DIRS.map(([dRow, dCol]) => [pos[0] + dRow, pos[1] + dCol])
61        .filter(isPosInGrid)
62        .filter(isAtMostOneHigher(grid[pos[0]][pos[1]]))
63        .filter(pos => !visited.has(posToStr(pos)))
64        .forEach(pos => {
65          visited.add(posToStr(pos))
66          queue.push([pos, steps + 1])
67        })
68    }
69
70    return res
71  }
72
73  const res = bfs(start)
74
75  console.log(res)
76}
77
78main()

Part 2

Like Part 1, but we have multiple start positions

Find the shortest in the shortest-es

Implementation

1const fs = require("fs")
2
3const readData = () => {
4  const data = fs
5    .readFileSync("./input", "utf-8")
6    .split(/\r?\n/)
7    .map(s => s.split(""))
8    .filter(Boolean)
9
10  const [numberOfRows, numberOfCols] = [data.length, data[0].length]
11
12  let start, end
13
14  for (let row = 0; row < numberOfRows; row++) {
15    for (let col = 0; col < numberOfCols; col++) {
16      if (data[row][col] === "S") {
17        start = [row, col]
18        data[row][col] = "a"
19      } else if (data[row][col] === "E") {
20        end = [row, col]
21        data[row][col] = "z"
22      }
23    }
24  }
25
26  return { grid: data, start, end, numberOfRows, numberOfCols }
27}
28
29const main = () => {
30  const { grid, end, numberOfRows, numberOfCols } = readData()
31
32  const posToStr = ([row, col]) => `${row} ${col}`
33  const isPosInGrid = ([row, col]) =>
34    row >= 0 && row < numberOfRows && col >= 0 && col < numberOfCols
35  const isAtMostOneHigher =
36    currentElevation =>
37    ([row, col]) =>
38      grid[row][col].charCodeAt(0) - currentElevation.charCodeAt(0) <= 1
39  const isElevationA = ([row, col]) => grid[row][col] === "a"
40
41  const DIRS = [
42    [-1, 0],
43    [1, 0],
44    [0, -1],
45    [0, 1],
46  ]
47
48  const bfs = start => {
49    const queue = [[start, 0]]
50    const visited = new Set([posToStr(start)])
51    let res = Number.POSITIVE_INFINITY
52
53    while (queue.length) {
54      const [pos, steps] = queue.shift()
55
56      if (posToStr(pos) === posToStr(end)) {
57        res = steps
58        break
59      }
60
61      DIRS.map(([dRow, dCol]) => [pos[0] + dRow, pos[1] + dCol])
62        .filter(isPosInGrid)
63        .filter(isAtMostOneHigher(grid[pos[0]][pos[1]]))
64        .filter(pos => !visited.has(posToStr(pos)))
65        .forEach(pos => {
66          visited.add(posToStr(pos))
67          queue.push([pos, steps + 1])
68        })
69    }
70
71    return res
72  }
73
74  const starts = Array.from({ length: numberOfRows }, (_, row) =>
75    Array.from({ length: numberOfRows }, (_, col) => [row, col])
76  )
77    .flat()
78    .filter(isElevationA)
79
80  const res = Math.min(...starts.map(bfs))
81
82  console.log(res)
83}
84
85main()

References

Original problem