https://kotlinlang.org logo
Join Slack
Powered by
<Advent of Code 2023 day 5> :thread:
# advent-of-code
a
k
It seems I have finally awoken this month
🙌 4
⭐ 4
👏 2
j
Oh man my part2 solution is slow, maybe I'll get back this evening to use a better idea to do it. https://github.com/bulldog98/advent-of-code/blob/main/advent2023/src/main/kotlin/year2023/Day05.kt
☝️ 1
a
looking at my part 2 solution going on endlessly, I'm sure the correct way to do it is in reverse 🤦 -> start with each of the locations (ascending) and figure out which ranges of existing seeds can fall into the smallest possible
or create intersections of ranges from top to bottom
e
https://github.com/ephemient/aoc2023/blob/main/kt/aoc2023-lib/src/commonMain/kotlin/com/github/ephemient/aoc2023/Day5.kt I spent quite a while chasing an off-by-one bug in part 2. I probably would have gotten an answer faster doing it the "slow" way, but then I would have spent more time cleaning up after it, so I guess it all works out.
m
I knew the trick to part 2 pretty fast, but debugging ranges and manually constructing them gave me off-by-one errors
m
Part 1
x
hmm i think i bruteforced part 2.. somehow 🤔 not sure if i saw the trick or not, but it took a while
p
needed to rubber duck programming hard to debug my part2. partner not believing i'm still sane
I used Pair(min, max) and did the intersections manually and got a fast solution
downside is if it goes wrong, and it did, debugging was a pain in the butt
x
@Michael de Kaste dont want to spoil myself the trick - but how long does it take to solve 2? mine took 
4m 49.512857667s
- is that about the same time it took you with your trick?
m
Part 2
Whew...
n
Not looking at your solutions yet, but my brute-force solution for part 2 produces the correct result for the sample but not the input. The only optimizations I have done so far is to avoid looking at the same seed value multiple times (assuming there are overlaps in the seed ranges). This runs for 10 minutes, but then produces the wrong result.
p
here's my part 2, not cleaned up and probably not very readable:
bright side, it takes 36ms to spit out the result
m
Under 1ms for my part 2 😄
🙌 3
x
mine is 
4m 49.512857667s
crap
i guess i brute-forced it and got lucky 😅
n
I still do not see a way to avoid looking at all non-duplicated seed values. I thought of caching results from the 7 mappings, but that runs OOM.
n
Until the last moment I was hoping that there is some solution without dealing with all those stuff with ranges, overlappings etc 😞 But had to implement it, and it seems to be not so scary, but spent quite some time on debugging when trying to properly calculate overlaps.
j
Spent over an hour implementing an optimized solution that runs in ~1ms. Went back and spent a few minutes on the brute force solution which runs in 6m24s. So I guess I should have gone with brute force first. 😅
m
> I still do not see a way to avoid looking at all non-duplicated seed values. Since the mappings form continuous ranges, you only need to look at one seed value from each seed value range. (And then same for every following stage)
n
I see the continuous ranges in the sample data, but where in the puzzle did it state that the ranges do not have holes?
but of course I should optimize the mappings to combine them if possible. Will do now.
k
OMG, I got lucky, I forgot to implement the fact that unmapped values map to themself
m
That's not fair, it took a fair bit of time to code that (find the unmapped ranges). 😄
Wow it also happens to work on my input if I remove it... but doesn't on the sample input.
r
Took 4m for part 2 😬
m
Part 2 (cheesy version that doesn't do unmapped ranges and won't work for all inputs, but quite a bit shorter than the proper version, and works for my input)
j
Hi Kotlin experts 😉 Today I'm facing a refactoring challenge. I already have 
fun Iterable<IntRange>.union(): List<IntRange>
in my utils class but today I need 
fun Iterable<LongRange>.union(): List<LongRange>
. Since 
IntRange
and 
LongRange
don't have any common predecessor (or do they? maybe I could use 
ClosedRange
) it seems that I need to have the same code duplicated in my utils. However, even after duplicating the function, during (JVM) compilation I'm getting 
Platform declaration clash: The following declarations have the same JVM signature (union(Ljava/lang/Iterable;)Ljava/util/List;)
. Is there some way how to create a 
union
function that works for both 
IntRange
and 
LongRange
? I.e. ideally by declaring it so that it can work with both (and returns corresponding type) or declaring it twice without compilation signature conflict?
n
Your idea about using common 
ClosedRange
seems to be good. Was there any issues with that?
j
to start with... (even though 
ClosedRange
only accepts 
Comparable
). But I'm not sure about 
T : ClosedRange<T>
syntax, looks weird.
👀 1
n
@Marcin Wisniowski: your code also seems to assume that the destination for all transformations of a mapping are aligned. There could be a mapping of 2 transformations: 1..5 => +3 and 6..9 => + 6. This then would mean we could not combine these into a single 1..9 transformation, correct?
m
My code does not combine them, these would be two separate mapped ranges, one with a shift of 3 and one with a shift of 6.
p
A fun part2 - splitting ranges into mapped ranges. Solves part2 in ~6ms cold, ~150us once warmed up.
Day05.kt
m
first attempt at a cleanup of today, does reduce quite nicely after you get what the problem wants;
Copy code
object Day5 : Challenge() {
    val parsed = input.splitOnEmpty().let {
        it.first().substringAfter("seeds: ").split(" ").map { it.toLong() } to it.drop(1).map {
            it.lines().drop(1).map { it.split(" ").map { it.toLong() } }
        }.map { maps ->
            buildMap {
                maps.forEach { (target, source, range) ->
                    put(source..<source + range, target - source)
                }
            }
        }
    }

    override fun part1(): Any? {
        val almanac = parsed.second
        val seeds = parsed.first
        return seeds.minOf {
            almanac.fold(it) { source, range ->
                source + (range.entries.firstOrNull { (targetRange, _) -> source in targetRange }?.value ?: 0L)
            }
        }
    }

    private fun LongRange.add(add: Long): LongRange = (start + add)..(last + add)
    private fun LongRange.rangeIntersect(other: LongRange) =
        max(first, other.first)..min(last, other.last)

    override fun part2(): Any? {
        val almanac = parsed.second
        val seeds = parsed.first.chunked(2).map { (seed, range) -> seed..<seed + range }
        fun recursiveMinimalSliver(range: LongRange, step: Int): Long {
            return when (step) {
                almanac.size -> range.first
                else -> almanac[step].mapNotNull { (target, step) ->
                    target.rangeIntersect(range).takeUnless { it.isEmpty() }?.add(step)
                }.minOfOrNull {
                    recursiveMinimalSliver(it, step + 1)
                } ?: range.first
            }
        }
        return seeds.minOf { recursiveMinimalSliver(it, 0) }
    }
}
n
@Jan Durovec I didn't want to impement full union function 🙂 but here is the snippet to get started:
Copy code
fun main() {
    println(listOf(1..5, 3..8).unionTwo())
    println(listOf(1L..5L, 3L..8L).unionTwo())
}

private fun <T : Comparable<T>> Iterable<ClosedRange<T>>.unionTwo(): ClosedRange<T>? {
    val (firstRange, secondRange) = this.toList()
    return if (secondRange.start <= firstRange.endInclusive) {
        firstRange.start..secondRange.endInclusive
    } else {
        null
    }
}
As long as you only need to compare start's and end's of ranges, 
Comparable
bound should be enough. Please let me know if that helps.
Ah, another note - actually above example will not properly union ranges like 1..2 and 3..5.
m
I build a library of intervalmaps a while back that I didn't update for a bit here: https://github.com/mdekaste/interval/blob/master/src/main/kotlin/Main.kt You can basically have maps like IntervalMap<Long, String> for which an entire interval maps to a string, and just ask it map[12L] == "its an interval"
j
Thanks... this helped me fix the union and overlaps. However I still have issues with subtract because I need "T+1" which is not doable with 
Comparable
m
granted I didn't use it today because I didn't have it prepared
n
Ye, if you need +1, than it is a trouble 🙂
n
My part 2 solution now works (had an off by one error), but still runs for a long time. I still do not see any way to avoid looking at all seed values, because the last transformation could map a single value from the middle of a range to the smallest final value. And I still do not see a way to predict which input value that would be.
n
@Jan Durovec As a simple workaround I can suggest to just convert int range to long range, execute your function (which will be written once for long ranges only), then convert back.
If you want to go hard route you can do like this:
Copy code
fun main() {
    println(listOf(1..5, 6..8).unionTwo(Int::inc))
    println(listOf(1L..5L, 3L..8L).unionTwo(Long::inc))
}

private fun <T : Comparable<T>> Iterable<ClosedRange<T>>.unionTwo(inc: (T) -> T): ClosedRange<T>? {
    val (firstRange, secondRange) = this.toList()
    return if (secondRange.start <= inc(firstRange.endInclusive)) {
        firstRange.start..secondRange.endInclusive
    } else {
        null
    }
}
🙂
j
Sure, but that's not the util function I'd like to use 😄
n
Argh. Took way longer than you all and my solution takes 10s..
j
n
@Jan Durovec Completely missed your question about possibility of declaring two functions, I was focusing on avoiding duplication. If you just want to delcare two functions 
union
, but you get that signature clash, you simply can use 
@JvmName
annotation. Smth like:
Copy code
@JvmName("unionIntRange")
fun Iterable<IntRange>.union(): List<IntRange> {
    TODO()
}

@JvmName("unionLongRange")
fun Iterable<LongRange>.union(): List<LongRange> {
    TODO()
}
👍 1
p
@Norbert Kiesel you can avoid looking at every seed by tracking entire ranges of seeds. When a mapping only splits part of a range, split the range up and map each of them. See https://kotlinlang.slack.com/archives/C87V9MQFK/p1701763312480159?thread_ts=1701752404.073549&cid=C87V9MQFK
d
That was the hardest one so far. Went down a couple of wrong paths, then when I went down the right path, hit multiple off by one errors that didn’t trigger in the test input. Need to clean up the code.
Had to add validation that I wasn’t generating overlapping ranges, which triggered
p
Did I get lucky with my input that I didn't need to merge or check ranges for overlaps?
d
No I had a bug where I produced overlapping ranges, which shouldn’t happen
👍 1
n
Another case, when incomplete logic resulted in correct answer: While refactoring I found that I was not propely mapping range if mapper is fully within bounds of source. E.g. input range = 1..10, mapping = 4..5 to 1..2. I was returning 1..10 unmodified 😞. Though result should contain 3 ranges (if not joining overlappings) - 1..3, 1..2, 6..10. Somehow this still led to the proper answer.
e
the puzzle is quite lenient in terms of errors. in that example, 5 shouldn't be included, but there's a very low probability it ends up mapped to something smaller than the final answer, so it doesn't matter
o
j
@Norbert Kiesel try with LongRang, and check if you need to split them up, if they are not fully mapped.
r
n
Another option to approach "map ranges and keep unmapped" problem is to pregenerate kind of dummy mappings at init stage, when you parse mappings from file. Like for existing mapping 4..5 -> 1..2, generate two additional mappings 0..3 -> 0..3 and 6..Long.Max -> 6..Long.Max. It doesn't really reduces the code, it basically moves same logic from each stage processing to init stage, but it bit reduces mental load from stage processing, as you now don't need to care about unmapped pieces of input range - input range will always be fully mapped, so processing stage will be only about finding overlapings. (Maybe someone was already posting this, sorry was not checking each snippet)
e
It's funny, the example in part 2 takes 9 ms and the (clearly bigger) problem only takes 6 ms.
j
Part 2, oops 😅 but the result is correct.
😂 4
e
a
Part 1 takes 27 µs. Part 2 takes 46 µs. Both take 0.1ms including parsing, measured on M2 max with warmup. Github
r
I have to code it out and see if it improves part 2, but i was thinking of splitting the ranges into different intervals - not sure if it will work Some thing like...... We have seed range for part 2 seed range -> 
[79..92, 55..67]
and map for seed to soil -> 
[(98..99, 50..51), (50..97, 52..99)]
here first pair is source and second is destination using ☝️ map and seed range, new soil range we get 
[81..94, 57..69]
and so on for others... can avoid looping thru all seeds.
d
Yes that's the "correct" solution: transform ranges into lists of ranges repeatedly, then find the min start of all the output ranges
gratitude thank you 1
n
Got it down to 25ms cold start. Think I'll call it a day. Impressed with the rest of you.
c
Used a sequence to brute force it. Had an annoying off by 1 error in the construction of my ranges which annoyingly didn't cause a problem in the samples or my part 1. Didn't really get the trick to this one but it works so whatever. Hard mode well and truly activated this year it seems.
n
Still wrapping my head around merging the ranges, given that every mapping also has a default range for all other numbers with offset 0. Seems that for some inputs, this "if value does not fall into a listed transformer, pass the unchanged value on to the next mapping" can be ignored. But is that really a correct solution for all possible inputs?
d
You don’t need to merge ranges
You can just iteratively project the ranges from stage N into stage N+1, it’s fine if that projection contains overlaps
Unless I’m misunderstanding what you mean by merge
projecting a range (in my impl), means: determine the interior split points (places where there’s a discontinuity in the output ranges), generate a new list of contiguous ranges that will project to contiguous ranges in the destination, do that projection
m
Seems that for some inputs, this "if value does not fall into a listed transformer, pass the unchanged value on to the next mapping" can be ignored
In some inputs the answer value (smallest location) happens to always pass through a valid mapping, so even though other values would be wrong, the answer will be right.
t
day05.part1.kt.png,day05.part2.kt.png
m
Or maybe all inputs have this property, hard to tell.
d
I added a check at some point that I never generated overlapping ranges, which helped me find a bug (off by 1 error), it did not fire for my input once I got it right, even though it’s not a general property of all possible inputs
c
Me and the Wife had the exact same input values today. First time i've seen that happen.
m
I believe all inputs have non-overlapping ranges
This is probably to allow backtracking solutions
👍 1
n
There's a kind carcinisation in my code that for every hour I spend refactoring my code, the more it ends up looking like what @ephemient dashed off in 20 minutes... And that's when I'm not stealing his solution outright!
🦀 1
t
This new job is killing my Advent of Code productivity. I solved it over lunch and then couldn't write it up until I got home just a bit ago. At any rate, I used 
LongRange
for most things and flipped everything backwards for part 2 and it works. It runs in about a second, so not the best implementation, but I think it is Good Enough. 🙂 • Blog • Code
n
Todd, I was surprised reading that your solution only took 1.1-1.4s because it follows the same strategy I originally used, and mine took 10s. So then I ran your code on my machine and part2 took 18s! Even with warmup and multiple iterations it's about 8s per run. Granted, I have a mid-range machine from 2018 but still... What are you running this on? Do you use any fancy JVM speedup tricks?
t
Oh, that's not good. Just got a new laptop so maybe that's it. D'oh! Well, that's not great. I'll see if I can get time tonight to get back at it. 😞
e
may also be luck of the inputs too
n
good point
Todd, quit your job.
🤣 1
t
Also a good point.
d
yey, finally got my 13 min solution down to a few ms :-)
48 Views
Open in Slack
PreviousNext
Powered by