Day 10: Monitoring Station

We're going to store the asteroids in a grid, where, luckily, array notation and the positions are (almost) identical.

Instead of doing anything smart, just try out every possible asteroid position and see how many asteroids one can scan from that particular asteroid.

This is achieved by doing subtraction of coordinates for relative position, then getting a direction vector by dividing out the GCD of the (absolute value of the) two coordinates. This guarantees that all lines that are going in the same direction have exactly the same direction vector, so we only need to then find the number of distinct elements.

We can do this by sticking all the direction vectors into a hash set (or tree set as I did).

This one really sucks, because sorting by angle is terrible if it's not specifically part of the language.

If you're clever or lucky, you probably have stuff like sin and cos, which you can use to find slope and thus angle and sort that way.

I'm not clever but I have atan2 which, long story short, lets one get the counterclockwise angle of a vector relative to one fixed line.

In our case, we take out all of our distinct direction vectors and then sort them using atan2,after which we must identify where "vertical up" is (it's <0,-1>) and then "cycle" the array to make sure it starts there (it turns out my array already started there) and possibly reverse it if you sorted the wrong way (I did).

Finally, to get the 200th asteroid, we literally simulate the laser by cycling through this sorted list of direction vectors and stretching it out from our recorded origin point until it either hits an asteroid and goes out of bounds. With the right processing (setting the asteroid to false, using a counter, etc.) we will have a position coordinate at the end where at last we can process the coordinates of that asteroid and get the answer.

If you look at my code, there are some even crappier details (a custom implementation of atan, requiring that <0,-1> is even in the slopes, swapping x and y coords, etc.) but those are just me kludging an implementation of this strategy.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> ii;
typedef vector<vi> vvi;
int gcd(int a, int b) {
	if(a == 0) return b;
	if(b == 0) return a;
	return gcd(b,a%b);
}
int sgn(int val) {
	if(val > 0) return 1;
	if(val < 0) return -1;
	return 1;
}
ll cro(const ii& a, const ii& b) {
	return (a.first*b.second)-(b.first*a.second);
}
int hlf(ii x) {
	ii rv = {x.second,x.first};
	const ii z = {0,0};
	return (rv > z);
}
bool cmp(const ii& a, const ii& b) {
	int A = hlf(a),B = hlf(b);
	return (A==B?cro(a,b) > 0:A<B);
}
ii red(int a, int b) {
	/*
	if(b == 0) {
		return {sgn(a),0};
	}
	if(a == 0) {
		return {0,sgn(b)};
	}
	*/
	if(a == 0 && b == 0) {return {0,0};}
	int g = gcd(abs(a),abs(b));
	a /= g;b /= g;
	return {a,b};
}
vvi g;
int main() {
	int n,m;
	string s;
	while(cin >> s) {
		g.push_back(vi());
		for(int i=0;i<s.size();i++) {
			g.back().push_back((s[i] == '#'));
		}
	}
	n = g.size();m = g[0].size();
	int ma = 0;
	ii mi = {0,0};
	set<ii> ok;
	for(int i=0;i<n;i++) {
		for(int j=0;j<m;j++) {
			if(!g[i][j]) continue;
			set<ii> mp;
			for(int k=0;k<n;k++) {
				for(int l=0;l<m;l++) {
					if(!g[k][l]) continue;
					int a = k-i,b = l-j;
					if(a == 0 && b == 0) continue;
					mp.insert(red(a,b));
				}
			}
			//cout << "TTT " << i << " " << j << '\n';
			//cout << mp.size() << '\n';
			/*
			for(auto& it: mp) {
				cout << it.first << " " << it.second << '\n';
			}
			*/
			if(mp.size() > ma) {
				mi = {i,j};
				ma = mp.size();
				ok = mp;
			}
		}
	}
	vector<ii> w,x;
	for(auto& it: ok) {
		w.push_back(it);
	}
	sort(w.begin(),w.end(),cmp);
	int se = -1;
	for(int i=0;i<w.size();i++) {
		ii ch = {-1,0};
		if(w[i] == ch) {
			se = i;break;
		}
	}
	for(int i=se;i>=0;i--) {
		x.push_back(w[i]);
	}
	for(int i=w.size()-1;i>se;i--) {
		x.push_back(w[i]);
	}
	int ctr = 0;
	int cc = 0;
	ii sho;
	while(ctr < 200) {
		ii val = {x[cc].first,x[cc].second};
		ii co = {val.first+mi.first,val.second+mi.second};
		while(1) {
			if(co.first < 0) break;
			if(co.second < 0) break;
			if(co.first >= g.size()) break;
			if(co.second >= g[0].size()) break;
			if(g[co.first][co.second]) {
				g[co.first][co.second] = 0;
				ctr++;
				sho = co;
				break;
			}
			co.first += val.first;co.second += val.second;
		}
		cc = (cc+1)%x.size();
	}
	cout << "Part 1:\n";
	cout << ma << '\n';
	cout << "Part 2:\n";
	cout << sho.second*100 + sho.first << '\n';
}

import math
asteroid_map = """INPUT GOES HERE"""

asteroid_map_rows = asteroid_map.split("\n")

print(asteroid_map_rows)

asteroid_list = []
for y in range(len(asteroid_map_rows)):
    for x in range(len(asteroid_map_rows[y])):
        if asteroid_map_rows[y][x] == '#':
            asteroid_list.append((x,y))
            #print(f"X: {x}, Y: {y}")
            
def offset(x1, y1, x2, y2):
    return [x2-x1, y2-y1]
def gen_offset_list(x, y):
    offset_list = []
    for asteroid in asteroid_list:
        if offset(x,y, asteroid[0], asteroid[1]) != [0, 0]:
            offset_list.append(offset(x,y, asteroid[0], asteroid[1]))
    return offset_list
def num_visible(x,y):
    offset_list = gen_offset_list(x,y)
    angle_list = []
    for offset in offset_list:
        i_list = []
        for i in range(1,30):
            if offset[0] % i == 0 and offset[1] % i == 0:
                i_list.append(i)
        if len(i_list) > 0:
            angle_list.append((offset[0]/i_list[-1], offset[1]/i_list[-1]))
            
    return set(angle_list)

most_seen = None
most_number_seen = 0
for asteroid in asteroid_list:
    print(f"Asteroid at X: {asteroid[0]} Y: {asteroid[1]} can see {len(num_visible(asteroid[0], asteroid[1]))} other asteroids")
    if len(num_visible(asteroid[0], asteroid[1])) > most_number_seen:
        most_seen = asteroid
        most_number_seen = len(num_visible(asteroid[0], asteroid[1]))
print("---------------------")
print(f"Asteroid {most_seen} saw the most other asteroids")
print(f"Asteroids seen: {most_number_seen}")

import math
asteroid_list = []
for y in range(len(asteroid_map_rows)):
    for x in range(len(asteroid_map_rows[y])):
        if asteroid_map_rows[y][x] == '#':
            asteroid_list.append((x,y))
            #print(f"X: {x}, Y: {y}")
            
def offset(x1, y1, x2, y2):
    return [x2-x1, y2-y1]
def gen_offset_list(x, y):
    offset_list = []
    for asteroid in asteroid_list:
        if offset(x,y, asteroid[0], asteroid[1]) != [0, 0]:
            offset_list.append(offset(x,y, asteroid[0], asteroid[1]))
    return offset_list
def num_visible(x,y):
    offset_list = gen_offset_list(x,y)
    angle_list = []
    for offset in offset_list:
        i_list = []
        for i in range(1,30):
            if offset[0] % i == 0 and offset[1] % i == 0:
                i_list.append(i)
        if len(i_list) > 0:
            sorted(i_list)
            angle_list.append((offset[0]/i_list[-1], offset[1]/i_list[-1]))
            
    return set(angle_list)
def visible_asteroid_at_offset_angle(x,y,offset_x, offset_y):
    offset_list = gen_offset_list(x,y)
    multiplier = 1
    while multiplier < 30:
        for offset in offset_list:
            if offset[0] == offset_x * multiplier and offset[1] == offset_y * multiplier:
                return [x + offset[0], y + offset[1]]
        multipler = multiplier + 1
most_seen = None
most_number_seen = 0
for asteroid in asteroid_list:
    #print(f"Asteroid at X: {asteroid[0]} Y: {asteroid[1]} can see {len(num_visible(asteroid[0], asteroid[1]))} other asteroids")
    if len(num_visible(asteroid[0], asteroid[1])) > most_number_seen:
        most_seen = asteroid
        most_number_seen = len(num_visible(asteroid[0], asteroid[1]))
print("---------------------")
print(f"Asteroid {most_seen} saw the most other asteroids")
print(f"Asteroids seen: {most_number_seen}")
print("---------------------")
seen_list = num_visible(most_seen[0], most_seen[1])
angle_list = []



for seen in seen_list:
    #angle = (math.atan2(seen[1],seen[0])/math.pi*180)
    angle = (((math.atan2(seen[1],seen[0])/math.pi*180)+270) % 360) - 180
    angle_list.append([angle, seen])
    
    #print(seen)
    #print(angle)
    

angle_list.sort()
#print(angle_list)

starting_point = None
distance_from_0 = 180
starting_index = None
for idx, angle in enumerate(angle_list):
    if abs(angle[0]) < distance_from_0:
        starting_point = [angle[1][0], angle[1][1]]
        distance_from_0 = abs(angle[0])
        starting_index = idx
print("---------------------")
print(f"Starting Point Offset {starting_point}")
starting_asteroid = visible_asteroid_at_offset_angle(most_seen[0], most_seen[1], starting_point[0] , starting_point[1])
print(f"Starting Point Asteroid {starting_asteroid}")
print()
#print("---------------------")
#print("Positive Angles")
pos_angles = angle_list[starting_index:]
#print(pos_angles)
#print("---------------------")
#print("Negative Angles")
neg_angles = angle_list[:starting_index]
#print(neg_angles)

repaired_list = pos_angles + neg_angles

#print("---------------------")
#print("Corrected List")
#print(repaired_list)

print("---------------------")
possible_asteroid = repaired_list[199]
print(possible_asteroid)
corrected_asteroid = visible_asteroid_at_offset_angle(most_seen[0], most_seen[1], possible_asteroid[1][0] , possible_asteroid[1][1])
print(f"200th asteroid to be vaporized: {corrected_asteroid}")

print(asteroid_list)

I've spent too much time playing (and some time writing) text-based roguelikes that use # as a wall character, and interpreted the problem as a typical roguelike-grid LOS problem where each # blocks LOS entirely. I spent a chunk of time writing a line-walking algorithm and inspecting each tile on the line to see if it occluded or not.

Setting up and testing this took a bit of time, and it was working "correctly" until I examined it against the test cases from AoC, which were completely different, since the "asteroids" are actually more-or-less sizeless points that only occlude something if they are exactly behind each other.

This means that the important piece of information about any given asteroid is not what grid tile it's on, but the angle to that asteroid from your base station (or candidate). If any two asteroids share the exact same angle from the base, then the nearer one is occluding the further one; in any other cases both are visible, even if the LOS passes through the same tile.

Once I understood how it worked, I switched to using a hashmap of angle => [points] and the problem opened up.

#!/usr/bin/env crystal
struct Point
  property x : Int32
  property y : Int32
  def initialize(x,y)
    @x = x
    @y = y
  end
end

def dist(a, b)
  (a.x - b.x).abs + (a.y - b.y).abs
end

# part 1
input = File.read("day10/input.txt").strip
map = input.lines.map { |l| l.chars.select{ |c| c == '.' || c == '#'}.to_a }.reject(&.empty?)

# find all the asteroids
rocks = {} of Point => Hash(Float64, Array(Point))
(0..map.size-1).each do |y|
  (0..map[y].size-1).each do |x|
    # for each asteroid, make a set to hold the angles to the other rocks note
    #  that asteroids are essentially sizeless, and only block if the angle is
    #  *exactly* the same
    set = {} of Float64 => Array(Point)

    rocks[Point.new(x,y)] = set if map[y][x] == '#'
  end
end

# for each rock, for each other rock
rocks.each do |a,_|
  rocks.each do |b,_|
    if a != b
      # add the angle from rock a to rock b to our set
      theta = Math.atan2(a.y - b.y, a.x - b.x)
      rocks[a][theta] = rocks[a][theta]? ? rocks[a][theta] << b : [b]
    end
  end
end

best = rocks.max_by { |p, s| s.size } # count how many unique rock-angles there are
puts "Part 1"
puts best[0], best[1].size

# part 2
# we need to find the order of laser hits
base = best[0] # grab the laser base station from p1
to_hit = best[1] # map of angles to hit and matching rocks
#puts best[1]

angles = to_hit.keys
# ensure we have our start angle of pi/2
angles << Math::PI/2 if ! angles.index Math::PI/2
angles = angles.sort

start = angles.index(Math::PI/2) || 0
count = 1

angles.rotate(start).each do |theta|
  to_hit[theta] = to_hit[theta].sort_by { |p| dist(base, p) }
  #puts "%5f => %i" % [theta, to_hit[theta].size]
  puts "    hit %i = %s" % [count, to_hit[theta].first] if count == 200
  to_hit[theta] = to_hit[theta].skip(1)
  count += 1
end

import math
import operator

def create_asteroid_map(file):

    with open(file, 'r') as fid:

        raw_data = fid.readlines()

    map = []

    # This could probably be a list comprehension but eh
    for line in raw_data:
        map_line = []
        for item in line:
            map_line.append(item == '#')
        map.append(map_line)

    return map

def find_max_asteroids(map):

    max_asteroids = 0
    station_location = None

    for idx in range(len(map)):
        for jdx in range(len(map[0])):

            # Skip checking blank squares
            if not map[idx][jdx]:
                continue

            blocked_slopes = []

            for kdx in range(len(map)):
                for ldx in range(len(map[0])):

                    # Skip checking blank squares, or against yourself
                    if not map[kdx][ldx]:
                        continue
                    elif kdx == idx and ldx == jdx:
                        continue

                    try:
                        slope = float(kdx - idx) / float(ldx - jdx)

                        if float(kdx - idx) >= 0 and float(ldx - jdx) > 0:
                            quadrant = 1
                        elif float(kdx - idx) >= 0 and float(ldx - jdx) < 0:
                            quadrant = 2
                        elif float(kdx - idx) <= 0 and float(ldx - jdx) > 0:
                            quadrant = 3
                        elif float(kdx - idx) <= 0 and float(ldx - jdx) < 0:
                            quadrant = 4

                    except ZeroDivisionError:
                        if float(kdx - idx) < 0:
                            slope = -1 * math.inf
                            quadrant = 2
                        else:
                            slope = math.inf
                            quadrant = 1

                    valid_spot = True

                    for blocked in blocked_slopes:
                        if (math.isclose(slope, blocked[0], rel_tol=1e-5)
                            and blocked[1] == quadrant):
                            valid_spot = False
                            break

                    if valid_spot:
                        blocked_slopes.append([slope, quadrant])
                        # The length of this is also the number of asteroids

            if len(blocked_slopes) > max_asteroids:
                max_asteroids = len(blocked_slopes)
                station_location = [jdx, idx] # Convert to xy from yx

    return max_asteroids, station_location

test_files = ["Test1_1.txt", "Test1_2.txt", "Test1_3.txt", "Test1_4.txt", "Test1_5.txt"]
test_results = [8, 33, 35, 41, 210]

puzzle_input = "PuzzleInput.txt"


for idx in range(len(test_files)):

    asteroid_map = create_asteroid_map(test_files[idx])

    max_asteroids, location = find_max_asteroids(asteroid_map)
    assert max_asteroids == test_results[idx]

print("Tests Passed!")

asteroid_map = create_asteroid_map(puzzle_input)
max_asteroids, location = find_max_asteroids(asteroid_map)
print(max_asteroids)

I don't think I solved this in a terribly good way, but I just took everything, divided it into quadrants to reduce ambiguity, and then sorted them in a way that would mean if I kept track of what had been destroyed overall and in that rotation I would be okay.

def find_asteroid_annihilated(map, station_location, asteroid_num):

    station_location = station_location[::-1]

    quad_1 = []
    quad_2 = []
    quad_3 = []
    quad_4 = []

    for idx in range(len(map)):
        for jdx in range(len(map[0])):

            # Skip checking blank squares, or against yourself
            if not map[idx][jdx]:
                continue
            elif station_location[0] == idx and station_location[1] == jdx:
                continue

            try:
                slope = float(station_location[0] - idx) / float(station_location[1] - jdx)

                if float(station_location[0] - idx) >= 0 and float(station_location[1] - jdx) > 0:
                    quadrant = 4
                elif float(station_location[0] - idx) >= 0 and float(station_location[1] - jdx) < 0:
                    quadrant = 3
                elif float(station_location[0] - idx) <= 0 and float(station_location[1] - jdx) > 0:
                    quadrant = 2
                elif float(station_location[0] - idx) <= 0 and float(station_location[1] - jdx) < 0:
                    quadrant = 1

            except ZeroDivisionError:
                if float(station_location[0] - idx) < 0:
                    slope = -1 * math.inf
                    quadrant = 2
                else:
                    slope = math.inf
                    quadrant = 1

            distance = (float(station_location[0] - idx)**2.0 + float(station_location[1] - jdx)**2.0)**0.5
            slope = round(slope, 5)

            if quadrant == 1:
                quad_1.append([quadrant, slope, distance, [idx, jdx]])
            elif quadrant == 2:
                quad_2.append([quadrant, slope, distance, [idx, jdx]])
            elif quadrant == 3:
                quad_3.append([quadrant, slope, distance, [idx, jdx]])
            elif quadrant == 4:
                quad_4.append([quadrant, slope, distance, [idx, jdx]])

    quad_1.sort(key = lambda x: (-x[1], x[2]))
    quad_2.sort(key = lambda x: (-x[1], x[2]))
    quad_3.sort(key = lambda x: (x[1], x[2]))
    quad_4.sort(key = lambda x: (x[1], x[2]))

    asteroid_annihilation = quad_1 + quad_2 + quad_3 + quad_4

    previously_annihilated = []
    num_annihilated = 0
    while num_annihilated < asteroid_num:
        annihilated_this_round = []
        for asteroid in asteroid_annihilation:

            skip = False
            for annihilated in previously_annihilated:
                if (asteroid[3][0] == annihilated[3][0] and
                    asteroid[3][1] == annihilated[3][1]):
                    skip = True
                    break

            if skip:
                continue

            for annihilated in annihilated_this_round:
                if (asteroid[1] == annihilated[1]
                    and asteroid[0] == annihilated[0]):
                    skip = True
                    break

            if skip:
                continue

            annihilated_this_round.append(asteroid)
            num_annihilated += 1

        previously_annihilated.extend(annihilated_this_round)

    return previously_annihilated[asteroid_num - 1]

target_asteroid = find_asteroid_annihilated(asteroid_map, location, 200)
print(target_asteroid[3][1]* 100 + target_asteroid[3][0])

package d10

import (
	"math"
	"sort"
	"strings"

	"github.com/jzimbel/adventofcode-go/solutions"
)

const (
	// width and height of my puzzle input, used for some slight optimizations
	width  = 24
	height = 24
)

var epsilon float64

type point struct {
	x int
	y int
}

type grid map[point]struct{}

// stores memoized results
var gcdCache map[[2]int]int

// gcd returns the greatest common denominator of two ints.
// Results are memoized for a slight performance bump.
func gcd(a, b int) (n int) {
	var key [2]int
	if a < b {
		key = [...]int{a, b}
	} else {
		key = [...]int{b, a}
	}

	var ok bool
	if n, ok = gcdCache[key]; !ok {
		if b != 0 {
			n = gcd(b, a%b)
		} else {
			n = a
		}
		gcdCache[key] = n
	}
	return
}

// axisDistances returns (separately) the x and y distances between two points.
func axisDistances(p1, p2 *point) (xDist int, yDist int) {
	xDist, yDist = int(math.Abs(float64(p1.x-p2.x))), int(math.Abs(float64(p1.y-p2.y)))
	return
}

func isBlocked(p1, p2 *point, g grid) (blocked bool) {
	denom := gcd(axisDistances(p1, p2))
	xStepSize, yStepSize := (p2.x-p1.x)/denom, (p2.y-p1.y)/denom
	for i := 1; i < denom; i++ {
		if _, ok := g[point{p1.x + i*xStepSize, p1.y + i*yStepSize}]; ok {
			blocked = true
			break
		}
	}
	return
}

func part1(g grid) (maxVisibleCount int, optimalPoint point) {
	for p1 := range g {
		var visibleCount int
		for p2 := range g {
			if p1 == p2 {
				continue
			}
			if !isBlocked(&p1, &p2, g) {
				visibleCount++
			}
		}
		if visibleCount > maxVisibleCount {
			maxVisibleCount = visibleCount
			optimalPoint = p1
		}
	}
	return
}

type rPoint struct {
	r    float64
	θ    float64 // #codegolfing
	orig point
}

// rPoints is an ordered list of radial (or polar) coordinates.
// Polar axis (where θ = 0) is up.
type rPoints []rPoint

func (rg rPoints) Len() int {
	return len(rg)
}

func (rg rPoints) Less(i, j int) bool {
	if math.Abs(rg[i].θ-rg[j].θ) < epsilon {
		return rg[i].r < rg[j].r
	}
	return rg[i].θ < rg[j].θ
}

func (rg rPoints) Swap(i, j int) {
	rg[i], rg[j] = rg[j], rg[i]
}

// dist returns the Euclidean distance between two points. ( sqrt(a**2 + b**2) )
func dist(p1, p2 *point) float64 {
	return math.Sqrt(math.Pow(math.Abs(float64(p1.x-p2.x)), 2) + math.Pow(math.Abs(float64(p1.y-p2.y)), 2))
}

// clockwiseAngleFromUp calculates the angle from -y in radians of the ray from p1 to p2, moving clockwise.
// Atan2 normally takes arguments as (y,x), but we reverse them and negate x in order to
// have polar θ = 0 be Cartesian (0,-1) and increasing θ move in a clockwise direction.
// Atan2 also produces values in range [-π, π], but we want them to be [0, 2π],
// so when it would normally produce a negative, we use 2π + atan2Result.
func clockwiseAngleFromUp(p1, p2 *point) (θ float64) {
	newX, newY := -(p2.y - p1.y), p2.x-p1.x
	θ = math.Atan2(float64(newY), float64(newX))
	if θ < 0 {
		θ = 2*math.Pi + θ
	}
	return
}

func part2(g grid, optimalPoint point) int {
	// record angle and distance from center of each asteroid in a sorted slice of struct {rad float64; dist float64}
	rp := make(rPoints, 0, len(g))
	for p := range g {
		if p == optimalPoint {
			continue
		}
		rp = append(rp, rPoint{r: dist(&optimalPoint, &p), θ: clockwiseAngleFromUp(&optimalPoint, &p), orig: p})
	}
	sort.Sort(rp)

	var vaporizedCount int
	for len(rp) > 0 {
		nextRp := make(rPoints, 0, len(rp))
		remove := make([]*point, 0, len(rp))
		for i := range rp {
			if isBlocked(&optimalPoint, &rp[i].orig, g) {
				nextRp = append(nextRp, rp[i])
			} else {
				vaporizedCount++
				if vaporizedCount == 200 {
					return rp[i].orig.x*100 + rp[i].orig.y
				}
				remove = append(remove, &rp[i].orig)
			}
		}

		for i := range remove {
			delete(g, *remove[i])
		}
		rp = nextRp
	}
	// unreachable as long as there are at least 200 asteroids on the grid
	return 0
}

// Solve provides the day 10 puzzle solution.
func Solve(input string) (*solutions.Solution, error) {
	g := make(grid, width*height)
	rows := strings.Split(input, "\n")
	for y := range rows {
		for x := range rows[y] {
			if rows[y][x] == '#' {
				g[point{x, y}] = struct{}{}
			}
		}
	}
	maxVisibleCount, optimalPoint := part1(g)

	return &solutions.Solution{Part1: maxVisibleCount, Part2: part2(g, optimalPoint)}, nil
}

func init() {
	epsilon = math.Nextafter(1, 2) - 1
	gcdCache = make(map[[2]int]int, width*height)
}