https://kotlinlang.org logo
Join Slack
Powered by
<Advent of Code 2021 day 21> :thread:
# advent-of-code
a
d
I think I may need a new CPU fan after AoC is over...
e
Did you manage to brute-force the second part? It should not be possible even on a very powerful desktop, since the answers are on order of 10^15
d
I tried that at first and then realized I had to put in some memoization to reduce the cycles
j
can't really get the part 2 meaning QQ
d
@Jintin so forget the die going to 100, now it only goes from 1 to 3, but each time it rolls, it "opens" three new universes of possibilities to all three outcomes.
💯 1
e
https://github.com/ephemient/aoc2021/blob/main/kt/src/commonMain/kotlin/com/github/ephemient/aoc2021/Day21.kt I wonder if I should pre-compute them all, there's only 100 possible inputs
m
Learning to love 
groupingBy(…).fold
…
e
The simple recursive impl with memoization (aka dynamic programming) is significantly shorter and very straightforward.
☝️ 1
e
@ephemient can you please explain your method for part 2?
e
@Endre Deak imagine 
fun score(player1: Int, player2: Int, score1: Int, score2: Int)
returns 
(x, y)
where 
x
is the number of universes in which player 1 wins and 
y
is the number of universes in which player 2 wins, starting from the given state. 
object Score
is exactly that, but with caching of recursive calls; because 
player1 in 1..10
, 
player2 in 1..10
, 
score1 in 0..20
, and 
score2 in 0..20
, a flat array of 44100 can store everything
👍 1
m
@elizarov See, that solution is only shorter and more straightforward if you know about dynamic programming 🙂
e
Call it memoization.
m
Can I call it caching? 🙂
I agree, it’s very powerful. I’ve just watched Jonathan Paulson’s video explaining his solution (got him rank 1 on the second star). 🙂
j
backtracking is still able to solve it btw.
m
@Jintin backtracking?
e
well, the recursion is 6 wide (if you merge the dice rolls like I did) and 7 deep at most, which is feasible even without DP
but 27 wide by 7 deep is not doable :D
j
keep moving forward and backward and record the result, but dp is powerful definitely.
m
What I did is actually quite simple as well: With all the current game states mapped to their quantities (starting with one initial state), flatMap these entries into the next generation (pruning and recording games that are over) and fold the resulting entries back into a map.
d
m
somehow had struggles today, but I'm actually quite fond of the result. First I precalculate the frequency of sums of 3 rolls then I precalculate what each position would map to and how much. Than I just fold over those values with a memoized statetracker. https://github.com/mdekaste/AdventOfCode2021/blob/main/src/main/kotlin/year2021/day21/Day21.kt part 1 is still ugly though, will clean up later
d
Mine is conceptually the same as problem 14 — advance counts of game states
I also had a bunch of bugs in part 2 that made it take a long time
m
Huge fan of kotlins buildfunctions and the nested functions. I basically used a buildmap with a nested function to create a memoized recursive function and it performs way better than making a mutablemap and adding.
this is score: 100 in ~3 seconds
d
For part 2, I realized the position number isn't important anymore, so I simplified indices (for player number and for positions) to be 0-based, then used what I called a cache (@Michael Böiers 👀)
Copy code
data class gameOutcome(val player: Int, val score0: Long, val score1: Long, val pos0: Int, val pos1: Int)
private val cache = mutableMapOf<gameOutcome, Pair<Long, Long>>()
d
Updated my solution to also use the cache / dynamic programming approach. Direct state count advancement is shorter for me but the DP approach runs faster. Reminds me of project Euler problem # 493 which also has a dynamic programming solution for computing the average number of colors you get if you pick 20 colored balls out of an urn with 70 balls, 7 colors 10 each.
m
@Michael Böiers 44 lines? That's a lot. 😅
m
Well, I’m not particularly good at coding. I’m here to learn😊
n
learn not to golf in real code 😉
Mine's 65 lines and I think trying to make anything shorter would make it take more time to read, rather than less
m
@Nir I’m trying to find the most elegant solution, which is obviously somewhat subjective. In my experience the most elegant solution tend to be among the shortest, too.
n
well.....
for some definition of "among" 🙂
In the python slack I'm watching people golf the solution to today to 1 line for each part 🤷
My solution starts off like this
Copy code
class DeterministicDice {
    private var value = 1
    fun roll() = value.also { ++value; if (value > 100) value = 1 }
}

data class Player(val position: Int, val score: Int = 0)

fun Player.forward(steps: Int): Player {
    val newPosition = (position + steps - 1) % 10 + 1
    return Player(newPosition, score + newPosition)
}

data class GameState(val players: List<Player>, val curPlayer: Int = 0)

fun GameState.forward(steps: Int): GameState {
    val newPlayers = players.toMutableList()
    newPlayers[curPlayer] = players[curPlayer].forward(steps)
    return GameState(newPlayers, (curPlayer + 1) % 2)
}
defining nice classes for the abstractions in the problem probably costs more lines than it saves, but IMHO it breaks apart the complexity better and makes the whole thing take less time to read
to me that makes it more elegant, but as you say, subjective
m
I am trying to get to a solution that’s concise. Typically that means fewer and shorter lines.
That code looks fine to me. Having a class for the deterministic dice is cool - that doesn’t add a lot of boilerplate code and allows you to name the thing and what it does.
Here’s an example for something I don’t find elegant: The DP solution I came up with today, as an exercise. It works quite well, it’s only 24 lines, but it’s not very readable. Quite terse (I like Venkat Subramaniam’s distinction between concise and terse).
Copy code
fun main(vararg args: String) = listOf(args[0].toInt(), args[1].toInt()).map { it - 1 }.let { (start1, start2) ->
    println(part1(start1, start2, die = generateSequence(1) { if (it == 100) 1 else it + 1 }.iterator()))
    println(part2(start1, start2))
}

fun part1(p1: Int, p2: Int, s1: Int = 0, s2: Int = 0, turn: Int = 0, die: Iterator<Int>): Int =
    if (s1 >= 1000 || s2 >= 1000) (if (s1 > s2) s2 else s1) * turn * 3
    else ((p1 + die.next() + die.next() + die.next()) % 10)
        .let { newP1 -> part1(p1 = p2, p2 = newP1, s1 = s2, s2 = s1 + newP1 + 1, turn + 1, die) }

fun part2(start1: Int, start2: Int): Long {
    val die = listOf(1, 2, 3).run { flatMap { a -> flatMap { b -> map { c -> a + b + c } } } }
    val cache = mutableMapOf<List<Int>, Pair<Long, Long>>()
    fun play(p1: Int, p2: Int, s1: Int, s2: Int, turn: Int): Pair<Long, Long> =
        listOf(p1, p2, s1, s2, turn % 2).let { k ->
            cache[k]?.let { return it }
            if (s1 >= 21 || s2 >= 21) {
                val won = turn % 2 == if (s1 >= 21) 1 else 0
                if (won) (1L to 0L) else (0L to 1L)
            } else die.map { ((p1 + it) % 10) }
                .map {play(p1 = p2, p2 = it, s1 = s2, s2 = s1 + it + 1, turn + 1)}
                .fold(0L to 0L) { (allWon, allLost), (won, lost) ->allWon + won to allLost + lost}
                .also { cache[k] = it }
        }
    return play(start1, start2, 0, 0, turn = 0).toList().maxOf { it }
}
But bits of it are quite readable, and with another ten lines and some of the functionality refactored into functions, it could be quite nice.
n
that's the rest of mine. I could save some lines I suppose by inlining functions, deleting whitespace, more clever one liners, but nothing that I actually really want to do 🙂
m
Haha your solutions are way more elegant and readable than mine, I just have a goal for myself to golf it a bit.
p
https://github.com/tKe/aoc-21/blob/main/kotlin/src/main/kotlin/year2021/Day21.kt I spent some time down a rabbit hole … but got there in the end
m
@Marcin Wisniowski Lol, I’m also trying to golf to some extent. Let’s say I’m exploring various goals and approaches, a bit like circuit training in the gym 😉
@Nir Check out my refactored DP solution. I actually really like this one. Very functional, but also a lot cleaner by using two data classes and extension functions. https://github.com/MikeEnRegalia/AdventOfCode2021/blob/main/kotlin/src/main/kotlin/Day21DP.kt
n
yeah, there's a couple nice tricks in there
I like the 1,2,3 flatmap thing
i feel like kotlin kind of lacks good equivalents to python's itertools.product, but unfortunately it's hard to do that sort of thing well because Kotlin's tuples are rather crippled
m
Pushed a new version where I also streamlined the part1/part2 functions to expression bodies. Especially part2 flows even nicer now 🙂
Yeah, Java and Kotlin suffer when it comes to tuples. TBF, they are much easier to do in languages which aren’t as strictly typed.
n
yeah, so in python it's not much extra effort
m
I think that Python is the ideal language for these puzzles. Which is a pity, since I don’t know Python. I’ll try to do AoC 2016 in Python in January, to learn Python. 🙂
n
if it were up to me though, Kotlin would have stuck with cranking out tuples up until 9-arity, really just for the purpose of supporting proper versions of things like zip and product
in python you can just do 
for i, j, k in product(range(1,3), repeat=3))
in Kotlin that function is hard to even write nicely
it can't really
m
Isn’t it nice how you can wrap the memoization code around the when expression? 🙂
Copy code
fun State.play(): Score = cache[this] ?: when { /* compute the result */ }.also { cache[this] = it }
n
I guess I"m just confused why you need a 
when
there
ah i see
I think you can use getOrPut instead, it's a bit more natural
getOrPut will handle the also bit automatically
and you won't need 
?:
so it'll just be 
cache.getOrPut(this) { when { ... } }
that was in my solution 😉
🙌 1
d
Yes 
getOrPut
is def what you want
🙌 1
m
Yes, changed it. Looks very nice now, and I only needed it in one when branch anyway. 🙂
Much, much nicer now. Moved all of the game logic into the State class, which leads to this condensed game “loop”:
Copy code
fun State.play(): Score = when {
    isGameOver(minScore = 21) -> if (doesPlayerLead) Score(playerWon = 1L) else Score(playerLost = 1L)
    else -> cache.getOrPut(this) { dieCasts.map(::withCast).map(State::play).reduce(Score::plus) }
}
t
I really liked this problem. Part 1 is iterative and gets the job done even though it isn’t all that functional (I did have a sequence of game states but it seemed overkill for a single game). Part 2 is a recursive function with caching that finishes in less than 100ms for me. • Code • Blog
❤️ 1
m
Was that your initial solution? For part 1, this is what I came up with at the time and which got me the first star:
Copy code
fun main() {
    val input = listOf(2, 5)
    val positions = input.map { it - 1 }.toMutableList()
    val scores = mutableListOf(0, 0)
    var player = 0

    val die = generateSequence(1) { if (it == 100) 1 else it + 1 }.iterator()

    var turn = 1
    while (true) {
        val nextPosition = (positions[player] + (die.next() + die.next() + die.next())) % 10
        positions[player] = nextPosition
        scores[player] += nextPosition + 1
        if (scores[player] >= 1000) break
        player = (player + 1) % 2
        turn++
    }
    println(scores[(player + 1) % 2] * turn * 3)
}
t
I’d have to go back through IntelliJ’s local history to dig it up, which is now on the computer I’ve packed away for the night (this is my work machine shhhh).
m
Nevermind, I was just curious. 🙂
e
I did have a sequence of states yesterday (for reuse between parts 1 and 2), but no particular need for it today
t
Yeah, I wrote it for part one and thinking maybe I'd need it for two (I am so bad at predicting what I'll need code-wise in the future). Ended up cutting it out because I ended up using it once. I do like sequences though, they help me organize my thoughts if nothing else.
d
I’ve refactored mine a bunch now and am pretty happy with it
My very first cut on part 1 was
Copy code
#!/usr/bin/env kotlin

val lines = java.io.File(args[0]).readLines()

fun Iterator<Int>.roll() = (0..2).sumOf { next() }

val positions = lines.map { it.split(": ").mapNotNull { it.toIntOrNull() }.single() - 1 }.toMutableList()
val scores = mutableListOf(0, 0)
val dice = generateSequence(1) { 1 + (it % 100) }.iterator()
var turnCount = 0

while (true) {
    turnCount++
    val roll0 = dice.roll()
    positions[0] = (positions[0] + roll0) % 10
    scores[0] += positions[0] + 1
    if (scores[0] >= 1000) break

    turnCount++
    val roll1 = dice.roll()
    positions[1] = (positions[1] + roll1) % 10
    scores[1] += positions[1] + 1
    if (scores[1] >= 1000) break
}

println(scores.minOf { it} * (turnCount * 3))
3 Views
Open in Slack
PreviousNext
Powered by