problems/day07.html

   1 <!DOCTYPE html>
   2 <html lang="en-us">
   3 <head>
   4 <meta charset="utf-8"/>
   5 <title>Day 7 - Advent of Code 2017</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?11"/>
   9 <link rel="stylesheet alternate" type="text/css" href="/static/highcontrast.css?0" title="High Contrast"/>
  10 <link rel="shortcut icon" href="/favicon.ico?2"/>
  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 Google, and I can only take
  23 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, ads, social media),
  27 I built the whole thing myself, including the design, animations, prose, and
  28 all of the puzzles.
  29
  30 The puzzles probably took the longest; the easiest ones took an hour or two
  31 each, but the harder ones took 4-5 hours, and a few even longer than that. A
  32 lot of effort went into building this thing - I hope you're enjoying playing it
  33 as much as I 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="/2017/about">[About]</a></li><li><a href="/2017/support">[AoC++]</a></li><li><a href="/2017/events">[Events]</a></li><li><a href="/2017/settings">[Settings]</a></li><li><a href="/2017/auth/logout">[Log Out]</a></li></ul></nav><div class="user">Neil Smith <span class="supporter">(AoC++)</span> <span class="star-count">18*</span></div></div><div><h1 class="title-event">&nbsp;&nbsp;&nbsp;<span class="title-event-wrap">var y=</span><a href="/2017">2017</a><span class="title-event-wrap">;</span></h1><nav><ul><li><a href="/2017">[Calendar]</a></li><li><a href="/2017/leaderboard">[Leaderboard]</a></li><li><a href="/2017/stats">[Stats]</a></li><li><a href="/2017/sponsors">[Sponsors]</a></li></ul></nav></div></header>
  91
  92 <div id="sidebar">
  93 <div id="sponsor"><div class="quiet">Our <a href="/2017/sponsors">sponsors</a> help make Advent of Code possible:</div><p><a href="https://formlabs.com/" target="_blank" onclick="if(ga)ga('send','event','sponsor','click',this.href);" rel="noopener">Formlabs</a> - We make powerful, affordable 3D printers for professionals.</p></div>
  94 <div id="ad">
  95 <script async src="//pagead2.googlesyndication.com/pagead/js/adsbygoogle.js"></script>
  96 <!-- Advent of Code Wide Skyscraper -->
  97 <ins class="adsbygoogle"
  98      style="display:inline-block;width:160px;height:600px"
  99      data-ad-client="ca-pub-9420604735624631"
 100      data-ad-slot="8014013294"></ins>
 101 <script>
 102 (adsbygoogle = window.adsbygoogle || []).push({});
 103 </script>
 104 </div><!--/ad-->
 105 </div><!--/sidebar-->
 106
 107 <main>
 108 <article class="day-desc"><h2>--- Day 7: Recursive Circus ---</h2><p>Wandering further through the circuits of the computer, you come upon a tower of <span title="Turtles, all the way down.">programs</span> that have gotten themselves into a bit of trouble.  A recursive algorithm has gotten out of hand, and now they're balanced precariously in a large tower.</p>
 109 <p>One program at the bottom supports the entire tower. It's holding a large disc, and on the disc are balanced several more sub-towers. At the bottom of these sub-towers, standing on the bottom disc, are other programs, each holding <em>their</em> own disc, and so on. At the very tops of these sub-sub-sub-...-towers, many programs stand simply keeping the disc below them balanced but with no disc of their own.</p>
 110 <p>You offer to help, but first you need to understand the structure of these towers.  You ask each program to yell out their <em>name</em>, their <em>weight</em>, and (if they're holding a disc) the <em>names of the programs immediately above them</em> balancing on that disc. You write this information down (your puzzle input). Unfortunately, in their panic, they don't do this in an orderly fashion; by the time you're done, you're not sure which program gave which information.</p>
 111 <p>For example, if your list is the following:</p>
 112 <pre><code>pbga (66)
 113 xhth (57)
 114 ebii (61)
 115 havc (66)
 116 ktlj (57)
 117 fwft (72) -> ktlj, cntj, xhth
 118 qoyq (66)
 119 padx (45) -> pbga, havc, qoyq
 120 tknk (41) -> ugml, padx, fwft
 121 jptl (61)
 122 ugml (68) -> gyxo, ebii, jptl
 123 gyxo (61)
 124 cntj (57)
 125 </code></pre>
 126 <p>...then you would be able to recreate the structure of the towers that looks like this:</p>
 127 <pre><code>                gyxo
 128               /
 129          ugml - ebii
 130        /      \
 131       |         jptl
 132       |
 133       |         pbga
 134      /        /
 135 tknk --- padx - havc
 136      \        \
 137       |         qoyq
 138       |
 139       |         ktlj
 140        \      /
 141          fwft - cntj
 142               \
 143                 xhth
 144 </code></pre>
 145 <p>In this example, <code>tknk</code> is at the bottom of the tower (the <em>bottom program</em>), and is holding up <code>ugml</code>, <code>padx</code>, and <code>fwft</code>.  Those programs are, in turn, holding up other programs; in this example, none of those programs are holding up any other programs, and are all the tops of their own towers. (The actual tower balancing in front of you is much larger.)</p>
 146 <p>Before you're ready to help them, you need to make sure your information is correct.  <em>What is the name of the bottom program?</em></p>
 147 </article>
 148 <p>Your puzzle answer was <code>vtzay</code>.</p><article class="day-desc"><h2>--- Part Two ---</h2><p>The programs explain the situation: they can't get down.  Rather, they <em>could</em> get down, if they weren't expending all of their energy trying to keep the tower balanced. Apparently, one program has the <em>wrong weight</em>, and until it's fixed, they're stuck here.</p>
 149 <p>For any program holding a disc, each program standing on that disc forms a sub-tower. Each of those sub-towers are supposed to be the same weight, or the disc itself isn't balanced. The weight of a tower is the sum of the weights of the programs in that tower.</p>
 150 <p>In the example above, this means that for <code>ugml</code>'s disc to be balanced, <code>gyxo</code>, <code>ebii</code>, and <code>jptl</code> must all have the same weight, and they do: <code>61</code>.</p>
 151 <p>However, for <code>tknk</code> to be balanced, each of the programs standing on its disc <em>and all programs above it</em> must each match. This means that the following sums must all be the same:</p>
 152 <ul>
 153 <li><code>ugml</code> + (<code>gyxo</code> + <code>ebii</code> + <code>jptl</code>) = 68 + (61 + 61 + 61) = 251</li>
 154 <li><code>padx</code> + (<code>pbga</code> + <code>havc</code> + <code>qoyq</code>) = 45 + (66 + 66 + 66) = 243</li>
 155 <li><code>fwft</code> + (<code>ktlj</code> + <code>cntj</code> + <code>xhth</code>) = 72 + (57 + 57 + 57) = 243</li>
 156 </ul>
 157 <p>As you can see, <code>tknk</code>'s disc is unbalanced: <code>ugml</code>'s stack is heavier than the other two. Even though the nodes above <code>ugml</code> are balanced, <code>ugml</code> itself is too heavy: it needs to be <code>8</code> units lighter for its stack to weigh <code>243</code> and keep the towers balanced.  If this change were made, its weight would be <code>60</code>.</p>
 158 <p>Given that exactly one program is the wrong weight, <em>what would its weight need to be</em> to balance the entire tower?</p>
 159 </article>
 160 <p>Your puzzle answer was <code>910</code>.</p><p class="day-success">Both parts of this puzzle are complete! They provide two gold stars: **</p>
 161 <p>At this point, you should <a href="/2017">return to your advent calendar</a> and try another puzzle.</p>
 162 <p>If you still want to see it, you can <a href="7/input" target="_blank">get your puzzle input</a>.</p>
 163 <p>You can also <span class="share">[Share<span class="share-content">on
 164   <a href="https://twitter.com/intent/tweet?text=I%27ve+completed+%22Recursive+Circus%22+%2D+Day+7+%2D+Advent+of+Code+2017&amp;url=http%3A%2F%2Fadventofcode%2Ecom%2F2017%2Fday%2F7&amp;related=ericwastl&amp;hashtags=AdventOfCode" target="_blank">Twitter</a>
 165   <a href="https://plus.google.com/share?url=http%3A%2F%2Fadventofcode%2Ecom%2F2017%2Fday%2F7" target="_blank">Google+</a>
 166   <a href="http://www.reddit.com/submit?url=http%3A%2F%2Fadventofcode%2Ecom%2F2017%2Fday%2F7&amp;title=I%27ve+completed+%22Recursive+Circus%22+%2D+Day+7+%2D+Advent+of+Code+2017" target="_blank">Reddit</a
 167 ></span>]</span> this puzzle.</p>
 168 </main>
 169
 170 <!-- ga -->
 171 <script>
 172 (function(i,s,o,g,r,a,m){i['GoogleAnalyticsObject']=r;i[r]=i[r]||function(){
 173 (i[r].q=i[r].q||[]).push(arguments)},i[r].l=1*new Date();a=s.createElement(o),
 174 m=s.getElementsByTagName(o)[0];a.async=1;a.src=g;m.parentNode.insertBefore(a,m)
 175 })(window,document,'script','//www.google-analytics.com/analytics.js','ga');
 176 ga('create', 'UA-69522494-1', 'auto');
 177 ga('send', 'pageview');
 178 </script>
 179 <!-- /ga -->
 180 </body>
 181 </html>