Day21.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "571255d2-7bab-457f-ae95-82559d01d0b0",
   "metadata": {},
   "source": [
    "<h2>--- Day 21: Dirac Dice ---</h2>"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f7a3f76c-cab3-4f6f-a28b-13b69ccc798a",
   "metadata": {},
   "source": [
    "[![Binder](https://mybinder.org/badge_logo.svg)](https://mybinder.org/v2/gh/oddrationale/AdventOfCode2021FSharp/main?urlpath=lab%2Ftree%2FDay21.ipynb)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "73bcba6b",
   "metadata": {},
   "source": [
    "<p>There's not much to do as you slowly descend to the bottom of the ocean. The submarine computer <span title=\"A STRANGE GAME.\">challenges you to a nice game</span> of <em>Dirac Dice</em>.</p>\n",
    "<p>This game consists of a single <a href=\"https://en.wikipedia.org/wiki/Dice\" target=\"_blank\">die</a>, two <a href=\"https://en.wikipedia.org/wiki/Glossary_of_board_games#piece\" target=\"_blank\">pawns</a>, and a game board with a circular track containing ten spaces marked <code>1</code> through <code>10</code> clockwise. Each player's <em>starting space</em> is chosen randomly (your puzzle input). Player 1 goes first.</p>\n",
    "<p>Players take turns moving. On each player's turn, the player rolls the die <em>three times</em> and adds up the results. Then, the player moves their pawn that many times <em>forward</em> around the track (that is, moving clockwise on spaces in order of increasing value, wrapping back around to <code>1</code> after <code>10</code>). So, if a player is on space <code>7</code> and they roll <code>2</code>, <code>2</code>, and <code>1</code>, they would move forward 5 times, to spaces <code>8</code>, <code>9</code>, <code>10</code>, <code>1</code>, and finally stopping on <code>2</code>.</p>\n",
    "<p>After each player moves, they increase their <em>score</em> by the value of the space their pawn stopped on. Players' scores start at <code>0</code>. So, if the first player starts on space <code>7</code> and rolls a total of <code>5</code>, they would stop on space <code>2</code> and add <code>2</code> to their score (for a total score of <code>2</code>). The game immediately ends as a win for any player whose score reaches <em>at least <code>1000</code></em>.</p>\n",
    "<p>Since the first game is a practice game, the submarine opens a compartment labeled <em>deterministic dice</em> and a 100-sided die falls out. This die always rolls <code>1</code> first, then <code>2</code>, then <code>3</code>, and so on up to <code>100</code>, after which it starts over at <code>1</code> again. Play using this die.</p>\n",
    "<p>For example, given these starting positions:</p>\n",
    "<pre><code>Player 1 starting position: 4\n",
    "Player 2 starting position: 8\n",
    "</code></pre>\n",
    "<p>This is how the game would go:</p>\n",
    "<ul>\n",
    "<li>Player 1 rolls <code>1</code>+<code>2</code>+<code>3</code> and moves to space <code>10</code> for a total score of <code>10</code>.</li>\n",
    "<li>Player 2 rolls <code>4</code>+<code>5</code>+<code>6</code> and moves to space <code>3</code> for a total score of <code>3</code>.</li>\n",
    "<li>Player 1 rolls <code>7</code>+<code>8</code>+<code>9</code> and moves to space <code>4</code> for a total score of <code>14</code>.</li>\n",
    "<li>Player 2 rolls <code>10</code>+<code>11</code>+<code>12</code> and moves to space <code>6</code> for a total score of <code>9</code>.</li>\n",
    "<li>Player 1 rolls <code>13</code>+<code>14</code>+<code>15</code> and moves to space <code>6</code> for a total score of <code>20</code>.</li>\n",
    "<li>Player 2 rolls <code>16</code>+<code>17</code>+<code>18</code> and moves to space <code>7</code> for a total score of <code>16</code>.</li>\n",
    "<li>Player 1 rolls <code>19</code>+<code>20</code>+<code>21</code> and moves to space <code>6</code> for a total score of <code>26</code>.</li>\n",
    "<li>Player 2 rolls <code>22</code>+<code>23</code>+<code>24</code> and moves to space <code>6</code> for a total score of <code>22</code>.</li>\n",
    "</ul>\n",
    "<p>...after many turns...</p>\n",
    "<ul>\n",
    "<li>Player 2 rolls <code>82</code>+<code>83</code>+<code>84</code> and moves to space <code>6</code> for a total score of <code>742</code>.</li>\n",
    "<li>Player 1 rolls <code>85</code>+<code>86</code>+<code>87</code> and moves to space <code>4</code> for a total score of <code>990</code>.</li>\n",
    "<li>Player 2 rolls <code>88</code>+<code>89</code>+<code>90</code> and moves to space <code>3</code> for a total score of <code>745</code>.</li>\n",
    "<li>Player 1 rolls <code>91</code>+<code>92</code>+<code>93</code> and moves to space <code>10</code> for a final score, <code>1000</code>.</li>\n",
    "</ul>\n",
    "<p>Since player 1 has at least <code>1000</code> points, player 1 wins and the game ends. At this point, the losing player had <code>745</code> points and the die had been rolled a total of <code>993</code> times; <code>745 * 993 = <em>739785</em></code>.</p>\n",
    "<p>Play a practice game using the deterministic 100-sided die. The moment either player wins, <em>what do you get if you multiply the score of the losing player by the number of times the die was rolled during the game?</em></p>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "b3d2fe85",
   "metadata": {
    "dotnet_interactive": {
     "language": "fsharp"
    }
   },
   "outputs": [],
   "source": [
    "let input = File.ReadAllLines @\"input/21.txt\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "6a3f421b",
   "metadata": {
    "dotnet_interactive": {
     "language": "fsharp"
    }
   },
   "outputs": [],
   "source": [
    "type Player = {\n",
    "    Position: int\n",
    "    Score: int\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "430ff3b9",
   "metadata": {
    "dotnet_interactive": {
     "language": "fsharp"
    }
   },
   "outputs": [],
   "source": [
    "let parse (input: string array) = \n",
    "    let p1 = input.[0].Split(\": \").[1] |> int\n",
    "    let p2 = input.[1].Split(\": \").[1] |> int\n",
    "    {\n",
    "        Position = p1\n",
    "        Score = 0\n",
    "    },\n",
    "    {\n",
    "        Position = p2\n",
    "        Score = 0\n",
    "    }"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "71c4f8ca",
   "metadata": {
    "dotnet_interactive": {
     "language": "fsharp"
    }
   },
   "outputs": [],
   "source": [
    "let deterministicDie = \n",
    "    Seq.initInfinite (fun i -> (i % 100) + 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "b4ad23d9",
   "metadata": {
    "dotnet_interactive": {
     "language": "fsharp"
    }
   },
   "outputs": [],
   "source": [
    "let move rollTotal player = \n",
    "    let newPosition = ((player.Position - 1 + rollTotal ) % 10) + 1\n",
    "    {\n",
    "        Position = newPosition\n",
    "        Score = player.Score + newPosition\n",
    "    }"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "3ee0f075",
   "metadata": {
    "dotnet_interactive": {
     "language": "fsharp"
    }
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div class=\"dni-plaintext\">797160</div>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/plain": [
       "Wall time: 160.4685ms"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "#!time\n",
    "let (player1, player2) = parse input\n",
    "\n",
    "deterministicDie\n",
    "|> Seq.chunkBySize 3\n",
    "|> Seq.map Seq.sum\n",
    "|> Seq.indexed\n",
    "|> Seq.scan (fun (p1, p2, r) (i, rollTotal) -> \n",
    "    if i % 2 = 0 then\n",
    "        move rollTotal p1, p2, (i + 1) * 3\n",
    "    else\n",
    "        p1, move rollTotal p2, (i + 1) * 3) (player1, player2, 0)\n",
    "|> Seq.find (fun (p1, p2, r) ->\n",
    "    p1.Score >= 1000 || p2.Score >= 1000)\n",
    "|> fun (p1, p2, r) -> ([p1.Score; p2.Score] |> List.min) * r"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "845efdd9-7742-41e1-889d-dc706863d93d",
   "metadata": {},
   "source": [
    "<h2 id=\"part2\">--- Part Two ---</h2>"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d6207d17",
   "metadata": {},
   "source": [
    "<p>Now that you're warmed up, it's time to play the real game.</p>\n",
    "<p>A second compartment opens, this time labeled <em>Dirac dice</em>. Out of it falls a single three-sided die.</p>\n",
    "<p>As you experiment with the die, you feel a little strange. An informational brochure in the compartment explains that this is a <em>quantum die</em>: when you roll it, the universe <em>splits into multiple copies</em>, one copy for each possible outcome of the die. In this case, rolling the die always splits the universe into <em>three copies</em>: one where the outcome of the roll was <code>1</code>, one where it was <code>2</code>, and one where it was <code>3</code>.</p>\n",
    "<p>The game is played the same as before, although to prevent things from getting too far out of hand, the game now ends when either player's score reaches at least <code><em>21</em></code>.</p>\n",
    "<p>Using the same starting positions as in the example above, player 1 wins in <code><em>444356092776315</em></code> universes, while player 2 merely wins in <code>341960390180808</code> universes.</p>\n",
    "<p>Using your given starting positions, determine every possible outcome. <em>Find the player that wins in more universes; in how many universes does that player win?</em></p>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "e6a4ef09",
   "metadata": {
    "dotnet_interactive": {
     "language": "fsharp"
    }
   },
   "outputs": [],
   "source": [
    "open System.Collections.Generic"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "5d386b39",
   "metadata": {
    "dotnet_interactive": {
     "language": "fsharp"
    }
   },
   "outputs": [],
   "source": [
    "let memoize func =\n",
    "    let cache = Dictionary<_, _>();\n",
    "    fun key ->\n",
    "        let exists, value = cache.TryGetValue key\n",
    "        if exists then\n",
    "            value\n",
    "        else\n",
    "            let value = func key\n",
    "            cache.Add(key, value)\n",
    "            value"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "dd1ac180",
   "metadata": {},
   "source": [
    "Got the memoization technique from [here](https://thesharperdev.com/posts/fsharp-memoization/)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "fa4f24fc",
   "metadata": {
    "dotnet_interactive": {
     "language": "fsharp"
    }
   },
   "outputs": [],
   "source": [
    "let diracDiceRolls = \n",
    "    [\n",
    "        [1;1;1]\n",
    "        [1;1;2]\n",
    "        [1;1;3]\n",
    "        [1;2;1]\n",
    "        [1;2;2]\n",
    "        [1;2;3]\n",
    "        [1;3;1]\n",
    "        [1;3;2]\n",
    "        [1;3;3]\n",
    "        [2;1;1]\n",
    "        [2;1;2]\n",
    "        [2;1;3]\n",
    "        [2;2;1]\n",
    "        [2;2;2]\n",
    "        [2;2;3]\n",
    "        [2;3;1]\n",
    "        [2;3;2]\n",
    "        [2;3;3]\n",
    "        [3;1;1]\n",
    "        [3;1;2]\n",
    "        [3;1;3]\n",
    "        [3;2;1]\n",
    "        [3;2;2]\n",
    "        [3;2;3]\n",
    "        [3;3;1]\n",
    "        [3;3;2]\n",
    "        [3;3;3]\n",
    "    ]\n",
    "    |> List.map List.sum\n",
    "    |> List.countBy id\n",
    "\n",
    "let rec play (player1, player2) =\n",
    "    if player2.Score >= 21 then\n",
    "        0L, 1L\n",
    "    else\n",
    "        diracDiceRolls\n",
    "        |> Seq.fold (fun (wins1, wins2) (rollTotal, numberOfUniverses) -> \n",
    "            let (w2, w1) = play (player2, move rollTotal player1)\n",
    "            wins1 + (int64 numberOfUniverses) * w1, wins2 + (int64 numberOfUniverses) * w2) (0L, 0L)\n",
    "\n",
    "let memoizedPlay = memoize play"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "1b2ef7da",
   "metadata": {
    "dotnet_interactive": {
     "language": "fsharp"
    }
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div class=\"dni-plaintext\">27464148626406</div>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/plain": [
       "Wall time: 1373.314ms"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "#!time\n",
    "memoizedPlay (player1, player2)\n",
    "|> fun (win1, win2) -> [win1; win2] |> List.max"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2cf45427-c80e-4427-963f-cef8340e03e7",
   "metadata": {},
   "source": [
    "[Prev](Day20.ipynb) | [Next](Day22.ipynb)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": ".NET (F#)",
   "language": "F#",
   "name": ".net-fsharp"
  },
  "language_info": {
   "file_extension": ".fs",
   "mimetype": "text/x-fsharp",
   "name": "C#",
   "pygments_lexer": "fsharp",
   "version": "4.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}