Part 1
Human Solution
I was again lazy this morning and I just did it the dumb way. You can do better than this linear scan of the ranges by doing some sorting of the endpoints. But I took a quick scan of the input file and it’s pretty short so this works out nicely. It seems like it’s just a check that you’ve correctly parsed the input file before proceeding onto part 2.
function part1(path="input.txt")
input = open(path, "r") do f
chomp(read(f, String))
end
range_str, ingredients_str = split(input, "\n\n")
ranges = map(x -> parse.(Int, split(x, "-")), split(range_str, "\n"))
ingredients = parse.(Int, split(ingredients_str, "\n"))
tot = 0
for ingredient in ingredients
for range in ranges
if range[1] <= ingredient <= range[2]
tot += 1
break
end
end
end
return tot
end
GenAI Solution
Another case where it solved it better than me again. But not on the first try: just prompting the model gets us the same approach as I did of just looping through (though it uses some generic functions to make it slightly cleaner).
function solve()
# Read the input file
s = read("input.txt", String)
# Split the input into two parts: ranges and IDs
parts = split(s, "\n\n")
range_lines = split(parts[1], "\n")
id_lines = split(parts[2], "\n")
# Parse the ranges
fresh_ranges = []
for line in range_lines
if !isempty(line)
range_parts = split(line, "-")
start_id = parse(Int, range_parts[1])
end_id = parse(Int, range_parts[2])
push!(fresh_ranges, start_id:end_id)
end
end
# Parse the available ingredient IDs
available_ids = [parse(Int, line) for line in id_lines if !isempty(line)]
# Count how many available IDs are fresh
fresh_count = 0
for id in available_ids
is_fresh = false
for r in fresh_ranges
if id in r
is_fresh = true
break
end
end
if is_fresh
fresh_count += 1
end
end
# Print the result
println(fresh_count)
end
solve()
It’s only when I prompt it to improve that things get interesting. Now I knew that this solution was going to be better than mine just because I was lazy; I could easily describe what to do but I just didn’t want to expend the effort. So easy win for the LLM. But then it surprised me again:
This is great but let’s see if we can make it more efficient. Suppose we sorted the ranges could we do binary search instead of iterating through them all?
Yes, that’s an excellent idea. The current solution has a time complexity of roughly O(NumRanges * NumIDs). We can significantly improve this.
Sorting the ranges is the first step. After sorting, we can merge overlapping or adjacent ranges into a smaller set of disjoint (non-overlapping) ranges. For example, `10-14` and `12-18` would merge into `10-18`.
Once we have a sorted list of disjoint ranges, we can use a more efficient method than checking every range for every ID. Instead of a binary search for each ID, an even faster way is to iterate through both the sorted IDs and the merged ranges simultaneously. This avoids repeated searches and becomes a single-pass check with O(NumRanges + NumIDs) complexity after the initial sort.
I didn’t notice the additional efficiency of sorting the search integers which lets us iterate linearly through both!
function solve()
# Read the input file
s = read("input.txt", String)
# Split the input into two parts: ranges and IDs
parts = split(s, "\n\n")
range_lines = split(parts[1], "\n")
id_lines = split(parts[2], "\n")
# Parse the ranges
ranges = []
for line in range_lines
if !isempty(line)
range_parts = split(line, "-")
start_id = parse(Int, range_parts[1])
end_id = parse(Int, range_parts[2])
push!(ranges, (start_id, end_id))
end
end
# Sort ranges by their start points
sort!(ranges, by = x -> x[1])
# Merge overlapping ranges
merged_ranges = []
if !isempty(ranges)
current_start, current_end = ranges[1]
for i in 2:length(ranges)
next_start, next_end = ranges[i]
if next_start <= current_end + 1
current_end = max(current_end, next_end)
else
push!(merged_ranges, current_start:current_end)
current_start, current_end = next_start, next_end
end
end
push!(merged_ranges, current_start:current_end)
end
# Parse and sort the available ingredient IDs
available_ids = [parse(Int, line) for line in id_lines if !isempty(line)]
sort!(available_ids)
# Count fresh IDs using a single pass
fresh_count = 0
range_idx = 1
for id in available_ids
# Advance past ranges that are entirely before the current ID
while range_idx <= length(merged_ranges) && id > last(merged_ranges[range_idx])
range_idx += 1
end
# If we found a range that could contain the ID, check it
if range_idx <= length(merged_ranges) && id in merged_ranges[range_idx]
fresh_count += 1
end
end
# Print the result
println(fresh_count)
end
solve()
Part 2
Human Solution
Again another fun one. The core realization is that you can align your ingredient lists to be non-overlapping and then just count out the length of the ranges. The original UnitRange struct is immutable so I make my own just to have a little nicer syntax.
mutable struct MyUnitRange
start::Int
stop::Int
end
import Base.length
function length(xx::MyUnitRange)
return length(xx.start:xx.stop)
end
function align!(left::MyUnitRange, right::MyUnitRange)
if left.start > right.start
left, right = right, left
end
lo = left.start
if left.stop < right.start
mid1 = left.stop
mid2 = right.start
hi = right.stop
else
mid1 = right.start - 1
mid2 = right.start
hi = max(right.stop, left.stop)
end
left.start = lo
left.stop = mid1
right.start = mid2
right.stop = hi
end
function part2(path="input.txt")
input = open(path, "r") do f
chomp(read(f, String))
end
range_str, ingredients_str = split(input, "\n\n")
ranges = map(x -> parse.(Int, split(x, "-")), split(range_str, "\n"))
ranges = [MyUnitRange(lo, hi) for (lo, hi) in ranges]
for ii in 2:length(ranges), jj in 1:ii
align!(ranges[ii], ranges[jj])
end
return sum(length.(ranges))
end
GenAI Solution
It’s funny that with my prompting on part 1 then part 2 is now trivial since the LLM already hit upon merging the intervals to be non-overlapping.
Of course. This second part asks for the total count of all unique fresh IDs, ignoring the “available IDs” list.
The most efficient way to do this is to use the same range-merging logic from our improved `part1.jl` script. Once we have the final list of merged, non-overlapping ranges, we can simply sum up the lengths of each of those ranges.
function solve()
# Read the input file
s = read("input.txt", String)
# Split the input and take only the range data
parts = split(s, "\n\n")
range_lines = split(parts[1], "\n")
# Parse the ranges
ranges = []
for line in range_lines
if !isempty(line)
range_parts = split(line, "-")
start_id = parse(Int, range_parts[1])
end_id = parse(Int, range_parts[2])
push!(ranges, (start_id, end_id))
end
end
# If there are no ranges, there are no fresh IDs
if isempty(ranges)
println(0)
return
end
# Sort ranges by their start points
sort!(ranges, by = x -> x[1])
# Merge overlapping ranges
merged_ranges = []
current_start, current_end = ranges[1]
for i in 2:length(ranges)
next_start, next_end = ranges[i]
# Check for overlap or adjacency
if next_start <= current_end + 1
# Merge by extending the current range
current_end = max(current_end, next_end)
else
# No overlap, finalize the current range and start a new one
push!(merged_ranges, (current_start, current_end))
current_start, current_end = next_start, next_end
end
end
# Add the last processed range
push!(merged_ranges, (current_start, current_end))
# Calculate the total number of fresh IDs from the merged ranges
total_fresh_count = 0
for (start_id, end_id) in merged_ranges
total_fresh_count += (end_id - start_id + 1)
end
# Print the final result
println(total_fresh_count)
end