# AoC Day 15: Beverage Bandits

### Ryan Palo ・1 min read

Advent of Code (26 Part Series)

1) AoC Day 1: Chronal Calibration
2) AoC Day 2: Inventory Management System
3 ... 24
3) AoC Day 3: No Matter How You Slice It
4) AoC Day 4: Repose Record
5) AoC Day 5: Alchemical Reduction
6) AoC Day 6: Chronal Coordinates
7) AoC Day 7: The Sum of Its Parts
8) AoC Day 8: Memory Maneuver (Placeholder)
9) AoC Day 9: Marble Mania
10) AoC Day 10: The Stars Align
11) AoC Day 11: Chronal Charge
12) AoC Day 12: Subterranean Sustainability
13) AoC Day 13: Mine Cart Madness
14) AoC Day 14: Chocolate Charts
15) AoC Day 15: Beverage Bandits
16) AoC Day 16: Chronal Classification
17) AoC Day 17: Reservoir Research
18) AoC Day 18: Settlers of The North Pole
19) AoC Day 19: Go With the Flow
20) AoC Day 20: A Regular Map
21) AoC Day 21: Chronal Conversion
22) AoC Day 22: Mode Maze
23) AoC Day 23: Experimental Emergency Teleportation
24) AoC Day 24: Immune System Simulator 20XX
25) AoC Day 25: Four-Dimensional Adventure
26) Advent of Code Wrap-Up

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!

Classic DEV Post from Jun 17

## 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

## 15a.js

## 15b.js

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.

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:`Number.POSITIVE_INFINITY`

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

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)

In other words,

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.

Awesome! Really nice work!

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!

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.

## Parsing

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

## Simulation

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

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: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.

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

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.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.

Full code as ever here

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!

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.

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.

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:

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

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 :(.

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)