Notebooks 2.0 is here.
exampleMap = parseMap(exampleInput)
isStart = (map) => {
const start = findCellPosition(map, 'S')
return pos => manhattan(pos, start) === 0
}
solvePart1 = R.pipe(
parseMap,
map => findShortestPath(map, findCellPosition(map, 'E'), isStart(map), costFunction(map)),
R.length,
R.add(-1)
)
solvePart1(exampleInput)
solvePart1(input)
isLowEnough = map => pos => getHeight(getCell(map, pos)) === 1
solvePart2 = R.pipe(
parseMap,
map => findShortestPath(map, findCellPosition(map, 'E'), isLowEnough(map), costFunction(map)),
R.length,
R.add(-1)
)
solvePart2(input)
// reverse reachability because pathfinding is done from E to S to make Part 2 easier
costFunction = map => (origin, target) => getHeight(getCell(map, target)) >= (getHeight(getCell(map, origin)) - 1) ? 1 : Infinity
findShortestPath = (map, start, isTarget, getCost, getHeuristic = () => 0) => {
const queue = [start]
const alreadyEnqueued = {}
const visited = {}
const tentativeScores = {[start]: 0}
const heuristicsAdjustedScores = {[start]: getHeuristic(start)}
const parents = {}
const getScore = pos => tentativeScores[hashPosition(pos)] ?? Infinity
while (queue.length) {
// full (but inefficient) A* just for shits and giggles
queue.sort((a, b) => heuristicsAdjustedScores[a] - heuristicsAdjustedScores[b])
const current = queue.shift()
if (isTarget(current)) {
return reconstruct(current, parents)
}
const validNeighbors = getOrthogonalNeighbors(current)
.filter(isInMap(map.size))
.filter(pos => !visited[pos])
for (const neighbor of validNeighbors) {
const cost = getCost(current, neighbor)
if (cost === Infinity) continue
const score = tentativeScores[current] + cost
if (score < (tentativeScores[neighbor] ?? Infinity)) {
tentativeScores[neighbor] = score
heuristicsAdjustedScores[neighbor] = score + getHeuristic(neighbor)
parents[neighbor] = current
}
if (!alreadyEnqueued[neighbor]) {
queue.push(neighbor)
alreadyEnqueued[neighbor] = true
}
}
visited[current] = true
}
}
reconstruct = (pos, parents) => {
let current = pos
const path = [pos]
while (parents[current]) {
current = parents[current]
path.unshift(current)
}
return path
}
findCellPosition = ({data, size}, cell) => indexToCoords(size, data.indexOf(cell))
getOrthogonalNeighbors = ([x, y]) => [
[x - 1, y],
[x, y + 1],
[x + 1, y],
[x, y - 1]
]
hashPosition = ([x, y]) => `${x}/${y}`
getCell = ({data, size}, position) => data[coordsToIndex(size, position)]
getHeight = cell => {
if (cell === 'S') return 1
if (cell === 'E') return 26
return cell.charCodeAt(0) - 96 // a-z maps to 1-26
}
manhattan = ([x1, y1], [x2, y2]) => Math.abs(x2 - x1) + Math.abs(y2 - y1)
import {parseMap, coordsToIndex, indexToCoords, isInMap} from '@senritsu/advent-of-code-2022-day-8'
Purpose-built for displays of data
Observable is your go-to platform for exploring data and creating expressive data visualizations. Use reactive JavaScript notebooks for prototyping and a collaborative canvas for visual data exploration and dashboard creation.
