01020304050607080910111213141516171819202122232425

Advent of Code

2019/10

Monitoring Station

in C#

by encse

You fly into the asteroid belt and reach the Ceres monitoring station. The Elves here have an emergency: they're having trouble tracking all of the asteroids and can't be sure they're safe.

The Elves would like to build a new monitoring station in a nearby area of space; they hand you a map of all of the asteroids in that region (your puzzle input).

Read the full puzzle.

using System;
using System.Collections.Generic;
using System.Linq;
using AsteroidsByDir = System.Collections.Generic.Dictionary<
(int drow, int dcol), System.Collections.Generic.List<(int irow, int icol)>
>;

namespace AdventOfCode.Y2019.Day10;

[ProblemName("Monitoring Station")]
class Solution : Solver {

    public object PartOne(string input) => SelectStationPosition(input).asteroidsByDir.Count;

    public object PartTwo(string input) {
        var asteroid = Destroy(input).ElementAt(199);
        return (asteroid.icol * 100 + asteroid.irow);
    }

    IEnumerable<(int irow, int icol)> Destroy(string input) {
        var (station, asteroidsByDir) = SelectStationPosition(input);

        foreach (var dir in asteroidsByDir.Keys.ToArray()) {
            asteroidsByDir[dir] = asteroidsByDir[dir]
                .OrderBy(a => Math.Abs(a.irow - station.irow) + Math.Abs(a.icol - station.icol))
                .ToList();
        }

        foreach (var dir in Rotate(asteroidsByDir.Keys)) {
            if (asteroidsByDir.ContainsKey(dir)) {
                var asteroid = asteroidsByDir[dir].First();
                asteroidsByDir[dir].RemoveAt(0);

                yield return asteroid;

                if (!asteroidsByDir[dir].Any()) {
                    asteroidsByDir.Remove(dir);
                }
            }
        }
    }

    IEnumerable<(int drow, int dcol)> Rotate(IEnumerable<(int drow, int dcol)> dirs) {
        var ordered = dirs.OrderBy(dir => -Math.Atan2(dir.dcol, dir.drow)).ToList();
        for (var i = 0; ; i++) {
            yield return ordered[i % ordered.Count];
        }
    }

    ((int irow, int icol) station, AsteroidsByDir asteroidsByDir) SelectStationPosition(string input) {

        var res = ((0, 0), asteroidsByDir: new AsteroidsByDir());
        var asteroids = Asteroids(input);

        foreach (var station in asteroids) {
            var asteroidsByDir = new AsteroidsByDir();
            foreach (var asteroid in asteroids) {
                if (station != asteroid) {
                    var (rowDir, colDir) = (asteroid.irow - station.irow, asteroid.icol - station.icol);
                    var gcd = Math.Abs(Gcd(rowDir, colDir));
                    var dir = (rowDir / gcd, colDir / gcd);

                    if (!asteroidsByDir.ContainsKey(dir)) {
                        asteroidsByDir[dir] = new List<(int irow, int icol)>();
                    }
                    asteroidsByDir[dir].Add(asteroid);
                }
            }
            if (asteroidsByDir.Count > res.asteroidsByDir.Count) {
                res = (station, asteroidsByDir);
            }
        }

        return res;
    }

    List<(int irow, int icol)> Asteroids(string input) {
        var map = input.Split("\n");
        var (crow, ccol) = (map.Length, map[0].Length);

        return (
            from irow in Enumerable.Range(0, crow)
            from icol in Enumerable.Range(0, ccol)
            where map[irow][icol] == '#'
            select (irow, icol)
        ).ToList();
    }

   int Gcd(int a, int b) => b == 0 ? a : Gcd(b, a % b);
}

Please ☆ my repo if you like it!

© 2025 Advent of Code is a registered trademark in the US Images provided by Bing image creator