Part 1
Human Solution
This is just a classic dynamic programming solution. I was a bit lazy and just used memoization rather than building up the solution iteratively.
using Memoize
function max_joltage(batteries)
@memoize function dp_max_joltage(start, n_left)
n_left == 0 && return 0
start > length(batteries) && return 0
maxval = 10 ^ (n_left - 1) * batteries[start] + dp_max_joltage(start + 1, n_left - 1) # inclusion
for el in (start + 1):(length(batteries) - n_left + 1)
maxval = max(maxval, dp_max_joltage(el, n_left)) # skip
end
return maxval
end
return dp_max_joltage(1, 2)
end
function solve(path = "input.txt")
return sum(max_joltage(parse.(Int, collect(line))) for line in readlines(path))
end
GenAI Solution
It just brute-forced the solution trying all possible combinations. This is O(n^2) but the inputs are all pretty small so not a big deal. It keeps everything as a string which is weird. I forgot about eachline: I’ll have to borrow that for my future solutions.
function get_max_joltage(line::AbstractString)
max_joltage = 0
len = length(line)
if len < 2
return 0
end
for i in 1:len-1
for j in i+1:len
joltage = parse(Int, string(line[i], line[j]))
if joltage > max_joltage
max_joltage = joltage
end
end
end
return max_joltage
end
function solve(filename::AbstractString)
total_joltage = 0
for line in eachline(filename)
total_joltage += get_max_joltage(line)
end
return total_joltage
end
Part 2
Human Solution
Super nice when you just have to change one number and the solution follows:
using Memoize
function max_joltage(batteries)
@memoize function dp_max_joltage(start, n_left)
n_left == 0 && return 0
start > length(batteries) && return 0
maxval = 10 ^ (n_left - 1) * batteries[start] + dp_max_joltage(start + 1, n_left - 1) # inclusion
for el in (start + 1):(length(batteries) - n_left + 1)
maxval = max(maxval, dp_max_joltage(el, n_left)) # skip
end
return maxval
end
return dp_max_joltage(1, 12)
end
function solve(path = "input.txt")
return sum(max_joltage(parse.(Int, collect(line))) for line in readlines(path))
end
GenAI Solution
I was expecting problems here: the brute force strategy that worked on the previous case is going to stumble hard with the increased number of combos. Instead I get something that I do not understand. To be clear it works, but I have no idea how.
function get_largest_number_str(line::AbstractString, num_digits::Int)
n = length(line)
if n <= num_digits
return line
end
k = n - num_digits # number of digits to remove
result_chars = Char[]
for digit in line
while !isempty(result_chars) && result_chars[end] < digit && k > 0
pop!(result_chars)
k -= 1
end
push!(result_chars, digit)
end
# Trim any excess digits from the end to ensure the result has `num_digits` length
while length(result_chars) > num_digits
pop!(result_chars)
end
return String(result_chars)
end
function solve_part2(filename::AbstractString)
total_joltage = BigInt(0)
num_digits = 12
for line in eachline(filename)
largest_num_str = get_largest_number_str(line, num_digits)
if !isempty(largest_num_str)
total_joltage += parse(BigInt, largest_num_str)
end
end
return total_joltage
end
So again I prompt the model to explain it to me:
Of course. Let me break down the logic of the solution.
### The Core Problem
The goal is to find the largest possible 12-digit number you can create from a longer sequence of digits (like a 15-digit string) by picking 12 digits while keeping their original order.
For example, if the input is `818…` and you pick the first `8`, the second `8`, and so on, you are forming a subsequence.
### The Strategy: A Greedy Approach
To construct the largest possible number, you want the digits on the left to be as large as possible. A `9` in the first position is always better than an `8`. This suggests a “greedy” strategy: for each position in our 12-digit result, we should pick the best possible digit we can.
The script implements a very efficient version of this idea. Think of it as building the 12-digit number from left to right.
### How `get_largest_number_str` Works
This is the heart of the solution. It works by iterating through the digits of the input line and maintaining a `result_chars` list, which is our best-so-far number.
Here’s the main logic for each `digit` it looks at:
Is this new digit better than the last one we chose? It compares the current `digit` with the last digit added to `result_chars`.
If the new digit is larger, it means we can potentially form a bigger number. For example, if our result so far is `[‘8’, ‘1’]` and we see a `8`, we realize that the sequence `88…` is better than `81…`.
Trade up! If the new digit is larger, and we still have “discards” available (the number of digits we’re allowed to skip, `k`), we pop the smaller digit from the end of our result. We keep doing this until we can no longer improve the result or we run out of discards.
Add the new digit. After making any possible improvements, the current `digit` is added to the end of `result_chars`.
Let’s trace `8181819…` (we can discard `k=3` digits):
- `8`: `result_chars` is `[‘8’]`
- `1`: `1` is not > `8`. Add it. `result_chars` is `[‘8’, ‘1’]`
- `8`: `8` is > `1`. Pop `1` (use 1 discard, `k=2`). `result_chars` is `[‘8’]`. Now add the new `8`. `result_chars` is `[‘8’, ‘8’]`
- `1`: `1` is not > `8`. Add it. `result_chars` is `[‘8’, ‘8’, ‘1’]`
- `8`: `8` is > `1`. Pop `1` (use 1 discard, `k=1`). `result_chars` is `[‘8’, ‘8’]`. Now add the new `8`. `result_chars` is `[‘8’, ‘8’, ‘8’]`
- …and so on. This process guarantees that it builds the lexicographically largest possible subsequence.
### Final Touches
- Handling descending numbers: If the input is like `9876…`, no “trade-ups” will happen. The code ends up with a list of all 15 digits. The `while length(result_chars) > num_digits` loop cleans this up by removing the smallest digits from the end, leaving the correct 12-digit number.
- `BigInt` for Huge Numbers: The 12-digit numbers and especially their final sum are enormous, far too large for a standard 64-bit integer. The code uses `BigInt` throughout the `solve_part2` function to handle these massive numbers without error.
- `solve_part2` function: This function orchestrates the whole process: it reads each line, calls `get_largest_number_str` to do the hard work, converts the resulting string to a `BigInt`, and adds it to the running total.
This was fascinating! I hadn’t realized that the greedy solution would work here. Score another one for the AI!