https://kotlinlang.org logo
Join Slack
Powered by
<Advent of Code 2022 day 4> :thread:
# advent-of-code
a
m
Copy code
object Day4 : Challenge() {
    val parsed = input.lines().map { line ->
        line.split(",").map {
            it.split("-").map(String::toInt).let { (a, b) -> (a..b).toSet() } }
        }
    override fun part1() =  parsed.count { (a, b) -> a.containsAll(b) || b.containsAll(a) }
    override fun part2() =  parsed.count { (a, b) -> a.intersect(b).isNotEmpty() }
}
Thanks Kotlin for the 
..
:)
j
same, just I went with
Copy code
.count { (s1, s2) -> s1.all { it in s2 } || s2.all { it in s1 } }
and
Copy code
.count { (s1, s2) -> s1.any { it in s2 } || s2.any { it in s1 } }
r
I think today was the easiest one!
j
yes. and a bit boring, tbh. I hope rest of you had more fun with it 🙂
m
In some languages, range overlaps might be more exciting
r
Wrote a very naive solution using kotlin ranges.. will try to optimise. less and more kotlinish 😄
m
but that would only be if they had no range functionality
😛
r
In some languages, range overlaps might be more exciting
In second part i just had to change the condition from 
&&
to 
||
😄
m
@ritesh at first I just had the ranges thinking that kotlin ranges had overlap and containsAll functionality, but alas, I was wrong. so Initially my solution was
Copy code
(a.start <= b.start && b.end >= a.end) || (b.start <= a.start && b.end >= a.end)
which is probably optimized
r
ahh okay, i am not very proud of my solution, i will optimise it but it looks like this first
Copy code
input.forEach {
    val (first,second) = it.split(",").map { it.trim() }
    val (firstSecF, firstSecS) = first.split("-").map { it.trim() }.map { it.toInt() }
    val (secondSecF, secondSecS) = second.split("-").map { it.trim() }.map { it.toInt() }

    if ((firstSecF in secondSecF..secondSecS) && (firstSecS in secondSecF..secondSecS))
        sum++
    else if ((secondSecF in firstSecF..firstSecS) && (secondSecS in firstSecF..firstSecS)){
        sum++
    }
}
second
Copy code
input.forEach {
    val (first,second) = it.split(",").map { it.trim() }

    val (firstSecF, firstSecS) = first.split("-").map { it.trim() }.map { it.toInt() }
    val (secondSecF, secondSecS) = second.split("-").map { it.trim() }.map { it.toInt() }
    
    if ((firstSecF in secondSecF..secondSecS) || (firstSecS in secondSecF..secondSecS))
        sum++
    else if ((secondSecF in firstSecF..firstSecS) || (secondSecS in firstSecF..firstSecS)){
        sum++
    }
}
x
Ranges finally paid off 😅
Copy code
fun part1(input: List<String>) = input
  .map { line -> line.split(",").map { it.split("-").let { (start, end) -> start.toInt()..end.toInt() } } }
  .count { (first, second) -> (first - second).isEmpty() || (second - first).isEmpty() }

fun part2(input: List<String>): Int =  input
  .map { line -> line.split(",").map { it.split("-").let { (start, end) -> start.toInt()..end.toInt() } } }
  .count { (first, second) -> first.intersect(second).isNotEmpty() || second.intersect(first).isNotEmpty() }
n
With each tumble down the leaderboard, it's becoming increasingly implausible that the accounts above me are bots.
d
Hey I also used 
intersect
today - thanks everyone for the learnings yesterday! 🙂
m
Part 1
Part 2
I see not much variance today. But I found using sets is shorter for part 1, and using ranges is shorter for part 2.
j
I ended up with the following but looking at the 
(a..b).toSet()
lines above we're lucky it's still just day 4 because I can imagine that in 2-digit days Eric would have include some massive interval 😉
r
I was hoping Eric will throw some matrix or some kinda puzzle today, as it's day 4 😄
c
Took way too long on this one 😢
j
I think the most optimized is what @Michael de Kaste posted above, with just a bunch of 
<=
and 
>=
if you want to be more kotlinish, you can go with
Copy code
s1.first in s2 && s1.last in s2 || s2.first in s1 && s2.last in s1
but that’s four unnecessary comparisons under the hood. But you’re in trouble if you go (as I did initially) with 
.any
, 
.all
since they check for every number in the range. Even worse, 
intersect
, is actually O(n^2) (or n log n ?) in cpu and O(n) memory usage. so for input data 
1-100000000,2-99999999
the intersect might say “you know what, count it yourself”. 🙂
c
It is not optimal but I think is readable snowball hehe
d
Here's my solution. I'm using extension functions to create a fluent API. I like how that makes the code of the 
solutionX
functions easier to read without making it overly verbose.
c
There is one thing in the standard library that I was expecting was there, but wasn't: an intersect or contains method for IntRange on another IntRange. It'd be a pretty simple check to have in the standard, and would be faster/easier than conversions to sets, or hand-writing it each time.
j
Not really strictly day4 related, but have you noticed that every time you reload the calendar page the jungle changes? 🤔 I hope the Elves don't get lost.
c
@Jan Durovec I think it's to animate the movement of the trees
m
Every year the image changes on every reload, usually there is an animation too.
m
Didn’t know this was possible in Kotlin (call referenced extension functions like that)! Takes DRY one step too far though 😉
Copy code
package aoc2022

fun main() = day04(String(System.`in`.readAllBytes())).forEach(::println)

fun day04(input: String) = input.lines()
    .map { line ->
        line.split(",").map { elf ->
            elf.split("-").map(String::toInt).let { it[0]..it[1] }
        }
    }
    .run {
        listOf(Iterable<Int>::all, Iterable<Int>::any).map { op ->
            count { (a, b) -> op(a) { it in b } || op(b) { it in a } }
        }
    }
j
WTF I love infix functions now 🙂
m
Could do operator 
contains
instead of 
isInside
, and then you can call it with the built-in 
in
operator.
j
@Marcin Wisniowski that works too (I tried that first), but then I need to swap the 
this
and 
other
operands and it looks meh 🙂
Copy code
private operator fun IntRange.contains(other: IntRange) = other.first in this && other.last in this
w
I've found using typealias makes code more readable without adding overhead. For example here I used typealis Assignment = IntRange typealias ElfPair = Pair<Assignment, Assignment > and defined function on each. Made testing/debugging easier. https://github.com/wellithy/aoc2022/blob/main/src/Day04.kt
c
@Wael Ellithy you can also use value classes
e
I just used 
IntRange
as the representation, it's pretty natural
didn't use any range-like aspect of it though, since it's cheaper to do 4 comparisons (part 1) or 2 comparisons (part 2) than to actually compute the intersection
d
nice simplification in part 2, i used 4 comparisons reasoning from first principles
Also forgot about the predicate accepting "count" function
a
Woot woot! got it 😄
v
Day 4
Looking at other's code, mine feels like the most less idiomatic kotlin 😂 .. Will improve
I think, eventhough the solutions with 
containsAll
, 
in
, 
intersect
, 
set
are seems to be more kotlin idiomatic... they are less performant than the solutions involve simple math.... your opinion
r
I made it more kotlinish.
p
I do love a bit of K in the morning 🙂
p
I used IntRanges for detection of containsFully and overlaps: https://github.com/PoisonedYouth/advent-of-code-kotlin-2022/blob/main/src/day04/Day04.kt
Copy code
fun splitToRange(input: String): IntRange {
        val (start, end) = input.split("-")
        return IntRange(
            start = start.toInt(),
            endInclusive = end.toInt()
        )
    }

    fun IntRange.fullyContains(other: IntRange): Boolean {
        return this.all { other.contains(it) }
    }

    fun IntRange.overlap(other: IntRange): Boolean {
        return this.any { other.contains(it) }
    }

    fun part1(input: List<String>): Int {
        return input.count { line ->
            val (elv1, elv2) = line.split(",")
            val elv1Range = splitToRange(elv1)
            val elv2Range = splitToRange(elv2)
            elv1Range.fullyContains(elv2Range) || elv2Range.fullyContains(elv1Range)
        }
    }

    fun part2(input: List<String>): Int {
        return input.count { line ->
            val (elv1, elv2) = line.split(",")
            val elv1Range = splitToRange(elv1)
            val elv2Range = splitToRange(elv2)
            elv1Range.overlap(elv2Range)
        }
    }
a
I went with Pairs of IntRanges and compared for All vs Any.
c
That was the easiest part 2 ever. Copy/paste and change 
all
to 
any
🙂 https://github.com/CfGit12/aoc-2022/blob/master/src/main/kotlin/aoc2022/4.kt
a
I have asked ChatGPT today's question, and it correctly breakdown the problem. The only error it made was it used a HashMap to store range start as key and range end as value. Then it used a nested loop to check all the key/value in the HashMap. Although the solution was amazing, the calculation was incorrect.
d
My solution making use of extension functions for IntRanges:
Copy code
fun getResultPart1(): Int {
        fun IntRange.contains(other: IntRange) = this.first <= other.first && this.last >= other.last

        return getInputAsSequence()
            .map { line -> line.split(",") }
            .map { lineParts -> lineParts[0].toIntRange() to lineParts[1].toIntRange() }
            .count { ranges -> ranges.first.contains(ranges.second) || ranges.second.contains(ranges.first) }
    }

    fun getResultPart2(): Int {
        fun IntRange.overlaps(other: IntRange) = this.any { other.contains(it) }

        return getInputAsSequence()
            .map { line -> line.split(",") }
            .map { lineParts -> lineParts[0].toIntRange() to lineParts[1].toIntRange() }
            .count { ranges -> ranges.first.overlaps(ranges.second) }
    }

    private fun String.toIntRange(): IntRange {
        val parts =this.split("-")
        return parts[0].toInt()..parts[1].toInt()
    }
I'm pretty sure there is a more clever way to determine if 2 ranges overlap (comparing the first and last values of each range), but I was too lazy to figure it out today 😄
m
@Venkataramanan Parameswaran Make it work, make it elegant, make it fast - if needed. In that order😊
m
message has been deleted
v
@Michael Böiers yes i refactored my code to be more kotlinish and faster
d
@Venkataramanan Parameswaran you can make use of Kotlin's builtin IntRange class to replace your custom class 🙂
f
went through some iterations and ended up with:
k
s
Copy code
fun part1(input: List<String>) = input.map {
    it.split(",", "-").map(String::toInt)
}.count { (from1, to1, from2, to2) ->
    from1 <= from2 && to1 >= to2 || from1 >= from2 && to1 <= to2
}

fun part2(input: List<String>) = input.map {
    it.split(",", "-").map(String::toInt)
}.count { (from1, to1, from2, to2) ->
    (from1..to1).intersect((from2..to2)).isNotEmpty()
}
k
No need to use 
Sets
for this one, just plain range comparisons (code)
t
Today's puzzle is almost exactly like an interview question my workplace used to ask about range overlaps (except using SQL). So that was fun. 🙂 • Blog • Code There were a lot of options on how to represent the ranges and ultimately I went with 
IntRange
because I thought 
Pair<Int,Int>
wasn''t ideal looking and I'd have to write extension functions on either one of them to test for overlaps.
k
Yeah, the solution with 
IntRange
feels pretty natural and easy to do, you can just grab your limits and check if on is contained inside another, and for the overlap you can use the already defined 
contains
function for single elements, which implementation also uses range comparison, which you don't have to rewrite again
d
Or you can use 
intersect(other).isNotEmpty()
r
I didn't knew split can take 
varargs
and limit the receiving part before today. It came handy. I learnt about it from this thread 🙂
k
@Davio 
intersect
will create a 
Set
😬 which is not needed at all for this case if you can use simple logic
m
Refactored solution, both for clarity and performance 🙂
Copy code
package aoc2022

fun main() = day04(String(System.`in`.readAllBytes())).forEach(::println)

fun day04(input: String) = input.lines()
    .map { it.split(",", "-").map(String::toInt).let { (a, b, c, d) -> a..b to c..d } }
    .run {
        listOf(
            count { (a, b) -> a.includes(b) || b.includes(a) },
            count { (a, b) -> a.overlapsWith(b) || b.overlapsWith(a) },
        )
    }

fun IntRange.overlapsWith(o: IntRange) = first in o || last in o || includes(o)
fun IntRange.includes(o: IntRange) = o.first in this && o.last in this
d
@Kevin that is correct, you don't need a set, but it does make the code more readable as intersect is just an alias for overlap
g
Hi everyone. I'd like to share my solution for today:
Copy code
fun main() {

    fun List<String>.splitToRanges(): List<Pair<IntRange, IntRange>> =
        map { text ->
            val numbers = text.split(",").flatMap { it.split("-") }.map { it.toInt() }
            check (numbers.size == 4)
            Pair(numbers[0]..numbers[1], numbers[2]..numbers[3])
        }

    fun IntRange.contains(other: IntRange) =
        other.first in this && other.last in this

    fun fullyContains(ranges: Pair<IntRange, IntRange>) =
        ranges.first.contains(ranges.second) || ranges.second.contains(ranges.first)

    fun overlaps(pairOfRanges: Pair<IntRange, IntRange>) =
        pairOfRanges.first.intersect(pairOfRanges.second).isNotEmpty()

    fun part1(input: List<String>): Int =
        input.splitToRanges().count(::fullyContains)

    fun part2(input: List<String>): Int =
        input.splitToRanges().count(::overlaps)

    val testInput = readInput("Day04_test")
    check(part1(testInput) == 2) { "Part1 Test - expected value doesn't match" }
    check(part2(testInput) == 4) { "Part2 Test - expected value doesn't match" }

    val input = readInput("Day04")
    println(part1(input))
    println(part2(input))
}
j
Hi all! It's been a while since I joined the AoC, but this Sunday I had some time so I did the first four days. I picked up my old approach, which is to do AoC in Kotlin multiplatform, compile for JVM, NodeJS and native (MacOS M1 this time around), and do some benchmarking to check relative performance. All very ad hoc, unscientific, and just for my curiosity - nothing anyone should form any professional opinion on. All code is on github. As all years, getting everything to compile was a bit of a drag, but it works, including multiplatform input file reading and performance benchmarking using Kotlin's 
expect/actual
mechanism. My day 4 in common code:
Copy code
val p04 = suspend {
    // List of Lists, each containing two IntRanges
    val input = readInput("04.txt").split("\n").map {
        it.split(",").map { it.split("-").map { it.toInt() }.let { it[0]..it[1] } }
    }

    input.count {
        it[0].containsFully(it[1]) || it[1].containsFully(it[0])
    }.print()

    input.count {
        it[0].overlapsWith(it[1])
    }.print()
}
Using some utility functions:
Copy code
fun IntRange.permute() = this.toList().permute()
fun IntRange.containsFully(other: IntRange) = this.contains(other.first) && this.contains(other.last)
fun IntRange.overlapsWith(other: IntRange) =
    this.contains(other.first) || this.contains(other.last) || other.contains(this.first) || other.contains(this.last)
Execution times per platform in microseconds (15 repetitions):
Copy code
JVM    : 13017,  2816, 2513, 2390, 2315, 2297, 1983, 1523,  991,  901,  736,  767,  751,  747,  729
JS     : 47697, 13468, 5338, 7299, 4328, 2491, 1374, 1297, 1638, 2772, 1361, 1236, 1165, 1470, 1304
Native :  8143,  7496, 7079, 7967, 7424, 7372, 8403, 6711, 7832, 7634, 8017, 7093, 7932, 7437, 7825
This is a pattern I have seen many times over the past AoC's. Native beating JVM and JS on the first run, but when the virtual machines get warm they rapidly start peforming better, with the JVM being fastest.
k
Fastest way! Without set and intersection.
Copy code
fun main() {
    fun Sequence<String>.splitBounds() = map { it.split('-', ',').map(String::toInt) }

    fun part1(input: Sequence<String>): Int =
        input.splitBounds().count { (a, b, c, d) -> (a <= c) && (b >= d) || (a >= c) && (b >= d) }

    fun part2(input: Sequence<String>): Int =
        input.splitBounds().count { (a, b, c, d) -> a <= d && c <= b }

    check(part1(readInputAsSequence("Day04_test")) == 2)
    check(part2(readInputAsSequence("Day04_test")) == 4)

    println(part1(readInputAsSequence("Day04")))
    println(part2(readInputAsSequence("Day04")))
}
b
Nice. I wanted to see solution that used Regex. What is the drop(1) doing? @Karloti On part2, I did the split that a lot of people used a little more sussinctly. To get the 4 numbers, I did
Copy code
val ranges = line.split(",","-").map { it.toInt() }
k
@Baghaii In fact, your solution is better, but the speed comes from the way of checks. I just wanted to do something different from split()
d
I realized that you don't have to check the last in overlapping, i.e.
Copy code
fun IntRange.overlaps(other: IntRange) =
            this.first in other || this.last in other || other.first in this 
// No other.last in this is needed here
Take range 1-10 as this and another range which doesn't match the first 2 criteria, so for instance 4-5 Now this.first in other = false (1 is not in 4-5), this.last in other is also false, (10 is not in 4-5) At this point, there can only be overlap if both the first and the last of other are also inside this range (and thus fully contained). If the first and last of other are not in this range, say it was 11 instead of 5, then it would have matched the second criterium
As the last of the 3 conditions, you can pick either 
other.last in this
or 
other.first in this
it has the same result. Now with short circuiting, there wouldn't be a performance hit specifying both
m
^ my solution is way simpler, IMHO.
Where‘s the point in a solution that requires so much explaining?
d
There isn't a point, I wasn't even trying to make a point, it was a realization that because of how things can mathematically overlap, you don't need to check for a condition which can't occur
I'm just trying to train my 'insight / realization skills' because I know I'll need them for later puzzles 😄
p
e
@Joris PZ I too set up Kotlin/Native. the benchmark results are absolutely dismal. https://ephemient.github.io/aoc2022/jmh-visualizer/index.html
o
e
@Ozioma Ogbe why 
.map { ... }.count { it }
? 
.count { ... }
has the same result with less work
d
For me, I forgot that 
count
also took a predicate (looked for a 
countBy
or 
countIf
method)
p
Copy code
class Day4 {
    val sections = readInput(4).map {
        val pair = it.split(",").let { it[0] to it[1] }
        return@map pair.first.toRange() to pair.second.toRange()
    }

    fun String.toRange() = split("-").let { it[0].toInt()..it[1].toInt() }
    fun IntRange.contains(other: IntRange) = other.all { this.contains(it) }
    fun IntRange.overlaps(other: IntRange) = other.any { this.contains(it) }

    fun part1() = sections.filter { it.first.contains(it.second) || it.second.contains(it.first) }.size

    fun part2() = sections.filter { it.first.overlaps(it.second) }.size
}

fun main() {
    val day = Day4()
    println(day.part1())
    println(day.part2())
}
d
The downside of using all/any with containsIn is that it's O(N), but that doesn't matter for these inputs.
e
similarly, 
.count { ... }
works better than 
.filter { ... }.size
p
Yeah I have no idea why I went for filter, I used count in all my other days so far
I decided that it was faster to just loop through them all than to reason out how overlaps work. Although I changed the overlaps method to use intersect later
o
I forgot you do not have to map before counting too, lol
Its interesting how popular declarative/functional programming is becoming.
m
@ephemient I compared count vs filter size with the method I used to solve the problem and filter size is faster...unless im measuring this wrong? https://github.com/Jaavv/advent-of-code-2022/blob/main/src/Day04.kt
m
@Marc Javier now turn those two tests around (filter first, count second) and see some magic
Measuring speed in a JVM is a bit finnicky
e
microbenchmark harnesses like JMH and kotlinx-benchmark are readily available. use them.
p
e
p
You stole my benchmark code, did you? 🧌
36 Views
Open in Slack
PreviousNext
Powered by