Mars Rovers III: The Solutions — Clojure

;;; rover/core.clj --- Mars Rovers Problem
;;
;; SPDX-FileCopyrightText: © flandrew <https://flandrew.srht.site/listful>
;; SPDX-License-Identifier: EPL-2.0
;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;


;;; Code
;;;; Common to all solutions
;;;;; Namespace

(ns ^{:doc    "My solutions to the Mars Rovers Problem."
      :author "flandrew" :version "0.1.0" :updated "2026-04-17"}
    rover.core
  (:require (clojure [string :as s]
                     [zip    :as z])))


;;;;; Parse input

(defn- rover-seq->map
  "Given a sequence of two strings of rover data, convert it to map."
  [[s1 s2]]
  (let [[x y h cs] (s/split (str s1 " " s2) #" +")]
    {:id nil :x (Integer. x) :y (Integer. y) :h h :cs cs}))

(defn parse-input
  "Parse input string into a vector.
  Vector's first two items are the given pairs of min and max coordinates.
  The remaining items are maps, each of which for a rover."
  [s]
  (if (s/blank? s) ""           ; this⬎ for present but empty commands
      (let [[x-y-max & rs] (->> (str s " ")  s/split-lines  (map s/trim))
            rovers         (->> rs  (partition 2)  (map rover-seq->map)
                                (map-indexed #(assoc %2 :id (inc %1))))
            [xM yM]        (map #(Integer. %) (s/split x-y-max #" +"))]
        (into [[0 xM] [0 yM]] rovers))))


;;;;; Make maps

(defn- deltas
  "Given a heading and a change, return vector of deltas.
  The vector corresponds to the changes in x, y, and heading."
  [h c]
  (case c
    "R" [0 0  1]
    "L" [0 0 -1]
    "M" (case h
          "N" [ 0  1  0]
          "E" [ 1  0  0]
          "S" [ 0 -1  0]
          "W" [-1  0  0])))

(defn- new-head
  "Given a heading and a delta integer, return new heading."
  [h i]
  (->> "NESW" cycle
       (drop-while #(not= (str %) h))
       (drop (+ 4 i))   first   str))

(defn- rover-map-next
  "Given a rover map, return map of after-the-next-change.
  If there's no next change, return the very map."
  [{:keys [id x y h cs] :as m}]
  (if-not (empty? cs)
    (let [next-change (-> cs  first  str)
          [Δx Δy Δh]  (deltas h next-change)]
      {:id id
       :x  (+ x Δx)
       :y  (+ y Δy)
       :h  (new-head h Δh)
       :cs (subs cs 1)})
    m))

(defn rover-map-all
  "Given a rover initial map, list all its maps, up to the last change."
  [m]
  (into [] (take (-> m  :cs  count  inc)
                 (iterate rover-map-next m))))


;;;;; Make output string

(defn- rover-map->str
  "Given a rover map, convert it to a string line: x y h."
  [{:keys [x y h]}]
  (format "%s %s %s" x y h))

(defn- rover-maps-all->str
  "Convert to output string a collection of map collections."
  [coll]
  (->> coll
       (mapv (comp rover-map->str peek))
       (s/join "\n")))


;;;; Used only by Solution 1
;;;;; Output

(defn output-1
  "Given input string, produce output string."
  [s]
  (let [[_ _ & rovers] (parse-input s)]
    (->> rovers
         (mapv rover-map-all)
         (rover-maps-all->str))))


;;;; Common to Solutions 2 and 3
;;;;; Validate

(defn- validations
  "Given xrange and yrange, create validations map."
  [[xmin xmax] [ymin ymax]]
  {:id pos-int?
   :x  (every-pred number? #(<= xmin % xmax))
   :y  (every-pred number? #(<= ymin % ymax))
   :h  (every-pred string? #(s/includes? "NESW" %))
   :cs (every-pred string? #(re-seq #"^[RLM]*$" %))})

(defn- valid-pair?
  "Given validations map and a pair, validate the pair."
  [vmap [k v]]
  ((k vmap) v))

(defn- valid-map?
  "Given validations map and a map, validate the map."
  [vmap m]
  (every? (partial valid-pair? vmap) m))

(defn- valid-map
  "Return map if valid; throw exception otherwise."
  [vmap m]
  (if (valid-map? vmap m)
    m (throw (ex-info "Invalid rover map" m))))

(defn- ensure-valid
  "Ensure that all rover maps are valid.

  Each item of collection represents a rover. Each of these items is itself a
  collection, whose items are all the maps of the rover, from first to last.

  A rover is valid if all of its maps are valid.
  If all rovers are valid, return coll. Otherwise, throw exception."
  [vmap coll]
  (mapv (partial mapv (partial valid-map vmap)) coll))


;;;; Used only by Solution 2
;;;;; Output with validation of each map

(defn output-2
  "Given input string, produce output string.
  Throw an exception if any map is invalid."
  [s]
  (let [[xr yr & rovers] (parse-input s)
        vmap             (validations xr yr)]
    (->> rovers
         (mapv rover-map-all)
         (ensure-valid vmap)
         (rover-maps-all->str))))


;;;; Used only by Solution 3
;;;;; Look for collisions

(def xy
  "Extract position from map."
  (juxt :x :y))

(defn- assert-no-collisions
  "Assert that a moving rover won't collide.

  Args are:
  - n (node), a map collection: all maps of a rover, from first to last
  - two collections of map collections:
    - l (left):  previous rovers
    - r (right): next rovers

  A moving rover is collision-free if the last position of each rover before
  it and the first position of each rover after it are not in its path.

  If a collision is detected, throw exception. Otherwise return nil."
  [l n r]
  (let [path (map xy n)
        left (map (comp xy last)  l)
        rite (map (comp xy first) r)
        test `[~@left nil ~@rite]]
    (dotimes [i (count test)]
      (let [p (get test i)]
        (when (some #{p} path)
          (let [id1 (inc (count left))
                id2 (inc i)]
            (throw (ex-info "Collision detected!"
                            {:moving {:id id1 :path path}
                             :into   {:id id2 :at p}}))))))))

(defn- ensure-no-collisions
  "Ensure that there wouldn't be rover collisions.

  Each item of collection represents a rover. Each of these items is itself a
  collection, whose items are all the maps of the rover, from first to last.

  For each of these rovers, assert that there're no collisions.

  If all rovers are collision-free, return coll. Otherwise, throw exception."
  [coll]
  (loop [loc (-> coll  z/vector-zip  z/down)]
    (if loc
      (recur (let [[l n r] ((juxt z/lefts z/node z/rights) loc)]
               (assert-no-collisions l n r)
               (z/right loc)))
      coll)))


;;;;; Output with validation of each map, plus no collisions

(defn output-3
  "Given input string, produce output string.
  Throw an exception if any map is invalid or if there're any collisions."
  [s]
  (let [[xr yr & rovers] (parse-input s)
        vmap             (validations xr yr)]
    (->> rovers
         (mapv rover-map-all)
         (ensure-valid vmap)
         (ensure-no-collisions)
         (rover-maps-all->str))))


;;; Local Variables:
;;  coding:                     utf-8
;;  indent-tabs-mode:           nil
;;  sentence-end-double-space:  nil
;;  outline-regexp:             ";;;;* "
;;  End:

;;; rover/core.clj ends here

;;; rover/core_test.clj --- Mars Rovers Problem: Tests


;;; Code
;;;; Namespace

(ns rover.core-test
  (:require [clojure.test :refer :all]
            [rover.core   :refer :all]))


;;;; Tests
;;;;; All three solutions must parse the sample input correctly

(def good-input   "Given valid input"
  "5 5
  1 2 N
  LMLMLMLMM
  3 3 E
  MMRMMRMRRM")

(def good-output  "Given expected output"
  "1 3 N\n5 1 E")

(deftest test-good-input
  (testing "Good input: given."
    (are [f] (= (f good-input) good-output)
      output-1
      output-2
      output-3)))


;;;;; All three solutions must throw an error at this bad input


(def bad-input-1  "Has invalid change Z"
  "5 5
  1 2 N
  LMZZLM
  3 3 E
  MMMMMR")

(deftest test-bad-input-1
  (testing "Bad input: bogus command Z"
    (are [f] (thrown-with-msg?
              IllegalArgumentException #"No matching clause: Z"
              (f bad-input-1))
      output-1
      output-2
      output-3)))


;;;;; The 2nd and 3rd solutions must be able to catch rovers going off-grid


(def bad-input-2a "Goes to :y -1"
  "5 5
  1 2 N
  LLMMMMRR
  3 3 E
  MMRMMRMRRM")

(def bad-input-2b "Goes to :x 6"
  "5 5
  1 2 N
  LMLMLMLMM
  3 3 E
  MMMMMR")

(deftest test-bad-input-2
  (testing "Bad input: rover ends up out of bounds"
    (are [in out] (= (output-1 in) out)
      bad-input-2a "1 -2 N\n5 1 E"
      bad-input-2b "1 3 N\n8 3 S")

    (are [f in] (thrown-with-msg?
                 clojure.lang.ExceptionInfo #"Invalid rover map"
                 (f in))
      output-2 bad-input-2a
      output-2 bad-input-2b
      output-3 bad-input-2a
      output-3 bad-input-2b)))


;;;;; The 3rd solution must be able to catch rover collisions

(def bad-input-3a "Rover #2 collides with #1 at 1,3"
  "5 5
  1 2 N
  LMLMLMLMM
  3 3 W
  MMRMMRMRRM")

(def bad-input-3b "Rover #2 collides with #4 at 5,2"
  "5 5
  1 2 N
  LMLMLMLMM
  3 3 E
  MMRMMRMRRM
  0 0 N
  MMMMRM
  5 2 W
  MMMLM")

(deftest test-bad-input-3
  (testing "Bad input: a collision would happen"
    (are [f] (= (f bad-input-3a) "1 3 N\n1 5 W")
      output-1
      output-2)

    (are [f] (= (f bad-input-3b) "1 3 N\n5 1 E\n1 4 E\n2 1 S")
      output-1
      output-2)

    (are [in] (thrown-with-msg?
               clojure.lang.ExceptionInfo #"Collision detected!"
               (output-3 in))
      bad-input-3a
      bad-input-3b)))


;;;; Running them

(comment
  (run-tests) => {:test 4, :pass 18, :fail 0, :error 0, :type :summary})


;;; Local Variables:
;;  coding:                     utf-8
;;  indent-tabs-mode:           nil
;;  sentence-end-double-space:  nil
;;  outline-regexp:             ";;;;* "
;;  End:

;;; rover/core_test.clj ends here