https://kotlinlang.org logo
Join Slack
Powered by
My solution for day 5 part 2, using reverse mappin...
# advent-of-code
w
My solution for day 5 part 2, using reverse mappings and binary search (runs in 15 ms): https://github.com/werner77/AdventOfCode/blob/master/src/main/kotlin/com/behindmedia/adventofcode/year2023/day5/Day5.kt
👍 2
🤯 1
n
Hm, I've tried to run your code against sample input and it prints 35 twice - for part 1 and for part 2. Though per task page it should be 35 for the part 1 and 46 for the part 2. Do you see the same?
w
Ah I see I take part1 as the initial guess which is not correct
The initial guess should be:
Copy code
// We can start with the best estimate based on the boundaries of the ranges
var part2 = seedRanges.minOf { range -> min(almanac.process(range.first), almanac.process(range.last)) }
Fixed and pushed it, thanks for the remark
👍 1
n
I'm still in the process of learning the logic behind the algorithm, therefore trying some simple inputs, and seems I don't get correct answers. For the input like this (exactly this, it is not trimmed)
Copy code
seeds: 2 10

seed-to-soil map:
20 2 1
Program will print answer 2 for the second part. Though for the given seed range 2..11 and mapping 2..2->20..20, it should process input range to two ranges: 20..20 and 3..11, so the minimal start would be 3.
w
Hmm this may be true for non invertible mappings, in your example multiple locations map to the same seed (2 and 20) map both to 2. I’m note sure this is a realistic input, but it might indeed be flaw in the approach. A mathematical function is not invertible if such behaviour exists.
The idea of the approach however is to invert the function so that you search in location space instead of in the seed space. The location space can generally be broken up in ranges and with binary search you alternate between finding the min and max bound of those ranges. The test for validity of a point is if the inverse mapping results in a seed which is in the set of valid seed ranges.
It should be fixable as follows:
Copy code
part2 = binarySearch(lowerBound = 0, upperBound = part2 - 1, inverted = findMin) { value ->
                // Valid if any of the ranges contains the value
                seedRanges.any { range ->
                    val seedValue = inverseAlmanac.process(value)
                    range.contains(seedValue) && almanac.process(seedValue) == value
                }
            } ?: break
Just extending the check by making sure the transformation is valid in both directions
n
Not sure I got about non invertible mappings. In that example seed 2 is mapped to location 20, so by location 20 you can restore seed 2. There is no any other location which is mapped to seed 2.
w
if you fill in location 2 and walk the inverse route you also end up on seed 2, that’s what I meant
However, location 2 is not reachable in a forward manner
it would be an unreachable location
n
Ah, I see
w
To understand the binary search part you would have to read up on the binary search algorithm, however, even without binary search it should run within 10 seconds using the inverse approach (just iterating up from 0 until you find the first valid number)
Copy code
part2 = 0L
        while (true) {
            val valid = seedRanges.any { range ->
                    val seed = inverseAlmanac.process(part2)
                    range.contains(seed) && almanac.process(seed) == part2
                }
            if (valid) break
            part2++
        }
20 seconds actually on my machine
Thanks @Nikita Merinov for spotting the bugs
👍 1
n
For the binary search algorithm in general I'm good as luckily I know what it is 🙂 The thing was that your initial version was suspicious and not clear for me, though to mathematically prove the issue I might not be so good. And the best way to demo the problem is to show an input for which the code will produce the wrong answer. The last part with no binary search and with additional check in straight direction seems to be ok in terms of correctness, without considering run time. Thanks for providing that, I'm now much clear about your logic. But for the binary search version I was still suspicious 🙂 Again to prove my doubts I had no other option to find an input. So here is one:
Copy code
seeds: 1 10

seed-to-soil map:
20 1 5
30 7 4
This will give answer 20 for the part 2, though the correct one should be 6. I've checked with the latest version from your repo.
The part of the logic calling me doubts is - when finding mid and not finding corresponding seed, you may go upper, though the proper value is below.
g
Hi Werner! Really interesting solution, I was finding the same issue for the input Nikita provided.
w
Yes I think indeed it might not be correct
g
My guess is that the current binary search relies on finding a seed value for the first iteration, and if it the search returns null, which consequently returns the original value in part2.
These are the logs I have for the binary search using Nikita’s input:
Copy code
Begin: 0 End: 19 Result: null
Begin: 10 End: 19 Result: null
Begin: 15 End: 19 Result: null
Begin: 18 End: 19 Result: null
Begin: 19 End: 19 Result: null
w
The part looking for a local min can work, however, looking for the next max is not reliable. I can think of some counter examples as well.
As long as there are little gaps between the ranges you may get lucky, as with the actual puzzle input
g
The correct answer seems to be seed 6 for location 6, so I think the current algorithm doesn’t account for values in between the moving window for (begin, end).
Nevertheless, really cool approach to the problem! If you manage to get it working for the edge cases please let me know!
w
The problem with the binary search is that if the mid point (the guess of the search algorithm) ends up to not be in a range than you might be missing values.
I replaced the binary search with a parallel linear search, runs on my machine in ~ 3s.
22 Views
Open in Slack
PreviousNext
Powered by