problems/day08.html

   1 <!DOCTYPE html>
   2 <html lang="en-us">
   3 <head>
   4 <meta charset="utf-8"/>
   5 <title>Day 8 - 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">16*</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://www.tcgplayer.com/adventofcode/?utm_campaign=aoc&amp;utm_source=adventOfCode&amp;utm_medium=aocPromo" target="_blank" onclick="if(ga)ga('send','event','sponsor','sidebar',this.href);" rel="noopener">TCGplayer.com</a> - - . Hiring .NET &amp; . . JS engineers. . . Help us serve . . our community . . of game stores. . &amp; hobbyists!! . ---- JOIN US ----</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 8: Seven Segment Search ---</h2><p>You barely reach the safety of the cave when the whale smashes into the cave mouth, collapsing it. Sensors indicate another exit to this cave at a much greater depth, so you have no choice but to press on.</p>
  99 <p>As your submarine slowly makes its way through the cave system, you notice that the four-digit <a href="https://en.wikipedia.org/wiki/Seven-segment_display" target="_blank">seven-segment displays</a> in your submarine are malfunctioning; <span title="Yes, just the four-digit seven-segment ones. Whole batch must have been faulty.">they must have been damaged</span> during the escape. You'll be in a lot of trouble without them, so you'd better figure out what's wrong.</p>
 100 <p>Each digit of a seven-segment display is rendered by turning on or off any of seven segments named <code>a</code> through <code>g</code>:</p>
 101 <pre><code>  0:      1:      2:      3:      4:
 102  <em>aaaa</em>    ....    <em>aaaa    aaaa</em>    ....
 103 <em>b    c</em>  .    <em>c</em>  .    <em>c</em>  .    <em>c  b    c</em>
 104 <em>b    c</em>  .    <em>c</em>  .    <em>c</em>  .    <em>c  b    c</em>
 105  ....    ....    <em>dddd    dddd    dddd</em>
 106 <em>e    f</em>  .    <em>f  e</em>    .  .    <em>f</em>  .    <em>f</em>
 107 <em>e    f</em>  .    <em>f  e</em>    .  .    <em>f</em>  .    <em>f</em>
 108  <em>gggg</em>    ....    <em>gggg    gggg</em>    ....
 109
 110   5:      6:      7:      8:      9:
 111  <em>aaaa    aaaa    aaaa    aaaa    aaaa</em>
 112 <em>b</em>    .  <em>b</em>    .  .    <em>c  b    c  b    c</em>
 113 <em>b</em>    .  <em>b</em>    .  .    <em>c  b    c  b    c</em>
 114  <em>dddd    dddd</em>    ....    <em>dddd    dddd</em>
 115 .    <em>f  e    f</em>  .    <em>f  e    f</em>  .    <em>f</em>
 116 .    <em>f  e    f</em>  .    <em>f  e    f</em>  .    <em>f</em>
 117  <em>gggg    gggg</em>    ....    <em>gggg    gggg</em>
 118 </code></pre>
 119 <p>So, to render a <code>1</code>, only segments <code>c</code> and <code>f</code> would be turned on; the rest would be off. To render a <code>7</code>, only segments <code>a</code>, <code>c</code>, and <code>f</code> would be turned on.</p>
 120 <p>The problem is that the signals which control the segments have been mixed up on each display. The submarine is still trying to display numbers by producing output on signal wires <code>a</code> through <code>g</code>, but those wires are connected to segments <em>randomly</em>. Worse, the wire/segment connections are mixed up separately for each four-digit display! (All of the digits <em>within</em> a display use the same connections, though.)</p>
 121 <p>So, you might know that only signal wires <code>b</code> and <code>g</code> are turned on, but that doesn't mean <em>segments</em> <code>b</code> and <code>g</code> are turned on: the only digit that uses two segments is <code>1</code>, so it must mean segments <code>c</code> and <code>f</code> are meant to be on. With just that information, you still can't tell which wire (<code>b</code>/<code>g</code>) goes to which segment (<code>c</code>/<code>f</code>). For that, you'll need to collect more information.</p>
 122 <p>For each display, you watch the changing signals for a while, make a note of <em>all ten unique signal patterns</em> you see, and then write down a single <em>four digit output value</em> (your puzzle input). Using the signal patterns, you should be able to work out which pattern corresponds to which digit.</p>
 123 <p>For example, here is what you might see in a single entry in your notes:</p>
 124 <pre><code>acedgfb cdfbe gcdfa fbcad dab cefabd cdfgeb eafb cagedb ab |
 125 cdfeb fcadb cdfeb cdbaf</code></pre>
 126 <p>(The entry is wrapped here to two lines so it fits; in your notes, it will all be on a single line.)</p>
 127 <p>Each entry consists of ten <em>unique signal patterns</em>, a <code>|</code> delimiter, and finally the <em>four digit output value</em>. Within an entry, the same wire/segment connections are used (but you don't know what the connections actually are). The unique signal patterns correspond to the ten different ways the submarine tries to render a digit using the current wire/segment connections. Because <code>7</code> is the only digit that uses three segments, <code>dab</code> in the above example means that to render a <code>7</code>, signal lines <code>d</code>, <code>a</code>, and <code>b</code> are on. Because <code>4</code> is the only digit that uses four segments, <code>eafb</code> means that to render a <code>4</code>, signal lines <code>e</code>, <code>a</code>, <code>f</code>, and <code>b</code> are on.</p>
 128 <p>Using this information, you should be able to work out which combination of signal wires corresponds to each of the ten digits. Then, you can decode the four digit output value. Unfortunately, in the above example, all of the digits in the output value (<code>cdfeb fcadb cdfeb cdbaf</code>) use five segments and are more difficult to deduce.</p>
 129 <p>For now, <em>focus on the easy digits</em>. Consider this larger example:</p>
 130 <pre><code>be cfbegad cbdgef fgaecd cgeb fdcge agebfd fecdb fabcd edb |
 131 <em>fdgacbe</em> cefdb cefbgd <em>gcbe</em>
 132 edbfga begcd cbg gc gcadebf fbgde acbgfd abcde gfcbed gfec |
 133 fcgedb <em>cgb</em> <em>dgebacf</em> <em>gc</em>
 134 fgaebd cg bdaec gdafb agbcfd gdcbef bgcad gfac gcb cdgabef |
 135 <em>cg</em> <em>cg</em> fdcagb <em>cbg</em>
 136 fbegcd cbd adcefb dageb afcb bc aefdc ecdab fgdeca fcdbega |
 137 efabcd cedba gadfec <em>cb</em>
 138 aecbfdg fbg gf bafeg dbefa fcge gcbea fcaegb dgceab fcbdga |
 139 <em>gecf</em> <em>egdcabf</em> <em>bgf</em> bfgea
 140 fgeab ca afcebg bdacfeg cfaedg gcfdb baec bfadeg bafgc acf |
 141 <em>gebdcfa</em> <em>ecba</em> <em>ca</em> <em>fadegcb</em>
 142 dbcfg fgd bdegcaf fgec aegbdf ecdfab fbedc dacgb gdcebf gf |
 143 <em>cefg</em> dcbef <em>fcge</em> <em>gbcadfe</em>
 144 bdfegc cbegaf gecbf dfcage bdacg ed bedf ced adcbefg gebcd |
 145 <em>ed</em> bcgafe cdgba cbgef
 146 egadfb cdbfeg cegd fecab cgb gbdefca cg fgcdab egfdb bfceg |
 147 <em>gbdfcae</em> <em>bgc</em> <em>cg</em> <em>cgb</em>
 148 gcafb gcf dcaebfg ecagb gf abcdeg gaef cafbge fdbac fegbdc |
 149 <em>fgae</em> cfgab <em>fg</em> bagce
 150 </code></pre>
 151 <p>Because the digits <code>1</code>, <code>4</code>, <code>7</code>, and <code>8</code> each use a unique number of segments, you should be able to tell which combinations of signals correspond to those digits. Counting <em>only digits in the output values</em> (the part after <code>|</code> on each line), in the above example, there are <code><em>26</em></code> instances of digits that use a unique number of segments (highlighted above).</p>
 152 <p><em>In the output values, how many times do digits <code>1</code>, <code>4</code>, <code>7</code>, or <code>8</code> appear?</em></p>
 153 </article>
 154 <p>Your puzzle answer was <code>255</code>.</p><article class="day-desc"><h2 id="part2">--- Part Two ---</h2><p>Through a little deduction, you should now be able to determine the remaining digits. Consider again the first example above:</p>
 155 <pre><code>acedgfb cdfbe gcdfa fbcad dab cefabd cdfgeb eafb cagedb ab |
 156 cdfeb fcadb cdfeb cdbaf</code></pre>
 157 <p>After some careful analysis, the mapping between signal wires and segments only make sense in the following configuration:</p>
 158 <pre><code> dddd
 159 e    a
 160 e    a
 161  ffff
 162 g    b
 163 g    b
 164  cccc
 165 </code></pre>
 166 <p>So, the unique signal patterns would correspond to the following digits:</p>
 167 <ul>
 168 <li><code>acedgfb</code>: <code>8</code></li>
 169 <li><code>cdfbe</code>: <code>5</code></li>
 170 <li><code>gcdfa</code>: <code>2</code></li>
 171 <li><code>fbcad</code>: <code>3</code></li>
 172 <li><code>dab</code>: <code>7</code></li>
 173 <li><code>cefabd</code>: <code>9</code></li>
 174 <li><code>cdfgeb</code>: <code>6</code></li>
 175 <li><code>eafb</code>: <code>4</code></li>
 176 <li><code>cagedb</code>: <code>0</code></li>
 177 <li><code>ab</code>: <code>1</code></li>
 178 </ul>
 179 <p>Then, the four digits of the output value can be decoded:</p>
 180 <ul>
 181 <li><code>cdfeb</code>: <code><em>5</em></code></li>
 182 <li><code>fcadb</code>: <code><em>3</em></code></li>
 183 <li><code>cdfeb</code>: <code><em>5</em></code></li>
 184 <li><code>cdbaf</code>: <code><em>3</em></code></li>
 185 </ul>
 186 <p>Therefore, the output value for this entry is <code><em>5353</em></code>.</p>
 187 <p>Following this same process for each entry in the second, larger example above, the output value of each entry can be determined:</p>
 188 <ul>
 189 <li><code>fdgacbe cefdb cefbgd gcbe</code>: <code>8394</code></li>
 190 <li><code>fcgedb cgb dgebacf gc</code>: <code>9781</code></li>
 191 <li><code>cg cg fdcagb cbg</code>: <code>1197</code></li>
 192 <li><code>efabcd cedba gadfec cb</code>: <code>9361</code></li>
 193 <li><code>gecf egdcabf bgf bfgea</code>: <code>4873</code></li>
 194 <li><code>gebdcfa ecba ca fadegcb</code>: <code>8418</code></li>
 195 <li><code>cefg dcbef fcge gbcadfe</code>: <code>4548</code></li>
 196 <li><code>ed bcgafe cdgba cbgef</code>: <code>1625</code></li>
 197 <li><code>gbdfcae bgc cg cgb</code>: <code>8717</code></li>
 198 <li><code>fgae cfgab fg bagce</code>: <code>4315</code></li>
 199 </ul>
 200 <p>Adding all of the output values in this larger example produces <code><em>61229</em></code>.</p>
 201 <p>For each entry, determine all of the wire/segment connections and decode the four-digit output values. <em>What do you get if you add up all of the output values?</em></p>
 202 </article>
 203 <p>Your puzzle answer was <code>982158</code>.</p><p class="day-success">Both parts of this puzzle are complete! They provide two gold stars: **</p>
 204 <p>At this point, you should <a href="/2021">return to your Advent calendar</a> and try another puzzle.</p>
 205 <p>If you still want to see it, you can <a href="8/input" target="_blank">get your puzzle input</a>.</p>
 206 <p>You can also <span class="share">[Share<span class="share-content">on
 207   <a href="https://twitter.com/intent/tweet?text=I%27ve+completed+%22Seven+Segment+Search%22+%2D+Day+8+%2D+Advent+of+Code+2021&amp;url=https%3A%2F%2Fadventofcode%2Ecom%2F2021%2Fday%2F8&amp;related=ericwastl&amp;hashtags=AdventOfCode" target="_blank">Twitter</a>
 208   <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+%22Seven+Segment+Search%22+%2D+Day+8+%2D+Advent+of+Code+2021+%23AdventOfCode+https%3A%2F%2Fadventofcode%2Ecom%2F2021%2Fday%2F8'}else{return false;}" target="_blank">Mastodon</a
 209 ></span>]</span> this puzzle.</p>
 210 </main>
 211
 212 <!-- ga -->
 213 <script>
 214 (function(i,s,o,g,r,a,m){i['GoogleAnalyticsObject']=r;i[r]=i[r]||function(){
 215 (i[r].q=i[r].q||[]).push(arguments)},i[r].l=1*new Date();a=s.createElement(o),
 216 m=s.getElementsByTagName(o)[0];a.async=1;a.src=g;m.parentNode.insertBefore(a,m)
 217 })(window,document,'script','//www.google-analytics.com/analytics.js','ga');
 218 ga('create', 'UA-69522494-1', 'auto');
 219 ga('set', 'anonymizeIp', true);
 220 ga('send', 'pageview');
 221 </script>
 222 <!-- /ga -->
 223 </body>
 224 </html>