Install Rust: https://www.rust-lang.org/tools/install.
Tested with rustc 1.65.0.
Run tests with cargo test.
Run benchmarks with cargo bench.
⌛ = Time complexity of solution 📦 = Space complexity of solution (not including the input string)
TODO
Part 1: TODO
⌛O(n)|📦O(1), where TODO
Part 2: TODO
⌛O(n)|📦O(1), where TODO
For both parts we need to sum each continuous run of integers, seperated by blank lines. If only there was a split function on an Iter like there is on a String - I could have just written one 🤔.
Part 1: Track the largest sum and return it.
⌛O(n)|📦O(1), where n is the number of individual rations.
Part 2: Calculate all sums and find the top 3 at the end of a sorted array. The time and space complexity could be improved by just tracking the top 3 sums.
⌛O(n·log(n))|📦O(n), where n is the number of individual rations.
For both parts we can calculate the scores of each round by a simple lookup table of 6 items. I maybe went a bit overboard with trying to design some nice structs for an alternate solution which turned out to be a rather complicated abstraction.
The performance could be further improved by avoiding string handling and looking at the individual bytes which are always at a fixed offset from the last round.
Part 1: Perform a lookup for the score on each line and sum them.
⌛O(n)|📦O(1), where n is the number of rounds.
Part 2: Perform a lookup for the score on each line and sum them.
⌛O(n)|📦O(1), where n is the number of rounds.
Sets are the easiest way to solve this and lead to the most readable code, but performance is better (at least for this specific use case) when performing naieve comparisons with an early return.
Part 1 (Solve 1): Split each rucksack into a set and perform an intersection to find the common element.
⌛O(m·n)|📦O(m), where n is the number of rucksacks and m is the size of each rucksack.
Part 1 (Solve 2): Check the cartesian product of both sides of the rucksack to find a duplicate tuple.
While the complexity of this algorithim is quadratic, the small input size makes this ~4x faster than the overhead of creating and comparing sets.
⌛O(m^2·n)|📦O(1), where n is the number of rucksacks and m is the size of each rucksack.
Part 2: Chunk into groups of 3 elves (rucksacks) and find the single item (char) present in all 3.
We check the rucksacks smallest-to-largest to reduce the search space and quickly cull false possibilites.
⌛O(m^3·n)|📦O(1), where n is the number of rucksacks and m is the size of each rucksack.`
The most complicated part here is parsing each line into 4 numbers so we can perform comparisons on them. 6 lines - I wonder if we can do better?
Part 1: For each pair, parse the 4 values and check if either range is fully contained within the other.
⌛O(n)|📦O(1), where n is the number of elf pairs.
Part 2: For each pair, parse the 4 values and check if the two ranges overlap.
⌛O(n)|📦O(1), where n is the number of elf pairs.
Split the input into two parts - the crate diagram and a list of instructions. We parse the crate diagram into a 2d array of vectors and use the inner ones as stacks as we only ever touch the top elements in a single operation. The instructions are parsed in a fixed format and then applied to the stacks to move elements.
We could make this more efficient by avoiding the temporary array in Part 2. If only get_many_mut was in Stable.
Part 1 (Solve 1): As above, while ensuring that multiple crates moved in a single command end up on the opposite order on the destination stack.
⌛O(s + i)|📦O(s), where s is the number of squares in the crate diagram and i is the number of instructions.
Part 2 (Solve 1): As above, while ensuring that multiple crates moved in a single command end up on the same order on the destination stack.
⌛O(s + i)|📦O(s), where s is the number of squares in the crate diagram and i is the number of instructions.
This day is about finding runs of 4 and 14 unique characters in a string, as well as the index of this run. My second solution for Part 2 was the most interesting an runs in 60% of the time as the first.
Part 1: Compare all characters in a 4-wide sliding window over the input (6 comparisons) and return the index of the found with unique characters.
⌛O(n·m^2)|📦O(1), where n is the length of the input and m is the length of the run to find.
Part 2 (Solve 1): Iterate over each character in each 14-char sliding window and track if it was already found in this window using a fixed-size (26 element) array used as a lookup table. Return the index of the window with no duplicates.
⌛O(n·m)|📦O(1), where n is the length of the input and m is the length of the run to find.
Part 2 (Solve 2): Slide the window across the input, but only handle two the two chars on the edges on each slide/iteration. We use lookup to track how many times we've seen each character and a counter so we know when we have no duplicates in our window.
⌛O(n)|📦O(1), where n is the length of the input and m is the length of the run to find.
The directory traveral commands in our input are the result of a depth-first search of an arbitrary directory tree. Using this assumption, we can simplify the traversal tracking logic to only consider when we actually change directories (the names don't matter at all) and the size of files in a directory.
Part 1: Sum all directories which contain files (directly, or indirectly in child directories) with a combined size of <= 100,000.
⌛O(n)|📦O(m), where n is the number of directories we have to traverse, and m is the depth of the directory tree.
Part 2: Calculate and store the sizes of all directories in an array. Then we determine how much additional space we need (based on the size of the root directory and known constants) and proceed to find the smallest single directory which is larger that this.
⌛O(n)|📦O(n), where n is the number of directories we have to traverse.
This day is about finding adjacent trees and distances from other trees. We start by parsing the input into a 2d array of heights (stored as bytes) and then proceed to cast rays to find visibilities and scores.
An alternate solution for Part 1 (and the most obvious) would have been very similar to part 2 - alongside the scary complexity.
My solution for Part 2 has scary complexity due to casting 4 rays from each and every tree. It feels like there should be a better solution... Maybe for each tree we could store the distance to a tree of each possible height in each direction, then cast a ray from each cardinal direction to calculate the values and a final pass to calculate the top scenic score 🤔. If that worked, the time complexity would be reduced to O(4n + n) = O(n).
Part 1: Start with all trees marked as hidden, then cast rays from the edges along all 4 cardinal directions and mark the visible trees based on their height and if they are obsured by taller trees along the ray's path.
⌛O(n)|📦O(n), where n is the number of trees
Part 2: For each tree on the grid we cast a ray in each of the 4 cardinal directions to calculate it's scenic score.
⌛O(n^3)|📦O(n), where n is the number of trees
Simulating rope! We track the 2D positions of each rope knot and update them on each movement.
We simulate every single step of movement and every square moved but I haven't found a way to avoid this - especially for the 10-knot rope in Part 2.
Part 1: Simulate the head movements and check if the tail is still adjacent. If not we move the tail to the last head position.
⌛O(n)|📦O(1), where n is the number of head movements.
Part 2: Simulate the head movements and iteratively update the tail positions if they are too far from the head. We use a clamped vector (-1,1 for x and y) to move each component adjacent to it's parent again.
⌛O(n·m)|📦O(1), where n is the number of head movements and m is the tail length.
We create an iterator which consumes opcodes and outputs the value of the x register at each cycle (it also takes into account noops and multi-cycle instructions). We then simply consume this iterator to perform the calculations we need at each cycle/time step.
Part 1: Calculate the signal strength from the nth elements (cycles) of the iterator.
⌛O(n)|📦O(1), where n is the number of commands.
Part 2: Calculate the pixel value on each cycle based on the distance from the center of the sprite (xregister value) and output them formatted in a 40x6 grid.
⌛O(n)|📦O(n), where n is the number of commands/cycles/pixels.
For this one I hardcoded the monkey definitions for both the example and the input to avoid parsing them 😅. We loop over the monkeys in each round to process which monkeys their items should end up with.
This gets interesting in Part 2, as there is no longer a safely of dividing each item's worry level by 3. This results in overflows of even a 64-bit usize type as we run 10000 rounds (Not surprising, given the 4th monkey squares their items every round).
The key is that the only property of each item's value we actually care about is the divisibility check that lets each monkey determine who to throw to. If we modulo each item by the LCM of all divisors we test against, the result will remain unchanged but we avoid overflow.
For a larger number of rounds we can also check if there are any repetitions and if at some point the monkey states start to repeat themselves. Part 2 (Solve 2) shows an implementation where we keep track of the number of monkey inspections on each round as well as a hash of the monkey's state. Once we find a round state that we've seen before, we know this will continue to infinity and we can look back in the history to calculate the expected number of inspections of each monkey by the 10000th round.
Possible improvements include:
- Using an
i32instead of ausizefor state. We actually only need to worry about overflow in thex*xoperations, so we could just perform the multiply there and convert back toi32after the modulo. - Using a better squaring-modulo algorithm to avoid overflow with
i32data types entirely. Calculate the actual LCM (least-common-multiple) of all divisors to use for reducing the size of each item. Right now we naievely multiply them all together.Actually, this won't help, as the divisors are all prime numbers so multiplying them all together is the LCM.
Part 1: Run 20 iterations and return the product of the top-2 inspect counts.
⌛O(n·m)|📦O(n), where n is the number of monkeys and m is the number of rounds.
Part 2 (Solve 1): Run 10000 iterations and return the product of the top-2 inspect counts.
⌛O(n·m)|📦O(n·m), where n is the number of monkeys and m is the number of rounds.
Part 2 (Solve 2): Run 10000 iterations and return the product of the top-2 inspect counts. We also check for and skip cycles in the monkey states to avoid similating all 10000 rounds.
⌛O(n·m)|📦O(n·m)), where n is the number of monkeys and m is the number of rounds.
We're tasked to find the length of the shortest route between two points on map considering the traversal requirmements between squares of different heights. We use a simplified version of Dijkstra's algorithm that considers all edges to have the same weight (i.e. moving from one square to any valid adjacent square is always a distance of 1).
Possible improvements include:
- Make this solution truly work for any input in Part 2 by also allowing it to still find the marked starting point if it's actually the closest of all level
amap squares.
Part 1: Find the shortest path from the marked starting point to the marked goal.
⌛O(n)|📦O(n), where n is the number of map squares.
Part 2: Find the shortest path from the marked goal to the closest square at levela. The algorithm is essentially reversed in direction from Part 1.
⌛O(n)|📦O(n), where n is the number of map squares.
This problem involves sorting string packets which consist of nested lists and integer.
Possible improvements include:
- Use a more efficient packet comparison algorithm that doesn't require any allocations. This would avoid adding
mto the space complexity and also result in a sizable speedup.
Part 1: Compare each pair of packets and sum the indices of pairs in the correct order.
⌛O(n·m)|📦O(m), where n is the number of packets and m is the length of each packet.
Part 2 (Solve 1): Sort all individual packets into the correct order and multiply the indices of two specific packets in the resulting sorted list.
⌛O((n·m) * log(n·m))|📦O(n+m)), where n is the number of packets and m is the length of each packet.
Part 2 (Solve 2): For each of the two divider packets, we count the number of input packets that would come before it (2ncomparisons) and therefore allow us to find it's effective index to save us from sorting the entire list.
⌛O(n*m)|📦O(n+m)), where n is the number of packets and m is the length of each packet.
This was a fun one about simulating falling sand. I initially used a HashMap<Position2D> to store a sparse representation of cave tiles blocked by rocks and sand, but after benchmarking, an 2D array of Grid<bool> the simulated cave area is both faster (1/10 the time) and takes less memory (> 22k * 16 bytes down to ~50k * 1 byte). The utilisation of the cave space ends up being around 50% which isn't worth the overhead of a sparse data structure in this instance.
For Part 2 Solve 2, I improved the falling sand algorithm by taking into account that the next block of sand, dropped from the same place, will mostly adhere to the path of the previous block. We store each sand block movement in a stack (to represent the travel path of the previous block) and start our seach for the resting position of the next block above the end position of the previous one.
Part 1: Simulate sand until a block moves down past the lowest level (highest
y) of rock formations.
⌛O(n^3)|📦O(n), where n is the size of the simulated area.
Part 2 (Solve 1): Simulate sand until it gets high enough to block the sand spout.
⌛O(n^3)|📦O(n), where n is the size of the simulated area.
Part 2 (Solve 2): Simulate sand until it gets high enough to block the sand spout. We also use a cache to avoid simulating the entire sand fall path each time.
⌛O(n^2 · log(n))|📦O(n), where n is the size of the simulated area.
For Part 1, we are tasked with finding the total number of points on a single row that are overlapped from diamonds centered on each probe and sized by their nearest beacon. This is simple enough to do with intervals (and a library) to avoid double-counting overlaps.
For Part 2, we can take the same idea but instead find which row of the 4,000,000 row search space has a gap between two intervals. My current solution takes ~7 seconds to run in release mode as it runs 4m times 😱. It was quick to implement after Part 1, but it definitely is not efficient.
Possible improvements for Part 2 would involve a better algorithm or further profiling to find quick wins in the current one.
Part 1: Find the size of the interval on row
xbased on overlapping ranges.
⌛O(n)|📦O(1), where n is the number of probes
Part 2: Find the row with a disjoint interval formed by overlapping ranges.
⌛O(n·m)|📦O(1), where n is the number of probes and m is the y search range
This one took me a long time to get working for both parts. I ended up reading about other people's approaches before I got a working solution, though I didn't copy any code and re-implemented everything myself.
- Parse the input into a directed graph.
- Create matrix to find the distance of each valve to all other valves.
- Find all valves that we would care about travelling to (has a flow rate).
For Part 1, we then perform a depth-first search across all possible orderings of useful valves to see which results in the highest pressure release after 30 minutes. I originally tried a greedy algorithm, but it wasn't quite optimal.
For Part 2, we know that 2 independent actors will take 2 disjoint paths through the available valves (where a path includes a valve that is turned on), as we can't turn on the same valve twice. We build on the algorithm in Part 1, but instead return all subsets of possible paths along with their total pressure release. The solution must then be the maximim sum of the pressure releases of two of these disjoint paths. We can efficiently find this pair by sorting the list of paths by total pressure release and starting a N^2 comparison with early exit.
Part 1: Find the path which results in the highest pressure release, assuming 1 actor.
⌛O(n!)|📦O(n), where n is the number of valves.
Part 2: Find the path which results in the highest pressure release, assuming 2 actors.
⌛O(n! · n)|📦O(n!), where n is the number of valves.
Simulating this problem is like Tetris, except we never make a complete row (I checked).
My solution for Part 1 is a simple simulation with minimal optimisations.
In Part 2 we can't feasibly simulate or store 1 trillion rocks so we have to make some optimisations. The pattern of rock formations eventually repeats after the gas movements provided as an input start cycling. Once we have identified the cycle parameters, we can extrapolate the tower height at any point without simulating it.
To identify the cycle point, we first optimise the data structure holding the rocks to drop old rows that won't be useful again (+ a margin). Then we hash this after each rock and find the point where it looks the same.
Possible future optimisations include:
- Representing each row as a byte (instead of a vector of bool) and each rock shape as an array of bytes. We could then use bitshift operations to simulate the gas jets pushing rocks left and right, and binary OR to stamp dropped rocks into existing formations.
Part 1: Find the height of the tower after 2022 rocks.
⌛O(n)|📦O(n), where n is the number of rocks to drop.
Part 2: Find the height of the tower after 1 Trillion rocks.
⌛O(n)|📦O(n), where n is the number of rocks to drop.
This challenge is about finding the surface area of a 3d grid of cubes.
For Part 1 we simply iterate over each cube and check all 6 neighbors. Each missing neighbor adds 1 to the surface area.
For Part 2 we only want to find the exterior area and exclude any air pockets inside. We do this by running a flood-fill algorithm starting from the outside which counts each exposed face it finds. Since it will never find a path to any interior pockets, this will give us the exterior surface area. Of note is that we also have a 1-wide margin in all dimensions around the object to allow the algorithm to correctly count any faces on the edges.
Possible improvements include:
- Use a flood-fill algorithm in Part 1 starting within the connected mass of cubes.
- Improving the flood-fill algorithm in Part 2 to only traverse across the surface of the volume, rather than also through the empty space.
Part 1: Count empty neighbors of all cubes.
⌛O(n)|📦O(m), where n is the number of cubes and m is the dimensions of the droplet.
Part 2: Flood-fill from outside to find exterior surfaces.
⌛O(m)|📦O(m), where m is the dimensions of the droplet.
We have to find the maximum number of geodes we can mine with each blueprint over the course of 24 (Part 1) or 32 (Part 2) minutes. The possible decisions that we can make are to advance time (to accumulate more resources), or to build a bot (if we have resources available). This continues until time runs out.
Since we should always be looking to expand production if possible to maximise the total output, each decisions are compressed into a choice of what bot to build next and abstracting away the concept of time. e.g. we can wait x minutes until we have enough resources to build A bot, or y minutes to build B bot. Time is fast-forwarded to the point where the new bot is build.
My original solution for Part 2 was waaaay too slow, but reading through the Reddit thread lead me to the optimisation I needed: "Don't build a bot if we're already generating enough resources from that type to build any other bot in 1 minute". It's still quite slow, but now becomes computationally feasible.
Possible improvements include:
- Improving heuristics to cull build orders that are worse that what we've seen so far.
Part 1: Find build order to maximize mined geodes in 24 minutes.
⌛O(n · 2^m)|📦O(m), where n is the number of blueprints and m is the number of minutes.
Part 2: Find build order to maximize mined geodes in 32 minutes.
⌛O(n · 2^m)|📦O(m), where n is the number of blueprints and m is the number of minutes.
I had a lot of trouble understanding the movement logic for this one for some reason. I also got a little messed up by duplicates in the input as well as needing to modulo by len() - 1 instead of len() (I still don't understand why this is needed).
Overall this is a rather inefficent solution, but it was fast enough to solve the problem (~150 ms).
Possible improvements include:
- Implementing an array-based linked list to allow finding, insertion, and removal of elements in
O(1)instead ofO(n). This would bring overall time complexity down toO(n)for both parts.
Part 1: Mix all numbers once and sum numbers at 3 coordinates.
⌛O(n^2)|📦O(n), where n is the count of numbers in the input.
Part 2: Multiply all numbers by a fixed value, mix them 10 times, and sum numbers at 3 coordinates.
⌛O(n^2)|📦O(n), where n is the count of numbers in the input.
This challenge is about evaluating a deeply nested tree of operations.
Possible improvements include:
- Avoid repeating the binary search if we have to change the sort order.
- Using an iterative algorithm instead of recursive to avoid possible stack overflows on larger inputs.
- In Part 2, only evaluate the children that change after updating the value of the "humn" monkey. At the very least, we could only evalute one side of the root node each time which changes.
- After reading about some other people's solutions, we could also use algebra to reverse the operations and directly calculate the value of "humn" once we have calculated the other side of the root node.
Part 1: Recursively evaluate expressions to find the final value of the root node.
⌛O(n)|📦O(n), where n is the number of monkeys.
Part 2: Find the value of given to a monkey which makes both children of the root node evaluate to the same number using a binary search.
⌛O(n log n)|📦O(n), where n is the number of monkeys.
...
A conversion betwen numerical systems. Standard Base-10 and some weird Base-5 thing.
The place values of each digit are as follows.
2 = 2
1 = 1
0 = 0
- = -1
= = -2
Part 1: Convert from SNAFU to decimal, sum all numbers, and convert the sum from decimal to SNAFU.
⌛O(n)|📦O(1), where TODO
Part 2: TODO: Requires all other puzzles to be solved.
~~⌛O(n)|📦O(1), where TODO