Day21 part 2

Day21p2.kt

package day21

import java.lang.Long.max

typealias Pos = Int
typealias Step = Int


val scroll3 : Map<Pos, Int> = (1..3).flatMap { f1 ->
        (1..3).flatMap { f2 ->
            (1..3).map { f3 -> f1 + f2 + f3 }
        }
    }.groupBy { it }.mapValues { it.value.size }

data class Incarnation(
    val landingPos: Pos,
    val score: Int,
    val step: Step,
    val startPos: Pos,
    val winning: Int
) {
    private fun moveBack(by: Pos) = if(landingPos > by) landingPos - by else 10 + landingPos - by
    fun before(by: Pos)= Incarnation(moveBack(by), score - this.landingPos, step - 1, startPos, winning)
}

fun getTo(i: Incarnation): Long {
    val cache =  mutableMapOf<Incarnation, Long> ()
    fun privDp(p: Incarnation): Long {
        val round by lazy {
            if(p.score - p.landingPos >= p.winning)  0
            else scroll3.map {e -> privDp(p.before(e.key)) * e.value }.sum()
        }
        return cache.getOrPut(p) {
            if (p.step == 0) {
                if (p.score == 0 && p.landingPos == p.startPos) 1 else 0
            } else if (p.score <= 0) {
                0
            } else round
        }
    }
    return privDp(i)
}

fun countWins(startPos: Pos, oStartPos: Pos, isStarting: Boolean, winning: Pos = 21): Long {
    fun countLooses(step: Int): Long {
        return  (0 until winning).flatMap { sc ->
            (1..10).map{end -> getTo(Incarnation(end, sc, step, oStartPos, winning)) }
        }.sum()
    }

    val maxIncrement = scroll3.keys.maxOrNull()!!
    val minIncrement = scroll3.keys.minOrNull()!!
    val maxSteps = (winning + maxIncrement) / minIncrement + 1

    return (1..maxSteps).flatMap { step ->
        (winning..(winning+maxIncrement)).flatMap { score ->
            (1..10).map { endP ->
                val p1 = Incarnation(endP, score, step, startPos, winning)
                val p1Count = getTo(p1)
                if(p1Count > 0) {
                    p1Count * countLooses(if(isStarting) step -1 else step)
                } else 0
            }
        }
    }.sum()
}

fun main() {
    println(scroll3)


    val p1Start = 3
    val p2Start = 7
    val score = 21

    val p1Wins = countWins(p1Start, p2Start, true, score)
    val p2Wins = countWins(p2Start, p1Start, false, score)
    println(max(p1Wins, p2Wins))
}