JP's Blog

  • GitHub * Flickr * Resume
  • Home Automation
  • Reviews
  • Programming
  • Photography
  • Maker
  • Writing
  • Research
  • Search
  • RSS

Programming, Topic: Dijkstra's Algorithm

All posts

  • 2024-12-20: AoC 2024 Day 20: Shadow Catinator

Recent posts

AoC 2024 Day 20: Shadow Catinator

2024-12-20

Source: Day 20: Race Condition

Full solution for today (spoilers!).

  • Source: Day 20: Race Condition
  • Part 1
    • Version 1: Entirely over complicated…
    • Version 2: Floodfill
    • Version 3: Directly scan along the path
    • Optimization 1: Calculate distances once (Dijkstra’s algorithm)
    • Optimization 2: Store distances in a Grid
    • Pretty pictures
  • Part 2
    • Optimization 3: Store distances in a Grid
    • Optimization 4: Inverting the loop
    • Prettier pictures
  • Benchmarks

Part 1

Given a maze with exactly one path, find how many single walls you can walk through (remove) that shorten the best path by at least 100 units.

read more...

  • All posts: By Date
  • All posts: By Tag
  • RSS: All
  • RSS: programming

All posts unless otherwise mentioned are licensed under Creative Commons License

Any source code unless otherwise mentioned is licensed under the 3 clause BSD license