# AoC Day 15: Beverage Bandits

### Ryan Palo ・1 min read

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 Oct 21 '18

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