-
Notifications
You must be signed in to change notification settings - Fork 0
/
day15.js
123 lines (105 loc) · 3.28 KB
/
day15.js
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
const { data, test } = require('./data/day15');
const parseInput = (input) => {
return input.map((row) => row.split('').map(Number));
};
const getShortestNode = (unvisitedDistances, visited) => {
return Object.entries(unvisitedDistances)
.reduce((currentShortest, [nextKeys, nextDistance]) => {
let currentIsShortest = currentShortest.point === null || nextDistance < currentShortest.distance;
if (currentIsShortest && !visited[nextKeys]) {
return { point: nextKeys.split(',').map(Number), distance: nextDistance };
}
return currentShortest;
}, { point: null, distance: Infinity });
}
const findShortestPath = (map) => {
const visited = {};
const xLen = map[0].length;
const yLen = map.length;
const unvisitedDistances = {};
const start = [0, 0];
unvisitedDistances[String(start)] = 0;
const dest = [xLen - 1, yLen - 1];
let currentNode = {
point: start,
distance: unvisitedDistances[String(start)],
};
let i = 0;
while (!visited[String(dest)]) {
const { point: [pX, pY], distance: d } = currentNode;
const unvisitedNeighbors = [];
// right
if (pX < xLen - 1) {
if (!visited[`${pX + 1},${pY}`]) {
unvisitedNeighbors.push([pX + 1, pY]);
}
}
// down
if (pY < yLen - 1) {
if (!visited[`${pX},${pY + 1}`]) {
unvisitedNeighbors.push([pX, pY + 1]);
}
}
// left
if (pX > 0) {
if (!visited[`${pX - 1},${pY}`]) {
unvisitedNeighbors.push([pX - 1, pY]);
}
}
// up
if (pY > 0) {
if (!visited[`${pX},${pY - 1}`]) {
unvisitedNeighbors.push([pX, pY - 1]);
}
}
unvisitedNeighbors.forEach(([cX, cY]) => {
const nextLen = d + map[cY][cX];
if (typeof unvisitedDistances[String([cX, cY])] === 'undefined' || nextLen < unvisitedDistances[String([cX, cY])]) {
unvisitedDistances[String([cX, cY])] = nextLen;
}
});
visited[String(currentNode.point)] = true;
if (String(currentNode.point) === String(dest)) {
return currentNode.distance;
}
delete unvisitedDistances[String(currentNode.point)];
const nextMinPoint = getShortestNode(unvisitedDistances, visited);
currentNode = nextMinPoint;
i++;
if (i % 5000 === 0) {
console.log({ i, currentNode: String(currentNode.point)});
}
}
return Infinity;
};
const ADVANCE = {
'1': '2',
'2': '3',
'3': '4',
'4': '5',
'5': '6',
'6': '7',
'7': '8',
'8': '9',
'9': '1',
};
const applyAdvanceNTimes = (start, count) => (
Array.from({ length: count }).reduce((agg) => ADVANCE[agg], start)
);
const turnInputIntoInputTimes5 = (input) => {
const expandedInX = input
.map(
(row) => Array
.from({ length: 5 }, () => row.split(''))
.reduce((agg, curr) => [...agg, ...curr], [])
.map((el, idx) => applyAdvanceNTimes(el, Math.floor(idx / input[0].length)))
);
const expandedInY = Array.from({ length: 5 }, () => expandedInX)
.reduce((agg, curr) => [...agg, ...curr], [])
.map((row, idx) => row.map((el) => applyAdvanceNTimes(el, Math.floor(idx / input.length))).join(''))
return expandedInY;
};
const dist1 = findShortestPath(parseInput(data));
console.log(dist1);
const dist2 = findShortestPath(parseInput(turnInputIntoInputTimes5(data)));
console.log(dist2);