81 lines
3.1 KiB
Racket
81 lines
3.1 KiB
Racket
|
#lang racket
|
||
|
|
|
||
|
|
(define (parse-input inp)
|
||
|
|
(string-split (string-trim inp)))
|
||
|
|
|
||
|
|
(define input (parse-input (file->string "input.10.txt")))
|
||
|
|
(define size (max (length input) (string-length (first input))))
|
||
|
|
|
||
|
|
(struct pos [x y] #:transparent)
|
||
|
|
|
||
|
|
(define (input->positions inp)
|
||
|
|
(apply append
|
||
|
|
(for/list ([line inp] [y (in-range (length inp))])
|
||
|
|
(for/list ([char line] [x (in-range (string-length line))] #:when (equal? char #\#))
|
||
|
|
(pos x y)))))
|
||
|
|
|
||
|
|
(define asteroids (apply set (input->positions input)))
|
||
|
|
|
||
|
|
(define (pos-on-line a b c)
|
||
|
|
(define (pos-on-line+ a b c)
|
||
|
|
(let ([crs (- (* (- (pos-y c) (pos-y a)) (- (pos-x b) (pos-x a)))
|
||
|
|
(* (- (pos-x c) (pos-x a)) (- (pos-y b) (pos-y a))))]
|
||
|
|
[dot (+ (* (- (pos-x c) (pos-x a)) (- (pos-x b) (pos-x a)))
|
||
|
|
(* (- (pos-y c) (pos-y a)) (- (pos-y b) (pos-y a))))]
|
||
|
|
[sqdist (+ (sqr (- (pos-x b) (pos-x a)))
|
||
|
|
(sqr (- (pos-y b) (pos-y a))))])
|
||
|
|
(cond [(not (zero? crs)) #f]
|
||
|
|
[(negative? dot) #f]
|
||
|
|
[(<= dot sqdist)])))
|
||
|
|
(or (equal? b c) (pos-on-line+ a b c) (pos-on-line+ a c b)))
|
||
|
|
|
||
|
|
(define (collide-line-pos start to pos-set)
|
||
|
|
(for/set ([pos pos-set] #:when (pos-on-line start to pos))
|
||
|
|
pos))
|
||
|
|
|
||
|
|
(define (count-reachable-asteroids pos-set start)
|
||
|
|
(define pos-set/nostart (set-remove pos-set start))
|
||
|
|
(define (count-reachable+ pos-set start)
|
||
|
|
(cond [(set-empty? pos-set) 0]
|
||
|
|
[else (begin
|
||
|
|
(define any (set-first pos-set))
|
||
|
|
(define reachables (collide-line-pos start any pos-set))
|
||
|
|
(add1 (count-reachable+ (set-subtract pos-set reachables) start)))]))
|
||
|
|
(count-reachable+ pos-set/nostart start))
|
||
|
|
|
||
|
|
;; Part 1
|
||
|
|
;; The super naive way lol
|
||
|
|
(define best (argmax (curry count-reachable-asteroids asteroids) (set->list asteroids)))
|
||
|
|
(count-reachable-asteroids asteroids best)
|
||
|
|
|
||
|
|
(define (dist-between p1 p2)
|
||
|
|
(sqrt (+ (sqr (- (pos-x p1) (pos-x p2))) (sqr (- (pos-y p1) (pos-y p2))))))
|
||
|
|
|
||
|
|
;; intentionally flip y and x for fun and profit
|
||
|
|
;; also negative x
|
||
|
|
;; (this is fuckery to get the sweep to start at 0 and go the normal direction)
|
||
|
|
(define (angle-to center p)
|
||
|
|
(define dx (- (pos-x center) (pos-x p)))
|
||
|
|
(define dy (- (pos-y p) (pos-y center)))
|
||
|
|
(+ (* 2 pi) (atan dx dy)))
|
||
|
|
|
||
|
|
(define sorted (sort (set->list (set-remove asteroids best)) < #:key (curry angle-to best)))
|
||
|
|
(define grouped (group-by (curry angle-to best) sorted))
|
||
|
|
|
||
|
|
(define (min-of-group group)
|
||
|
|
(argmin (curry dist-between best) group))
|
||
|
|
|
||
|
|
(define (destroy-asteroids grouped n)
|
||
|
|
(cond [(zero? n) (min-of-group (first grouped))]
|
||
|
|
[else
|
||
|
|
(let* ([this-group (first grouped)]
|
||
|
|
[min-asteroid (min-of-group this-group)]
|
||
|
|
[rest-of-group (remove min-asteroid this-group)])
|
||
|
|
(cond [(empty? rest-of-group) (destroy-asteroids (rest grouped) (sub1 n))]
|
||
|
|
[else (destroy-asteroids
|
||
|
|
(append (rest grouped) (list rest-of-group)) (sub1 n))]))]))
|
||
|
|
|
||
|
|
;; I am like
|
||
|
|
;; 200 billion % not sure why this is 198 and not 199 (ie, 200 but starting at zero)
|
||
|
|
;; but it rly do be like that sometime
|
||
|
|
(destroy-asteroids grouped 198)
|