problems/day15.html

   1 <!DOCTYPE html>
   2 <html lang="en-us">
   3 <head>
   4 <meta charset="utf-8"/>
   5 <title>Day 15 - Advent of Code 2022</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?30"/>
   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="/2022/about">[About]</a></li><li><a href="/2022/events">[Events]</a></li><li><a href="https://teespring.com/stores/advent-of-code" target="_blank">[Shop]</a></li><li><a href="/2022/settings">[Settings]</a></li><li><a href="/2022/auth/logout">[Log Out]</a></li></ul></nav><div class="user">Neil Smith <a href="/2022/support" class="supporter-badge" title="Advent of Code Supporter">(AoC++)</a> <span class="star-count">30*</span></div></div><div><h1 class="title-event">&nbsp;&nbsp;&nbsp;<span class="title-event-wrap">int y=</span><a href="/2022">2022</a><span class="title-event-wrap">;</span></h1><nav><ul><li><a href="/2022">[Calendar]</a></li><li><a href="/2022/support">[AoC++]</a></li><li><a href="/2022/sponsors">[Sponsors]</a></li><li><a href="/2022/leaderboard">[Leaderboard]</a></li><li><a href="/2022/stats">[Stats]</a></li></ul></nav></div></header>
  92
  93 <div id="sidebar">
  94 <div id="sponsor"><div class="quiet">Our <a href="/2022/sponsors">sponsors</a> help make Advent of Code possible:</div><div class="sponsor"><a href="https://kotlinlang.org/" target="_blank" onclick="if(ga)ga('send','event','sponsor','sidebar',this.href);" rel="noopener">Kotlin by JetBrains</a> - Trees, lists, packages - it&apos;s Advent of Code time! Get ready to solve puzzles in Kotlin. Watch us livestream our discussions about the solutions for the first few puzzles, join our leaderboard, win prizes. Happy holidays!</div></div>
  95 </div><!--/sidebar-->
  96
  97 <main>
  98 <article class="day-desc"><h2>--- Day 15: Beacon Exclusion Zone ---</h2><p>You feel the ground rumble again as the distress signal leads you to a large network of subterranean tunnels. You don't have time to search them all, but you don't need to: your pack contains a set of deployable <em>sensors</em> that you imagine were originally built to locate lost Elves.</p>
  99 <p>The sensors aren't very powerful, but that's okay; your handheld device indicates that you're close enough to the source of the distress signal to use them. You pull the emergency sensor system out of your pack, hit the big button on top, and the sensors zoom off down the tunnels.</p>
 100 <p>Once a sensor finds a spot it thinks will give it a good reading, it attaches itself to a hard surface and begins monitoring for the nearest signal source <em>beacon</em>. Sensors and beacons always exist at integer coordinates. Each sensor knows its own position and can <em>determine the position of a beacon precisely</em>; however, sensors can only lock on to the one beacon <em>closest to the sensor</em> as measured by the <a href="https://en.wikipedia.org/wiki/Taxicab_geometry" target="_blank">Manhattan distance</a>. (There is never a tie where two beacons are the same distance to a sensor.)</p>
 101 <p>It doesn't take long for the sensors to report back their positions and closest beacons (your puzzle input). For example:</p>
 102 <pre><code>Sensor at x=2, y=18: closest beacon is at x=-2, y=15
 103 Sensor at x=9, y=16: closest beacon is at x=10, y=16
 104 Sensor at x=13, y=2: closest beacon is at x=15, y=3
 105 Sensor at x=12, y=14: closest beacon is at x=10, y=16
 106 Sensor at x=10, y=20: closest beacon is at x=10, y=16
 107 Sensor at x=14, y=17: closest beacon is at x=10, y=16
 108 Sensor at x=8, y=7: closest beacon is at x=2, y=10
 109 Sensor at x=2, y=0: closest beacon is at x=2, y=10
 110 Sensor at x=0, y=11: closest beacon is at x=2, y=10
 111 Sensor at x=20, y=14: closest beacon is at x=25, y=17
 112 Sensor at x=17, y=20: closest beacon is at x=21, y=22
 113 Sensor at x=16, y=7: closest beacon is at x=15, y=3
 114 Sensor at x=14, y=3: closest beacon is at x=15, y=3
 115 Sensor at x=20, y=1: closest beacon is at x=15, y=3
 116 </code></pre>
 117 <p>So, consider the sensor at <code>2,18</code>; the closest beacon to it is at <code>-2,15</code>. For the sensor at <code>9,16</code>, the closest beacon to it is at <code>10,16</code>.</p>
 118 <p>Drawing sensors as <code>S</code> and beacons as <code>B</code>, the above arrangement of sensors and beacons looks like this:</p>
 119 <pre><code>               1    1    2    2
 120      0    5    0    5    0    5
 121  0 ....S.......................
 122  1 ......................S.....
 123  2 ...............S............
 124  3 ................SB..........
 125  4 ............................
 126  5 ............................
 127  6 ............................
 128  7 ..........S.......S.........
 129  8 ............................
 130  9 ............................
 131 10 ....B.......................
 132 11 ..S.........................
 133 12 ............................
 134 13 ............................
 135 14 ..............S.......S.....
 136 15 B...........................
 137 16 ...........SB...............
 138 17 ................S..........B
 139 18 ....S.......................
 140 19 ............................
 141 20 ............S......S........
 142 21 ............................
 143 22 .......................B....
 144 </code></pre>
 145 <p>This isn't necessarily a comprehensive map of all beacons in the area, though. Because each sensor only identifies its closest beacon, if a sensor detects a beacon, you know there are no other beacons that close or closer to that sensor. There could still be beacons that just happen to not be the closest beacon to any sensor. Consider the sensor at <code>8,7</code>:</p>
 146 <pre><code>               1    1    2    2
 147      0    5    0    5    0    5
 148 -2 ..........#.................
 149 -1 .........###................
 150  0 ....S...#####...............
 151  1 .......#######........S.....
 152  2 ......#########S............
 153  3 .....###########SB..........
 154  4 ....#############...........
 155  5 ...###############..........
 156  6 ..#################.........
 157  7 .#########<em>S</em>#######S#........
 158  8 ..#################.........
 159  9 ...###############..........
 160 10 ....<em>B</em>############...........
 161 11 ..S..###########............
 162 12 ......#########.............
 163 13 .......#######..............
 164 14 ........#####.S.......S.....
 165 15 B........###................
 166 16 ..........#SB...............
 167 17 ................S..........B
 168 18 ....S.......................
 169 19 ............................
 170 20 ............S......S........
 171 21 ............................
 172 22 .......................B....
 173 </code></pre>
 174 <p>This sensor's closest beacon is at <code>2,10</code>, and so you know there are no beacons that close or closer (in any positions marked <code>#</code>).</p>
 175 <p>None of the detected beacons seem to be producing the distress signal, so you'll need to <span title="&quot;When you have eliminated all which is impossible, then whatever remains, however improbable, must be where the missing beacon is.&quot; - Sherlock Holmes">work out</span> where the distress beacon is by working out where it <em>isn't</em>. For now, keep things simple by counting the positions where a beacon cannot possibly be along just a single row.</p>
 176 <p>So, suppose you have an arrangement of beacons and sensors like in the example above and, just in the row where <code>y=10</code>, you'd like to count the number of positions a beacon cannot possibly exist. The coverage from all sensors near that row looks like this:</p>
 177 <pre><code>                 1    1    2    2
 178        0    5    0    5    0    5
 179  9 ...#########################...
 180 <em>10 ..####B######################..</em>
 181 11 .###S#############.###########.
 182 </code></pre>
 183 <p>In this example, in the row where <code>y=10</code>, there are <code><em>26</em></code> positions where a beacon cannot be present.</p>
 184 <p>Consult the report from the sensors you just deployed. <em>In the row where <code>y=2000000</code>, how many positions cannot contain a beacon?</em></p>
 185 </article>
 186 <p>Your puzzle answer was <code>5147333</code>.</p><article class="day-desc"><h2 id="part2">--- Part Two ---</h2><p>Your handheld device indicates that the distress signal is coming from a beacon nearby. The distress beacon is not detected by any sensor, but the distress beacon must have <code>x</code> and <code>y</code> coordinates each no lower than <code>0</code> and no larger than <code>4000000</code>.</p>
 187 <p>To isolate the distress beacon's signal, you need to determine its <em>tuning frequency</em>, which can be found by multiplying its <code>x</code> coordinate by <code>4000000</code> and then adding its <code>y</code> coordinate.</p>
 188 <p>In the example above, the search space is smaller: instead, the <code>x</code> and <code>y</code> coordinates can each be at most <code>20</code>. With this reduced search area, there is only a single position that could have a beacon: <code>x=14, y=11</code>. The tuning frequency for this distress beacon is <code><em>56000011</em></code>.</p>
 189 <p>Find the only possible position for the distress beacon. <em>What is its tuning frequency?</em></p>
 190 </article>
 191 <p>Your puzzle answer was <code>13734006908372</code>.</p><p class="day-success">Both parts of this puzzle are complete! They provide two gold stars: **</p>
 192 <p>At this point, you should <a href="/2022">return to your Advent calendar</a> and try another puzzle.</p>
 193 <p>If you still want to see it, you can <a href="15/input" target="_blank">get your puzzle input</a>.</p>
 194 <p>You can also <span class="share">[Share<span class="share-content">on
 195   <a href="https://twitter.com/intent/tweet?text=I%27ve+completed+%22Beacon+Exclusion+Zone%22+%2D+Day+15+%2D+Advent+of+Code+2022&amp;url=https%3A%2F%2Fadventofcode%2Ecom%2F2022%2Fday%2F15&amp;related=ericwastl&amp;hashtags=AdventOfCode" target="_blank">Twitter</a>
 196   <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+%22Beacon+Exclusion+Zone%22+%2D+Day+15+%2D+Advent+of+Code+2022+%23AdventOfCode+https%3A%2F%2Fadventofcode%2Ecom%2F2022%2Fday%2F15'}else{return false;}" target="_blank">Mastodon</a
 197 ></span>]</span> this puzzle.</p>
 198 </main>
 199
 200 <!-- ga -->
 201 <script>
 202 (function(i,s,o,g,r,a,m){i['GoogleAnalyticsObject']=r;i[r]=i[r]||function(){
 203 (i[r].q=i[r].q||[]).push(arguments)},i[r].l=1*new Date();a=s.createElement(o),
 204 m=s.getElementsByTagName(o)[0];a.async=1;a.src=g;m.parentNode.insertBefore(a,m)
 205 })(window,document,'script','//www.google-analytics.com/analytics.js','ga');
 206 ga('create', 'UA-69522494-1', 'auto');
 207 ga('set', 'anonymizeIp', true);
 208 ga('send', 'pageview');
 209 </script>
 210 <!-- /ga -->
 211 </body>
 212 </html>