https://kotlinlang.org logo
Join Slack
Powered by
<Advent of Code 2022 day 13> :thread:
# advent-of-code
a
k
mfw json
s
Parsed with a stack and used a recursive 
compareTo
method, the second part was a breeze.
j
for part1 example why is
Copy code
[2,3,4] vs 4
ok, since it says that if the right list runs out first it is not ok?
s
@Jonathan Kolberg the right part is not a list, it's a number, so the comparison goes according to the third rule, "If exactly one value is an integer..."
k
if you compare [2,3,4] and [4] you have to compare 2 and 4 and 2 is less than 4
j
@Kroppeb but after that the right list is empty, I think I did not get the rules
s
The values of the lists are integers and are therefore compared according to the first rule. 2 is less than 4, so the comparison stops here.
m
My solution (part 2)
e
https://github.com/ephemient/aoc2022/blob/main/kt/src/commonMain/kotlin/com/github/ephemient/aoc2022/Day13.kt I'll come up with a better parser later, this is just the thing I could write up easily
j
In the end I used kotlinx.serialize to parse
m
Copy code
object Day13 : Challenge() {
    private val regex = """(,)|(?=\[)|(?=])|(?<=\[)|(?<=])""".toRegex()
    val parsed = input.lines().filter(String::isNotBlank).map(::lineToNode)

    private fun lineToNode(line: String) = buildList<MutableList<Node>> {
        add(mutableListOf())
        line.split(regex).filter(String::isNotBlank).forEach { t ->
            when(t){
                "[" -> add(mutableListOf())
                "]" -> removeLast().also { last().add(Holder(*it.toTypedArray())) }
                else -> last().add(Value(t.toInt()))
            }
        }
    }[0][0]


    override fun part1() = parsed.chunked(2)
        .mapIndexed { index, (a,b) -> if(a < b) index + 1 else 0 }
        .sum()

    override fun part2(): Any? {
        val packet1 = Holder(Holder(Value(2)))
        val packet2 = Holder(Holder(Value(6)))
        val list = (parsed + packet1 + packet2).sorted()
        return (1 + list.indexOf(packet1)) * (1 + list.indexOf(packet2))
    }
}

sealed interface Node : Comparable<Node>

class Holder(vararg val nodes: Node) : Node{
    override fun compareTo(other: Node): Int = when(other){
        is Value -> compareTo(Holder(other))
        is Holder -> nodes.zip(other.nodes, Node::compareTo).firstOrNull { it != 0 }
            ?: nodes.size.compareTo(other.nodes.size)
    }
}
class Value(val int: Int) : Node {
    override fun compareTo(other: Node): Int = when(other){
        is Value -> int.compareTo(<http://other.int|other.int>)
        is Holder -> Holder(this).compareTo(other)
    }
}
sealed interfaces to the rescue
d
Thankfully I solved part 1 with 
sealed interface PacketData : Comparable<PacketData>
so part 2 was easy
Did you need DeepRecursiveFunction? I wrote a recursive parser and it’s doesn’t stack overflow
p
Argh! always with the off-by-one on the indexes! … Solved. Part2 indeed easier with 
Comparable<PacketEntry>
Also arrow intensifies 
arrow.core
having
Copy code
Iterable<A>.compareTo(other: Iterable<A>)
let me skip part of the implementation
d
My feeling when IntelliJ complains about code complexity for an AoC puzzle:

https://media.tenor.com/nwoJ4BS0XHYAAAAS/oh-no-anyway.gif▾

Like @Dan Fingal-Surma I solved part with a sealed interface with Comparable as well so part 2 was a breeze, I could just do 
sorted()
with 2 
indexOf
calls and call it a day 🙂
The parsing function is not very pretty, but it works, it's a recursive function which tries to figure out which elements belong to the current list and parses them recursively, of course I am only human so I started with a very naive split on comma 😄
e
@Dan Fingal-Surma I didn't need DeepRecursiveFunction, it's just a habit I have when dealing with unknown input
hmm. the fact that I only did that on the parsing but not on 
compareTo
means that if it would have blown the stack, it wouldn't have been avoided anyway
did nobody else here discover that you don't actually need to sort for part 2?
p
sorted()
and 
mapIndexedNotNull { idx, it -> if(it in dividers) idx + 1 else null }
were quicker to throw down as needed
d
@ephemient if you don't sort, I guess you could just count the number of elements smaller than both dividers? In my case, because I already had comparable implemented, sorted was easy, but I guess I can write it like this instead:
Copy code
val packetList = getInputAsList()
            .split { it.isBlank() }
            .map { parsePacketPair(it) }
            .plus(Pair(divider1, divider2))
            .flatMap { listOf(it.first, it.second) }

        return (packetList.count { it < divider1 } + 1) * (packetList.count { it < divider2 } + 1)
j
@ephemient yes but depends whether you optimize on time to write or time to execute 🙂 Using 
sort
is faster to write whereas just counting smaller lists is O(n). I first used sort, submitted the solution and then refactored to linear solution before committing to repo.
e
I screwed up the indexing on sorted().indexOf() so this way helped me fix it 🙂
j
I kept wondering where I've seen this type of input before... then I discovered the "_The snailfish called. They want their distress signal back._" hint referring to 2021 day 18.
e
gonna experiment with skipping the parsing altogether…
d
For funsies, I refactored it to one big chain:
Copy code
return getInputAsList()
            .split { it.isBlank() }
            .map { parsePacketPair(it) }
            .plus(Pair(divider1, divider2))
            .flatMap { listOf(it.first, it.second) }
            .sorted()
            .mapIndexedNotNull { index, packet -> if (packet === divider1 || packet === divider2) index + 1 else null }
            .reduce(Int::times)
It may not be the most performant (although it is decent), but it's pretty straightforward: split and map are parsing the input, then insert the dividers (as I used pairs in part 1 I reused that bit) and make one giant list (removing the pairs), then just sort, find the indices of the dividers and multiply them
It runs in ~30ms which is good enough for me
a
We could parse with Jackson the Input 🙂
e
yeah wow, just comparing tokens instead of building a data structure is an order of magnitude faster. let me see if I can clean it up enough to publish
a
😄
A colleague of mine ideas, I found it very clever
e
a
Your code speed is terrifying @ephemient 😄
e
it goes 20× faster on part 1 and 7× faster on part 2
d
@Suppress("CyclomaticComplexMethod", "NestedBlockDepth", "ReturnCount")
lol
e
yeah there's a reason I'm keeping the nicer solution around 😄
d
@ephemient do you also find it sad that with 
when
you can't match literals and conditions? Would be nice if you could do something like:
Copy code
when (c) {
  '[' ->
  Char::isDigit ->
}
m
I’m really happy with how this one turned out. I particularly like how the literal center of the code is the switch (when) containing the packet comparison logic. https://github.com/MikeEnRegalia/advent-of-code/blob/master/src/main/kotlin/aoc2022/day13.kt
(and it’s only 27 sloc 😉)
d
Even though I work with CRUD REST services which produce/consume JSON daily, it did not enter my mind that the input was actual valid JSON so I ended up rolling my own manual parser, just like last year with the SnailFish 🤪
m
^ Been there, done that 😉
d
AoC has conditioned me that nothing is straightforward, so I always assume the worst and start doing everything by hand 😄
p
c
So irritating when your solution passes for the sample but not the input
a
I need to teach my child how to code to do puzzles, to understand what's frustration really means 🧌
o
@Charles Flynn Some things that you can check. 1. Does you solution parse inputs with digits greater than 9? 2. Does you solution parse the input in the same order, if you are parsing it as a tree its has to be in the same order as the input.
c
Managed to work it out. It wasn’t correctly handling two exactly equal lists. Interestingly this made a difference of only 2 to my final answer.
For parsing I just went
Copy code
Json.parseToJsonElement(it)
Not sure if that was cheating or not 🙂
d
Nah, it isn't cheating there'll be other chances to write your own lexer and parser
e
my python solution used eval. I wrote a parser as normal in kotlin haskell and rust, but python code is just so slow...
j
So sad to not see @Sebastian Aigner’s live stream today.
d
I tried to get Json parsing to work with kotlinx serialization, a sealed interface and two value classes (one wrapping Int and one wrapping list), but to no avail. It kept demanding a JsonObject where it got a JsonArray instead, probably because it was trying to disambiguate between the subclasses and was looking for a discriminator...
p
d
Okay, after seeing that code @phldavies, I am not so sorry anymore I did not go through trying to implement deserialization for my types 😄
So I just went the lazy route, this still uses my value classes which is nice, but only some minimal manual deserialization:
Copy code
private fun parsePacket(line: String) = parseJson(Json.decodeFromString<JsonArray>(line))

    private fun parseJson(jsonElement: JsonElement) : Packet {
        return when (jsonElement) {
            is JsonArray -> PacketList(jsonElement.map { parseJson(it) })
            is JsonPrimitive -> PacketValue(<http://jsonElement.int|jsonElement.int>)
            else -> throw IllegalStateException()
        }
    }
So some good ol' recursion to parse arrays in arrays in arrays...
t
This reminded me of Snailfish, so I solved it the same way (with a sealed class structure). I used an 
Iterator<String>
for the recursive parsing and implemented 
Comparable<Int>
to do all the dirty work. • Blog • Code
f
I also have a 
zip
call when comparing the lists, and found that using 
asSequence
on the result from 
zip
reduced the number of comparisons considerably part 1 - 2266 => 598 part 2 - (sort of entire list) 32933 => 10427
t
I ❤️ 
zip
f
refactoring my code now to your sealed classes @todd.ginsberg - having one single compareTo function is what took me ages to debug.... had I gone with the two seperate classes I think I would have nailed it much quicker... as every year - thx for a great bog - love reading it
t
Thanks @Fredrik Rødland - I’m glad it helped! 🙂
ç
t
Things I need to get better at - when to use sequences and destructuring. I’ve missed obvious improvements by not considering those. Although I did try to get my parser working with 
Sequence<String>
instead of 
Iterator<String>
and I gave up on it because I was getting frustrated. Maybe I’ll come back to it after.
f
(for parsing I "cheated" - used 
json-simple
from google)
Copy code
fun from(input: Any): Packet {
        return when (input) {
            is String -> from(JSONValue.parse(input))
            is JSONArray -> ListPacket(input.map { from(it!!) })
            is Long -> IntPacket(input.toInt())
            is Packet -> input
            else -> error("$input type is " + input.javaClass)
        }
    }
d
I've implemented compareTo many many times but I always have trouble deciding to return 1 or -1 🤔 I mean I know what each means, but it always takes a lot of mental effort somehow
f
@Davio yes. but also the contract is not to return -1/1 - it's to return negativt, 0, postive. so tod's
Copy code
.firstOrNull { it != 0 } ?: subPackets.size.compareTo(other.subPackets.size)
could be simplified to
Copy code
.firstOrNull { it != 0 } ?: (size - other.size)
which I find neat - but maybe a bit more obscure?
j
Konbini lib parser (for both part 1 and 2)
I was annoyed I could not create a union type of Int and List<Int>, felt very limiting
Had to create 
zipWithNull
😄
m
I too wrote a parser and used sealed classes. weird thing is I implemented the comparators. I am using dataclasses so hashcode and equals should be ok. But I think becuase I have immutables things in the data class 🙈 (I know… I know… )this doesn’t work. It is fine for < and > and it will sort the list but 
indexOf
gives some stack overflow error so I ended up chasing through the list and manually counting elements lower than the dividers.
there is probably something small wrong with the comparators …
d
Copy code
sealed interface PacketData : Comparable<PacketData>
Copy code
data class ListValue(val values: List<PacketData>) : PacketData {
    override fun toString() = values.toString()
    override operator fun compareTo(other: PacketData): Int = when (other) {
        is ListValue -> values.zip(other.values).asSequence()
            .map { (a, b) -> a.compareTo(b) }
            .firstOrNull { it != 0 } ?: values.size.compareTo(other.values.size)
        else -> compareTo(ListValue(listOf(other)))
    }
}
Copy code
data class IntValue(val value: Int) : PacketData {
    override fun toString() = value.toString()
    override operator fun compareTo(other: PacketData): Int = when (other) {
        is IntValue -> value.compareTo(other.value)
        else -> ListValue(listOf(this)).compareTo(other)
    }
}
x
Am i the only one parsed these inputs like an animal? 😅
Copy code
fun format(line: String): List<Any> =
  buildList {
    var index = 0
    var number = ""
    while (true) {
      if (index > line.lastIndex) break
      var char = line[index++]
      when {
        char == ',' && number.isNotBlank() -> {
          add(number.toInt())
          number = ""
        }

        char.isDigit() -> number += char

        char == '[' -> {
          val start = index
          var depth = 1

          while (depth != 0) {
            char = line[index++]
            if (char == '[') depth++
            if (char == ']') depth--
          }

          val end = index - 1
          add(format(line.substring(start until end)).toList())
        }
      }
    }
    
    if (number.isNotBlank()) add(number.toInt())
  }
  .also { check("[${line}]" == it.toString().replace(" ", "")) { "Failed to parse $line" } }
Managed to use kotlin's type system as is 🙌 Wish we had something like 
zipWithNull
in the stdlib. Posted about this in #language-proposals here. Source here
w
i did my own parsing and was able to get solutions in 17, and 11 ms respectively: https://github.com/wakingrufus/advent-of-code-2022/blob/main/src/main/kotlin/com/github/wakingrufus/aoc/day13/Day13.kt
k

https://www.youtube.com/watch?v=JA-TkN5Zm2A▾

14 Views
Open in Slack
PreviousNext
Powered by