Instantly share code, notes, and snippets.

Created December 18, 2023 01:55
Show Gist options
• Save ephbaum/1f706b4abe932af7436f6f17fc1e46f2 to your computer and use it in GitHub Desktop.

# Advent of Code Day 17 - Part 1: Clumsy Crucible

## Problem Summary

In this challenge, the objective is to navigate a crucible filled with lava from the starting point to the destination within a city grid. Each block in the grid has a heat loss value, and the goal is to find the path that minimizes the total heat loss while adhering to specific movement rules.

### Movement Rules

• The crucible can move up to three blocks in a single direction but must turn 90 degrees left or right after moving three consecutive blocks.
• It can turn before completing three straight moves.
• It cannot reverse direction immediately; it can only turn left, continue straight, or turn right after entering each city block.

### Modified Dijkstra's Algorithm

We adapted Dijkstra's algorithm, traditionally used for finding the shortest paths between nodes in a graph, to fit the unique requirements of this problem. The modifications include:

1. Graph Representation:
• Each position in the grid is treated as a node.
• The state of each node includes the position on the grid, the current direction of movement, and the number of consecutive moves in that direction.
2. Priority Queue:
• A priority queue is used to keep track of the nodes to be processed, prioritized by the current heat loss.
3. Processing Nodes:
• When a node (grid block) is processed, we calculate the heat loss for all valid next positions based on the movement rules.
• The next positions include only those blocks where a turn is possible, ignoring straight moves directly to the next decision point.
• This significantly reduces the number of states to consider.
4. Symmetry Handling:
• North and south directions are treated equivalently, as are east and west, due to the symmetry of turning options.
• This reduces the complexity of the problem by minimizing redundant paths.
5. End State Check:
• The algorithm terminates when the destination node is processed, and the least heat loss path is found.

Using this modified approach, the algorithm efficiently explores the grid while adhering to the movement constraints and successfully finds the path that incurs the least heat loss.

### Challenges and Solutions

• The main challenge was adapting the algorithm to handle the unique movement rules and efficiently navigate the grid.
• By focusing on decision points for turns and leveraging the symmetry in the movement options, we significantly reduced the search space and complexity.

This tailored approach to Dijkstra's algorithm proved effective for this problem, balancing the need to explore different paths with the efficiency of avoiding unnecessary calculations.

## Part 2: Ultra Crucibles

### Problem Description

• Similar to Part 1 but with different movement constraints for the "ultra crucibles."
• Ultra crucibles must move a minimum of four blocks and a maximum of ten blocks in the same direction before turning.