AoC Day 15: Beverage Bandits

Ho ho ho holy cow. Day 15 is a doozy. The elves and goblins are having a battle, and your code is in charge of everything: the decision-making, the path-finding, the moving, the attacking, the HP and more.

Happy war-gaming!

Comments

[Tiago Romero]

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[0].length;

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

    return type ? adjacents.filter(square => square.type === type) : adjacents;
}

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[0].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);
                unvisitedSquares.add(square);
            }
        }
    }

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

    let current = start;
    while (current) {
        const nextDistance = getDistance(current) + 1;
        getAdjacents(dungeon, current, MAP.CAVERN)
            .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 adjacents = getAdjacents(dungeon, enemy.square, MAP.CAVERN);
        const inRange = adjacents.map(square => {
            return {
                square,
                distance: getMinimumDistance(dungeon, square, unit.square).endDistance
            };
        });
        const reachables = inRange.filter(adjacent => adjacent.distance < Number.POSITIVE_INFINITY);
        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)[0];

    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 }) => {
    return adjacents
        .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[0].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
                let adjacents = getAdjacents(dungeon, unit.square);
                let enemiesInRange = getEnemiesInRange(adjacents, unit);

                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
                        adjacents = getAdjacents(dungeon, unit.square);
                        enemiesInRange = getEnemiesInRange(adjacents, unit);
                        if (enemiesInRange.length > 0) {
                            attack(unit, enemiesInRange);
                        }
                    }
                }
                else {
                    // Attacks
                    attack(unit, enemiesInRange);
                }
            }
            else {
                hasCombatEndedEarly = true;
            }
        }
    }

    // Removes dead
    while (units.some(unit => !unit.isAlive)) {
        const nextDead = units.find(unit => !unit.isAlive);
        units.splice(units.indexOf(nextDead), 1);
    }

    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 = {
    readDungeon,
    makeRound,
    getGoblins,
    getElves,
    printStats,
    getOutcome  
};

15a.js

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

(async () => {
    const lines = await readFile('15-input.txt');

    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 { readFile } = require('./reader');
const {
    readDungeon,
    makeRound,
    getElves,
    getGoblins,
    printStats,
    getOutcome  
} = require('./15-common');



(async () => {
    const lines = await readFile('15-input.txt');

    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);    
})();

[Javid Asgarov]

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]

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]

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

[Javid Asgarov]

Oh, awesome. I got it. I want to come back after I've done others and revisit this problem with breadth-first-search. Maybe it'll be faster.

[Ryan Palo]

Awesome! Really nice work!

[Neil Gall]

The lack of discussion here makes me think everyone is having the same trouble I am! My code works for the main worked example in part 1, but counts one extra round and a creature taking one extra hit for each of the other examples. I admit I'm stuck!

[Neil Gall]

I kind of got it to work in the end. With a fudge I got the right answers to the puzzles but it doesn't actually pass all the test cases. Anyway, here goes...

Day 15

Goblins fighting elves. We're getting into serious business now. This puzzle seems quite involved, with a bunch of searching and sorting and a shortest-path finding algorithm. Let's start as usual by building a model and parsing the input.

Model

There's a lot in common with some of the earlier problems. I'm going to try a slightly different approach from Day 13 and model the open positions (i.e. the inverse of the walls) as a set of positions, as that's a useful starting point for the Dijkstra shortest path algorithm.

data class Pos(val x: Int, val y: Int)

enum class Dir { UP, LEFT, RIGHT, DOWN }

enum class CreatureType { ELF, GOBLIN }

data class Creature(val id: Int, val type: CreatureType, val pos: Pos, val hitPoints: Int=200, val attackPower: Int=3)

data class Cave(val size: Size, val openPositions: Set<Pos> = setOf(), val creatures: Map<ID, Creature> = mapOf())

Parsing

Simply a matter of turning the 2D array of characters into a model of the things found.

fun Size.positions(): Sequence<Pos> =
    (0..height-1).asSequence().flatMap { y ->
        (0..width-1).asSequence().map { x -> Pos(x, y) }
    }

fun parse(input: String, elfAttackPower: Int = 3): Cave {
    val rows: List<CharArray> = input.trim().lines().map { s -> s.trim().toCharArray() }
    val size = Size(rows.size, rows.map { it.size }.max()!!)

    val (walls, creatures) = size.positions().fold( Pair(listOf<Pos>(), listOf<Creature>()) ) { (w, c), pos ->
        when(rows[pos.y][pos.x]) {
            '.' -> Pair(w, c)
            '#' -> Pair(w + pos, c)
            'E' -> Pair(w, c + Creature(c.size, CreatureType.ELF, pos, attackPower = elfAttackPower))
            'G' -> Pair(w, c + Creature(c.size, CreatureType.GOBLIN, pos, attackPower = 3))
            else -> throw IllegalArgumentException("unexpected '${rows[pos.y][pos.x]}' at $pos")
        }
    }

    return Cave(size, (size.positions() - walls).toSet(), creatures.associateBy { it.id })
}

Simulation

Let's make use of some nice Kotlin features. Ordering:

val readingOrder: Comparator<Creature> = 
    Comparator<Creature> { 
        c1, c2 -> c1.pos.y - c2.pos.y
    }.then(Comparator<Creature> {
        c1, c2 -> c1.pos.x - c2.pos.x
    })

val attackOrder: Comparator<Creature> =
    Comparator<Creature> {
        c1, c2 -> c1.hitPoints - c2.hitPoints
    }.then(readingOrder)

We'll model the timeline not as an infinite sequence but one that runs until the simulation is stable. Note that this inside the sequence lambda refers to the SequenceScope so we have to qualify it with the label of the outer scope, which is the function name. This is a nice feature of Kotlin and a massive improvement in readability over the outer-class this from Java:

fun Cave.timeline(): Sequence<Cave> = sequence {
    var current: Cave = this@timeline
    while (true) {
        val next = current.turn().validate()
        if (next != current) { 
            yield(next)
            current = next
        } else {
            break
        }
    }
}

Let's start with a basic structure for turns then flesh it out from there. This is really similar to the minecart-crashing scenario from two days ago. It was not clear in today's puzzle description whether actions should all apply at the end of a round, or as they happen. So I wrote the code in a way that each creature returns an Action from its turn, and I could apply them in different ways to experiment.

There's still an issue here as while I got the right answers in the end there's a cosmological constant fudge in my solution (well, a subtraction of one) and it only gives the correct result for some of the example inputs.

fun Cave.turn(): Cave {
    val scanOrder: List<Creature> = creatures.values.sortedWith(readingOrder { it.pos })

    val newCreatures = scanOrder.fold(creatures) { creatures_, c ->
        val action = c.takeTurn(openPositions, creatures_.values)
        action.applyTo(creatures_)
    }

    return copy(creatures = newCreatures)
}

The update is tricky as we need to deal with creatures that have possibly died, and also remove creatures which die during an attack.

fun Creature.isDead(): Boolean = hitPoints <= 0 

fun Action.applyTo(creatures: Map<ID, Creature>): Map<ID, Creature> = when(this) {
    is Action.None ->
        creatures

    is Action.Move -> {
        val c = creatures[id]?.copy(pos = pos)
        if (c == null) creatures else creatures + (id to c)
    }

    is Action.Attack -> {
        val damage = creatures[attacker]?.attackPower ?: 0
        val c = creatures[attacked]?.let { it.copy(hitPoints = it.hitPoints - damage) }
        if (c == null || c.isDead()) creatures - attacked else creatures + (attacked to c)
    }

    is Action.Multiple ->
        actions.fold(creatures) { cs, a -> a.applyTo(cs) }
}

The meat comes in each creature's turn. If it can't attack it moves. After it has moved if it can attack it does so. The orderings defined above come in useful for selecting the target to attack and the best target to move towards.

Moving is an application of Dijkstra's shortest path algorithm, uses in the moveTowards() inner function. For the product of valid start positions (which are neighbours as a creature can only move one step) and potential targets we calculate the shortest path. Then take the shortest of those, if present, and move to the associated start position.

fun Creature.takeTurn(openPositions: Set<Pos>, otherCreatures: Collection<Creature>, vis: Visualiser): Action {
    val unblocked: Set<Pos> = openPositions - otherCreatures.map { c -> c.pos }
    val targets: List<Creature> = otherCreatures.filter { c -> c.type != type }

    fun canAttackFrom(p: Pos): Boolean = targets.any { t -> t.pos.isNeighbour(p) }
    fun attackTargetAt(p: Pos): Creature? = targets.filter { t -> t.pos.isNeighbour(p) }.minWith(attackOrder)

    fun moveTowards(targets: List<Creature>): Pos? {
        val validStarts = pos.neighbours.filter(unblocked::contains)
        val goals: List<Goal> = targets.flatMap { target -> 
            validStarts.mapNotNull { start -> 
                dijkstra(start, target.pos, unblocked, vis)?.let { d -> Goal(start, target.pos, d) }
            }
        }
        return goals.minWith(shortestDistance)?.start
    }

    val newPos = if (canAttackFrom(pos)) pos else moveTowards(targets) ?: pos
    val moveAction = if (newPos != pos) Action.Move(id, newPos) else Action.None
    val attackAction = attackTargetAt(newPos)?.let { t -> Action.Attack(id, t.id) } ?: Action.None

    return moveAction + attackAction
}

Dijkstra's algorithm is straightforward. At this point I guess I should admit I once worked at TomTom and this stuff was bread and butter for me in those days.

1. Start with a set of unvisited nodes, and a current node at the start node with a distance of 0
2. While there are unvisited nodes:
   • Go to all unvisited unblocked neighbours of the current node and update the distance to (current+1) if that is less than that node's current value
   • Remove the current node from the unvisited set
   • Make the unvisited node with the shortest distance the current node
3. At the end, if there is a distance recorded on the end node, that is the shortest distance from start to end

fun dijkstra(start: Pos, end: Pos, unblocked: Set<Pos>, vis: Visualiser): Int? {
    val unvisited = (unblocked + end).toMutableSet()
    val distances = mutableMapOf<Pos, Int>()
    fun distance(p: Pos) = distances[p] ?: NO_PATH

    distances[start] = 0
    var current: Pos? = start

    while (current != null && distance(current) != NO_PATH && !unvisited.isEmpty()) {
        var neighbourDistance = distance(current) + 1
        var validNeighbours = current.neighbours.filter(unvisited::contains)

        validNeighbours.forEach { n ->
            distances[n] = minOf(neighbourDistance, distance(n))
        }

        unvisited.remove(current)
        current = unvisited.minBy(::distance)

        // vis(start, end, current, unvisited, distances)
    }

    return distances[end]
}

Full code as ever here

[Tiago Romero]

I have been working only on this problem for the past 2 days. I must have already spent 10 hours or so. I have a working solution for all the examples but not for the real solution.

Long story short, I had decided to use a greedy algorithm and after I saw your reply I will now try with Dijkstra's algorithm.

Thank you so much!

[Mustafa Haddara]

The lack of discussion is because no one wants to do it, haha.

This problem has probably taken me 5+ hours over the entire weekend, and I still haven't gotten part 1...yet. I'm not too excited about this kind of problem because it just feels like a lot of...grunt work? I guess? The instructions feel too detailed, so I feel like I'm just some typist inscribing someone else's algorithm instead of actually coming up with the algorithm.

[Neil Gall]

Agreed, I was reading the description over and over looking for what I missed rather than googling for better algorithms or a problem insight. I got through it - kind of - but it wasn't as fun as many of the others.

[E. Choroba]

I had a stupid bug in the shortest path searching - I forgot to update the distance in some cases. What helped me a lot to debug the issue was this reddit answer which contains a correct solution shown step by step, so you can compare yours and analyse the differences.

I guess posting the code in this case is useless. It's 342 lines of Perl code that started with good intentions (objects in Moo with lazy builders and after modifiers) but grew a bit dishevelled alongside my frustration.

Here's an animation of the part 2 solution:

[Carsten]

this did cost me a lot of time (around 3.5 hours) - I don't mind to much (was fun) but I hope we don't see this kind of long problem on a weekday

[Gerard Klijs]

I got it working for part 1 and for all the examples of part 2, but still my solution for part 2 isn't correct :(.

[Carsten]

it seems there are some border cases with selection - say you have multiple paths of the same length to attacking-positions

as I understand it you should select the one from those where end up in the first attacking-positions in reading order!

I made a mistake here first as well - I reused an A* algorithm I keep around for AoC (it was handy in every single year) and I did not really concentrate while reading so I thought it a good idea to use the simple manhatten-distance for a heuristic.

Luckily the example given showed me the mistake rather quickly.

Overall I'm actually not sure if I got it really right but my algorithm worked for my input on both parts.

If you have your input around I can test it and give you the answer (I'm actually curious if mines would be right)