DEV Community is a community of 788,395 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

Discussion on: AoC Day 15: Beverage Bandits Tiago Romero Garcia

JavaScript solution

After about 20 hours (distributed over 4 days) I finally got this one! I didn't give up, it felt like a real-life project, requiring research and intensive debugging, and after so much effort, it was SOOO satisfying to see it running.!

For me, Part 1 executed in 3 minutes, and Part 2 took 54 minutes!!!

I would be more than happy to answer questions and give tips about that, but basically I really thank @neilgall for his fantastic explanation and the usage of Dijkstra's algorithm.

I'm gonna omit reader.js which is the same as the other solutions and jump to the point:

15-common.js

const MAP = {
WALL: '#',
CAVERN: '.',
GOBLIN: 'G',
ELF: 'E'
};

const ENEMIES = {
[MAP.GOBLIN]: MAP.ELF,
[MAP.ELF]: MAP.GOBLIN
}

const MAX_HP = 200;
const INITIAL_AP = 3;

let generator = 0;
class Square {
constructor({x, y, type}) {
this.x = x;
this.y = y;
this.type = type;

if ([MAP.GOBLIN, MAP.ELF].includes(type)) {
this.unit = {
id: generator++,
type,
square: this,
enemyOf: ENEMIES[type],
hp: MAX_HP,
ap: INITIAL_AP,
isAlive: true
}
}
}
}

const readDungeon = lines => {
const n = lines.length;

const dungeon = Array.from({ length: n }, row => []);

const units = [];
for (let i = 0; i < n; i++) {
let m = lines[i].indexOf(' ');
m = m === -1 ? lines[i].length : m;
for (let j = 0; j < m; j++) {
const square = dungeon[i][j] = new Square({x: i, y: j, type: lines[i][j]});
if (square.unit) {
units.push(square.unit);
}
}
}

return { dungeon, units };
};

const getAdjacents = (dungeon, square, type) => {
const n = dungeon.length;
const m = dungeon.length;

const { x, y } = square;
if (y < m - 1) adjacents.push(dungeon[x][y+1]);
if (x < n - 1) adjacents.push(dungeon[x+1][y]);

}

const getKey = ({ x, y }) => `\${x},\${y}`;

const getMinimumDistance = (dungeon, start, end) => {
const unvisitedSquares = new Set();
const distances = new Map();
const getDistance = square => distances.get(getKey(square));

// Setting initial infinite distances
const n = dungeon.length;
const m = dungeon.length;
for (let i = 0; i < n; i++) {
for (let j = 0; j < m; j++) {
const square = dungeon[i][j];
if (square.type === MAP.CAVERN) {
distances.set(getKey(square), Number.POSITIVE_INFINITY);
}
}
}

distances.set(getKey(start), 0);

let current = start;
while (current) {
const nextDistance = getDistance(current) + 1;
.filter(square => unvisitedSquares.has(square))
.forEach(square => distances.set(getKey(square), Math.min(getDistance(square), nextDistance)));

unvisitedSquares.delete(current);

current = unvisitedSquares.size > 0 ?
[...unvisitedSquares].reduce((minimum, square) => getDistance(minimum) <= getDistance(square) ? minimum : square) :
undefined;
}

const endDistance = Math.min(...getAdjacents(dungeon, end, MAP.CAVERN).map(getDistance));

return { endDistance, getDistance };
};

const getNext = (dungeon, unit, nearest) => {
const { endDistance, getDistance } = getMinimumDistance(dungeon, nearest, unit);
return getAdjacents(dungeon, unit, MAP.CAVERN).find(square => getDistance(square) === endDistance);
};

const step = (unit, nearest) => {
const oldSquare = unit.square;
delete oldSquare.unit;
oldSquare.type = MAP.CAVERN;

nearest.unit = unit;
nearest.type = unit.type;
unit.square = nearest;
};

const move = (unit, units, enemies, openCaverns, dungeon) => {
const allReachables = [];
for (let enemy of enemies) {
const inRange = adjacents.map(square => {
return {
square,
distance: getMinimumDistance(dungeon, square, unit.square).endDistance
};
});
allReachables.push(...reachables);
}

if (allReachables.length > 0) {
const nearest = allReachables.reduce((nearest, square) => nearest.distance <= square.distance ? nearest : square);
const next = getNext(dungeon, unit.square, nearest.square);

step(unit, next);
}
}

const attack = (unit, enemiesInRange) => {
const minHp = enemiesInRange.reduce((min, enemy) => Math.min(min, enemy.hp), MAX_HP);
const weakestEnemy = enemiesInRange.filter(({hp}) => hp === minHp);

weakestEnemy.hp -= unit.ap;

if (weakestEnemy.hp <= 0) {
weakestEnemy.isAlive = false;
weakestEnemy.square.type = MAP.CAVERN;
delete weakestEnemy.square.unit;
delete weakestEnemy.square;
}
}

const getEnemiesInRange = (adjacents, { enemyOf }) => {
.filter(square => square.type === enemyOf && square.unit)
.map(square => square.unit);
};

const sort = units => {
units.sort((a, b) => {
const sA = a.square;
const sB = b.square;
return (sA.x === sB.x) ? sA.y - sB.y : sA.x - sB.x;
});
};

const makeRound = (dungeon, units) => {
const n = dungeon.length;
const m = dungeon.length;

let hasCombatEndedEarly = false;
for (let unit of units) {
if (unit.isAlive) {
// If no enemies, combat ends early
const hasEnemies = units.some(enemy => enemy.type === unit.enemyOf && enemy.isAlive);
if (hasEnemies) {
// Determine action

if (enemiesInRange.length === 0) {
// Moves and attacks
const openCaverns = adjacents.filter(square => square.type === MAP.CAVERN);
const enemies = units.filter(nextUnit => unit.enemyOf === nextUnit.type && nextUnit.isAlive);
if (openCaverns.length > 0 && enemies.length > 0) {
// Moves
move(unit, units, enemies, openCaverns, dungeon);

// Attacks
if (enemiesInRange.length > 0) {
attack(unit, enemiesInRange);
}
}
}
else {
// Attacks
attack(unit, enemiesInRange);
}
}
else {
hasCombatEndedEarly = true;
}
}
}

while (units.some(unit => !unit.isAlive)) {
const nextDead = units.find(unit => !unit.isAlive);
}

sort(units);

return hasCombatEndedEarly;
};

const getOutcome = (rounds, units) => {
const remainingHp = units.reduce((total, unit) => total += unit.hp, 0);
return rounds * remainingHp;
};

const getGoblins = units => units.filter(unit => unit.type === MAP.GOBLIN);
const getElves = units => units.filter(unit => unit.type === MAP.ELF);

const printStats = (rounds, dungeon, units) => {
console.log(`round \${rounds}:`);
console.log(dungeon.map(row => row.map(col => col.type).join('')).join('\n'));
console.log(units.map(u => `\${u.type}(\${u.id}): \${u.hp}`));
}

module.exports = {
makeRound,
getGoblins,
getElves,
printStats,
getOutcome
};

15a.js

const {
makeRound,
getGoblins,
getElves,
printStats,
getOutcome
} = require('./15-common');

(async () => {

const { dungeon, units } = readDungeon(lines);

let goblins, elves, rounds = 0;
do {
const hasCombatEndedEarly = makeRound(dungeon, units);
if (!hasCombatEndedEarly) rounds++;

goblins = getGoblins(units).length;
elves = getElves(units).length;

printStats(rounds, dungeon, units);
} while (goblins > 0 && elves > 0);

console.log(`The \${goblins > 0 ? 'goblins': 'elves'} won!`);
console.log(`The outcome of the combat is \${getOutcome(rounds, units)}`);
})();

15b.js

const {
makeRound,
getElves,
getGoblins,
printStats,
getOutcome
} = require('./15-common');

(async () => {

let ap = 3;
let areAllElvesAlive;
do {
ap++;
console.log(`\nWith AP as \${ap}:`);

const { dungeon, units } = readDungeon(lines);
const elves = getElves(units);
elves.forEach(elf => elf.ap = ap);

let initialElvesCount = elves.length;
let elvesCount, goblinsCount;

let rounds = 0;
do {
console.log(`AP \${ap}, round \${rounds+1}`);
const hasCombatEndedEarly = makeRound(dungeon, units);
if (!hasCombatEndedEarly) rounds++;

goblinsCount = getGoblins(units).length;
elvesCount = getElves(units).length;
areAllElvesAlive = elvesCount === initialElvesCount;
} while (areAllElvesAlive && goblinsCount > 0);

printStats(rounds, dungeon, units);

if (areAllElvesAlive) {
console.log(`\nAll elves survived when AP is \${ap}`);
console.log(`The outcome of the last combat is \${getOutcome(rounds, units)}`);
}
else {
console.log(`There was an elf casualty!`);
}
} while (!areAllElvesAlive);
})(); Ryan Palo

Awesome! Really nice work! Is your path finding algorithm the dijkstra one? Thanks, it was very clear how it works, maybe because it in javascript :), I used it for my solution for part one.

But I didn't understand how you choose the next step exactly. It works, but I can't see where you break the ties in reading order. Anyhow, nicely done, learned how to find shortest route with your code. Tiago Romero Garcia • Edited on

Hi @askeroff , thanks!! Yes, I'm using Dijkstra's algorithm (even though I didn't explicitly mention it in the code), but it's implemented on getMinimumDistance function, where I basically do the following steps to get the minimum step between "start" and "end" squares:

1. create a map for the distances of all squares and set each one of them as Number.POSITIVE_INFINITY
2. create a set to mark unvisited squares and add every square to it
3. set "current" as the unvisited square with the lowest distance (or the "start" square in the beginning)
4. for each unvisited unblocked neighbors of "current", update the distance to the minimum between distance(current)+1 and the neighbor's current distance.
5. mark "current" as visited (by removing it from the unvisited squares set)
6. go back to step 3 and repeat until there are no more unvisited squares

The final distance between "start" and "end" is the smallest distance of all "end"'s unblocked neighbors. Tiago Romero Garcia

Also, to break the ties in the reading order, it's all in getAdjacents function, where I look for the following neighbor squares and return in their reading order.

Considering we're getting adjacents for position X,Y, N=max(X) and M=max(Y)

1. if X > 0, adjacent on X-1,Y
2. if Y > 0, adjacent on X,Y-1
3. if Y < M-1, adjacent on X,Y+1
4. if X < N-1, adjacent on X+1,Y

In other words,

1. Neighbor on the line above
2. Neighbor on the same line, to the left
3. Neighbor on the same line, to the right
4. Neighbor on the line below