I have some orange spiced tea, a calm dog, and good music. I'm feeling good tdoay.

~

A simple board game with easy to understand rules. It basically seems like gambling, but with a very basic input and rules, it doesn't seem bad.

A small optimization: It will be easier to zero-index everything on the board, so each player will get a flat 1 point, plus whatever space 0-9 they land on on the board. Their moves are just their rolls modulo 10.

If C++ had an equivalent to the yeild keyword, this would make the die roll really easy. But it looks like the concept for it, coroutines, is still in a draft state. I want to use it, but the compiler I'm using doesn't seem to support any C++20 additions. Oh well. Global variables it is.

int nextRoll = -1;
int getRoll() { ++nextRoll %= 100; return nextRoll+1; }

If I treat their current space as a carry, it should be pretty easy.

while (true) {
    int roll = (getRoll() + getRoll() + getRoll() + pawns[player]) % 10;
    if (roll == 0) roll = 10;
    pawns[player] = roll;
    scores[player] += roll;

    if (scores[player] >= 1000) break;
    player = (player + 1) % pawns.size();
}

Eazy, compared to the last week.

I spoke WAY too soon, oh my god.

At least based on the example, there are about 15 digits of possible universes. Which makes sense. I guess. Ugh. There's some trick to this. I'm trying REALLY hard not to look at someone else's solution for this.

At least the final score only reaches 21, which means the games will be a lot shorter.

This really has an air of learning how to play Candyland, then immediately switching to 5D Chess with Multiverse Time Travel.

~

Okay. I've thought about it. There's only so many turns a player can take, a minimum number. A single roll only has 3 outcomes. A full turn has 27. They can roll as little as 3, and as much as 9. It's impossible to land on the same space two turns in a row.

I refuse to memoize, by the way.

A player can win in as few as 3 turns, with a lucky rolls in the higher positions (10+9+8 = 27). An unlucky player will keep getting low numbers and have to take six turns (1+2+3+4+5+6 = 21).

I think this may be the key actually.

[3]: 1
[4]: 3
[5]: 6
[6]: 7
[7]: 6
[8]: 3
[9]: 1

A traditional bell curve of values. This means that, while there are 27 distinct roll combinations, there are 1 that add up to 3, 3 add up to 4, 6 to five, etc., which is a MUCH lower number of possibilities to deal with. And I think I have a much more reasonable way to calculate the possibilities:

1. Create a 2d map for each player, indexed [<Score,Score>][CurrentSpace] = UniverseCount. Seed with [<0,0>][starting space] = 1
2. Each player's turn, for each combination of score and Current Space, split that universe a number of times according to the split counts
3. If during that, universes go to a score >= 21, instead just add it up to the player's victories
4. When there are no more possibilities to calculate, that is it, game over!

This doesn't seem unreasonable. I loop at most 10*maxScore. So for this game, it's 210 iterations per player per turn, so at most 210 * 6 * 2 = 2520, which seems like nothing. Great!

map<pair<int, int>, map<pair<int, int>, uint64_t>> universes;

This is a monstrosity of a type. But I think it will work.

~

I have a good start, I think... but it looks like player 1's wins are only 11 digits, theere should be 15. Hmm.

~

Oh, whoops. Small bug in my code. I was replacing the number of next universes, not adding to it. Just a = instead of +=. Simple mistake, instantly fixed!

bool p1turn = true;
while (u.size() != 0) {
    UNIVERSE next;

    for (auto ss: u) //ScoreSpace
    for (auto bs: ss.second) //BoardSpace
    for (auto ms: splits) { //MoveSpace
        if (p1turn) {
            p nextScore = p(ss.first.first + getMove(bs.first.first, ms.first), ss.first.second);
            if (nextScore.first >= MAX_SCORE) { wins[0] += bs.second * ms.second; continue; }
            p nextSpace = p(getMove(bs.first.first, ms.first), bs.first.second);
            next[nextScore][nextSpace] += bs.second * ms.second;
        } else {
            p nextScore = p(ss.first.first, ss.first.second + getMove(bs.first.second, ms.first));
            if (nextScore.second >= MAX_SCORE) { wins[1] += bs.second * ms.second; continue; }
            p nextSpace = p(bs.first.first, getMove(bs.first.second, ms.first));
            next[nextScore][nextSpace] += bs.second * ms.second;
        }
    }

    u = next;
    p1turn = !p1turn;
}

Was a fun one to solve, especially without memoization. It runs fast!

Fun fact - my rank was the same on both parts! 3219!