AoC 2021 - Day 15 Solutions (Spoilers!)

[Piet Souris]

Haven't started yet, but part A is the same as Project Euler,  exercise 83. So, if you have solved that one, part A should be simplicity itself.

[Stephan van Hulst]

Long day at the office today, so I can't do any coding right now, but my approach would be to turn the entire grid into a graph of neighboring cells, and then apply A*-search.

[Tim Cooke]

I have an idea to solve part 1 and I have no idea whether it is a known algorithm or not. I feel I'd do better at some of these puzzles if my knowledge of maths and algorithms were better.

[Piet Souris]

This is what I had as solution to Pr. Euler:

First a class called Field:

class Veld {
   int x;
   int y;
   int currentValue;
   int originalValue;    // from the input
   int x_voor;           // to recreate the path, once we get to the end
   int y_voor;           // idem
   
   public Veld(int x, int y, int value) {
      this.x = x;
      this.y = y;
      originalValue = value;
      currentValue = -1;
      x_voor = -1;
      y_voor = -1;
   }
   
   @Override
   public String toString() {
      return String.format(
          "x: %d, y: %d, or.val: %d, curr.val: %d, voor_x: %d, voor_y: %d",
          x, y, originalValue, currentValue, x_voor, y_voor
      );
   }
}

and I had this algo (use Google Translate if necessary):
/*
 we gaan het volgende doen; we beginnen met bord[0][0] in de queu
 te mikken. Dan zolang de queu niet leeg is, doen we:

 - haal het eerste element van queu, noem het Q
 - voor elke buurman B van Q, doe:
    - als B.currentValue = -1, dan sla B op in de Queu, met als
      currentValue: Q.curentValue + B.originalValue, en met
      x_voor = Q.x, en y_voor = Q.y
    - anders: als Q.currentValue + B.originalValue < B.currentValue
      sla B op in de queu, met als currentValue = Q.currentValue + B.originalValue
      en x_voor = Q.x, en y_voor = Q.y
 - als de queu leeg is, druk dan bord[80][80] (eigenlijk: bord[79][79]) af.
   De currentValue is dan wat we hebben moeten
*/
did the 80x80 matrix in less than half a second.

[Piet Souris]

Runtime for part A: 0.1 second, part B: 1.9 seconds

[Tim Cooke]

My brain has melted. I'm going to bed.

[Stephan van Hulst]

I analyzed your pseudocode Piet, and it appears to be Dijkstra's shortest path algorithm. It appears to be fast enough for this problem, but before I knew that I decided that I didn't want to risk writing it on the off-chance that it wouldn't be fast enough for part 2.

I chose to implement an A* search instead, which is faster than Dijkstra's algorithm if you pick a good heuristic. I'll post some timings later.

[Tim Cooke]

Currently reading up on Dijkstra's algorithm as a learning exercise as opposed to blindly taking Piet's solution and learning nothing.

Piet wrote:should be simplicity itself.

Speak for yourself :/

I've just reached the "oh that's why most of the solutions I've seen use a priority queue" part of my learning journey. Hopefully by the end of the evening I will have been able to translate it into code and gain some more of those sweet internet points.