problems/day21.html

   1 <!DOCTYPE html>
   2 <html lang="en-us">
   3 <head>
   4 <meta charset="utf-8"/>
   5 <title>Day 21 - Advent of Code 2021</title>
   6 <!--[if lt IE 9]><script src="/static/html5.js"></script><![endif]-->
   7 <link href='//fonts.googleapis.com/css?family=Source+Code+Pro:300&subset=latin,latin-ext' rel='stylesheet' type='text/css'/>
   8 <link rel="stylesheet" type="text/css" href="/static/style.css?26"/>
   9 <link rel="stylesheet alternate" type="text/css" href="/static/highcontrast.css?0" title="High Contrast"/>
  10 <link rel="shortcut icon" href="/favicon.png"/>
  11 </head><!--
  12
  13
  14
  15
  16 Oh, hello!  Funny seeing you here.
  17
  18 I appreciate your enthusiasm, but you aren't going to find much down here.
  19 There certainly aren't clues to any of the puzzles.  The best surprises don't
  20 even appear in the source until you unlock them for real.
  21
  22 Please be careful with automated requests; I'm not a massive company, and I can
  23 only take so much traffic.  Please be considerate so that everyone gets to play.
  24
  25 If you're curious about how Advent of Code works, it's running on some custom
  26 Perl code. Other than a few integrations (auth, analytics, social media), I
  27 built the whole thing myself, including the design, animations, prose, and all
  28 of the puzzles.
  29
  30 The puzzles are most of the work; preparing a new calendar and a new set of
  31 puzzles each year takes all of my free time for 4-5 months. A lot of effort
  32 went into building this thing - I hope you're enjoying playing it as much as I
  33 enjoyed making it for you!
  34
  35 If you'd like to hang out, I'm @ericwastl on Twitter.
  36
  37 - Eric Wastl
  38
  39
  40
  41
  42
  43
  44
  45
  46
  47
  48
  49
  50
  51
  52
  53
  54
  55
  56
  57
  58
  59
  60
  61
  62
  63
  64
  65
  66
  67
  68
  69
  70
  71
  72
  73
  74
  75
  76
  77
  78
  79
  80
  81
  82
  83
  84
  85
  86
  87
  88 -->
  89 <body>
  90 <header><div><h1 class="title-global"><a href="/">Advent of Code</a></h1><nav><ul><li><a href="/2021/about">[About]</a></li><li><a href="/2021/events">[Events]</a></li><li><a href="https://teespring.com/stores/advent-of-code" target="_blank">[Shop]</a></li><li><a href="/2021/settings">[Settings]</a></li><li><a href="/2021/auth/logout">[Log Out]</a></li></ul></nav><div class="user">Neil Smith <a href="/2021/support" class="supporter-badge" title="Advent of Code Supporter">(AoC++)</a> <span class="star-count">42*</span></div></div><div><h1 class="title-event">&nbsp;&nbsp;<span class="title-event-wrap">{:year </span><a href="/2021">2021</a><span class="title-event-wrap">}</span></h1><nav><ul><li><a href="/2021">[Calendar]</a></li><li><a href="/2021/support">[AoC++]</a></li><li><a href="/2021/sponsors">[Sponsors]</a></li><li><a href="/2021/leaderboard">[Leaderboard]</a></li><li><a href="/2021/stats">[Stats]</a></li></ul></nav></div></header>
  91
  92 <div id="sidebar">
  93 <div id="sponsor"><div class="quiet">Our <a href="/2021/sponsors">sponsors</a> help make Advent of Code possible:</div><div class="sponsor"><a href="https://retool.com/?utm_source=sponsor&amp;utm_medium=event&amp;utm_campaign=adventofcode" target="_blank" onclick="if(ga)ga('send','event','sponsor','sidebar',this.href);" rel="noopener">Retool</a> - Build internal apps remarkably fast. Drag and drop a form together, and have it POST back to your API in minutes. Write JavaScript anywhere to customize. Deploy instantly with access controls and audit logs.</div></div>
  94 </div><!--/sidebar-->
  95
  96 <main>
  97 <script>window.addEventListener('click', function(e,s,r){if(e.target.nodeName==='CODE'&&e.detail===3){s=window.getSelection();s.removeAllRanges();r=document.createRange();r.selectNodeContents(e.target);s.addRange(r);}});</script>
  98 <article class="day-desc"><h2>--- Day 21: Dirac Dice ---</h2><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>
  99 <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>
 100 <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>
 101 <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>
 102 <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>
 103 <p>For example, given these starting positions:</p>
 104 <pre><code>Player 1 starting position: 4
 105 Player 2 starting position: 8
 106 </code></pre>
 107 <p>This is how the game would go:</p>
 108 <ul>
 109 <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>
 110 <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>
 111 <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>
 112 <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>
 113 <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>
 114 <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>
 115 <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>
 116 <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>
 117 </ul>
 118 <p>...after many turns...</p>
 119 <ul>
 120 <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>
 121 <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>
 122 <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>
 123 <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>
 124 </ul>
 125 <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>
 126 <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>
 127 </article>
 128 <p>Your puzzle answer was <code>734820</code>.</p><article class="day-desc"><h2 id="part2">--- Part Two ---</h2><p>Now that you're warmed up, it's time to play the real game.</p>
 129 <p>A second compartment opens, this time labeled <em>Dirac dice</em>. Out of it falls a single three-sided die.</p>
 130 <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>
 131 <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>
 132 <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>
 133 <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>
 134 </article>
 135 <p>Your puzzle answer was <code>193170338541590</code>.</p><p class="day-success">Both parts of this puzzle are complete! They provide two gold stars: **</p>
 136 <p>At this point, you should <a href="/2021">return to your Advent calendar</a> and try another puzzle.</p>
 137 <p>If you still want to see it, you can <a href="21/input" target="_blank">get your puzzle input</a>.</p>
 138 <p>You can also <span class="share">[Share<span class="share-content">on
 139   <a href="https://twitter.com/intent/tweet?text=I%27ve+completed+%22Dirac+Dice%22+%2D+Day+21+%2D+Advent+of+Code+2021&amp;url=https%3A%2F%2Fadventofcode%2Ecom%2F2021%2Fday%2F21&amp;related=ericwastl&amp;hashtags=AdventOfCode" target="_blank">Twitter</a>
 140   <a href="javascript:void(0);" onclick="var mastodon_instance=prompt('Mastodon Instance / Server Name?'); if(typeof mastodon_instance==='string' && mastodon_instance.length){this.href='https://'+mastodon_instance+'/share?text=I%27ve+completed+%22Dirac+Dice%22+%2D+Day+21+%2D+Advent+of+Code+2021+%23AdventOfCode+https%3A%2F%2Fadventofcode%2Ecom%2F2021%2Fday%2F21'}else{return false;}" target="_blank">Mastodon</a
 141 ></span>]</span> this puzzle.</p>
 142 </main>
 143
 144 <!-- ga -->
 145 <script>
 146 (function(i,s,o,g,r,a,m){i['GoogleAnalyticsObject']=r;i[r]=i[r]||function(){
 147 (i[r].q=i[r].q||[]).push(arguments)},i[r].l=1*new Date();a=s.createElement(o),
 148 m=s.getElementsByTagName(o)[0];a.async=1;a.src=g;m.parentNode.insertBefore(a,m)
 149 })(window,document,'script','//www.google-analytics.com/analytics.js','ga');
 150 ga('create', 'UA-69522494-1', 'auto');
 151 ga('set', 'anonymizeIp', true);
 152 ga('send', 'pageview');
 153 </script>
 154 <!-- /ga -->
 155 </body>
 156 </html>