problems/day17.html

   1 <!DOCTYPE html>
   2 <html lang="en-us">
   3 <head>
   4 <meta charset="utf-8"/>
   5 <title>Day 17 - 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">34*</span></div></div><div><h1 class="title-event">&nbsp;&nbsp;&nbsp;<span class="title-event-wrap">0xffff&amp;</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.americanexpress.com/techcareers" target="_blank" onclick="if(ga)ga('send','event','sponsor','sidebar',this.href);" rel="noopener">American Express</a> - Work with the latest tech and back the engineering community through open source. Find your place in tech on #TeamAmex.</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 17: Trick Shot ---</h2><p>You finally decode the Elves' message. <code><span title="Maybe you need to turn the message 90 degrees counterclockwise?">HI</span></code>, the message says. You continue searching for the sleigh keys.</p>
  99 <p>Ahead of you is what appears to be a large <a href="https://en.wikipedia.org/wiki/Oceanic_trench" target="_blank">ocean trench</a>. Could the keys have fallen into it? You'd better send a probe to investigate.</p>
 100 <p>The probe launcher on your submarine can fire the probe with any <a href="https://en.wikipedia.org/wiki/Integer" target="_blank">integer</a> velocity in the <code>x</code> (forward) and <code>y</code> (upward, or downward if negative) directions. For example, an initial <code>x,y</code> velocity like <code>0,10</code> would fire the probe straight up, while an initial velocity like <code>10,-1</code> would fire the probe forward at a slight downward angle.</p>
 101 <p>The probe's <code>x,y</code> position starts at <code>0,0</code>. Then, it will follow some trajectory by moving in <em>steps</em>. On each step, these changes occur in the following order:</p>
 102 <ul>
 103 <li>The probe's <code>x</code> position increases by its <code>x</code> velocity.</li>
 104 <li>The probe's <code>y</code> position increases by its <code>y</code> velocity.</li>
 105 <li>Due to drag, the probe's <code>x</code> velocity changes by <code>1</code> toward the value <code>0</code>; that is, it decreases by <code>1</code> if it is greater than <code>0</code>, increases by <code>1</code> if it is less than <code>0</code>, or does not change if it is already <code>0</code>.</li>
 106 <li>Due to gravity, the probe's <code>y</code> velocity decreases by <code>1</code>.</li>
 107 </ul>
 108 <p>For the probe to successfully make it into the trench, the probe must be on some trajectory that causes it to be within a <em>target area</em> after any step. The submarine computer has already calculated this target area (your puzzle input). For example:</p>
 109 <pre><code>target area: x=20..30, y=-10..-5</code></pre>
 110 <p>This target area means that you need to find initial <code>x,y</code> velocity values such that after any step, the probe's <code>x</code> position is at least <code>20</code> and at most <code>30</code>, <em>and</em> the probe's <code>y</code> position is at least <code>-10</code> and at most <code>-5</code>.</p>
 111 <p>Given this target area, one initial velocity that causes the probe to be within the target area after any step is <code>7,2</code>:</p>
 112 <pre><code>.............#....#............
 113 .......#..............#........
 114 ...............................
 115 S........................#.....
 116 ...............................
 117 ...............................
 118 ...........................#...
 119 ...............................
 120 ....................TTTTTTTTTTT
 121 ....................TTTTTTTTTTT
 122 ....................TTTTTTTT#TT
 123 ....................TTTTTTTTTTT
 124 ....................TTTTTTTTTTT
 125 ....................TTTTTTTTTTT
 126 </code></pre>
 127 <p>In this diagram, <code>S</code> is the probe's initial position, <code>0,0</code>. The <code>x</code> coordinate increases to the right, and the <code>y</code> coordinate increases upward. In the bottom right, positions that are within the target area are shown as <code>T</code>. After each step (until the target area is reached), the position of the probe is marked with <code>#</code>. (The bottom-right <code>#</code> is both a position the probe reaches and a position in the target area.)</p>
 128 <p>Another initial velocity that causes the probe to be within the target area after any step is <code>6,3</code>:</p>
 129 <pre><code>...............#..#............
 130 ...........#........#..........
 131 ...............................
 132 ......#..............#.........
 133 ...............................
 134 ...............................
 135 S....................#.........
 136 ...............................
 137 ...............................
 138 ...............................
 139 .....................#.........
 140 ....................TTTTTTTTTTT
 141 ....................TTTTTTTTTTT
 142 ....................TTTTTTTTTTT
 143 ....................TTTTTTTTTTT
 144 ....................T#TTTTTTTTT
 145 ....................TTTTTTTTTTT
 146 </code></pre>
 147 <p>Another one is <code>9,0</code>:</p>
 148 <pre><code>S........#.....................
 149 .................#.............
 150 ...............................
 151 ........................#......
 152 ...............................
 153 ....................TTTTTTTTTTT
 154 ....................TTTTTTTTTT#
 155 ....................TTTTTTTTTTT
 156 ....................TTTTTTTTTTT
 157 ....................TTTTTTTTTTT
 158 ....................TTTTTTTTTTT
 159 </code></pre>
 160 <p>One initial velocity that <em>doesn't</em> cause the probe to be within the target area after any step is <code>17,-4</code>:</p>
 161 <pre><code>S..............................................................
 162 ...............................................................
 163 ...............................................................
 164 ...............................................................
 165 .................#.............................................
 166 ....................TTTTTTTTTTT................................
 167 ....................TTTTTTTTTTT................................
 168 ....................TTTTTTTTTTT................................
 169 ....................TTTTTTTTTTT................................
 170 ....................TTTTTTTTTTT..#.............................
 171 ....................TTTTTTTTTTT................................
 172 ...............................................................
 173 ...............................................................
 174 ...............................................................
 175 ...............................................................
 176 ................................................#..............
 177 ...............................................................
 178 ...............................................................
 179 ...............................................................
 180 ...............................................................
 181 ...............................................................
 182 ...............................................................
 183 ..............................................................#
 184 </code></pre>
 185 <p>The probe appears to pass through the target area, but is never within it after any step. Instead, it continues down and to the right - only the first few steps are shown.</p>
 186 <p>If you're going to fire a highly scientific probe out of a super cool probe launcher, you might as well do it with <em>style</em>. How high can you make the probe go while still reaching the target area?</p>
 187 <p>In the above example, using an initial velocity of <code>6,9</code> is the best you can do, causing the probe to reach a maximum <code>y</code> position of <code><em>45</em></code>. (Any higher initial <code>y</code> velocity causes the probe to overshoot the target area entirely.)</p>
 188 <p>Find the initial velocity that causes the probe to reach the highest <code>y</code> position and still eventually be within the target area after any step. <em>What is the highest <code>y</code> position it reaches on this trajectory?</em></p>
 189 </article>
 190 <p>Your puzzle answer was <code>5995</code>.</p><article class="day-desc"><h2 id="part2">--- Part Two ---</h2><p>Maybe a fancy trick shot isn't the best idea; after all, you only have one probe, so you had better not miss.</p>
 191 <p>To get the best idea of what your options are for launching the probe, you need to find <em>every initial velocity</em> that causes the probe to eventually be within the target area after any step.</p>
 192 <p>In the above example, there are <code><em>112</em></code> different initial velocity values that meet these criteria:</p>
 193 <pre><code>23,-10  25,-9   27,-5   29,-6   22,-6   21,-7   9,0     27,-7   24,-5
 194 25,-7   26,-6   25,-5   6,8     11,-2   20,-5   29,-10  6,3     28,-7
 195 8,0     30,-6   29,-8   20,-10  6,7     6,4     6,1     14,-4   21,-6
 196 26,-10  7,-1    7,7     8,-1    21,-9   6,2     20,-7   30,-10  14,-3
 197 20,-8   13,-2   7,3     28,-8   29,-9   15,-3   22,-5   26,-8   25,-8
 198 25,-6   15,-4   9,-2    15,-2   12,-2   28,-9   12,-3   24,-6   23,-7
 199 25,-10  7,8     11,-3   26,-7   7,1     23,-9   6,0     22,-10  27,-6
 200 8,1     22,-8   13,-4   7,6     28,-6   11,-4   12,-4   26,-9   7,4
 201 24,-10  23,-8   30,-8   7,0     9,-1    10,-1   26,-5   22,-9   6,5
 202 7,5     23,-6   28,-10  10,-2   11,-1   20,-9   14,-2   29,-7   13,-3
 203 23,-5   24,-8   27,-9   30,-7   28,-5   21,-10  7,9     6,6     21,-5
 204 27,-10  7,2     30,-9   21,-8   22,-7   24,-9   20,-6   6,9     29,-5
 205 8,-2    27,-8   30,-5   24,-7
 206 </code></pre>
 207 <p><em>How many distinct initial velocity values cause the probe to be within the target area after any step?</em></p>
 208 </article>
 209 <p>Your puzzle answer was <code>3202</code>.</p><p class="day-success">Both parts of this puzzle are complete! They provide two gold stars: **</p>
 210 <p>At this point, you should <a href="/2021">return to your Advent calendar</a> and try another puzzle.</p>
 211 <p>If you still want to see it, you can <a href="17/input" target="_blank">get your puzzle input</a>.</p>
 212 <p>You can also <span class="share">[Share<span class="share-content">on
 213   <a href="https://twitter.com/intent/tweet?text=I%27ve+completed+%22Trick+Shot%22+%2D+Day+17+%2D+Advent+of+Code+2021&amp;url=https%3A%2F%2Fadventofcode%2Ecom%2F2021%2Fday%2F17&amp;related=ericwastl&amp;hashtags=AdventOfCode" target="_blank">Twitter</a>
 214   <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+%22Trick+Shot%22+%2D+Day+17+%2D+Advent+of+Code+2021+%23AdventOfCode+https%3A%2F%2Fadventofcode%2Ecom%2F2021%2Fday%2F17'}else{return false;}" target="_blank">Mastodon</a
 215 ></span>]</span> this puzzle.</p>
 216 </main>
 217
 218 <!-- ga -->
 219 <script>
 220 (function(i,s,o,g,r,a,m){i['GoogleAnalyticsObject']=r;i[r]=i[r]||function(){
 221 (i[r].q=i[r].q||[]).push(arguments)},i[r].l=1*new Date();a=s.createElement(o),
 222 m=s.getElementsByTagName(o)[0];a.async=1;a.src=g;m.parentNode.insertBefore(a,m)
 223 })(window,document,'script','//www.google-analytics.com/analytics.js','ga');
 224 ga('create', 'UA-69522494-1', 'auto');
 225 ga('set', 'anonymizeIp', true);
 226 ga('send', 'pageview');
 227 </script>
 228 <!-- /ga -->
 229 </body>
 230 </html>