My solutions to AOC 2024 in The Rust Programming Language.
The following info is generated automatically
See explanation
To solve the puzzle, I employed the use of two
Vec to efficiently store and manipulate the location IDs from both groups of historians. First, I parsed the input to separate the left-hand side (lhs) and right-hand side (rhs) lists, which I then sorted using the sort() method to facilitate pairing. For calculating the total distance, I iterated through the sorted vectors, summing the absolute differences of the paired elements to get the final distance. Additionally, I created a filter() operation on the rhs vector in the get_similarity function to count occurrences of each element from lhs, allowing me to compute a similarity score based on the frequency of the numbers. This approach leverages sorting and simple iterations, ensuring efficient calculations for the distances and similarities between the two lists.
See explanation
In my solution, I utilized a recursive approach to validate the safety of the reports based on the specified conditions. I designed the function
is_safe to check if the levels in a report are either entirely increasing or decreasing while ensuring that adjacent differences remain within the tolerance range of 1 to 3. If a violation occurs and tolerance is allowed, I tested alternative lists by removing elements to see if the remaining numbers could form a valid sequence, which maintains the safety criteria through the recursive calls. I used a straightforward iterative loop in the count_safe function to count the number of reports that are safe, effectively managing the complexity of the checks. Overall, I leveraged the cloning and reversal of input vectors strategically to handle the two directional checks for safety.
See explanation
I used a
Regex to identify valid mul instructions within the corrupted input, which allows me to extract the relevant numerical values while ignoring any invalid characters. Each valid instruction is transformed into an Instruction enum, enabling clear differentiation between multiplication and control commands. I implemented a Machine struct that maintains an accumulator for results and a state indicating whether execution of multiplication instructions is enabled based on control commands. The run_program method iterates through the parsed instructions and executes them, allowing for a straightforward accumulation of results that can be used to derive the final answer.
See explanation
I used a custom
Grid data structure to represent the letter grid, which allows for easy access to rows, columns, and diagonals. To find occurrences of the target words "XMAS" and "SAMX", I created an iterator over the flattened search results from these dimensions. I then collected each line as a String and used the matches method to count occurrences efficiently. For the second part of the puzzle, I implemented a function is_xmas_grid that checks 3x3 squares to see if they contain specific arrangements of the letters, further aggregating results across multiple test cases.
See explanation
I employed a tuple-based representation using the type
Edge to encapsulate the ordering rules and a vector Path to represent the sequences of pages. To determine if a path adheres to the rules, I created the valid_path function, which checks adjacent page pairs against the ordering rules. When a path is invalid, I extract only the relevant edges using pick_edges, filtering rules that pertain to the current path. For invalid paths, I utilized a directed acyclic graph (DAG) with the Graph structure to perform a topological sort, allowing me to find the correct order for the pages. Finally, I computed the middle page number from valid updates and aggregated the results for the output.
See explanation
I designed the solution by modeling the world as a grid using a
Vec>, where each cell can represent either a guard, obstacle, visited position, or vacant space. The guard's state, including its position and direction, is encapsulated in a GuardState struct, while movement and interaction logic are handled in the World struct through the step method, which processes the guard's movement and updates the grid accordingly. To track positions visited by the guard, I employed a HashSet to store unique coordinates, ensuring efficient O(1) lookup and insertion. The traversal logic makes use of matching and condition checking to determine movements effectively, taking care to handle direction changes upon encountering obstacles. This structure not only maintains clean code but also allows for a straightforward implementation of the simulation.
See explanation
I used a combination of parallel processing and combinatorial generation to evaluate each equation against possible operator placements. By leveraging the
rayon crate for parallel iteration, I ensured that the computation could handle a large input efficiently. For each equation, I employed multi_cartesian_product from the itertools library to generate all possible combinations of operators ('+', '*', and '|') placed between operands. The evaluation of these combinations occurs iteratively, where I maintained an accumulator to compute the result based on the selected operators. If the computed result matches the expected value, I added it to a running total. This approach allows me to efficiently check multiple operators across numerous operand configurations while ensuring correctness through straightforward accumulation and conditional checks.
See explanation
I utilized a combination of the
Vec and Vec2d data structures to effectively manage the two-dimensional representation of the map and the antennas. To identify antinodes, I employed the combinations method from the itertools library to generate pairs of antennas with matching frequencies. In the find_antinodes_pt1 and find_antinodes_pt2 functions, I calculated potential antinode positions based on the distance between antennas while ensuring they remained within map bounds using the out_of_bounds check. By using flat_map and filter, I efficiently collected unique antinode coordinates and calculated their count using unique, which streamlined the process of obtaining the final result.
See explanation
I utilized a combination of custom data structures to represent the disk state efficiently, specifically using a
Vec to store DiskBlock enums for files and free spaces. The main defragmentation is accomplished through the defrag_simple method, which iteratively swaps blocks while maintaining the indices of the first free space and the last block. I also implemented a more advanced defrag_files that seeks optimal free regions for file moves, leveraging vectors to temporarily store file and free region data, ensuring files are properly reorganized while keeping track of their IDs. Finally, I calculated the checksum by iterating through the blocks and multiplying their positions by their corresponding IDs, accumulating the total in an i64 for accurate summation.
See explanation
I utilized a recursive depth-first search approach to explore the hiking trails in the topographic map. The core of the solution involves two functions,
find_trails and distinct_trails, which both traverse the grid starting from a trailhead at height 0. I leveraged a HashSet to keep track of reachable positions during the search, ensuring that duplicate positions were not counted when calculating the score for each trailhead. The map_score function iteratively evaluates each position in the grid, applying either trailhead_score or trailhead_rating to determine the score based on reachable heights, while accumulating the results in a vector for efficient summation. This design facilitates a clear separation of concerns, making it easy to adapt the scoring function as needed.
See explanation
I structured my solution using a series of functions to apply the transformation rules on the integer representations of the stones. I utilized three distinct functions for the rules:
rule1 for the 0-to-1 transformation, rule2 for splitting even-digit numbers into two stones, and rule3 for multiplying by 2024 for other cases. The main transformation is executed in the apply_rules function, which checks the applicable rules in order. To efficiently handle repeated calculations, I implemented a recursive function blink_recursive_count with memoization using a HashMap to store previously computed results based on current stone values and remaining blinks, thereby significantly reducing redundant computations over multiple iterations. Overall, this design optimizes the processing of transformations across potentially exponential growth in stone counts resulting from successive blinks.
See explanation
I used a depth-first search algorithm to identify and traverse regions of garden plots within a grid, tracking visited plots using a
HashSet to avoid re-exploration. Each region's area is calculated by counting the number of plots visited, while the perimeter is computed by collecting the edges of the region, using a HashSet to ensure no duplicates. For perimeter calculations, I leveraged the relationship between edges and vertices to determine which edges contribute to the perimeter based on adjacency rules. I then calculated the total price of fence for all regions, both by multiplying area and edge count, and by using a refined method based on edge orientation, ensuring efficient data handling and accurate calculations throughout.
See explanation
I designed a
ClawMachine struct to encapsulate the button behaviors and prize locations, which allows for easily managing the parameters necessary for each machine. To solve the problem, I employed a method for calculating the minimum token cost to reach the prize using linear equations, manipulating coefficients derived from the claw's movements and button costs. The solve function computes potential button presses by solving for the number of times each button must be pressed, and the cost function aggregates these results, ensuring that only valid combinations of button presses are considered. By iterating through all machines and summing their costs, I effectively obtain the total minimum token expenditure required to claim all prizes.
See explanation
I used a
Vec to store the collection of Robot instances, each containing their position and velocity, represented as Vec2d structs. The Map struct manages robot movements and handles the wrapping behavior at the edges of the defined grid by utilizing modulo arithmetic during position updates in the step function. I implemented the robot simulation by iterating through a specified number of steps in the step_n_times method, while the count_quadrants method calculates the number of robots in each quadrant and returns the counts as an array. Finally, I compute the safety factor by multiplying the counts of robots in each quadrant using the product method on the counts array, ensuring efficient and clear calculations to address the problem requirements.
See explanation
I utilized a custom
Grid structure to represent the warehouse, where each cell can be a wall, vacant space, box, or robot, thus allowing for effective manipulation during the simulation of movements. The robot's movements are processed sequentially, with the algorithm checking surrounding cells to see if it can move or push boxes, relying on recursion to gather pushable boxes in the given direction. Additionally, to handle the scenario of boxes being split into halves during movements, I implemented an enum Box with variants for single boxes and their halves, ensuring accurate tracking of their states. The GPS score is calculated after all movements by summing up the calculated positions of the boxes based on their distance from the warehouse edges. The structure and methods of Warehouse thus efficiently manage the simulation and the subsequent scoring process.
See explanation
To solve the puzzle, I implemented Dijkstra's algorithm to find the shortest path through the maze while considering the specific scoring rules for moving and turning. I utilized a
BinaryHeap as a priority queue to efficiently manage the unvisited nodes based on the current score, and a HashMap to store the minimum distances to each state, which consists of a position and direction. By defining a neighbours method, I generated possible states from the current position by moving forward and turning, while taking care to handle walls correctly. After calculating the distances, I backtracked from the target to identify and count all the optimal path tiles.
See explanation
See explanation
See explanation
I utilized dynamic programming to solve the problem of determining how many designs can be created from the available towel patterns. I maintained a memoization vector,
memo, where memo[i] represents the number of ways to form the substring of the design from the start up to index i. For each character index i in the design, I examined all possible substrings ending at that index, checking if they exist in a HashSet of available patterns. If a valid substring is found, I added the number of ways to form the preceding substring to memo[i]. This approach ensures that I efficiently compute the number of ways to achieve each design by reusing previously computed results, leading to a final count that is maintained through the memoization technique.