Advent of Code 2022 - Day 12: Hill Climbing Algorithm Solution
BFSPart 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")23const readData = () => {4 const data = fs5 .readFileSync("./input", "utf-8")6 .split(/\r?\n/)7 .map(s => s.split(""))8 .filter(Boolean)910 const [numberOfRows, numberOfCols] = [data.length, data[0].length]1112 let start, end1314 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 }2526 return { grid: data, start, end, numberOfRows, numberOfCols }27}2829const main = () => {30 const { grid, start, end, numberOfRows, numberOfCols } = readData()3132 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) <= 13940 const DIRS = [41 [-1, 0],42 [1, 0],43 [0, -1],44 [0, 1],45 ]4647 const bfs = start => {48 const queue = [[start, 0]]49 const visited = new Set([posToStr(start)])50 let res = Number.POSITIVE_INFINITY5152 while (queue.length) {53 const [pos, steps] = queue.shift()5455 if (posToStr(pos) === posToStr(end)) {56 res = steps57 break58 }5960 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 }6970 return res71 }7273 const res = bfs(start)7475 console.log(res)76}7778main()
Part 2
Like Part 1, but we have multiple start positions
Find the shortest in the shortest-es
Implementation
1const fs = require("fs")23const readData = () => {4 const data = fs5 .readFileSync("./input", "utf-8")6 .split(/\r?\n/)7 .map(s => s.split(""))8 .filter(Boolean)910 const [numberOfRows, numberOfCols] = [data.length, data[0].length]1112 let start, end1314 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 }2526 return { grid: data, start, end, numberOfRows, numberOfCols }27}2829const main = () => {30 const { grid, end, numberOfRows, numberOfCols } = readData()3132 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"4041 const DIRS = [42 [-1, 0],43 [1, 0],44 [0, -1],45 [0, 1],46 ]4748 const bfs = start => {49 const queue = [[start, 0]]50 const visited = new Set([posToStr(start)])51 let res = Number.POSITIVE_INFINITY5253 while (queue.length) {54 const [pos, steps] = queue.shift()5556 if (posToStr(pos) === posToStr(end)) {57 res = steps58 break59 }6061 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 }7071 return res72 }7374 const starts = Array.from({ length: numberOfRows }, (_, row) =>75 Array.from({ length: numberOfRows }, (_, col) => [row, col])76 )77 .flat()78 .filter(isElevationA)7980 const res = Math.min(...starts.map(bfs))8182 console.log(res)83}8485main()
References
Comments
Loading comments...
Tags
adventofcode
bfs
Apply and earn a $2,500 bonus once you're hired on your first job!
Clients from the Fortune 500 to Silicon Valley startups
Choose your own rate, get paid on time
From hourly, part-time, to full-time positions
Flexible remote working environment
A lot of open JavaScript jobs!!
Fact corner: Referred talent are 5x more likely to pass the Toptal screening process than the average applicant.
Still hesitate? Read HoningJS author's guide on dealing with Toptal interview process.