Day 8: Haunted Wasteland
Part one done in a reasonable amount of time, and I showed Tim how I'd done it and mentioned how I'm having a bit of trouble with recursive loops, bugs and stuff. He showed me Wallaby.js and Quokka.js, recommending them for immediate test running in the editor to quickly get test results and find failure points. Wallaby looked the most useful to me, although I am yet to write a test. I would like to learn more about this.
Working on part two the following day, I have been having trouble solving it. With my original, brute force, method of stepping every ghost through its path of positions until they reach synchronisation, I was able to get the answer with the test input. However I realised that the compute time with the real input is too long. I can't get an answer.
I actually left it computing last night whilst I went out, and at dinner, Tim, Gabo and I had a really interesting chat about AoC in general and these kind of problems where the compute time of the linear/brute force method is too slow, and how various patterns can essentially be compressed to reduce the amount of cycles that must be performed. When I got back home, it was still computing, and I realised I needed a better solution.
I've had a look online for better ways to approach this and see people have mentioned that each ghost reaches a certain point where it starts looping, and we can count the amount of steps to reach the loop point. There are people talking about finding the LCM (lowest common multiple) of the loop-point step number…
I've come back to part two of this problem days later now that I have some time. I had given the LCM idea some thought after reading that last time, and realised that it actually seemed quite simple and obvious to find how many steps each ghost takes to reach their destination, and find the lowest multiple of those values. Well it wasn't obvious to me until basically being told, but now it's quite embarassing that I even tried to brute force and loop all the ghosts until they reached synchronisation, when there is a clear mathematical solution to the problem.
I didn't know how to find the lowest common multiple of two numbers so found these two functions online, 'gcd' and 'lcmFunction'. I don't quite know how they work and should probably spend some time reading them and about LCM. For now good enough and the problem is solved!
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
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
const inputToUse = realInput;
const inputLines = inputToUse.split(/\n/);
// console.log('inputLines',inputLines);
const stepInstructions = inputLines[0];
const map = [];
inputLines.forEach(function(line){
if( line.includes('=' )) {
const trimmedLine = line.trim();
const lineParts = trimmedLine.split('=');
const posName = lineParts[0].trim();
const pathPosLine = lineParts[1].trim()
.replace('(','')
.replace(')','')
.replace(' ','');
const pathPosArr = pathPosLine.split(',');
const obj = {
posName: posName,
paths: pathPosArr
}
map.push(obj);
}
});
console.log('map',map);
// map and instructions now ready
var lost = true;
var currentPosName = 'AAA';
const destinationPosName = 'ZZZ';
const stepInstrucCount = stepInstructions.length;
var stepsTaken = 0;
var currentInstrucStep = 0;
// part 1 lost
while( lost ) {
if( currentPosName === destinationPosName ) {
lost = false;
} else {
const currentMapPos = Object.values(map).find( (obj) => {
return obj.posName == currentPosName;
});
// console.log('currentMapPos',currentMapPos);
const instrucStep = stepInstructions[currentInstrucStep];
if( instrucStep == 'L' ) {
currentPosName = currentMapPos.paths[0];
} else if( instrucStep == 'R' ) {
currentPosName = currentMapPos.paths[1];
}
stepsTaken = stepsTaken + 1;
// console.log('currentPosName after step',currentPosName);
currentInstrucStep = currentInstrucStep + 1;
if( currentInstrucStep == stepInstrucCount ) {
currentInstrucStep = 0;
}
}
}
// part one unlost
console.log('stepsTaken',stepsTaken);
// part 2
const ghostCurrentPositions = [];
map.forEach(function(mapNode){
// console.log(mapNode);
const posName = mapNode.posName;
const lastChar = posName.slice(posName.length-1);
// console.log('lastChar',lastChar);
if( lastChar == 'A' ) {
ghostCurrentPositions.push(mapNode);
}
});
console.log('ghostCurrentPositions',ghostCurrentPositions);
const ghostsLoopPoints = [];
ghostCurrentPositions.forEach(function(ghostPos, i) {
console.log('ghostPos',ghostPos);
var loopPointFound = false;
var pointsVisited = 0;
var currentInstrucStep = -1;
var posName = ghostPos.posName;
// var posNamesVisited = [];
while( !loopPointFound ) {
// console.log('––– checking pos',posName);
const lastChar = posName.slice(posName.length-1);
// console.log('lastChar',lastChar);
if( lastChar == 'Z' ) {
loopPointFound = true;
}
if( !loopPointFound ) {
pointsVisited = pointsVisited + 1;
currentInstrucStep = currentInstrucStep + 1;
if( currentInstrucStep == stepInstrucCount ) {
currentInstrucStep = 0;
}
const nextPosName = stepGhost(posName,currentInstrucStep);
posName = nextPosName;
}
}
const steps = pointsVisited - 1;
console.log(`this ghost reaches loop in ${steps} steps`);
ghostsLoopPoints.push(pointsVisited);
});
function stepGhost(posName, instrucToUse) {
const currentPos = Object.values(map).find((obj) => {
return obj.posName == posName;
});
const instrucStep = stepInstructions[instrucToUse];
// console.log('instrucStep',instrucStep);
var nextStepName = '';
if( instrucStep == 'L' ) {
// ghostCurrentPositions[i] =
nextStepName = currentPos.paths[0];
} else if( instrucStep == 'R' ) {
nextStepName = currentPos.paths[1];
}
return( nextStepName );
}
function gcd(a, b) {
for (let temp = b; b !== 0;) {
b = a % b;
a = temp;
temp = b;
}
return a;
}
function lcmFunction(a, b) {
const gcdValue = gcd(a, b);
return (a * b) / gcdValue;
}
var workingLCM = null;
console.log('ghostsLoopPoints',ghostsLoopPoints);
ghostsLoopPoints.forEach(function(loopPoint){
if( workingLCM === null ) {
workingLCM = loopPoint;
} else {
workingLCM = lcmFunction(workingLCM, loopPoint);
}
});
console.log('workingLCM',workingLCM);
stepsTaken = workingLCM;
console.log('stepsTaken',stepsTaken);