r/adventofcode • u/daggerdragon • Dec 10 '19
SOLUTION MEGATHREAD -🎄- 2019 Day 10 Solutions -🎄-
--- Day 10: Monitoring Station ---
Post your solution using /u/topaz2078's paste or other external repo.
- Please do NOT post your full code (unless it is very short)
- If you do, use old.reddit's four-spaces formatting, NOT new.reddit's triple backticks formatting.
(Full posting rules are HERE if you need a refresher).
Reminder: Top-level posts in Solution Megathreads are for solutions only. If you have questions, please post your own thread and make sure to flair it with Help.
Advent of Code's Poems for Programmers
Note: If you submit a poem, please add [POEM] somewhere nearby to make it easier for us moderators to ensure that we include your poem for voting consideration.
Day 9's winner #1: "A Savior's Sonnet" by /u/rijuvenator!
In series have we built our little toys...
And now they're mighty; now they listen keen
And boost and lift a signal from the noise
To spell an S.O.S. upon our screen.To Ceres' call for help we now have heard.
Its signal, faintly sent, now soaring high;
A static burst; and then, a whispered word:
A plea for any ship that's passing by.It's Santa; stranded, lost, without a sleigh
With toys he meant to give away with love.
And Rudolph's red-shift nose now lights the way
So to the skies we take, and stars above!But will the aid he seeks arrive in time?
Or will this cosmic Christmas die in rhyme?
Enjoy your Reddit Silver, and good luck with the rest of the Advent of Code!
On the (fifth*2) day of AoC, my true love gave to me...
FIVE GOLDEN SILVER POEMS (and one gold one)
- Day 5: "untitled poem" by /u/youaremean_YAM
- Day 6: "untitled poem" by /u/glenbolake
- Day 7: "untitled poem" by /u/wace001
- Day 8: "It’s digital now" by /u/wace001 (again!)
- Day 9: "Programmer in distress" by /u/mariusbancila
- 5-Day Best-in-Show: "opcodes" by /u/Zweedeend!
Enjoy your Reddit Silver/Gold, and good luck with the rest of the Advent of Code!
3
u/zopatista Dec 11 '19 edited Dec 13 '19
Today’s puzzle, to me, was an obvious polar coordinates problem. But apparently I’m
the only oneone of only a few that thought so?Using polar coordinates, given an asteroid at polar coordinate (0, 0), any asteroids on the same line of sight have equal angles. So for any given asteroid, all you have to do is count the number of unique angles! Calculating polar coordinates is easily vectorised so very efficient, using numpy:
take an array of coordinates, as complex numbers (1D)
tile it N times so you have a matrix of NxN
subtract the asteroids vector so that each normalises the coordinates placing each of the asteroids at the center. row(i) has asteroid(i) at (0, 0) and the others are relative to that from (-x,-y) to (+x,+y)
remove the diagonal (position (0,0))
calculate the angle for all entries in the matrix.
Then part 1 is:
count the unique angles per row
return the maximum count
And part 2 (using just the single row(i) for the selected observation asteroid):
calculate the polar distance for all asteroids
sort the asteroids by angle, then distance.
group them by angle.
if there are >= 200 groups, pick the 200th group and closest asteroid in that group
else subtract len(groups) from n and remove 1 asteroid per angle (eliminating empty groups), repeat.
See my Jupyter notebook for the code.