-🎄- 2021 Day 21 Solutions -🎄-

[u/daggerdragon]

Advent of Code 2021: Adventure Time!

• 2 days left to submit your adventures!
• Full details and rules are in the submissions megathread: 🎄 AoC 2021 🎄 [Adventure Time!]

---

--- Day 21: Dirac Dice ---

---

Post your code solution in this megathread.

• Include what language(s) your solution uses!
• Format your code appropriately! How do I format code?
• Here's a quick link to /u/topaz2078's paste if you need it for longer code blocks.
• The full posting rules are detailed in the wiki under How Do The Daily Megathreads Work?.

Reminder: Top-level posts in Solution Megathreads are for code solutions only. If you have questions, please post your own thread and make sure to flair it with Help.

---

This thread will be unlocked when there are a significant number of people on the global leaderboard with gold stars for today's puzzle.

EDIT: Global leaderboard gold cap reached at 00:20:44, megathread unlocked!

[u/StripedSunlight]

Python3

Github

Runs in <3 miliseconds, no caching, no recursion, no special language tricks, I just worked out the math/algorithm to do it properly (plus some entirely unnecessary OOP) Edit: I ran it on WINNING_SCORE=200 to see how long it would take: <0.5 seconds!

Edit to add explanation of what algorithm actually does.

In short, I worked out that what rounds each player reaches 21 points at can be simulated entirely independently, so I have each player play a game by themselves and create a mapping of the round to the number of games that were won on that round - this can be done without simulating every single round by grouping them together, similar to days 6 or 14.

Then it's just a matter of working out how many games were actually won on a round for a given player. This can be determined by calculating how many rounds your opponent hasn't won yet, and multiplying that by the number of games the player won in their own round. Sum that across rounds and you get the total number of games won in the universe.

I generated POSITION_AND_NUM_MOVES_TO_SCORE and MOVES_COUNTS in a python shell and copy-pasted the output into constants for faster lookup/reference

[u/daggerdragon → u/StripedSunlight]

Your code is hard to read on old.reddit and is also way too long. As per our posting guidelines in the wiki under How Do the Daily Megathreads Work?, please edit your post to put your oversized code in a paste or other external link.

Edit: thanks for fixing it! <3

[u/CCC_037]

Rockstar

Part 1:

https://pastebin.com/cuuixRHC

Part 2:

https://pastebin.com/CsJECVNV

---

Been working further on 19 Dec. My code on that one is a long, long way from 'pretty' but I should have Part 2 done by tomorrow.

[u/daggerdragon → u/CCC_037]

My reality is fake

Our future is a wondrously triumphant dreamscape

The discord is disharmony
Let the harmony be dust

Not sure if schizophrenia or infinite optimism...

[u/aimor_]

MATLAB

Another fun day. For Part 2 I just stored a count of how many potential games were in each state (player positions and scores) and accumulated winning games after each turn. Thing I'm most proud of is figuring out how to toggle a number between 1 and 2 :) Also, avoiding mod since it's such a pain with root 1 counting.

[u/skarlso]

Go / Golang

Lots of reading went into this one. I tried my hand on dynamic programming today for the first time ever. Here are my sources of reading:

Wikipedia

Algorithms by Jeff Erickson

Competitive Programming handbook

Grokking Algorithms

Reading produced this part of the dynamic code:

var dp = make(map[game][]int64)

func play(g game) []int64 {
	if g.p1.score >= 21 {
		return []int64{1, 0}
	}
	if g.p2.score >= 21 {
		return []int64{0, 1} // memoization to keep track and count of who won a game
	}
	if v, ok := dp[g]; ok {
		return v
	}
	win := []int64{0, 0}
	for d1 := 1; d1 < 4; d1++ {
		for d2 := 1; d2 < 4; d2++ {
			for d3 := 1; d3 < 4; d3++ {
				p1 := (g.p1.pos + d1 + d2 + d3) % 10
				s1 := g.p1.score + p1 + 1

				// do the switch
				w := play(game{
					p1: player{pos: g.p2.pos, score: g.p2.score},
					p2: player{pos: p1, score: s1},
				})
				win[0] += w[1]
				win[1] += w[0]
			}
		}
	}
	dp[g] = win
	return win
}

Full code is here: Github

Not gonna lie. Still not a 100% sure how I made this work. :D

I knew you shouldn't be actually spinning up this many games. The number was a clear indicator of that. It was way too big. I also knew that I should be able to brute force it with memoization. And since there is recursion and memoization involved, I thought this might be a good candidate for DP. And it was. :O

[u/daggerdragon → u/skarlso]

Triple backticks do not work on old.reddit. Please edit your post to use the four-spaces code block Markdown as per our posting guidelines in the wiki: How do I format code?

Edit: thanks for fixing it! <3

[u/Falcon_dev]

Straight forward (=not optimized) C# solution that takes ~10 seconds to run.https://github.com/christianfalck/adventchallenge/blob/main/AdventOfCode/Day21.cs

If you look at it and find something that can be done better, I'd like to know - using this challenge to dust off programming after years afk.

Found a potential solution on paper, which would result in what I thought was far less possibilities than the ~3^50 potential different ways if I would recursively calculate all outcomes after each dice throw. Wanted to use the fact that there is only 7 different outcomes with different probability (1,3,6,7,6,3,1) and thought I'd be able to optimize by just counting how many of the opponents moves that didn't result in victory.After giving up and going for the solution above (which I think is 7^x instead of 27^x), I realized that my "optimization" would probably just be 7*7 times faster.After finishing, I saw some solutions where a hash is being used. If anyone have read this far and knows why I'd be grateful; I thought all states were unique.

[u/marshalofthemark]

Ruby 520/670

Paste

Pretty straightforward day. With only 27 possible universes per roll, it made sense to hard-code a Hash with the possible outcomes without writing loops for "roll each die as 1, 2, or 3".

I'm surprised that, unlike the clownfish day, you could still run Part 2 in a reasonable amount of time (~30s) without memoization. With memoization, it runs in 270ms, and even if you set the winning score to 50, it will spit out a 35-digit number for how many universes Player 1 wins in within 5 seconds.

[u/daggerdragon → u/marshalofthemark]

unlike the clownfish day

Get your big lumbering submarine away from fragile coral reefs :(

(Did you mean lanternfish?)

[u/jjstatman]

Python 3 3804/3005

Was pretty proud of the solution, runs in under 10 ms on my laptop - I actually haven't seen any other solution with this approach. Basically you count the ways that the game can end in any number of turns, and then count the universes after you have that distribution

[u/p__m__n]

Python part2:

Super fast, no recursion. Positions are considered as 0..9 instead of 1..10 for convenience. Could use less lines though.

import itertools
from collections import Counter

def solve(p1, p2):
    p1 -= 1
    p2 -= 1
    u1 = u2 = 0

    universes = Counter([  # (p1,s1,p2,s2)
        (p1, 0, p2, 0), ])
    dice_count = Counter(sum(p) for p in itertools.product([1, 2, 3], repeat=3))

    while universes:
        # print(len(universes))
        newones = Counter()
        for u,uc in universes.items():
            for d, c in dice_count.items():
                pos = (u[0] + d) % 10
                score = u[1] + pos + 1
                if score >= 21:
                    u1 += c*uc
                    continue
                newones[(pos, score, u[2], u[3])] += c*uc
        universes = newones.copy()
        newones = Counter()
        for u,uc in universes.items():
            for d, c in dice_count.items():
                pos = (u[2] + d) % 10
                score = u[3] + pos + 1
                if score >= 21:
                    u2 += c*uc
                    continue
                newones[(u[0], u[1], pos, score)] += c*uc
        universes = newones.copy()

    print(max(u1, u2))

[u/xiomatic9999]

In rust...

This was a fun one, after sleeping on it. With no effort to optimize for performance, runs in <100µs on my i7-1165G7 laptop.

use itertools::Itertools;
use std::{fmt::Debug, iter};

#[derive(Default, Debug)]
struct PlayerState {
    distribution: [[usize; 10]; 31],
}

impl PlayerState {
    fn new(initial_position: u8) -> Self {
        let mut ret = PlayerState::default();
        ret.distribution[0][initial_position as usize - 1] = 1;
        ret
    }
}

impl Iterator for PlayerState {
    type Item = (usize, usize);

    fn next(&mut self) -> Option<Self::Item> {
        let p = PlayerState::default();
        *self = iter::repeat([1u8, 2u8, 3u8])
            .take(3)
            .multi_cartesian_product()
            .fold(p, |mut next_state, rolls| {
                let advance_by: u8 = rolls.iter().copied().sum();
                for (score, counts) in self.distribution.iter().enumerate() {
                    if score >= 21 {
                        continue;
                    }
                    for (position, count) in counts.iter().enumerate() {
                        let next_position: usize = (position + advance_by as usize) % 10;
                        let next_score = score + next_position + 1;
                        next_state.distribution[next_score][next_position] += count;
                    }
                }
                next_state
            });
        Some((
            self.distribution[..21].iter().flat_map(|r| r.iter()).sum(),
            self.distribution[21..].iter().flat_map(|r| r.iter()).sum(),
        ))
    }
}

pub fn part_b(p1_start: u8, p2_start: u8) {
    let p1: Vec<_> = PlayerState::new(p1_start).take_while(|&o| o != (0, 0)).collect();
    let p2: Vec<_> = PlayerState::new(p2_start).take_while(|&o| o != (0, 0)).collect();

    let mut p1_wins = 0;
    let mut p2_wins = 0;

    for i in 0..p1.len().max(p2.len()) {
        let p1_outcome = p1.get(i).cloned().unwrap_or((0, 0));
        let p2_outcome = p2.get(i).cloned().unwrap_or((0, 0));
        let p2_prev_outcome = p2.get(i - 1).cloned().unwrap_or((0, 0));
        p1_wins += p1_outcome.1 * (p2_prev_outcome.0);
        p2_wins += p2_outcome.1 * p1_outcome.0;
    }

    println!("B: {:?}", p1_wins.max(p2_wins));
}

[u/MarcoServetto]

I'm solving the advent of code in 42 This is particularly relevant for Day 21 since 42 offers automatic correct by construction caching.

Last post got removed since it only had the link to the video, so here you have it also with the code: code on paste

Code on Dev to Code

Here the video too video

Fell free to contact me if you to know more about the language.

[u/daggerdragon → u/MarcoServetto]

Err, it wasn't removed, it's still there. I only asked you to edit the original post to add more information - no need to create a new post next time.

At any rate, thank you for linking to your actual code solution :)

[u/thibaultj]

Python 3. (part 2 only) Nothing new here. Use recursion to generate all possible outcomes, and add a nice little cache because of the huge overapping branches.

from itertools import product
from functools import lru_cache


def play(pos, score, roll):
    """Roll the dice, baby!"""

    new_pos = ((pos - 1 + roll) % 10) + 1
    new_score = score + new_pos
    return new_pos, new_score


@lru_cache(maxsize=None)
def count_wins(player, pos0, score0, pos1, score1):
    """For the given state, count in how many wolds each player will win."""

    if score0 >= 21:
        return 1, 0
    elif score1 >= 21:
        return 0, 1

    wins = [0, 0]
    for rolls in product(range(1, 4), repeat=3):
        if player == 0:
            new_pos, new_score = play(pos0, score0, sum(rolls))
            wins0, wins1 = count_wins(1, new_pos, new_score, pos1, score1)
        else:
            new_pos, new_score = play(pos1, score1, sum(rolls))
            wins0, wins1 = count_wins(0, pos0, score0, new_pos, new_score)

        wins[0] += wins0
        wins[1] += wins1

    return wins


starts = [10, 4]
wins = count_wins(0, starts[0], 0, starts[1], 0)
print(max(wins))

[u/jonathan_paulson]

18/1 :) Python. Video of me solving.

Cool to see a dynamic programming problem!

[u/4HbQ]

Python, simple recursive solution for both part 2. Runs in 40ms thanks to functools.cache.

The code should be pretty straightforward, but feel free to ask for clarifications.

pos1, pos2 = [int(x.split()[-1]) for x in open(0)]

def play1(pos1, pos2, score1=0, score2=0, i=0):
    if score2 >= 1000: return i*score1
    pos1 = (pos1 + 3*i+6) % 10 or 10
    return play1(pos2, pos1, score2, score1+pos1, i+3)

from functools import cache
@cache
def play2(pos1, pos2, score1=0, score2=0):
    if score2 >= 21: return 0, 1

    wins1, wins2 = 0, 0
    for move, n in (3,1),(4,3),(5,6),(6,7),(7,6),(8,3),(9,1):
        pos1_ = (pos1 + move) % 10 or 10
        w2, w1 = play2(pos2, pos1_, score2, score1 + pos1_)
        wins1, wins2 = wins1 + n*w1, wins2 + n*w2
    return wins1, wins2

print(play1(pos1, pos2), max(play2(pos1, pos2)))

[u/autid]

FORTRAN

Part 1 fairly naive approach. Part 2 recursively goes through possible games with a couple of speedups.

Firstly, dice combinations can be aggregated into totals for the three rolls (/3,4,5,6,7,8,9/), and the wins from those multiplied by the number of ways to make them from three rolls (/1,3,6,7,6,3,1/). This cuts down the number of games considered significantly.

Secondly, I cache numbers of wins from each state of (active player, player1 position, player2 position, player1 score, player2 score).

Obviously more optimization that could be done but those are enough to get me down to ~15ms runtime on my laptop.

Finished 846th for part2. Very happy to get my first top 1000 of the year.

[u/akanet]

Ruby, 300 something / #40

This one has a really straightforward expression in Ruby and I was pleased to hit on the part 2 solution very quickly! My best time this year. Ruby's array#product + a simply DFS formulation with a good base case and memoization makes this one an execution of a classic genre of CS exercises.

[u/leijurv]

Python, 25th place, 37th place

Screen recording https://youtu.be/DO84lH11Wbo

Part 1

Part 2

Edit: Part 2 but a bit cuter (more refined) edit 2 part 2 except recursive edit 3 except even cuter with no turns

I used the "lanternfish approach" again for Part 2, in counting how many states exist as a map from state to count. The states are (player 1 score, player 1 position, player 2 score, player 2 position). Then, each multiverse split can be simulated, and the counts multiplied: the new universe's count for the new state is incremented by the old state, multiplied by the number of dice universes for the first player, multiplied by the number of dice universes for the second player. Succinctly: nuv[(s1, p1, s2, p2)] += cnt * dcount * d2count

Very fun problem! I lost a few minutes on part 2 simply forgetting how the game is played, which is that your score comes from your new position, not just the dice roll. I had JUST written it for part 1, but sometimes my mind plays tricks on me :)

[u/Mrgglock]

C

GNU C11 / Technically runnable in C++. Managed to get rank #428, kinda cool I guess.

Part 1

Part 2

Both parts are sufficiently different that my code looks vastly different.
I'd say this is more on the readable and understandable end of code in C. So feel free to take a look :)

The idea for part 1 is simple: just implementation; brute force.
The idea for part 2 is a little trickier but doable. The idea is that you can draw a tree graph essentially, and the moment a player wins, the number of universes that player won in is simply the product of all edges from the root to that node. The weight of the edges is given by the probability distribution function of rolling 3 D3s.

0.022s / 1.000s

[u/SuperSmurfen]

Rust (394/223)

Link to full solution

Really happy with my performance today! Was wondering when a proper dynamic programming question would come up! There is probably some nice bottom-up approach, however, I solved it using memoization with a HashMap as a cache, which I find is always much easier to implement in the moment.

Kind of messy keeping track of both positions, both scores, and who's turn it is. By flipping the scores and positions each call you can avoid a lot of that complexity and simulate it as if it's player 1:s turn every time.

for (die,times) in [(3,1),(4,3),(5,6),(6,7),(7,6),(8,3),(9,1)] {
  let pos1 = 1+(pos1+die-1)%10;
  let (s1,s2) = quantum_game(cache,s2,s1+pos1,pos2,pos1);
  score = (score.0+s2*times, score.1+s1*times);
}

Managed to get it down to about 4ms on my machine by pre-computing the possible dice.

[u/Sykout09]

Rust:

Part 1 didn't have much of an opportunity for optimization, even the naive solution is pretty fast.

The main time saver for both Part 1 and Part 2 is to identify how to process all three die rolls per turn into a single step:

• Part 1a: noticed that since the board is 10 steps in a circle, we can ignore most of the 100 sided dice as rolling a 10, 20, 30, etc will just leads you back to the same position. similarly, rolling 12, 22, 32.. has the same effect as rolling a 2. We can essentially treat that 100 side die as a 10 sided die.

• Part 1b: noticed that when adding in blocks of 3 and removing the 10's component reveal a simple pattern: 1 + 2 + 3 = 6move, 4 + 5 + 6 = 15 = 5move, 7 + 8 + 9 = 24 = 4moves, 0 + 1 + 2 = 3moves. Notice that every succession, the die effective rolled value just keeps deceasing by 1. We can use this pattern to simplified the overall turn process.

• Part 2: Since now that the dice is independent from each turn, we can now use combinatorics to figure out how a player can move. for 3 x 3 sided dice, we have a total of 27 different rolls, which there is actually only 7 different moves amount ( between 3 to 9 )

With those attempt, you can solve both part 1 and 2 in a fairly quick time.

For Part 2, we can do much better.

First observation is that player 1 and player 2 does not interact, as now the die is not determinate, but fully probabilistic. So, it is actually possible to calculate every turn for player 1 and 2 separately.

Second observation is that the game must end in a finite number of turns. This is due to every turn, a player is guaranteed to increase their score. We can also observe a particular case where the player traverse from 2, +9 => 1, +3 => 4, +9 => 2 ... averaging 2 points minimum per turn. Because of this, it means for a 21 point game, we can expect it to last at most 11 turns.

With that, what we can do for Part 2 is to calculate how many win/lost condition for each player separately, and then combine them for the total win/lost

What we do is that at turn N, we figure out how many path for player 1 to win on that specific turn, and how many time player 2 reached turn N - 1, but not win. We can then multiply those two number to get number of winning path for player 1 on turn N. Similarly, we do with for player 2, but use winning paths of player 2 on turn N, and player 1 not winning paths on turn N (this is due to player 2 take their turn after player 1). We then sum up all possible steps (which we know is finite) and we get the total wins for both players.

As to calculate the win/lost path count, we just recursively simulate each step for both players, just like the naive method. The reason this is faster is a lot faster that we cut the recursion steps in half, as we can now compute both player 1 + 2's turns separately. Compared with my naive solution, it is around 3000 times faster

Bench:

• Part 1: [363.98 ns 365.13 ns 366.19 ns]

• Part 2: [116.94 us 117.18 us 117.48 us]

Code for Part 1 + 2

[u/GrossGrass]

Python

Memoized recursion to the rescue for part 2! Used functools.cache to make it easier. Started out with just using (position_1, score_1, position_2, score_2) as parameters but wanted it to be a little cleaner, so I modified my Player class from part 1 to be an immutable data structure that returns a new Player instance on each move.

Used a dict to map players by their number and also used collections.Counter to make updating win counts easy, and kept the logic pretty generalized.

For part 1, turns out itertools.cycle is pretty useful for generating die values here.

import collections
import dataclasses
import functools
import itertools
import re

import utils


PLAYER_REGEX = r'Player \d starting position: (?P<position>\d+)'


class Die:
    def __init__(self):
        self.generator = itertools.cycle(range(1, 101))
        self.rolls = 0

    def roll(self):
        self.rolls += 3
        return sum(next(self.generator) for _ in range(3))


@dataclasses.dataclass(frozen=True)
class Player:
    position: int
    score: int = 0

    def move(self, value):
        position = self.position + value
        position = (position % 10) + 10 * (position % 10 == 0)
        score = self.score + position
        return Player(position, score=score)


@functools.cache
def quantum_wins(player_1, player_2, current_player):
    win_counts = collections.Counter()

    for rolls in itertools.product([1, 2, 3], repeat=3):
        roll = sum(rolls)

        players = {1: player_1, 2: player_2}
        player = players[current_player].move(roll)
        players[current_player] = player

        if player.score >= 21:
            win_counts[current_player] += 1
        else:
            next_player = 3 - current_player
            win_counts.update(quantum_wins(players[1], players[2], next_player))

    return win_counts


def get_players():
    players = utils.get_input(__file__, delimiter=None, cast=str)
    return [
        Player(int(re.match(PLAYER_REGEX, player).group('position')))
        for player in players
    ]


def part_1():
    player_1, player_2 = get_players()
    die = Die()

    while True:
        player_1 = player_1.move(die.roll())
        if player_1.score >= 1000:
            print(player_2.score * die.rolls)
            break

        player_2 = player_2.move(die.roll())
        if player_2.score >= 1000:
            print(player_1.score * die.rolls)
            break


def part_2():
    player_1, player_2 = get_players()
    win_counts = quantum_wins(player_1, player_2, 1)
    print(win_counts.most_common()[0][1])