Solution for Part 2 of https://adventofcode.com/2021/day/21 ... Runs in 0.0004 seconds on M1 MacBook Pro

AoC-2021-Day21-Part2.swift

import Foundation

/// Typealias used in case we need to use some BigInt type
/// for counting, but for games to 21, a 64-bit Int is sufficient
typealias CountingInt = Int

struct DiracDie {
    /// index is sum of three rolls of 3-sided die,
    /// value is the number of combinations that generate that sum
    static let threeRollCombinations: [Int] = {
        var probs: [Int] = Array<Int>(repeating: 0, count: 10)

        for a in 1...3 {
            for b in 1...3 {
                for c in 1...3 {
                    probs[a+b+c] += 1
                }
            }
        }

        return probs
    }()
}

struct PositionScore: Hashable {
    var position: Int
    var score: Int
}

struct QuantumGame: CustomStringConvertible {
    var turnNumber = 1

    /// Count the number of potential universes where each player is at
    /// different possible (position, score) states on this turn,
    /// tracking only the states that have not yet won
    var player1Positions: [PositionScore: CountingInt]
    var player2Positions: [PositionScore: CountingInt]

    /// Accumulate the number of potential universes where each
    /// player has won on/before this turn
    var player1Wins: CountingInt = 0
    var player2Wins: CountingInt = 0

    /// The number of *remaining* universes where each player
    /// has not yet reached a winning score
    /// Note: playerNRemainingUniverses == sum of values of playerNPositions
    var player1RemainingUniverses: CountingInt = 1
    var player2RemainingUniverses: CountingInt = 1

    init(player1: Int, player2: Int) {
        self.player1Positions = [PositionScore(position: player1, score: 0): 1]
        self.player2Positions = [PositionScore(position: player2, score: 0): 1]
    }

    mutating func takeATurn() {
        let positions = (turnNumber % 2 == 1) ? player1Positions : player2Positions

        /// Number of possibilities for each non-winning (position, score) state following this turn
        var newPositionScoreCounts = [PositionScore: CountingInt]()

        /// Number of possibilities in which the player hasn't won on this turn
        var possibleNonWins: CountingInt = 0

        /// Number of possibilities in which the player won on this turn
        var possibleWins: CountingInt = 0

        for (startingPositionScore, startingCount) in positions {
            for rollValue in 3...9 {
                let rollCombinations = DiracDie.threeRollCombinations[rollValue]
                let newPosition = ((startingPositionScore.position + rollValue - 1) % 10) + 1
                let newScore = startingPositionScore.score + newPosition

                let possibilities = startingCount * rollCombinations

                if newScore >= 21 {
                    possibleWins += possibilities
                } else {
                    let newPositionScore = PositionScore(position: newPosition, score: newScore)
                    newPositionScoreCounts[newPositionScore, default: 0] += possibilities
                    possibleNonWins += possibilities
                }
            }
        }

        if turnNumber % 2 == 1 {
            player1Positions = newPositionScoreCounts
            player1RemainingUniverses = possibleNonWins
            /// Note that we've been keeping tracking of the possibilities for the two players
            /// independently of each other:
            /// Total number of possible universes in which the player won on this turn is
            /// actually (number of win possibilities on this turn for this player) times
            /// (number of possibilities for the opponent where they have not yet won)
            player1Wins += possibleWins * player2RemainingUniverses
        } else {
            player2Positions = newPositionScoreCounts
            player2RemainingUniverses = possibleNonWins
            player2Wins += possibleWins * player1RemainingUniverses
        }

        turnNumber += 1
    }

    var isGameOver: Bool {
        return player1RemainingUniverses <= 0 || player2RemainingUniverses <= 0
    }

    var description: String {
        return "P1 rem: \(game.player1RemainingUniverses), P2 rem: \(game.player2RemainingUniverses) ||| P1 wins: \(game.player1Wins), P2 wins: \(game.player2Wins)"
    }
}

let startTime = ProcessInfo.processInfo.systemUptime

//var game = QuantumGame(player1: 4, player2: 8)
var game = QuantumGame(player1: 9, player2: 4)

while !game.isGameOver {
//    print(game)
    game.takeATurn()
}

print("GAME OVER")

print(game)

let endTime = ProcessInfo.processInfo.systemUptime

print("Time: \(endTime - startTime) s")