Discussion on: Advent of Code 2019 Solution Megathread - Day 6: Universal Orbit Map

View post

Part 1 was a no-brainer in clojure:

; Returns the number of orbits the given object is contained in (i.e. direct orbit + indirect orbits)
(defn orbit-centers [orbit-map object]
  (count (take-while some? (drop 1 (iterate orbit-map object)))))

; Returns the sum of the orbit centers for each object in the orbit map.
(defn direct-and-indirect-orbits [orbit-map]
  (apply + (map (partial orbit-centers orbit-map) (keys orbit-map))))

; Parses the input format into a map of object -> orbit center
(defn parse-orbit-map [raw]
  (apply hash-map (flatten (map (comp reverse #(.split #"\)" %)) (.split #"\n" raw)))))

(def input (parse-orbit-map (slurp (first *command-line-args*))))
(println "Total number of (in)direct orbits:" (direct-and-indirect-orbits input))

I kinda got stuck on part 2, so the solution for this isn't really optimal (takes around half a second):

; Returns a sequence of objects that orbit the given center
(defn orbiting [orbit-map center]
  (map first (filter #(= (% 1) center) orbit-map)))

; Calculates the minimum amount of traversals required in an orbit map to move from object to destination
; (This is currently very inefficient and bad, I might still improve it)
(defn traversals [orbit-map object destination]
  (condp = object
    nil Integer/MIN_VALUE
    destination -2
    (inc (apply max (traversals (dissoc orbit-map object) (orbit-map object) destination)
                (for [orbit-obj (orbiting (dissoc orbit-map object) object)]
                  (traversals (dissoc orbit-map orbit-obj) orbit-obj destination))))))

(println "Traversals required to get from you to santa:" (traversals input "YOU" "SAN"))

Fun one nonetheless!
(Full code: github.com/jkoenig134/AdventOfCode...)

Jon Bristow • Dec 6 '19

I am fake upset you didn't break out the clojure zipper library for this! (it's like using a cannon for flies in this case)

Johnny • Dec 6 '19 • Edited

Oh, I will definitely look into that, thanks for the suggestion.
I only knew about (tree-seq),
I'm still a newbie in clj.

Jon Bristow • Dec 7 '19

Zipper is extremely powerful for navigating trees efficiently.

It’s also as easy to read as overly point free Haskell.

Johnny • Dec 7 '19

I vastly improved it without using zippers now.

; Counts the amount of elements in coll before element appears. Returns (count coll) if it doesn't appear at all.
(defn count-until [element coll]
  (count (take-while (partial not= element) coll)))

; Calculates the minimum amount of traversals required in an orbit map to move from object to destination
(defn traversals [orbit-map object destination]
  (let [object-centers (orbit-centers orbit-map object)
        destination-centers (orbit-centers orbit-map destination)
        first-common-center (some (set destination-centers) object-centers)]
    (+ (count-until first-common-center object-centers)
       (count-until first-common-center destination-centers))))

I just fetch the first common center of both objects and add the steps it takes to get there for both.