Day21.cs

using System;
using System.Collections.Generic;
using System.Text;
using System.Linq;
using System.IO;
using System.Diagnostics;

namespace AdventOfCode2021
{
    class Day21
    {
        private static long player1Start = 6;
        private static long player2Start = 2;
        public static (long result, long time) PartOne()
        {
            var sw = new Stopwatch();
            sw.Start();
            var scores = new Dictionary<int, long>
            {
                [0] = 0L,
                [1] = 0L

            };
            var pos = new Dictionary<int, long>
            {
                [0] = player1Start,
                [1] = player2Start

            };
            var runs = 1L;
            var result = 0L;
            var run = true;
            while(run)
            {
                foreach(var player in Enumerable.Range(0, 2))
                {
                    var score = (pos[player] + runs + runs + 1 + runs + 2 - 1) % 10 + 1;
                    scores[player] += score;
                    pos[player] = score;
                    runs += 3;
                    if (scores[player] >= 1000)
                    {
                        result = (runs -1) * scores[1 - player];
                        run = false;
                        break;
                    }
                }
            }
            sw.Stop();

            return (result, sw.ElapsedMilliseconds);
        }

        public static (long result, long time) PartTwo()
        {
            var sw = new Stopwatch();
            sw.Start();
            var (score1, score2) = Play(player1Start - 1, 0, player2Start - 1, 0);
            var result = Math.Max(score1, score2);
            sw.Stop();

            return (result, sw.ElapsedMilliseconds);
        }
        private static int[] possibleRolls = new int[]
        {
            3, 4, 5, 4, 5, 6, 5, 6, 7, 4, 5, 6, 5, 6, 7, 6, 7, 8, 5, 6, 7, 6, 7, 8, 7, 8, 9
        };

        private static Dictionary<(long player1, long score1, long player2, long scores2), (long, long)> universes 
            = new Dictionary<(long player1, long score2, long player2, long scores2), (long, long)>();

        private static (long score1, long score2) Play(long player1, long score1, long player2, long score2)
        {
            if(score1 >= 21 || score2 >= 21)
            {
                return (score1 >= 21 ? 1 : 0, score2 >= 21 ? 1 : 0);
            }

            if(!universes.ContainsKey((player1, score1, player2, score2)))
            {
                var (x, y) = (0L, 0L);

                foreach(var roll in possibleRolls)
                {
                    var newScore = (player1 + roll) % 10;
                    var (i, j) = Play(player2, score2, newScore, score1 + newScore + 1);
                    x += j;
                    y += i;

                    universes[(player1, score1, player2, score2)] = (x, y);
                } 
            }
            return universes[(player1, score1, player2, score2)];
        }
    }
}