problems/day24.html

   1 <!DOCTYPE html>
   2 <html lang="en-us">
   3 <head>
   4 <meta charset="utf-8"/>
   5 <title>Day 24 - 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?28"/>
   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 <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>
  12 </head><!--
  13
  14
  15
  16
  17 Oh, hello!  Funny seeing you here.
  18
  19 I appreciate your enthusiasm, but you aren't going to find much down here.
  20 There certainly aren't clues to any of the puzzles.  The best surprises don't
  21 even appear in the source until you unlock them for real.
  22
  23 Please be careful with automated requests; I'm not a massive company, and I can
  24 only take so much traffic.  Please be considerate so that everyone gets to play.
  25
  26 If you're curious about how Advent of Code works, it's running on some custom
  27 Perl code. Other than a few integrations (auth, analytics, social media), I
  28 built the whole thing myself, including the design, animations, prose, and all
  29 of the puzzles.
  30
  31 The puzzles are most of the work; preparing a new calendar and a new set of
  32 puzzles each year takes all of my free time for 4-5 months. A lot of effort
  33 went into building this thing - I hope you're enjoying playing it as much as I
  34 enjoyed making it for you!
  35
  36 If you'd like to hang out, I'm @ericwastl on Twitter.
  37
  38 - Eric Wastl
  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 -->
  90 <body>
  91 <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">48*</span></div></div><div><h1 class="title-event">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span class="title-event-wrap">/^</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>
  92
  93 <div id="sidebar">
  94 <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://2021-aoc-templates.util.repl.co/" target="_blank" onclick="if(ga)ga('send','event','sponsor','sidebar',this.href);" rel="noopener">Replit</a> - Code and host in your browser with no setup in Python, React, Kaboom.js, Java, C, Nix, you name it, even Solidity. Happy coding!</div></div>
  95 </div><!--/sidebar-->
  96
  97 <main>
  98 <article class="day-desc"><h2>--- Day 24: Arithmetic Logic Unit ---</h2><p><a href="https://en.wikipedia.org/wiki/Magic_smoke" target="_blank">Magic smoke</a> starts leaking from the submarine's <a href="https://en.wikipedia.org/wiki/Arithmetic_logic_unit">arithmetic logic unit</a> (ALU). Without the ability to perform basic arithmetic and logic functions, the submarine can't produce cool patterns with its Christmas lights!</p>
  99 <p>It also can't navigate. Or run the oxygen system.</p>
 100 <p>Don't worry, though - you <em>probably</em> have enough oxygen left to give you enough time to build a new ALU.</p>
 101 <p>The ALU is a four-dimensional processing unit: it has integer variables <code>w</code>, <code>x</code>, <code>y</code>, and <code>z</code>. These variables all start with the value <code>0</code>. The ALU also supports <em>six instructions</em>:</p>
 102 <ul>
 103 <li><code>inp a</code> - Read an input value and write it to variable <code>a</code>.</li>
 104 <li><code>add a b</code> - Add the value of <code>a</code> to the value of <code>b</code>, then store the result in variable <code>a</code>.</li>
 105 <li><code>mul a b</code> - Multiply the value of <code>a</code> by the value of <code>b</code>, then store the result in variable <code>a</code>.</li>
 106 <li><code>div a b</code> - Divide the value of <code>a</code> by the value of <code>b</code>, truncate the result to an integer, then store the result in variable <code>a</code>. (Here, "truncate" means to round the value toward zero.)</li>
 107 <li><code>mod a b</code> - Divide the value of <code>a</code> by the value of <code>b</code>, then store the <em>remainder</em> in variable <code>a</code>. (This is also called the <a href="https://en.wikipedia.org/wiki/Modulo_operation" target="_blank">modulo</a> operation.)</li>
 108 <li><code>eql a b</code> - If the value of <code>a</code> and <code>b</code> are equal, then store the value <code>1</code> in variable <code>a</code>. Otherwise, store the value <code>0</code> in variable <code>a</code>.</li>
 109 </ul>
 110 <p>In all of these instructions, <code>a</code> and <code>b</code> are placeholders; <code>a</code> will always be the variable where the result of the operation is stored (one of <code>w</code>, <code>x</code>, <code>y</code>, or <code>z</code>), while <code>b</code> can be either a variable or a number. Numbers can be positive or negative, but will always be integers.</p>
 111 <p>The ALU has no <em>jump</em> instructions; in an ALU program, every instruction is run exactly once in order from top to bottom. The program halts after the last instruction has finished executing.</p>
 112 <p>(Program authors should be especially cautious; attempting to execute <code>div</code> with <code>b=0</code> or attempting to execute <code>mod</code> with <code>a&lt;0</code> or <code>b&lt;=0</code>  will cause the program to crash and might even <span title="Maybe this is what happened to the last one.">damage the ALU</span>. These operations are never intended in any serious ALU program.)</p>
 113 <p>For example, here is an ALU program which takes an input number, negates it, and stores it in <code>x</code>:</p>
 114 <pre><code>inp x
 115 mul x -1
 116 </code></pre>
 117 <p>Here is an ALU program which takes two input numbers, then sets <code>z</code> to <code>1</code> if the second input number is three times larger than the first input number, or sets <code>z</code> to <code>0</code> otherwise:</p>
 118 <pre><code>inp z
 119 inp x
 120 mul z 3
 121 eql z x
 122 </code></pre>
 123 <p>Here is an ALU program which takes a non-negative integer as input, converts it into binary, and stores the lowest (1's) bit in <code>z</code>, the second-lowest (2's) bit in <code>y</code>, the third-lowest (4's) bit in <code>x</code>, and the fourth-lowest (8's) bit in <code>w</code>:</p>
 124 <pre><code>inp w
 125 add z w
 126 mod z 2
 127 div w 2
 128 add y w
 129 mod y 2
 130 div w 2
 131 add x w
 132 mod x 2
 133 div w 2
 134 mod w 2
 135 </code></pre>
 136 <p>Once you have built a replacement ALU, you can install it in the submarine, which will immediately resume what it was doing when the ALU failed: validating the submarine's <em>model number</em>. To do this, the ALU will run the MOdel Number Automatic Detector program (MONAD, your puzzle input).</p>
 137 <p>Submarine model numbers are always <em>fourteen-digit numbers</em> consisting only of digits <code>1</code> through <code>9</code>. The digit <code>0</code> <em>cannot</em> appear in a model number.</p>
 138 <p>When MONAD checks a hypothetical fourteen-digit model number, it uses fourteen separate <code>inp</code> instructions, each expecting a <em>single digit</em> of the model number in order of most to least significant. (So, to check the model number <code>13579246899999</code>, you would give <code>1</code> to the first <code>inp</code> instruction, <code>3</code> to the second <code>inp</code> instruction, <code>5</code> to the third <code>inp</code> instruction, and so on.) This means that when operating MONAD, each input instruction should only ever be given an integer value of at least <code>1</code> and at most <code>9</code>.</p>
 139 <p>Then, after MONAD has finished running all of its instructions, it will indicate that the model number was <em>valid</em> by leaving a <code>0</code> in variable <code>z</code>. However, if the model number was <em>invalid</em>, it will leave some other non-zero value in <code>z</code>.</p>
 140 <p>MONAD imposes additional, mysterious restrictions on model numbers, and legend says the last copy of the MONAD documentation was eaten by a <a href="https://en.wikipedia.org/wiki/Japanese_raccoon_dog" target="_blank">tanuki</a>. You'll need to <em>figure out what MONAD does</em> some other way.</p>
 141 <p>To enable as many submarine features as possible, find the largest valid fourteen-digit model number that contains no <code>0</code> digits. <em>What is the largest model number accepted by MONAD?</em></p>
 142 </article>
 143 <p>Your puzzle answer was <code>91398299697996</code>.</p><article class="day-desc"><h2 id="part2">--- Part Two ---</h2><p>As the submarine starts booting up things like the <a href="https://www.youtube.com/watch?v=RXJKdh1KZ0w" target="_blank">Retro Encabulator</a>, you realize that maybe you don't need all these submarine features after all.</p>
 144 <p><em>What is the smallest model number accepted by MONAD?</em></p>
 145 </article>
 146 <p>Your puzzle answer was <code>41171183141291</code>.</p><p class="day-success">Both parts of this puzzle are complete! They provide two gold stars: **</p>
 147 <p>At this point, you should <a href="/2021">return to your Advent calendar</a> and try another puzzle.</p>
 148 <p>If you still want to see it, you can <a href="24/input" target="_blank">get your puzzle input</a>.</p>
 149 <p>You can also <span class="share">[Share<span class="share-content">on
 150   <a href="https://twitter.com/intent/tweet?text=I%27ve+completed+%22Arithmetic+Logic+Unit%22+%2D+Day+24+%2D+Advent+of+Code+2021&amp;url=https%3A%2F%2Fadventofcode%2Ecom%2F2021%2Fday%2F24&amp;related=ericwastl&amp;hashtags=AdventOfCode" target="_blank">Twitter</a>
 151   <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+%22Arithmetic+Logic+Unit%22+%2D+Day+24+%2D+Advent+of+Code+2021+%23AdventOfCode+https%3A%2F%2Fadventofcode%2Ecom%2F2021%2Fday%2F24'}else{return false;}" target="_blank">Mastodon</a
 152 ></span>]</span> this puzzle.</p>
 153 </main>
 154
 155 <!-- ga -->
 156 <script>
 157 (function(i,s,o,g,r,a,m){i['GoogleAnalyticsObject']=r;i[r]=i[r]||function(){
 158 (i[r].q=i[r].q||[]).push(arguments)},i[r].l=1*new Date();a=s.createElement(o),
 159 m=s.getElementsByTagName(o)[0];a.async=1;a.src=g;m.parentNode.insertBefore(a,m)
 160 })(window,document,'script','//www.google-analytics.com/analytics.js','ga');
 161 ga('create', 'UA-69522494-1', 'auto');
 162 ga('set', 'anonymizeIp', true);
 163 ga('send', 'pageview');
 164 </script>
 165 <!-- /ga -->
 166 </body>
 167 </html>