Skip to content

Instantly share code, notes, and snippets.

@MickeyKay
Created January 7, 2023 22:13
Show Gist options
  • Save MickeyKay/304d049113bb379f6acdaf589b24e382 to your computer and use it in GitHub Desktop.
Save MickeyKay/304d049113bb379f6acdaf589b24e382 to your computer and use it in GitHub Desktop.
const util = require('util')
const mapString = `
#.########################################################################################################################
#<^vvv<v^v>^vvv.v<vv<>^^<^><.vvv^>v<^<<<<^>^vv^>^<^>>v>v^v^>^v>vv>^.^..v<^<^^^>>>><<>v<^^^v<>>><>.vv^vv>v.vv<<^<.v...^v.<#
#<^^><><^^^<^>>v^^>v<^vvvv><vv<v.<vv^v<>v^.v^>v^v<>^<>^<vv.v^.^<<<^^^..<.><<v<vv^<v^^>>.><v<vv.>v>><<v.v^<^<v^^^^vv^v>^v>#
#<^.>>v<<vv^^<<<<<.<v<>^>v^v<v<<<^<v^<<vvvv>v<^v<^v<>v.<>v^^^.^vv.<vv>v<^^v^>>.><^.><<<>v^>><^.<><>v^vv>>^v>>.><vvv^<<>v<#
#>v^v<>^<.^.^>><>>..<vv<>^>>vv<.<.<^v<^<>>><<^v.v^<v<vv><v.<v.>v^v^<.v>^v^<^.v>.v.>^<v^>vv><<v.>^>v><<^vv<v^>v>v>.>v>>><.#
#><<<^<v.><>>^>v<^><^<^v.^v<vv<<^^vvv><^^>>>>v^.^^v^<v^^.vv^v^<.v<v^^v<^..>>v<^v^.v^^^^.>v^<vv^<<>><<>vv><^<<^^><..vv.v^.#
#<^>^.^v.><^>.v<v<>^<^<<<<<^^><vv.>^v><^<.>>.><^<v>>>^^^vvv<>v^^^<.^v^<^v<v>^.^.<>v^.v>v<v^<^^vv.^<><>v^>>.^>>><>><>v..^<#
#>.^>^>^.v<vv.<>.>>v<>><^vv>>^<<v^.><^^>^^^.<><><.<v<<^.^<><<^>v<v<v<v>^^<^<v<<...<<>v<v<>.^v>>^^^^<<<><v<^>.^v^.>v<v>v.>#
#<.>.^.<>^^<^v<<^^^^v..<><>^vvv<^>..v<>^vvvv<<<>v^<v.v^<<>v.<^v^>^>>vv<.<<.<^^^v^v<vv<.>^<^.v.<<<v.v^v>v^^<vv^^^>v>v^>><>#
#<v>v>^<vvv^v<^>^v>.<<^v^^>v>^v>^.<<v<vv<<v^<v<^vvv.<>.<>^vv.>^vvv<v<><v^.<^v<..><<><^v..v>^>v<>>.<<>^<^v>v.^><<^v<<.v^>>#
#<<<^<<^v^vv><><<>vv<>...<^<<<vv^^^...<><<<^vv^<vv<^<v>^<^^^^>v^>>.<^<^<>>v^><><v^v>>><v>^^<^.>><><^<v<^.>>v^>^v^v<v^^^<<#
#<>.><^v.vv><.v<v>^.>^><<^<><vv>^v<^>v<^.v^.v<>^.>^>vv>^^>>v<^><^v.>v^>^vvv^^<v<>..v^^<>..v^>v^^^<<>vv^vv>v><<v<.>><<vvv>#
#><><.^^<<<<.<<><v^<v>^>^>vv..v>^v<<v^<^^.<<>^>>.<>>^<<v.^>^^vv>^^v.^<<.>>><v^>.>>^.>>^<^v>^<>v<v.v<.<^.v>^<>v^v>.^.><^v>#
#><>>>>^<>>>v^v^v^vv.<^^.^.^>^v>>v<<^..^>><<.^<v><>v>>><<>vv.<>v.^<^^<v^vv^>v<>v><^^vv>vvv.v><v.<<<<>>>vv>v.>v>>^^v>.^<><#
#<<><><^>^v<>v^.^<.^<v^<v.>.>v^v.<^><<vv<vvv^<>^>.v>>v^><><<<v<.^v>><vv<^v<>^v>v.^<^.><.^<.v^v<^^><>^.^>v>.>^<..<<^>^vv..#
#><v>v.v<>>v<<><>>^<>vv^<<>^vvv^<>^>>v><^<v.<^<<<^><<<<<^.^v><><<><><v.vv^^v.<<<<>.<<>v^.<^.v<v>>v^<..^><v<<^^<^>^^v^>.<>#
#.<<>>>v.<>^<<^v.^<>v<><vv>.^v.^>.<v.>v<.^vvv>v^<<v<><^<v^.>vv^.<<^v^v>>vvv>.>>^>^<<<v.>>.vv>>>^v^vv^v<v<<^>>><.<>>^>v^<<#
#<<>><><>>^v>^>.<v^v..v.v^v^>.><^.><^<>^.>>v.^>vv^v><^..<>^vv<>.<<.<>v^^..>^<>v><<^>^v><<v>..>vvv<.>>v<v<vv<^^v>^v<v^v<v.#
#>vvv.><<<^<>>><<<v><>>>>^v<<.<><vvv.<<^^v.v<>^<>^v.^^>.<v>v>v^v^^<^.v^>^><v>^>>^<>>vvvv<.vv^v<^v^^^.^>^><><^vvv.>.v^<<v>#
#>vv.><>>^.^v<.>vv>>.^v^vv>^v^>>><v<<vv.><^><>.><>>><^<>v^v<>^<<<^>^>^<.><.v>><v<>v>>><vv^.>^v.>v^<>v>v^vv^<v<<^v^v<<^>^>#
#<v^vvv<><<<vv.<^v<<v^^>v^<vvv^^vvv^^>v<.<>v^>>>>^>.^><^>^^<^<^.v>>>v>^<<<v>>.v^v<v><^>>v.<^>^v^vv>>^^vv<<v<v<<vv^<^<.vv>#
#<^>v^^^^vv><>>^>v>^>v<vv<><v.v<^vv><v<^^^^^.<<><v<><^.>^^.<^v>^<v>^<<.v>>^v^^.^<.<v>.^><.>^v^^v<><v<.v<.>>><^>^vv<.^.>><#
#<>^^vvv<<v^vv<<>v>.^<>v^>.vv<vv^>.<^>v>v^>.^v<.<>^<vv^v><^v.^v>^^>v^>>><>vv<>vv>.^v><>.<^^v<<<^>^^^><>^^>^.^>vv<.<><<^>>#
#<<^^..>v>vv<v<>>v<><^<v<v^>.<>v>^^>^v<.v^.<>>.<<>>v^><<^^<>^.<v^vvv^v^<<<^v.^vv^^^<v><<<v^<<>^.<><vvv^<>v<^>.>>><>^v<>v<#
#<>>^.>^^^vv<>^>^<v.^^v><.v<^<vv>^^v><<>v<>>>>>.<^^vv^^^>.<<>v^>>.^.<v^>.>.v^vv>><>.><<^^>>v^>>>^>v<>.^^v>^>vvv^^^^.^^^.<#
#>v<vvv<^^>v^>>^^<vvvv.v.v>^<v^>>v><><<v^.<><v<^>v.<^v<>>^v<.^><^v>^^>v^<v^v>>^vv><v.^<><<v<<<v^v>vv><<^<>v^<<^...<<.<>^<#
########################################################################################################################.#
`;
const map = mapString.split('\n').filter(val => val).map(string => [...string]);
// Trim ### edges
map.shift();
map.pop();
map.forEach(line => {
line.shift();
line.pop();
});
const printMap = () => {
map.forEach(line => {
console.log(line.join(''));
});
console.log('\n');
};
const printStorms = (x = -1, y = -1) => {
const stormMap = [];
map.forEach((line, lineIndex) => {
stormMap.push(new Array(line.length).fill('.'))
});
storms.forEach(storm => {
stormMap[storm.x][storm.y] = storm.direction;
});
stormMap.forEach((line, lineIndex) => {
if (x < 0 || x == lineIndex) {
console.log(line.join(''));
}
});
console.log('\n');
};
// Set up storms array.
const storms = [];
map.forEach((line, x) => {
line.forEach((char, y) => {
if ('^v<>'.indexOf(map[x][y]) !== -1) {
storms.push({
direction: map[x][y],
x,
y,
});
}
})
});
// Memoize storm checks to save time.
let stormChecker = [];
// Update storms.
const updateStorm = (storm) => {
let {direction, x, y} = storm;
if ('^' == direction) {
x--;
} else if ('v' == direction) {
x++;
} else if ('<' == direction) {
y--;
} else if ('>' == direction) {
y++;
}
x %= map.length;
y %= map[0].length;
x = x >= 0 ? x : map.length + x;
y = y >= 0 ? y : map[0].length + y;
storm.x = x;
storm.y = y;
};
const updateStorms = () => {
storms.forEach(storm => {
updateStorm(storm);
})
stormChecker = [];
};
const doesStormOccupyPosition = (x, y) => {
const hasStorm = storms.filter(storm => {
return storm.x == x && storm.y == y;
}).length;
return hasStorm;
}
let stepsArray = [];
const startPosition = [-1,0];
let steps = 0;
let currentPositions = [[startPosition[0], startPosition[1], []]];
let nextPositions = [];
let endReached = false;
let i = 0;
const max = 1000;
while(!endReached && i <= max) {
i++;
console.log(`\nROUND ${i} ============`);
// Move storms.
updateStorms();
//printStorms();
//
while (currentPositions.length) {
let [x, y, history] = currentPositions.shift();
// Check if we're at the end, and if so maybe set a new min!
if (x == map.length - 1 && y == map[0].length - 1) {
console.log('END REACHED!', x, y);
endReached = true;
break;
}
// console.log('checking curr:', x, y)
// Try different directions
let newPositionsToTry = [
[x,y], // Current position (wait)
[x - 1, y], // Up
[x + 1,y], // Down
[x, y - 1], // Left
[x, y + 1], // Right
];
const alreadyInQueue = (x,y) => nextPositions.filter(item => item[0] == x && item[1] == y).length > 0;
newPositionsToTry.forEach(([newX, newY]) => {
// Only proceed if the position exists.
if (
map[newX] && map[newX][newY] // Exists
&& !doesStormOccupyPosition(newX, newY) // Isn't storm
&& !alreadyInQueue(newX, newY) // Not already queued
) {
let newHistory = JSON.parse(JSON.stringify(history));
newHistory.push([newX, newY]);
nextPositions.push([newX, newY, newHistory]);
}
});
// Always push current position since we can always wait.
if (!alreadyInQueue(x, y)) {
let newHistory = JSON.parse(JSON.stringify(history));
newHistory.push([x, y]);
nextPositions.push([x, y, newHistory]);
}
}
if (i == max) {
nextPositions.sort((a, b) => {
if (a[0] > b[0]) return 1;
if (a[0] < b[0]) return -1;
if (a[1] > b[1]) return 1;
if (a[1] < b[1]) return -1;
});
console.log('Valid next positions:', nextPositions.pop())
}
currentPositions = JSON.parse(JSON.stringify(nextPositions));
nextPositions = [];
}
const matching = currentPositions.filter(a => a[0] == map.length - 1 && a[1] == map[0].length - 1 )[0];
console.log(matching)
matching[2].forEach((item, index) => console.log(index + 1, item));
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment