commit 703e896dca75fbefc681f099c68449f0590c8681
parent bba64a36e16913403868854c5467498dc816ae49
Author: Shimmy Xu <shimmy.xu@shimmy1996.com>
Date: Tue, 10 Dec 2019 13:12:47 -0500
Add Julia solution for day 10
Diffstat:
| A | day-10/day-10.jl | | | 95 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
1 file changed, 95 insertions(+), 0 deletions(-)
diff --git a/day-10/day-10.jl b/day-10/day-10.jl
@@ -0,0 +1,95 @@
+function line_of_sight(x_diff, y_diff)
+ if x_diff == 0 || y_diff == 0
+ (sign(x_diff), sign(y_diff))
+ else
+ factor = gcd(x_diff, y_diff)
+ (x_diff ÷ factor, y_diff ÷ factor)
+ end
+end
+
+function coord_to_angle(coord)
+ angle = atan(coord[2], coord[1]) + 0.5π
+ if angle < 0
+ angle += 2π
+ end
+ angle
+end
+
+function part_1(input)
+ detected = Dict();
+ for x in 1:length(input)
+ for y in 1:length(input)
+ if input[y][x]
+ # If there's an asteroid, compute line of sight with all others.
+ view_curr = Set();
+ for (coord, view) in detected
+ push!(view,line_of_sight(
+ x - coord[1],
+ y - coord[2]
+ ))
+ push!(view_curr, line_of_sight(
+ coord[1] - x,
+ coord[2] - y,
+ ))
+ end
+ detected[(x, y)] = view_curr
+ end
+ end
+ end
+ maximum(p -> (length(p[2]), p[1]), detected)
+end
+
+function part_2(input, station)
+ # Record detected asteroids sorted by line of sight angle.
+ detected = Dict();
+ for x in 1:length(input)
+ for y in 1:length(input)
+ if input[y][x] && ((x, y) != station)
+ x_diff = x - station[1]
+ y_diff = y - station[2]
+ push!(get!(detected, line_of_sight(x_diff, y_diff), []),
+ (x_diff, y_diff))
+ end
+ end
+ end
+ # Sort line of sight by angle, which starts CW from north.
+ los_sorted = collect(keys(detected))
+ sort!(los_sorted; by = coord_to_angle)
+ los_count = Dict(map(p -> (p[1], length(p[2])), zip(keys(detected), values(detected))))
+ # Vaporize by going around sorted los until we hit 200th.
+ num_vaporized = 0
+ last_los = (0, 0)
+ while true
+ for key in los_sorted
+ if los_count[key] > 0
+ los_count[key] -= 1
+ num_vaporized += 1
+ last_los = key
+ if num_vaporized == 200
+ break
+ end
+ end
+ end
+ if num_vaporized == 200
+ break
+ end
+ end
+ # Sort asteroids in that los and count back.
+ asteroids_in_los = copy(detected[last_los])
+ sort!(asteroids_in_los, by=coord -> coord[1]^2 + coord[2]^2)
+ reverse!(asteroids_in_los)
+ jackpot = asteroids_in_los[los_count[last_los] + 1];
+ jackpot = [jackpot[1] + station[1] - 1, jackpot[2] + station[2] - 1]
+ # Convert relative coordinates to absolute one.
+ jackpot[1] * 100 + jackpot[2]
+end
+
+input = map(readlines(open("input.txt"))) do line
+ map(ch -> ch == '#', collect(line))
+end
+
+println("Julia:")
+println("Part 1: ")
+num_obs, station = part_1(input)
+println(num_obs, " asteroids observed at ", (station[1] - 1, station[2] - 1));
+println("Part 2: ", part_2(input, station))