# Data Structures --------------------------------------------------------------

# Represents a player's current "state", their current board position and score
struct Player
	position::Int64
	points::Int64
end
Player(pos::Int64) = Player(pos, 0)

# Represents the current state of the game, both players' board position and
# current score
struct Game
	player1::Player
	player2::Player
end


# Helper Functions -------------------------------------------------------------

# Given a string, return a Player whose position is the number at the end of
# the string.
playerpos(s) = Player(parse(Int, s[end]))


# Ingest the Data -------------------------------------------------------------

# There's only two lines, the first line for player one and the second line for
# player two, both of which end with a single digit representing that
# player's starting space
function ingest(path)
    return open(path) do f
		player1 = playerpos(readline(f))
		player2 = playerpos(readline(f))
		Game(player1, player2)
    end
end

# Helper Functions -------------------------------------------------------------

# Given a board position and a roll, return the next position that results from
# that roll. The only tricky bit here is that 10 + 1 wraps around to 1 instead
# of zero.
function nextposition(pos::Int64, roll::Int64)
    pos += roll
    pos > 10 && pos % 10 == 0 && return 10
    pos > 10 && return pos % 10
    return pos
end

# Given a player and a roll, return a `Player` at the next position that will 
# result from the given roll with their score updated to reflect the move.
function move(player::Player, roll::Int64)
    position = nextposition(player.position, roll)
    points = player.points + position
    return Player(position, points)
end

# Given a game board, a roll, and an optional boolean value indicating whether
# or not it is Player 1's turn, return a `Game` reflecting the state that would
# be achieved if the indicated player moves by the amount given by `roll`
function move(game::Game, roll::Int64, player1 = true)
    if player1
        player1 = move(game.player1, roll)
        return Game(player1, game.player2)
    else
        player2 = move(game.player2, roll)
        return Game(game.player1, player2)
    end
end

# Take a `Game` an return either the current high score or the current low score
highscore(game::Game) = max(game.player1.points, game.player2.points)
lowscore(game::Game)  = min(game.player1.points, game.player2.points)

# Some Useful Data Structures --------------------------------------------------

# Literally an empty struct for the purposes of creating an iterator over the
# possible die rolls
struct Die end

# On the first roll, the die returns `6` (1 + 2 + 3) and the next starting number
# of `4`. On subsequent rolls, return the sum of the next three numbers and the
# fourth number in sequence as a tuple, to keep the iterator going. The `if`
# statements are there for wrapping around 100 if need be (I don't think it
# actually happens).
Base.iterate(::Die) = (6, 4)
function Base.iterate(::Die, start::Int64)
    (nextvalue, nextstart) = if start < 98
        (sum(start:start+2), start + 3)
    elseif start == 98
        (297, 1)
    elseif start == 99
        (200, 2)
    elseif start == 100
        (103, 3)
    end

    return (nextvalue, nextstart)
end


# Solve Part One ---------------------------------------------------------------

# Play the game as described! Roll the die, move the players, check the score. 
# Whenever a winner is found, return the number of rolls (3 * the number of
# rounds) multiplied by the lowest player score
function part1(game)
    die = Die()
    player1turn = true
    round = 0
    for roll in die
        game = move(game, roll, player1turn)
        round += 1
        highscore(game) >= 1000 && break
        player1turn = !player1turn
    end
    rolls = round * 3
    return rolls * lowscore(game)
end

# Constants --------------------------------------------------------------------

# Of the 27 alternate realities created by three rolls of the 'Dirac Die', we
# already know in how many of those universes we rolled a total of `3` (1), a 
# total of `4` (3), and so on. Since these proportions don't change, we can
# define a constant.
const FREQUENCIES = Dict(3 => 1, 4 => 3, 5 => 6, 6 => 7, 7 => 6, 8 => 3, 9 => 1)


# Data Structures --------------------------------------------------------------

# Just a type alias for a Dict to keep track of the number of universes that
# current exist for each found game state.
const GameFreqMap = Dict{Game,Int64}


# Helper Functions -------------------------------------------------------------

# Shorthand function for convenience
function set!(dict, key, value)
    dict[key] = value
end

# For each round of the game, the active player "moves" 27 time in 27 alternate
# realities. We simulate this by keeping track of the number of games in each
# particular 'state' (a `Game` struct) and creating a new `GameFreqMap` where
# each previous game state is advanced by a roll of 3, 4, 5, 6, 7, 8, or 9 (the 
# possible values from three rolls from 1-3) the number of times those values
# can be made by rolling three three-sided dice. If, say, a particular game
# state existed in 10 alternate realities, then after moving there would exist
# 10 realities where that player rolled 3, 30 realities where that player rolled
# 4, 60 realities where that player rolled 5, etc.
function move(games::GameFreqMap, player1 = true)
    nextgames = GameFreqMap()
    victories = 0
    for (game, count) in games
        for (roll, frequency) in FREQUENCIES
            newstate = move(game, roll, player1)
            newcount = count * frequency
            if newstate.player1.points >= 21 || newstate.player2.points >= 21
                # If either player won, there's no need to continue this game
                # state forward, just count the number of realities where that
                # player won.
                victories += newcount
            else
                # Otherwise, check the next games frequency map for this new
                # state, initialize its count to 0 if it doesn't exist, then
                # add the number of new realities where this new state exists.
                newstate ∈ keys(nextgames) || set!(nextgames, newstate, 0)
                nextgames[newstate] += newcount
            end
        end
    end

    return (nextgames, victories)
end


# Solve Part Two ---------------------------------------------------------------

# Play the game, roll the crazy die, move the player, repeat until all the games
# have played themselves out. Each time a player wins a game (or more) in one of 
# the alternate realities, add it (them) to the ongoing sum.
function part2(input)
    games = GameFreqMap(input => 1)
    victoryarray = [0, 0]
    player1turn = true

    while !isempty(games)
        (games, victories) = move(games, player1turn)
        if player1turn
            victoryarray[1] += victories
        else
            victoryarray[2] += victories
        end
        player1turn = !player1turn
    end

    return maximum(victoryarray)
end