problems/day10.html

   1 <!DOCTYPE html>
   2 <html lang="en-us">
   3 <head>
   4 <meta charset="utf-8"/>
   5 <title>Day 10 - 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">20*</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://ximedes.com/working-at-ximedes/" target="_blank" onclick="if(ga)ga('send','event','sponsor','sidebar',this.href);" rel="noopener">Ximedes</a> - From Kotlin in the cloud to NodeJS in the terminal, our software powers payments and public transport ticketing all over the world.</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 10: Syntax Scoring ---</h2><p>You ask the submarine to determine the best route out of the deep-sea cave, but it only replies:</p>
  99 <pre><code>Syntax error in navigation subsystem on line: <span title="Some days, that's just how it is.">all of them</span></code></pre>
 100 <p><em>All of them?!</em> The damage is worse than you thought. You bring up a copy of the navigation subsystem (your puzzle input).</p>
 101 <p>The navigation subsystem syntax is made of several lines containing <em>chunks</em>. There are one or more chunks on each line, and chunks contain zero or more other chunks. Adjacent chunks are not separated by any delimiter; if one chunk stops, the next chunk (if any) can immediately start. Every chunk must <em>open</em> and <em>close</em> with one of four legal pairs of matching characters:</p>
 102 <ul>
 103 <li>If a chunk opens with <code>(</code>, it must close with <code>)</code>.</li>
 104 <li>If a chunk opens with <code>[</code>, it must close with <code>]</code>.</li>
 105 <li>If a chunk opens with <code>{</code>, it must close with <code>}</code>.</li>
 106 <li>If a chunk opens with <code>&lt;</code>, it must close with <code>&gt;</code>.</li>
 107 </ul>
 108 <p>So, <code>()</code> is a legal chunk that contains no other chunks, as is <code>[]</code>. More complex but valid chunks include <code>([])</code>, <code>{()()()}</code>, <code>&lt;([{}])&gt;</code>, <code>[&lt;&gt;({}){}[([])&lt;&gt;]]</code>, and even <code>(((((((((())))))))))</code>.</p>
 109 <p>Some lines are <em>incomplete</em>, but others are <em>corrupted</em>. Find and discard the corrupted lines first.</p>
 110 <p>A corrupted line is one where a chunk <em>closes with the wrong character</em> - that is, where the characters it opens and closes with do not form one of the four legal pairs listed above.</p>
 111 <p>Examples of corrupted chunks include <code>(]</code>, <code>{()()()&gt;</code>, <code>(((()))}</code>, and <code>&lt;([]){()}[{}])</code>. Such a chunk can appear anywhere within a line, and its presence causes the whole line to be considered corrupted.</p>
 112 <p>For example, consider the following navigation subsystem:</p>
 113 <pre><code>[({(&lt;(())[]&gt;[[{[]{&lt;()&lt;&gt;&gt;
 114 [(()[&lt;&gt;])]({[&lt;{&lt;&lt;[]&gt;&gt;(
 115 {([(&lt;{}[&lt;&gt;[]}&gt;{[]{[(&lt;()&gt;
 116 (((({&lt;&gt;}&lt;{&lt;{&lt;&gt;}{[]{[]{}
 117 [[&lt;[([]))&lt;([[{}[[()]]]
 118 [{[{({}]{}}([{[{{{}}([]
 119 {&lt;[[]]&gt;}&lt;{[{[{[]{()[[[]
 120 [&lt;(&lt;(&lt;(&lt;{}))&gt;&lt;([]([]()
 121 &lt;{([([[(&lt;&gt;()){}]&gt;(&lt;&lt;{{
 122 &lt;{([{{}}[&lt;[[[&lt;&gt;{}]]]&gt;[]]
 123 </code></pre>
 124 <p>Some of the lines aren't corrupted, just incomplete; you can ignore these lines for now. The remaining five lines are corrupted:</p>
 125 <ul>
 126 <li><code>{([(&lt;{}[&lt;&gt;[]}&gt;{[]{[(&lt;()&gt;</code> - Expected <code>]</code>, but found <code>}</code> instead.</li>
 127 <li><code>[[&lt;[([]))&lt;([[{}[[()]]]</code> - Expected <code>]</code>, but found <code>)</code> instead.</li>
 128 <li><code>[{[{({}]{}}([{[{{{}}([]</code> - Expected <code>)</code>, but found <code>]</code> instead.</li>
 129 <li><code>[&lt;(&lt;(&lt;(&lt;{}))&gt;&lt;([]([]()</code> - Expected <code>&gt;</code>, but found <code>)</code> instead.</li>
 130 <li><code>&lt;{([([[(&lt;&gt;()){}]&gt;(&lt;&lt;{{</code> - Expected <code>]</code>, but found <code>&gt;</code> instead.</li>
 131 </ul>
 132 <p>Stop at the first incorrect closing character on each corrupted line.</p>
 133 <p>Did you know that syntax checkers actually have contests to see who can get the high score for syntax errors in a file? It's true! To calculate the syntax error score for a line, take the <em>first illegal character</em> on the line and look it up in the following table:</p>
 134 <ul>
 135 <li><code>)</code>: <code>3</code> points.</li>
 136 <li><code>]</code>: <code>57</code> points.</li>
 137 <li><code>}</code>: <code>1197</code> points.</li>
 138 <li><code>&gt;</code>: <code>25137</code> points.</li>
 139 </ul>
 140 <p>In the above example, an illegal <code>)</code> was found twice (<code>2*3 = <em>6</em></code> points), an illegal <code>]</code> was found once (<code><em>57</em></code> points), an illegal <code>}</code> was found once (<code><em>1197</em></code> points), and an illegal <code>&gt;</code> was found once (<code><em>25137</em></code> points). So, the total syntax error score for this file is <code>6+57+1197+25137 = <em>26397</em></code> points!</p>
 141 <p>Find the first illegal character in each corrupted line of the navigation subsystem. <em>What is the total syntax error score for those errors?</em></p>
 142 </article>
 143 <p>Your puzzle answer was <code>339537</code>.</p><article class="day-desc"><h2 id="part2">--- Part Two ---</h2><p>Now, discard the corrupted lines.  The remaining lines are <em>incomplete</em>.</p>
 144 <p>Incomplete lines don't have any incorrect characters - instead, they're missing some closing characters at the end of the line. To repair the navigation subsystem, you just need to figure out <em>the sequence of closing characters</em> that complete all open chunks in the line.</p>
 145 <p>You can only use closing characters (<code>)</code>, <code>]</code>, <code>}</code>, or <code>&gt;</code>), and you must add them in the correct order so that only legal pairs are formed and all chunks end up closed.</p>
 146 <p>In the example above, there are five incomplete lines:</p>
 147 <ul>
 148 <li><code>[({(&lt;(())[]&gt;[[{[]{&lt;()&lt;&gt;&gt;</code> - Complete by adding <code>}}]])})]</code>.</li>
 149 <li><code>[(()[&lt;&gt;])]({[&lt;{&lt;&lt;[]&gt;&gt;(</code> - Complete by adding <code>)}&gt;]})</code>.</li>
 150 <li><code>(((({&lt;&gt;}&lt;{&lt;{&lt;&gt;}{[]{[]{}</code> - Complete by adding <code>}}&gt;}&gt;))))</code>.</li>
 151 <li><code>{&lt;[[]]&gt;}&lt;{[{[{[]{()[[[]</code> - Complete by adding <code>]]}}]}]}&gt;</code>.</li>
 152 <li><code>&lt;{([{{}}[&lt;[[[&lt;&gt;{}]]]&gt;[]]</code> - Complete by adding <code>])}&gt;</code>.</li>
 153 </ul>
 154 <p>Did you know that autocomplete tools <em>also</em> have contests? It's true! The score is determined by considering the completion string character-by-character. Start with a total score of <code>0</code>. Then, for each character, multiply the total score by 5 and then increase the total score by the point value given for the character in the following table:</p>
 155 <ul>
 156 <li><code>)</code>: <code>1</code> point.</li>
 157 <li><code>]</code>: <code>2</code> points.</li>
 158 <li><code>}</code>: <code>3</code> points.</li>
 159 <li><code>&gt;</code>: <code>4</code> points.</li>
 160 </ul>
 161 <p>So, the last completion string above - <code>])}&gt;</code> - would be scored as follows:</p>
 162 <ul>
 163 <li>Start with a total score of <code>0</code>.</li>
 164 <li>Multiply the total score by 5 to get <code>0</code>, then add the value of <code>]</code> (2) to get a new total score of <code>2</code>.</li>
 165 <li>Multiply the total score by 5 to get <code>10</code>, then add the value of <code>)</code> (1) to get a new total score of <code>11</code>.</li>
 166 <li>Multiply the total score by 5 to get <code>55</code>, then add the value of <code>}</code> (3) to get a new total score of <code>58</code>.</li>
 167 <li>Multiply the total score by 5 to get <code>290</code>, then add the value of <code>&gt;</code> (4) to get a new total score of <code>294</code>.</li>
 168 </ul>
 169 <p>The five lines' completion strings have total scores as follows:</p>
 170 <ul>
 171 <li><code>}}]])})]</code> - <code>288957</code> total points.</li>
 172 <li><code>)}&gt;]})</code> - <code>5566</code> total points.</li>
 173 <li><code>}}&gt;}&gt;))))</code> - <code>1480781</code> total points.</li>
 174 <li><code>]]}}]}]}&gt;</code> - <code>995444</code> total points.</li>
 175 <li><code>])}&gt;</code> - <code>294</code> total points.</li>
 176 </ul>
 177 <p>Autocomplete tools are an odd bunch: the winner is found by <em>sorting</em> all of the scores and then taking the <em>middle</em> score. (There will always be an odd number of scores to consider.) In this example, the middle score is <code><em>288957</em></code> because there are the same number of scores smaller and larger than it.</p>
 178 <p>Find the completion string for each incomplete line, score the completion strings, and sort the scores. <em>What is the middle score?</em></p>
 179 </article>
 180 <p>Your puzzle answer was <code>2412013412</code>.</p><p class="day-success">Both parts of this puzzle are complete! They provide two gold stars: **</p>
 181 <p>At this point, you should <a href="/2021">return to your Advent calendar</a> and try another puzzle.</p>
 182 <p>If you still want to see it, you can <a href="10/input" target="_blank">get your puzzle input</a>.</p>
 183 <p>You can also <span class="share">[Share<span class="share-content">on
 184   <a href="https://twitter.com/intent/tweet?text=I%27ve+completed+%22Syntax+Scoring%22+%2D+Day+10+%2D+Advent+of+Code+2021&amp;url=https%3A%2F%2Fadventofcode%2Ecom%2F2021%2Fday%2F10&amp;related=ericwastl&amp;hashtags=AdventOfCode" target="_blank">Twitter</a>
 185   <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+%22Syntax+Scoring%22+%2D+Day+10+%2D+Advent+of+Code+2021+%23AdventOfCode+https%3A%2F%2Fadventofcode%2Ecom%2F2021%2Fday%2F10'}else{return false;}" target="_blank">Mastodon</a
 186 ></span>]</span> this puzzle.</p>
 187 </main>
 188
 189 <!-- ga -->
 190 <script>
 191 (function(i,s,o,g,r,a,m){i['GoogleAnalyticsObject']=r;i[r]=i[r]||function(){
 192 (i[r].q=i[r].q||[]).push(arguments)},i[r].l=1*new Date();a=s.createElement(o),
 193 m=s.getElementsByTagName(o)[0];a.async=1;a.src=g;m.parentNode.insertBefore(a,m)
 194 })(window,document,'script','//www.google-analytics.com/analytics.js','ga');
 195 ga('create', 'UA-69522494-1', 'auto');
 196 ga('set', 'anonymizeIp', true);
 197 ga('send', 'pageview');
 198 </script>
 199 <!-- /ga -->
 200 </body>
 201 </html>