https://kotlinlang.org logo
Join Slack
Powered by
<Advent of Code 2022 day 6> :thread:
# advent-of-code
a
d
windowed ftw
j
yeap, was the fastest one to solve for me
d
first version
j
For me it was
d
indexOfFirst
, nice
m
Part 1
Part 2
m
I never expected day 6 to be this simple, but that's gotta be kotlins fault
Copy code
object Day6 : Challenge() {
    override fun part1() = solve(4)
    override fun part2() = solve(14)
    private fun solve(size: Int) = input.windowed(size).indexOfFirst { it.toSet().size == size } + size
}
d
j
@Michael de Kaste imagine doing it with loops and indices that sounds like off by one hell
x
thank god ktstdlib for the 
windowed
Copy code
fun part(inputs: List<String>, size: Int): List<Int> = inputs
  .map { input -> input.windowed(size).indexOfFirst { it.toSet().size == size } + size }

check(part(testInput, 4) == listOf(7, 5, 6, 10, 11))
println(part(input, 4))

check(part(testInput, 14) == listOf(19, 23, 23, 29, 26))
println(part(input, 14))
m
oh, this reminds me that an 'isDistinct()' function, that I have been needing for a while, also doesn't exist yet in the stdlib
m
Copy code
package aoc2022

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

private fun day06(input: String) = listOf(4, 14).map { n -> input.windowed(n).indexOfFirst { it.toSet().size == n } + n }
c
list.toSet().size == list.size is the key operator for me
Copy code
class Day06 : AdventDay(2022, 6) {

    override fun part1(): String {
        return input.withIndex().windowed(4, 1).first {
            val (a, b, c, d) = it
            a.value != b.value &&
                b.value != c.value &&
                c.value != d.value &&
                a.value != c.value &&
                a.value != d.value &&
                b.value != d.value
        }.last().let { it.index + 1}.toString()
    }

    override fun part2(): String {
        return input.asSequence().withIndex().windowed(14, 1).first {
            val set = it.map { it.value}.toSet()
            set.size == it.size
        }.last().let { it.index + 1}.toString()
    }
}

fun main() {
    Day06().main()
}
j
My first version:
j
Any one else learn about windowed just after solving?
s
This was just too easy in Kotlin
Copy code
fun solution(input: String, length: Int) = input.windowed(length)
    .indexOfFirst { it.toSet().size == length } + length

fun part1(input: String) = solution(input, 4)

fun part2(input: String) = solution(input, 14)
d
It's a good one to know for AoC
j
@Jonathan Kolberg Actually, looping wasn't too bad. But I wish I had known about windowed.
n
Weird that Day 2 has been the hardest one so far. For me 2 > 5 > 3 > 4 > 1. Last year we were already doing Snailfish by Day 6.
d
Hey no complaints here - glad to have the rest of the day/evening back. 🙂
m
Cool! I think we’re done discussing implementation variants for today 😉
@Jacob Moulton That was the case for me last season … windowed and chunked are really good to keep in mind for AoC.
a
I went with withIndex windowed toSet
b
Oh man, never seen 
windowed
before! That's hella nice. I went with:
Copy code
fun startOfInput(message: String, size: Int = 4): Int {
            var last4 = mutableListOf<Char>()
            return message.takeWhile {
                if (last4.size == size && last4.groupBy { c -> c }.map { g -> g.value.size }.all { n -> n == 1 }) {
                    false
                } else {
                    last4.add(it)
                    if (last4.size == size+1) {
                        last4.removeAt(0)
                    }
                    true
                }
            }.length
        }
r
Today, was the easiest of all, i guess. 
SlidingWindow + Set
a
wow! @Anirudh what is windowed in Kotlin? I used my own buffer var based on ArrayDeque
j
@Alex J. windowed gives you a sliding window over the input list (not sure if collection). So if I give you "abcdef" windowed 1 gives ["a", "b", "c", "d", "e", "f"] while windowed 2 gives ["ab", "bc", "cd", "de" "ef"] and so on
x
first time doing AoC - how common is it that both parts are exactly the same?
j
They are normally somehow related and normally it is possible to write both with some additional input or strategy that differenciates them
a
@Alex J. what Jonathan said. and the docs have some examples too: https://kotlinlang.org/api/latest/jvm/stdlib/kotlin.collections/windowed.html
j
I read the puzzle, scrolled through stdlib, there’s no 
.windowedIndexed()
? Oh screw it, i’ll write it myself:
Copy code
fun part1(input: String) = (0..input.length).first {
    input.substring(it, it + 4).toSet().size == 4
} + 4
Which was actually better, since 
.windowed
returns 
List<…>
of all possible substrings to the end of strings, it’s not a lazy sequence.
a
windowed returns a Sequence of Lists of substrings...
j
@Anirudh
Copy code
@SinceKotlin("1.2")
public fun CharSequence.windowed(size: Int, step: Int = 1, partialWindows: Boolean = false): List<String> {
    return windowed(size, step, partialWindows) { it.toString() }
}
a
oh, well that's a return type which lied to me... 😓 I didn't consider that it could be anything which is also a Sequence ie subclasses
s
A linear-time solution:
Copy code
fun solution(input: String, length: Int): Int {
    var distinctCount = 0
    val charCounts = IntArray(256)
    return 1 + input.indices.first {
        if (it >= length) {
            when (--charCounts[input[it - length].code]) {
                0 -> distinctCount--
                1 -> distinctCount++
            }
        }
        when (++charCounts[input[it].code]) {
            1 -> distinctCount++
            2 -> distinctCount--
        }
        distinctCount == length
    }
}
j
ahhhh 
.windowed()
on 
Sequence
is a 
Sequence
indeed, but 
CharSequence
is not a `Sequence`…. because I don’t know why :)
n
why not use 
windowedSequence
instead of 
windowed
?
j
@nkiesel ahhh that would work indeed
Actually it’s crazier. The stdlib docs that @Anirudh linked. states explicitly:
Copy code
fun <T> Iterable<T>.windowed(
    size: Int,
    step: Int = 1,
    partialWindows: Boolean = false
): List<List<T>>
but then it gives example on
Copy code
val sequence = generateSequence(1) { it + 1 }

val windows = sequence.windowed(size = 5, step = 1)
...
where the return type is a 
Sequence<…>
, not a `List<…>`… 😆
a
and using the 
transform
parameter would make our already short solutions even shorter 🤣
Copy code
fun <T, R> Iterable<T>.windowed(
    size: Int,
    step: Int = 1,
    partialWindows: Boolean = false,
    transform: (List<T>) -> R
): List<R>
the IDE should tell us that 'windowed followed map' could be used in the transform
o
fun findMarker(input: String, numberOfDistinctMarker: Int): Int {
return input.indexOf(
input.windowed(numberOfDistinctMarker).find {
it.toSet().size == it.length
}!!
) + numberOfDistinctMarker
}
Part 1
fun main() = solve { lines ->
findMarker(lines.joinToString(""), 4)
}
Part2
fun main() = solve { lines ->
findMarker(lines.joinToString(""), 14)
}
j
@Anirudh good point, ok then:
Copy code
private fun solve(input: String, size: Int) =
    input.windowedSequence(size) { it.toList().distinct().size }
        .indexOfFirst { it == size } + size
m
seen a more optimized version from earlier comments
a
@Jakub Gwóźdź just 
it.distinct()
would do, don't need 
it.toList().distinct()
j
is there .distinct() on string?
a
haha, dunno. the helpful IDE showed it to me for List<Char>
j
message has been deleted
but .asIterable() seems like better match than .toList(), since it’s a view
a
what about .toSet() ? Anirudh has to remind himself that 
Sequence<Char>
is not the same as 
CharSequence
j
distinct
is basically toSet, but more kotlinish 🙂
e
yeah everybody's solution basically looks the same, not much point to sharing this…https://github.com/ephemient/aoc2022/blob/main/kt/src/commonMain/kotlin/com/github/ephemient/aoc2022/Day6.kt
I am thinking of making a MutableMultiset that I could roll elements into and out of; in theory that would be faster. not sure if it's worth the effort though
p
I used groupBy for detection of the group:
Copy code
return input.map { line ->
            line.windowed(size).indexOfFirst { group -> group.groupBy { it }.size == size } + size
        }
https://github.com/PoisonedYouth/advent-of-code-kotlin-2022/blob/main/src/day06/Day06.kt
r
hi all, joined yesterday, this is my second AoC... Nice to see other people's solutions here, I came up with this (very similar to others):
Copy code
private fun String.findStartOfMessageMarker(size: Int) = asSequence()
    .windowed(size)
    .takeWhile { chars -> chars.toSet().size != size }
    .count() + size
thanks to your examples, could reduce it to this: 👌
Copy code
private fun String.findStartOfMessageMarker(size: Int) =
        windowedSequence(size) { it.toSet().size }.indexOfFirst { it == size } + size
indeed a pretty easy one today 😅
n
Pretty hard to improve on @Sergei Petunin's solution here, except arguably (and inconsequentially) using a size-26 IntArray instead of 256. The only downside is that his is not a one-liner anymore. 😀
m
I think I'm the only one without using window()
Copy code
input.substring(index-4, index)
😭
a
Mr. Wastl is gonna make us pay for our blasphemy by giving us some shortest path puzzle in infinite 4d space with negative vacuums and inputs provided in 2d grids of '+' & '-' which we need to use to calculate the target endpoints which change their location each time we enter a new node 😱
g
As the puzzle was easy today, I made also second variant which is 11x faster than the simple solution with 
windowed
and 
toSet
SolutionDay6.cpp
e
you could get that down even far by assuming we're only getting alphabetical or ascii inputs and specializing to an 
ByteArray
as your counter instead of a 
MutableMap<Char, Int>
f
k
based on the stats, the number of people giving up is pretty similar 😞 and so far easiest start
a
At first I went with windowed() then I realized I don't need to get windows all at once, so instead I went with a for-loop and slice(). Thoughts?
e
windowedSequence
gives you windows lazily instead of all at once
there's less indirection going on with a for loop but I wouldn't expect it to make a measurable difference here
a
Correct!
p
Probably very similar to most solutions I would guess
Much faster alternative using an IntArray for counting (based on @Grzegorz Aniol solution):
g
perfect! very nice @phldavies 🙂
r
Not different than other soltutions, but i did something similar to previous posts.
b
almost the same:
Copy code
fun part1(input: String): Int {
    val window = 4
    return (input.chars().toList().windowed(window,1).indexOfFirst {
        it.toSet().size == window
    })+window
}
p
a
@Ben Ooms You can omit 
chars.toList()
and just do 
input.windowed()
.
d
@Ben Ooms mine is similar to yours:
Copy code
object Day6 {

    private fun getStartMarker(messageLength: Int) = getInputAsLine()
        .windowed(messageLength)
        .indexOfFirst { it.length == it.toSet().size } + messageLength

    fun getResultPart1() = getStartMarker(4)
    fun getResultPart2() = getStartMarker(14)
}
I think this is my shortest one yet
Could potentially optimize it by instead of making a set doing some sort of advanced indexed check for duplicates but meh
b
Thanks @Abdul Khaliq this is the function for both parts now:
Copy code
fun getUniqueBlockIndexEndOf(input: String, window: Int) =
    (input.windowed(window)
        .indexOfFirst {
            it.toSet().size == window
        }) + window
d
Here is a slightly optimized, but more convoluted version:
Copy code
private val set = hashSetOf<Char>()

    private fun getStartMarker(messageLength: Int) = getInputAsLine()
        .windowed(messageLength)
        .indexOfFirst { !it.hasDuplicates } + messageLength

    private val String.hasDuplicates: Boolean get() {
        set.clear()
        return this.any { !set.add(it) }
    }
You can reuse the same set and just return immediately if you added a duplicate character to it instead of creating an entire set each time
m
Just for kicks, here’s a window-free solution with efficiency in mind:
Copy code
fun main() = with(String(System.`in`.readAllBytes())) {
    fun String.afterMarker(i: Int, n: Int) =
        i > n && with(mutableSetOf<Char>()) { (i - n until i).all { add(get(it)) } }

    var part1 = false
    indices.forEach { i ->
        if (!part1 && afterMarker(i, 4)) {
            println(i)
            part1 = true
        }
        if (afterMarker(i, 14)) {
            println(i)
            return
        }
    }
}
d
Ah yes, that reminded me I can use windowedSequence instead of windowed which for large lines might be better
w
I forgot about 
windowed
and iterated by hand.
Copy code
var buffer = ""
var index = 0
for (c in line) {
  if (buffer.length >= 14) {
    break
  } else {
    val repeatedIndex = buffer.indexOf(c)
    if (repeatedIndex >= 0) {
      buffer = buffer.drop(repeatedIndex + 1)
    }
    buffer += c
    index++
  }
}
println(index)
c
windowed
and 
indexOfFirst
here too. That was easy.
d
I mean, we are lucky with Kotlin's extensive standard library with all those nice extension functions 🙂
Usually I just start typing the name of a function I hope exists and more often than not, it does indeed exist 🙂
c
I do wonder if future days are going to do more with that input stream and we’ll have to actually process it as a stream but can worry about that if and when it comes up.
d
I'm using a BufferedReader to read the input and it has the function 
lineSequence
to get the lines as a sequence, or you can use 
useSequence
with a block which closes the reader at the end
j
@Davio Yeah, that's exactly how I do stuff, too. Helps a lot with finding functions like 
mapIndexed
, too! The standard library has great functional programming support. For me, I made it into a oneliner (if you don't count the hardcoded input string):
Copy code
fun main(): Unit = println(listOf(4, 14).map { n -> input.windowed(n).indexOfFirst { it.toSet().size == n } + n })
a
@Sergei Petunin I took some inspiration from you and did a similar solution O(n) but instead of array I used map, my reasoning is that this support any kind of char.
d
Some of the extension functions have an 
indexed
sibling, such as 
filterIndexed
, 
mapIndexed
etc, but not all. If you need to carry the index, say you want to do an 
anyIndexed
you can use 
withIndex, like "somestring".withIndex()
to create wrapped versions, in this instance you get an 
Iterable<IndexedValue<Char>>
where each IndexedValue contains an index property and a value property.
k
Can be 26x faster that window() in worst case!
Copy code
fun String.indexOf(n: Int): Int = asSequence()
    .withIndex()
    .runningFold(mutableMapOf<Char, Int>() to -1) { (m, r), (i, c) -> m to (m.put(c, i)?.coerceAtLeast(r) ?: r) }
    .withIndex()
    .indexOfFirst { (index, value) -> index - value.second - 1 == n }
https://github.com/karloti/advent-of-code-2022-kotlin/blob/main/src/Day06.kt
t
• Blog • Code A coworker basically did the same thing but much, much cleaner than I did. This is pretty clunky, but I’m going to stick with this.
@Karloti That’s clever!
I totally forgot about 
indexOfFirst
. That would have made mine better.
m
^ Even after one year of Kotlin AoC hacking, I hadn’t noticed 
windowedSequence
and 
indexOfFirst
before today. Thank you AoC! 🙂
(and the fact that windowed can simultaneously map)
k
@todd.ginsberg With muttableMap() is fastest, but not safety (with buffered flows)! I prefer immutability
p
@Karloti How did you measure that it’s 26x faster than with window? I benchmarked it against my solution: https://github.com/PaulWoitaschek/AdventOfCode/blob/main/src/main/kotlin/de/woitaschek/aoc/year2022/Day6.kt And I measure: runningFold: 1,183 ± 0,016 ms/op windowed: 0,557 ± 0,013 ms/op
d
What do you use to benchmark it?
p
JMH
d
Ah I was looking into incorporating that
p
No kidding, a stopwatch 🧌
j
Came here to confirm my suspicions, 
windowed
+ 
indexOfFirst
slays.
t
I wish I had remembered 
indexOfFirst
instead of 
withIndex().windowed
that I ended up with. So much cleaner that way.!
j
I completely stumbled upon it trying to access the index. 🙂 Cool to see some of these highly optimized approaches in here.
a
@todd.ginsberg You could also use 
windowedSequence()
instead of 
windowed()
.
t
@Abdul Khaliq Yeah, there’s that too! Man, I really should have stopped to think this one through. I was so happy I got it (I did not sleep and my head is killing me this morning) that I just took what I had and pushed. heh.
r
I really should have stopped to think this one through
but there's no time to think! Gotta get the stars as quickly as possible! ⭐ (/sarcasm)
a
@todd.ginsberg Sometimes I feel like I am solving more for idiomatic kotlin than the aoc problem itself. 😄
t
I don’t even start until 7am (7 full hours after the puzzle launches) because midnight is way, way past my bedtime. I think the last time I was even close to the leaderboard was in 2015 when comparatively few people were doing it.
k
@Paul Woitaschek Worst case is 25 distinct characters repeated xN and find index of 26 longest word (a..y+a..y+a..y+a..y+a..y+a..y+a..y+a..y+z).index of(26) 1. windowed(26) #=a..ya 2. windowed(26) #=b..ab ... You have got 25*N comparisons more
p
But the definition of 26x faster generally doesn’t mean “Only in the optimal case” faster, but rather: On the average
But even in the worst case:
Copy code
@Setup
  fun setUp() {
    input = buildString {
      repeat(100000) {
        append("aaaa")
      }
      append("abcd")
    }
  }
On my machine it runs with 47ms vs 69ms / op
k
This is not a good example for worst case testing!
It's very difficult to write a code from the phone.
t
Challenge for next year - all puzzles solved by typing into a remote workspace via a mobile phone.
d
The Kotlin standard library really shines in some of these puzzles lately. 🙂 Similar to most people here, I did a windowed, first index approach. Originally used 
.first{}.let{ indexOf() }
, but loved learning about 
indexOfFirst{}
!
w
I knew there was a function like windowed, but i couldn't remember what it was called >.< so I went this route instead
Untitled.cpp
i guess it performs pretty well, i had to change my timing measurement to microseconds because it was showing 0ms for this problem lol
k
d
@Karloti I almost didn't notice that the windowed run was in 
s
instead of 
ms
😅
d
@Paul Woitaschek got JMH working, my result is roughly 0.250 ms/op for my 'pessimistic set' algorithm, which is simply:
Copy code
private val set = hashSetOf<Char>()

private fun getStartMarker(messageLength: Int) = getInputAsLine()
        .windowedSequence(messageLength)
        .indexOfFirst { !it.hasDuplicates } + messageLength

    private val String.hasDuplicates: Boolean get() {
        set.clear()
        return this.any { !set.add(it) }
    }
So I'm using (abusing?) the fact that set.add returns a boolean to indicate whether the element was added
p
Nice @Davio 🙂 @Karloti Unfortuantelly you can’t benchmark things like this. Take a look at that whole JMH topic
l
My take with regexes. Unfortunately, I couldn't find a generic way to filter out all duplicate cases, so I had to fallback to 
windowed
+ 
indexOfFirst
too. I still used a regex instead of 
toSet().size
though
Untitled.cpp
n
@Alexander af Trolle That's some black magic right there!
p
I think that my general usage of jmh was wrong. I'll post an update later but tldr: I should make use of Blackhole to prevent dce
a
to those implementing optimisations: (imho) another optimisation would have been to skip the index ahead by the latest-repeating chars. once a repeat occurs in less than the require size, we can jump the "group" ahead to one after the last occurrence of the repeated character
v
my first solution
An hashmap does the work faster
a
wrt the jump index optimisation, if the current window or deque was; take the example of the "q" highlighted:
Copy code
*      *
nppdvjthqldpwncqszvftbrmjlhg
  ^^^^^^^^^^^^^^
instead of just moving the window or appending the next element, "s"; the index could be jumped to after the 1st "q" (to the "l"):
Copy code
*      *
nppdvjthqldpwncqszvftbrmjlhg
         ^^^^^^^^^^^^^^
n
@Anirudh Yes, but by that point we're abandoning the succinctness of a windowed -> set solution. If brevity/clarity is not our goal than I think @Alexander af Trolle's method is the current winner. If we want to prioritize clarity while still being efficient, @Sergei Petunin's method is probably the best.
@Anirudh Neither of those permit index skips because the state is being tracked constantly rather than coming up with new sets to test.
a
you mean this one? yes, I'm aware that the functional versions don't permit index skipping - but many optimised solutions don't do purely functional. would still be O(n) but some loops get skipped (btw, I prefer the functional approach anyway, I went with withIndex-windowed-toSet and then cleanup to asSeq-windowed-indexOfFirst)
n
@Anirudh Yes, that one. It's worlds faster than any set-based solution, and only a little more code (though you can't put the imperative code on one line). However, to my slow brain at least I couldn't make heads or tails of it until I stepped through it a couple times in a debugger. YMMV. Sergei's solution is more verbose but I could understand it by reading it. 🙂 I wasn't saying that the functional versions don't permit index skipping (though you're right that they don't). I was saying Sergei and Alexander's versions don't permit index skipping. In other words, there is the super-clean, clear, concise functional approach enabled by 
windowed
. The downside is abysmal performance. Once you abandon the functional approach to track the first character of a duplicate pair and the like, you may as well go with Sergei's or Alexander's approach. And those don't work with index skipping.
w
Easiest one so far:
Copy code
fun String.startOfMarker(size: Int): Int =
    asSequence().windowed(size).indexOfFirst { it.toSet().size == size } + size
37 Views
Open in Slack
PreviousNext
Powered by