This week's book giveaway is in the Other Languages forum.
We're giving away four copies of Rust Web Development and have Bastian Gruber on-line!
See this thread for details.
Win a copy of Rust Web Development this week in the Other Languages forum!
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Tim Cooke
  • Campbell Ritchie
  • Ron McLeod
  • Liutauras Vilda
  • Jeanne Boyarsky
Sheriffs:
  • Junilu Lacar
  • Rob Spoor
  • Paul Clapham
Saloon Keepers:
  • Tim Holloway
  • Tim Moores
  • Jesse Silverman
  • Stephan van Hulst
  • Carey Brown
Bartenders:
  • Al Hobbs
  • Piet Souris
  • Frits Walraven

AoC 2021 - Day 15 Solutions (Spoilers!)

 
Bartender
Posts: 4732
183
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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.
 
Saloon Keeper
Posts: 13481
304
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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.
 
Marshal
Posts: 5218
323
IntelliJ IDE Python Java Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
Bartender
Posts: 4732
183
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
This is what I had as solution to Pr. Euler:

First a class called Field:

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
Bartender
Posts: 4732
183
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Runtime for part A: 0.1 second, part B: 1.9 seconds

 
Tim Cooke
Marshal
Posts: 5218
323
IntelliJ IDE Python Java Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
My brain has melted. I'm going to bed.
 
Stephan van Hulst
Saloon Keeper
Posts: 13481
304
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
Marshal
Posts: 5218
323
IntelliJ IDE Python Java Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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.
reply
    Bookmark Topic Watch Topic
  • New Topic