https://kotlinlang.org logo
Join Slack
Powered by
<Advent of Code 2021 day 16> :thread:
# advent-of-code
a
d
Nothing like building a calculator on a fine December evening. 🧮
m
https://github.com/mdekaste/AdventOfCode2021/blob/main/src/main/kotlin/year2021/day16/Day16.kt I need to clean this up later, was looking too long for the functionality that I needed but couldn't find it, settled on two lining every operation (removeRange and resetting)
d
Nice! I used 
Stack
to keep track of to-be-calculated values
d
Single pass over an iterator
e
The easiest way to write it is using a recursive descent algorithm. Not only it is fast (virtually all industrial programming language parsers work this way), but it is also quite easy to write. Still, that’s the longest problem so far by time-to-submission.
👍 2
d
Cleaned up some. For some reason my sealed class is reporting 
error: 'when' expression must be exhaustive, add necessary 'else' branch (problem_16.main.kts:59:40)
Guessing this is because I’m using kts?
Factored methods out and (IIUC) it is indeed recursive descent
OK now it’s really clean, all parse methods are extension functions on 
Iterator<Char>
n
Yeah, this one was fun. I kept the bits as a 
Data
class with offset:
Copy code
class Data(private val data: String) {
        var offset = 0
        fun str(bits: Int) = data.substring(offset, offset + bits).also { offset += bits }
        fun int(bits: Int) = str(bits).toInt(2)
    }
That made the parser pretty simple (recursive descent).
d
wrote a renderer method as well
Copy code
((425542 * (247 < 247)) + (121 + 21236) + (((11 + 12 + 11) > (7 + 10 + 7)) * 32566) + (((8 + 7 + 15) < (6 + 11 + 10)) * 4507180) + min(max(min(min(max(max(min(130))))))) + 139930778832 + ((52 > 667118) * 10) + 602147 + max(62199) + (14849899 * (11716 < 26963)) + (4083 * (135 > 135)) + (135 * 217 * 224) + 73 + ((13 + 4 + 9) * (12 + 15 + 7) * (13 + 10 + 9)) + min(194) + (182 * 197 * 136 * 2 * 242) + (226 * 142 * 34 * 124) + max(4025, 186042) + min(30059, 126119002) + min(9, 260, 162) + ((4 < 4) * 28699) + (1945 * (1714 == 1714)) + (7 * (1545 < 108)) + 12 + (200 * (31050 > 655605)) + 3154 + (3 * (64896 < 116)) + 3055 + 13 + min(48082, 226938, 1175, 68077774919) + (66 + 15 + 181 + 1380642642 + 11831587) + (241 * 59) + (150 * (2742 > 113)) + 37007908601 + max(52444, 11, 13008816, 2935) + 20723 + 8 + (5 * (6241732 > 759708)) + ((15 * 7 * 4) + (14 * 2 * 12) + (13 * 6 * 6)) + (2877 + 229333 + 655820 + 1020971) + (39581 + 2 + 14) + max(982557, 44, 31) + 68 + ((11530 == 3492) * 41177) + ((236 == 918711093) * 3937) + max(903466, 228, 6, 25989131, 4028) + 229 + min(299875, 10969849, 11481, 2281, 13) + (55300721 * (63 > 63)) + (244 * ((7 + 13 + 7) > (12 + 5 + 14))) + (4494263 * ((4 + 15 + 4) == (3 + 3 + 14))) + ((45 < 3307915) * 58514) + (3596530693 * ((3 + 12 + 4) < (9 + 11 + 2))))
😯 1
n
Is there really no easy way to create a 0-padded string from an Int? I ended up simply using a map, but I feel I'm missing something.
e
x.toString().padStart(n, '0')
👍 1
n
hah! thx
e
But I use it so often, that I frankly wish that 
Int.toString()
had a few extra optional parameters to customize length and padding
d
Copy code
(+ (* 425542 (< 247 247)) (+ 121 21236) (* (> (+ 11 12 11) (+ 7 10 7)) 32566) (* (< (+ 8 7 15) (+ 6 11 10)) 4507180) (min (* (* (+ (* (max (* (min (* (min (* (max (+ (+ (max (+ (+ (min (* (* 130)))))))))))))))))))) 139930778832 (* (> 52 667118) 10) 602147 (max 62199) (* 14849899 (< 11716 26963)) (* 4083 (> 135 135)) (* 135 217 224) 73 (* (+ 13 4 9) (+ 12 15 7) (+ 13 10 9)) (min 194) (* 182 197 136 2 242) (* 226 142 34 124) (max 4025 186042) (min 30059 126119002) (min 9 260 162) (* (< 4 4) 28699) (* 1945 (== 1714 1714)) (* 7 (< 1545 108)) (+ 12) (* 200 (> 31050 655605)) 3154 (* 3 (< 64896 116)) 3055 (* 13) (min 48082 226938 1175 68077774919) (+ 66 15 181 1380642642 11831587) (* 241 59) (* 150 (> 2742 113)) 37007908601 (max 52444 11 13008816 2935) 20723 8 (* 5 (> 6241732 759708)) (+ (* 15 7 4) (* 14 2 12) (* 13 6 6)) (+ 2877 229333 <tel:6558201020971|655820 1020971>) (+ 39581 2 14) (max 982557 44 31) 68 (* (== 11530 3492) 41177) (* (== 236 918711093) 3937) (max 903466 228 6 25989131 4028) 229 (min <tel:29987510969849|299875 10969849> 11481 2281 13) (* 55300721 (> 63 63)) (* 244 (> (+ 7 13 7) (+ 12 5 14))) (* 4494263 (== (+ 4 15 4) (+ 3 3 14))) (* (< 45 3307915) 58514) (* 3596530693 (< (+ 3 12 4) (+ 9 11 2))))
m
I put it in a jtree for fun:
❤️ 1
e
p
https://github.com/tKe/aoc-21/blob/main/kotlin/src/main/kotlin/year2021/Day16.kt parsing into a packet hierarchy - got caught out by Int limits again 😄
k
@ephemient TIL about 
DeepRecursiveFunction
, always amazes me when coroutine is used for something other than concurrency.
e
it's totally unnecessary here - the recursive parsing uses as many stack frames as nesting of the data. but I found it to be a handy way to avoid having to name a couple helper functions 😆
p
I might have a play with a recursive solution later.
j
I must say I had a lot of fun today! not that it was tricky or something, but it was bit of complex and the process of overengineering (hours after result submission) was very joyful. In the end, I got this:
n
kind of annoyed because my solution looks very nice and works perfectly for part1 and all the test data... but not part 2 🤷
m
Both should just be a recursive function right?
👍 1
p
@Nir check your integer type... I had the same but the calculation blew past max int
n
I thought I'm using Long for everything
Copy code
sealed class Packet() {
    abstract val version: Int
    data class Literal(override val version: Int, val value: Long): Packet()
    data class Operator(override val version: Int, val typeId: Int, val subpackets: List<Packet>): Packet()
}
I parse the data into this
Then part1 is pretty trivial
Copy code
fun Packet.versionSum(): Long = version + if (this is Packet.Operator) subpackets.sumOf { it.versionSum() } else 0
And part 2 is also pretty straightforward:
Copy code
fun Packet.evaluate(): Long {
    if (this !is Packet.Operator) {
        return (this as Packet.Literal).value
    }
    if (typeId in 5..7) {
        assert(subpackets.size == 2)
    }
    val subValues = subpackets.map { it.evaluate() }
    return when (typeId) {
        0 -> subValues.sum()
        1 -> subValues.fold(1L) { x, y -> x * y }
        2 -> subValues.minOrNull()!!
        3 -> subValues.maxOrNull()!!
        5 -> if (subValues[0] > subValues[1]) 1 else 0
        6 -> if (subValues[0] < subValues[1]) 1 else 0
        7 -> if (subValues[0] == subValues[1]) 1 else 0
        else -> throw RuntimeException("unreachable")
    }
}
the evaluate function is simple enough that I just can't see where there's a bug; conversely I don't see how I could get part 1 right if my parsed 
Packet
is incorrect
m
Nir, if you are using sealed classes, it might be better to define both functions seperately for both
n
why?
m
For my sanity
n
🤷 that seems like a stylistic thing, I prefer this way, but not really the point
d
Would help to see the full code
n
d
I don’t see anything obviously wrong but you might try writing a Lisp renderer and comparing it to the output I pasted above
Copy code
fun Packet.render(): String = when (this) {
    is Literal -> "$value"
    is Operator -> {
        val results = subpackets.map { it.render() }.joinToString(" ")
        val op = when (typeId) {
            0 -> "+"
            1 -> "*"
            2 -> "min"
            3 -> "max"
            5 -> ">"
            6 -> "<"
            7 -> "=="
            else -> error("")
        }
        "($op $results)"
    }
    else -> error("")
}
that will tell you if the error is somewhere in the parsing or in the evaluating
e
@Nir your binaryToInt() truncates values in the input
d
aha
n
damn
d
value.binaryToInt().toLong()
it is
n
hmm, but I changed that already and reran
d
I ended up defining 2:
Copy code
fun List<Char>.binaryToInt() = joinToString("").toInt(radix = 2)
fun List<Char>.binaryToLong() = joinToString("").toLong(radix = 2)
n
😞
fun List<Int>.binaryToInt() = reversed().mapIndexed { index, it -> it.toLong() * (1 shl index) }.sum()
I changed it to this, but forget the L on the 1 😞
d
1 shl
yeah
e
fold(0L) { acc, x -> 2 * acc + x }
would be a be better way to do that anyway
and there's no purpose to multiplying by a shift, just shift directly
n
the multiplication is because there could be 0 or 1 there
but at any rate I'll go with the fold suggestion
definitely feeling the frustration of the 
Int
default everywhere
thanks for your help!
e
x shl i
has the same behavior as 
x * (1 shl i)
n
ah that's true
e
and checked arithmetic doesn't help here because you're simply shifting out of range, which is platform-defined in most languages (it is defined to shift by the masked shift value in Java)
n
right
d
I had the same error initially but thankfully 
toInt
on 
String
threw due to too much input
👍 1
t
Yay, that was fun (eventually). The instructions confused me for a good amount of time this morning but at some point between my 2nd and 3rd cup of coffee it all clicked. I ended up passing an 
Iterator<Char>
around, writing some extension functions to make it easier to work with, and defining a small sealed class hierarchy. • Blog • Code
👍 1
e
ah, I went for unboxed 
CharIterator
and 
BooleanIterator
p
I went for a custom interface that extended 
Iterator<Boolean>
(was going to extend 
BooleanIterator
but it's a class)
Copy code
private interface Biterator : Iterator<Boolean> {
    val remaining: Int
    fun next(bits: Int): Int
    override fun hasNext() = remaining > 0
    override fun next() = next(1) == 1
}
mainly because I liked the sound of "Biterator" 😉
n
I just used List<Int> as my list of bits, passed in sublists, and passed back how many bits were consumed 🙂
p
with my Biterator interface I just wrapped the bit-string directly (after converting from hex) and then just use 
.substring(ofs, ofs + bits).toInt(2)
to consume from it
m
Late but still made it on the day! 🙂
I started with a Packet class and subclasses for every operation, but ended up refactoring it so that parsing a packet returns a lambda that evaluates it.
d
Product of a list is just 
reduce(Long::times)
d
Similarly, sum of a list is 
reduce(Long::plus)
e
sum()
is more like 
fold(0L, Long::plus)
because it works on empty lists
n
probably a weirdo but I prefer 
x.reduce { x, y -> x * y }
over 
reduce(Long::times)
d
@Nir yes but when every second counts...
n
i don't understand, why would you anticipate a performance difference?
e
I don't know either, there is no performance difference. 
Long::times
is less to type, but with Kotlin I doubt that is a limiting factor
k
8 Views
Open in Slack
PreviousNext
Powered by