Skip to content

Instantly share code, notes, and snippets.

@miikka

miikka/core.clj Secret

Last active May 16, 2016 10:16
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
Star You must be signed in to star a gist
Save miikka/31c12cbc6749575d1573ea77ee39321d to your computer and use it in GitHub Desktop.
Solution to Reaktor's Orbital Challenge
;; [net.mikera/core.matrix "0.51.0"]
;; [aysylu/loom "0.6.0"]])
;; [metosin/potpuri "0.3.0"]
(ns orbital-challenge.core
(:use
clojure.core.matrix
clojure.core.matrix.linear
clojure.core.matrix.operators)
(:require
[clojure.string :as string]
[loom.graph :refer [weighted-graph]]
[loom.alg :refer [dijkstra-path]]
[potpuri.core :refer [map-vals]]))
(def earth-radius 6371)
(defn read-data [f]
(apply concat
(for [line (string/split f #"\n")]
(let [parts (string/split line #",")
read-nth (fn [idx] (read-string (nth parts idx)))]
(when (not= (nth line 0) \#)
(if (= (first parts) "ROUTE")
[[:start (concat (map read-nth [1 2]) [0])]
[:end (concat (map read-nth [3 4]) [0])]]
[[(first parts) (map read-nth [1 2 3])]]))))))
(defn point-line-segment-dist
"Compute the shortest distance between the line segment a-b and point c."
[a b c]
(let [k (- b a)
l (- c a)
;; scalar projection of l onto k.
t (/ (dot l k) (norm k))]
(distance (+ a (* (clamp t 0 1) k)) c)))
(defn line-of-sight? [a b]
(<= earth-radius (point-line-segment-dist a b [0 0 0])))
(defn geo->xyz [[lat lon alt]]
"Convert latitude/longitude/altitude to Euclidean coordinates."
(let [h (+ earth-radius alt)
lat (to-radians lat)
lon (to-radians lon)]
[(* h (Math/cos lat) (Math/cos lon))
(* h (Math/cos lat) (Math/sin lon))
(* h (Math/sin lat))]))
(defn build-graph [data]
(let [xyz-data (map-vals geo->xyz data)]
(apply weighted-graph
(for [[key1 pos1] xyz-data
[key2 pos2] xyz-data
:when (and (not= key1 key2)
(not= #{:start :end} (set [key1 key2]))
(line-of-sight? pos1 pos2))]
[key1 key2 (distance pos1 pos2)]))))
(defn get-route [graph]
(butlast (rest (dijkstra-path graph :start :end))))
(defn print-route [route]
(string/join "," route))
(defn solve-challenge [path]
(->> (slurp path)
read-data
(into {})
build-graph
get-route
print-route))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment