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

BFS

## Part 1

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

## Implementation

```.css-ds3kc{display:table-row;}.css-1t8atru{display:table-cell;opacity:0.5;padding-right:var(--chakra-space-6);-webkit-user-select:none;-moz-user-select:none;-ms-user-select:none;user-select:none;text-align:right;}1.css-2qghsv{display:table-cell;}const fs = require("fs")2
3const readData = () => {4  const data = fs5    .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, end13
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 < numberOfCols35  const isAtMostOneHigher =36    currentElevation =>37    ([row, col]) =>38      grid[row][col].charCodeAt(0) - currentElevation.charCodeAt(0) <= 139
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_INFINITY51
52    while (queue.length) {53      const [pos, steps] = queue.shift()54
55      if (posToStr(pos) === posToStr(end)) {56        res = steps57        break58      }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 res71  }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 = fs5    .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, end13
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 < numberOfCols35  const isAtMostOneHigher =36    currentElevation =>37    ([row, col]) =>38      grid[row][col].charCodeAt(0) - currentElevation.charCodeAt(0) <= 139  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_INFINITY52
53    while (queue.length) {54      const [pos, steps] = queue.shift()55
56      if (posToStr(pos) === posToStr(end)) {57        res = steps58        break59      }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 res72  }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()```

Original problem

bfs

## Next Post

Advent of Code 2022 - Day 13: Distress Signal

Dec 13, 2022

Handle conditional statements carefully

## Previous Post

Advent of Code 2022 - Day 11: Monkey in the Middle

Dec 11, 2022

Math and modulo operation

Search Posts