From 87ab487d59fa85dbe2afa55cc841b02805ae42ca Mon Sep 17 00:00:00 2001 From: Louis Burda Date: Fri, 7 Apr 2023 17:18:18 -0400 Subject: Reorder days into src --- src/06/input | 50 +++++++++++++++++++++++++++++++++++++ src/06/part1 | 65 ++++++++++++++++++++++++++++++++++++++++++++++++ src/06/part2 | 61 +++++++++++++++++++++++++++++++++++++++++++++ src/06/solve.py | 76 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 4 files changed, 252 insertions(+) create mode 100644 src/06/input create mode 100644 src/06/part1 create mode 100644 src/06/part2 create mode 100644 src/06/solve.py (limited to 'src/06') diff --git a/src/06/input b/src/06/input new file mode 100644 index 0000000..233e279 --- /dev/null +++ b/src/06/input @@ -0,0 +1,50 @@ +69, 102 +118, 274 +150, 269 +331, 284 +128, 302 +307, 192 +238, 52 +240, 339 +111, 127 +180, 156 +248, 265 +160, 69 +58, 136 +43, 235 +154, 202 +262, 189 +309, 53 +292, 67 +335, 198 +99, 199 +224, 120 +206, 313 +359, 352 +101, 147 +301, 47 +255, 347 +121, 153 +264, 343 +252, 225 +48, 90 +312, 139 +90, 277 +203, 227 +315, 328 +330, 81 +190, 191 +89, 296 +312, 255 +218, 181 +299, 149 +151, 254 +209, 212 +42, 76 +348, 183 +333, 227 +44, 210 +293, 356 +44, 132 +175, 77 +215, 109 \ No newline at end of file diff --git a/src/06/part1 b/src/06/part1 new file mode 100644 index 0000000..e34879f --- /dev/null +++ b/src/06/part1 @@ -0,0 +1,65 @@ +--- Day 6: Chronal Coordinates --- + +The device on your wrist beeps several times, and once again you feel like you're falling. + +"Situation critical," the device announces. "Destination indeterminate. Chronal interference +detected. Please specify new target coordinates." + +The device then produces a list of coordinates (your puzzle input). Are they places it thinks are +safe or dangerous? It recommends you check manual page 729. The Elves did not give you a manual. + +If they're dangerous, maybe you can minimize the danger by finding the coordinate that gives the +largest distance from the other points. + +Using only the Manhattan distance, determine the area around each coordinate by counting the number +of integer X,Y locations that are closest to that coordinate (and aren't tied in distance to any +other coordinate). + +Your goal is to find the size of the largest area that isn't infinite. For example, consider the +following list of coordinates: + +1, 1 +1, 6 +8, 3 +3, 4 +5, 5 +8, 9 + +If we name these coordinates A through F, we can draw them on a grid, putting 0,0 at the top left: + +.......... +.A........ +.......... +........C. +...D...... +.....E.... +.B........ +.......... +.......... +........F. + +This view is partial - the actual grid extends infinitely in all directions. Using the Manhattan +distance, each location's closest coordinate can be determined, shown here in lowercase: + +aaaaa.cccc +aAaaa.cccc +aaaddecccc +aadddeccCc +..dDdeeccc +bb.deEeecc +bBb.eeee.. +bbb.eeefff +bbb.eeffff +bbb.ffffFf + +Locations shown as . are equally far from two or more coordinates, and so they don't count as being +closest to any. + +In this example, the areas of coordinates A, B, C, and F are infinite - while not shown here, their +areas extend forever outside the visible grid. However, the areas of coordinates D and E are finite: +D is closest to 9 locations, and E is closest to 17 (both including the coordinate's location +itself). Therefore, in this example, the size of the largest area is 17. + +What is the size of the largest area that isn't infinite? + + diff --git a/src/06/part2 b/src/06/part2 new file mode 100644 index 0000000..1088955 --- /dev/null +++ b/src/06/part2 @@ -0,0 +1,61 @@ +--- Part Two --- + +Now, you just need to figure out how many orbital transfers you (YOU) need to take to get to Santa +(SAN). + +You start at the object YOU are orbiting; your destination is the object SAN is orbiting. An orbital +transfer lets you move from any object to an object orbiting or orbited by that object. + +For example, suppose you have the following map: + +COM)B +B)C +C)D +D)E +E)F +B)G +G)H +D)I +E)J +J)K +K)L +K)YOU +I)SAN + +Visually, the above map of orbits looks like this: + + YOU + / + G - H J - K - L + / / +COM - B - C - D - E - F + \ + I - SAN + +In this example, YOU are in orbit around K, and SAN is in orbit around I. To move from K to I, a +minimum of 4 orbital transfers are required: + + + - K to J + + - J to E + + - E to D + + - D to I + + +Afterward, the map of orbits looks like this: + + G - H J - K - L + / / +COM - B - C - D - E - F + \ + I - SAN + \ + YOU + +What is the minimum number of orbital transfers required to move from the object YOU are orbiting to +the object SAN is orbiting? (Between the objects they are orbiting - not between YOU and SAN.) + + diff --git a/src/06/solve.py b/src/06/solve.py new file mode 100644 index 0000000..f0627fe --- /dev/null +++ b/src/06/solve.py @@ -0,0 +1,76 @@ +import sys +sys.path.append("../common") +import aoc + +data = [[int(v) for v in l.split(",")] for l in aoc.data.split("\n")] + +minx = min(data, key = lambda x: x[0])[0] +maxx = max(data, key = lambda x: x[0])[0] +miny = min(data, key = lambda x: x[1])[1] +maxy = max(data, key = lambda x: x[1])[1] + +def closest(x, y): + mc = None + md = None + ad = None + for i in range(len(data)): + c = data[i] + dist = abs(c[0] - x) + abs(c[1] - y) + if md == None or dist < md: + md = dist + mc = i + ad = None + elif dist == md: + ad = dist + return mc, ad + +def combined_dist(x, y): + dist = 0 + for i in range(len(data)): + c = data[i] + dist += abs(c[0] - x) + abs(c[1] - y) + return dist + +def solve1(args): + areas = dict() + for x in range(minx, maxx): + for y in range(miny, maxy): + mc, ad = closest(x, y) + if ad == None: + if mc not in areas: + areas[mc] = 1 + else: + areas[mc] += 1 + + # remove outside points + for i in range(len(data)): + c = data[i] + mc, ac = closest(minx, c[1]) + if mc == i: + areas.pop(i) + continue + mc, ac = closest(maxx, c[1]) + if mc == i: + areas.pop(i) + continue + mc, ac = closest(c[0], miny) + if mc == i: + areas.pop(i) + continue + mc, ac = closest(c[0], maxy) + if mc == i: + areas.pop(i) + continue + + return max(areas.values()) + +def solve2(args): + safezone = 0 + for x in range(minx, maxx): + for y in range(miny, maxy): + dist = combined_dist(x,y) + if dist < 10000: + safezone += 1 + return safezone + +aoc.run(solve1, solve2, sols=[3276, 38380]) -- cgit v1.2.3-71-gd317