Mars Rovers IV: The Solutions — Emacs Lisp

This is part of the Mars Rovers series.

Having solved it in Clojure, I couldn’t resist inviting Emacs Lisp to the party.

The adaptation

My approach was:

  1. Open a new Emacs Lisp buffer.
  2. Copy-paste all my Clojure code into it.
  3. Batch-replace defn with defun.
  4. Eval buffer and— oh, it fails! Go figure. I guess there’s more than just defn to replace, eh?
  5. Replace whatever else needs replacement.
  6. Fine-tune a few remaining things, so that it gets closer to idiomatic Elisp.
  7. Run. Oops. Debug. Run. Oops. Debug. Run. ... oh, it runs now!
  8. Adapt the tests.

See? Simple.

Other than these, I tried to keep both as parallel as possible, so that an interested reader (you?) could put them side by side and look at the differences: “Oh, so Clojure’s X can be written as Y in Elisp?” — or vice-versa.

There’re comments about these replacements after the code.

The code

;;; rover.el --- Mars Rovers Problem  -*- lexical-binding: t -*-

;; SPDX-FileCopyrightText: © flandrew <https://flandrew.srht.site/listful>
;; SPDX-License-Identifier: GPL-3.0-or-later

;;---------------------------------------------------------------------------
;; Author:    flandrew
;; Updated:   2026-04-17
;; Keywords:  lisp
;; Homepage:  <https://flandrew.srht.site/listful/software.html>
;;---------------------------------------------------------------------------
;; Package-Version:  0.1.0
;; Package-Requires: ((emacs "25.1") (xht "2.0") (dash "2.18") (s "1.12"))
;;---------------------------------------------------------------------------

;;; Commentary:
;;
;; My solutions to the Mars Rovers Problem.
;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;


;;; Code:
;;;; Common to all solutions
;;;;; Libraries

(require 'dash)  ; ‘-iota’, therefore 2.18+
(require 'xht)   ; by the same author
(require 's)


;;;;; Parse input

(defun rover--lst->map (lst)
  "Given a list LST of two strings of rover data, convert it to hash table."
  (-let* (((s1 s2) lst)
          ((x y h cs) (s-split " +" (concat s1 " " s2))))
    (h* :id nil :x (read x) :y (read y) :h h :cs cs)))

(defun rover--parse-input (s)
  "Parse input string S into a list.
List's first two items are the given pairs of min and max coordinates.
The remaining items are hash tables, each of which for a rover."
  (if (s-blank? s) ""
    (-let* (((xymax . rs) (->>  s  s-lines        (-map #'s-trim)))
            (rovers       (->> rs  (-partition 2) (-map #'rover--lst->map)
                               (--map-indexed (h-put it :id (1+ it-index)))))
            ((xmax ymax)  (-map #'read (s-split " +" xymax))))
      `((0 ,xmax) (0 ,ymax) ,@rovers))))


;;;;; Make maps

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

;; Native compilation freezes here — apparently because of -cycle.
;; (But byte compilation works fine. Native compilation bug?)
(defun rover--new-head (h i)
  "Given a heading H and a delta integer I, return new heading."
  (->> "NESW" -cycle
       (--drop-while (not (string= (string it) h)))
       (-drop (+ 4 i))   car   string))

(defun rover--map-next (m)
  "Given a rover map M, return map of after-the-next-change.
If there's no next change, return M."
  (h-let m
    (if (s-present? .cs)
        (-let* ((next-change (-> .cs (aref 0) string))
                ([Δx Δy Δh]  (rover--deltas .h next-change)))
          (h* :id .id
              :x  (+ .x Δx)
              :y  (+ .y Δy)
              :h  (rover--new-head .h Δh)
              :cs (substring .cs 1)))
      m)))

(defun rover--map-all (m)
  "Given a rover initial map M, list all its maps, up to the last change."
  (-iterate #'rover--map-next m
            (-> m  (h-get :cs)  length  1+)))


;;;;; Make output string

(defun rover--map->str (m)
  "Given a rover map M, convert it to a string line: x y h."
  (h-let m (format "%s %s %s" .x .y .h)))

(defun rover--maps-all->str (coll)
  "Convert to output string collection COLL of map collections."
  (->> coll
       (-map (-compose #'rover--map->str #'car #'last))
       (s-join "\n")))

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

(defun rover-output-1 (s)
  "Given input string S, produce output string."
  (-let [(_ _ . rovers) (rover--parse-input s)]
    (->> rovers
         (-map #'rover--map-all)
         (rover--maps-all->str))))

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

(defmacro rover--validations (xr yr)
  "Given x and y ranges XR and YR, create validations map."
  `(h* :id (-andfn #'natnump (-not #'zerop))
       :x  (-andfn #'numberp (-cut <= (car ,xr) <> (cadr ,xr)))
       :y  (-andfn #'numberp (-cut <= (car ,yr) <> (cadr ,yr)))
       :h  (-andfn #'stringp (-cut s-contains?  <> "NESW"))
       :cs (-andfn #'stringp (-cut s-matches? "\\`[LRM]*\\'" <>))))

(defun rover--valid-pair? (vmap k v)
  "Given validations map VMAP, key K, and value V, validate the pair."
  (funcall (h-get vmap k) v))

(defun rover--valid-map? (vmap m)
  "Given validations map VMAP and map M, validate M."
  (h-all? (-partial #'rover--valid-pair? vmap) m))

(defun rover--valid-map (vmap m)
  "Return map M if validated by VMAP; otherwise, throw exception."
  (if (rover--valid-map? vmap m) m (error "Invalid rover map:\n%s"
                                          (h-h*-pp-str m))))

(defun rover--ensure-valid (vmap coll)
  "Ensure that all rover maps in COLL 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 map is valid if it's returned by ‘rover--valid-map’ using VMAP.

A rover is valid if all of its maps are valid.

If all rovers are valid, return coll. Otherwise, throw exception."
  (-map (-partial #'-map (-partial #'rover--valid-map vmap)) coll))

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

(defun rover-output-2 (s)
  "Given input string S, produce output string.
Throw an exception if any map is invalid."
  (-let* (((xr yr . rovers) (rover--parse-input s))
          (vmap             (rover--validations xr yr)))
    (->> rovers
         (-map #'rover--map-all)
         (rover--ensure-valid vmap)
         (rover--maps-all->str))))

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

(defun rover--xy (m)
  "Given a rover map M, return its position."
  (h-let m (list .x .y)))

(defun rover--assert-no-collisions (l n r)
  "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."
  (let* ((path (-map #'rover--xy n))
         (left (-map (-compose #'rover--xy #'car #'last) l))
         (rite (-map (-compose #'rover--xy #'car) r))
         (test `(,@left nil ,@rite)))
    (dotimes (i (length test))
      (-let [p (nth i test)]
        (and p (member p path)
             (let* ((id1 (1+ (length left)))
                    (id2 (1+ i))
                    (htb (h* :moving (h* :id id1 :path path)
                             :into   (h* :id id2 :at p))))
               (error "Collision detected!\n%s"
                      (h-h*-pp-str htb))))))))

;; Silly to walk the list three times, but the list is expected to be tiny
;; (we had only half a dozen actual rovers on Mars so far...) — so it'll do.
(defun rover--zip (n)
  "Return a lambda to convert a list into a \"zip\" at N.
A \"zip\" is a partition into left list, central element, right list.
N is the index of the central element."
  (-juxt (-partial #'-take n)
         (-partial #'nth   n)
         (-partial #'-drop (1+ n))))

(defun rover--all-zips (lst)
  "Zipper: convert LST into a list of all zips."
  (--map (funcall it lst)    ; -map-indexed takes a dyadic function, so
         (-map #'rover--zip  ; it doesn't work with rover--zip directly.
               (-iota (length lst)))))

(defun rover--ensure-no-collisions (lst)
  "Ensure that LST of map lists has no collisions.

Each item of LST represents a rover. Each of these items is itself a
list, 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 LST. Else, throw exception."
  (dolist (zip (rover--all-zips lst))
    (apply #'rover--assert-no-collisions zip))
  lst)

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

(defun rover-output-3 (s)
  "Given input string S, produce output string.
Throw an exception if any map is invalid or if there's any collision."
  (-let* (((xr yr . rovers) (rover--parse-input s))
          (vmap             (rover--validations xr yr)))
    (->> rovers
         (-map #'rover--map-all)
         (rover--ensure-valid vmap)
         (rover--ensure-no-collisions)
         (rover--maps-all->str))))


;;;; Wrapping up

(provide 'rover)

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

;;; rover.el ends here

The tests

I use Exemplify-ERT.

First, some input data as variables:

;;;; Variables

(defvar good-input
  "5 5
   1 2 N
   LMLMLMLMM
   3 3 E
   MMRMMRMRRM")

(defvar good-output
  "1 3 N\n5 1 E")

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

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

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

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

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

Then we test it:

;;;; Examples

(exemplify-ert rover-output-1
  ;;;; Should match
  (string= (rover-output-1 good-input) good-output) => t

  ;;;; Right: No clause matching "Z" (no such command)
  (rover-output-1 bad-input-1)  !!> error

  ;;;; Should return: validity and collisions aren't tested for rover-output-1
  (rover-output-1 bad-input-2a)  => "1 -2 N\n5 1 E"
  (rover-output-1 bad-input-2b)  => "1 3 N\n8 3 S"
  (rover-output-1 bad-input-3a)  => "1 3 N\n1 5 W"
  (rover-output-1 bad-input-3b)  => "1 3 N\n5 1 E\n1 4 E\n2 1 S")

(exemplify-ert rover-output-2
  ;;;; Should match
  (string= (rover-output-2 good-input) good-output) => t

  ;;;; Right: No clause matching "Z" (no such command)
  (rover-output-2 bad-input-1)  !!> error

  ;;;; Should error: validity is tested for rover-output-2
  (rover-output-2 bad-input-2a) !!> error
  ;; Invalid rover map:
  ;; (h* :id 1
  ;;     :x 1
  ;;     :y -1
  ;;     :h "S"
  ;;     :cs "MRR")

  (rover-output-2 bad-input-2b) !!> error
  ;; Invalid rover map:
  ;; (h* :id 2
  ;;     :x 6
  ;;     :y 3
  ;;     :h "E"
  ;;     :cs "MMR")

  ;;;; Should return: collisions are not tested for rover-output-2
  (rover-output-2 bad-input-3a)  => "1 3 N\n1 5 W"
  (rover-output-2 bad-input-3b)  => "1 3 N\n5 1 E\n1 4 E\n2 1 S")

(exemplify-ert rover-output-3
  ;;;; Should match
  (string= (rover-output-3 good-input) good-output) => t

  ;;;; Right: No clause matching "Z" (no such command)
  (rover-output-3 bad-input-1)  !!> error

  ;;;; Should error: validity is tested for rover-output-3
  (rover-output-3 bad-input-2a) !!> error
  ;; Invalid rover map:
  ;; (h* :id 1
  ;;     :x 1
  ;;     :y -1
  ;;     :h "S"
  ;;     :cs "MRR")

  (rover-output-3 bad-input-2b) !!> error
  ;; Invalid rover map:
  ;; (h* :id 2
  ;;     :x 6
  ;;     :y 3
  ;;     :h "E"
  ;;     :cs "MMR")

  ;;;; Should error: collisions are tested for rover-output-3
  (rover-output-3 bad-input-3a) !!> error
  ;; Collision detected!
  ;; (h* :moving (h* :id 2
  ;;                 :path '((3 3) (2 3) (1 3) (1 3) (1 4) (1 5)
  ;;                         (1 5) (2 5) (2 5) (2 5) (1 5)))
  ;;     :into (h* :id 1
  ;;               :at '(1 3)))

  (rover-output-3 bad-input-3b) !!> error
  ;; Collision detected!
  ;; (h* :moving (h* :id 2
  ;;                 :path '((3 3) (4 3) (5 3) (5 3) (5 2) (5 1)
  ;;                         (5 1) (4 1) (4 1) (4 1) (5 1)))
  ;;     :into (h* :id 4
  ;;               :at '(5 2)))
  )

The comments

I said:

  1. Replace whatever else needs replacement.
  2. Fine-tune a few remaining things, so that it gets closer to idiomatic Elisp.

Now, what was it that “needed replacement”? As it happens, a handful of things, such as:

  • The position of functions’ arguments: vector after docstring in own line → list at defun’s line.
  • Using list as the default sequence format instead of vector.
  • Using hash-table–creating functions instead of map literals.
  • Making let and case more verbose: parentheses around each pair that is being bound.
  • Hash-quoting all functions passed as arguments.
  • Adding funcall: Elisp compiler doesn’t like to see a lambda (fn) directly used as a function.
  • Replacing (last x) with (car (last x)): Elisp’s last is a one-item list; Clojure’s last is the item.
  • Creating zipper-like functions to do the job of clojure.zip.
  • Many others:
    • length instead of count
    • concat instead of str
    • . instead of & in -let’s destructuring
    • -andfn instead of every-pred?
    • different behavior of -iterate vs. iterate

The above were the essential replacements, without which the code would simply not run.

Then there were these:

  • Prefixing everything with rover-: once loaded, function names are globally available to all of Emacs.
  • Improving docstrings to idiomatic Elisp:
    • Aligning it all the way to the left.
    • Referencing all args’ names in it — each of which UPCASED.
    • First line using verbs in the imperative and ending in “.” (I do that in Clojure as well, so no modification).
  • Adding package-related headers and footers to make it require’able.
  • Replacing (first x) with (car x): no errors thrown, but in Elisp first is an obsolete alias for cl-first, which is itself an alias for car.

Extra notes follow.

Zipper

This function does this:

(rover-all-zips '(a b c d))

=>  '((()       a  (b c d))
      ((a)      b    (c d))
      ((a b)    c      (d))
      ((a b c)  d       ()))

Unfolding

Here’s rover-map-all:

(defun rover-map-all (m)
  "Given a rover initial map, list all its maps, up to the last change."
  (-iterate #'rover-map-next m
            (-> m  (h-get :cs)  length  1+)))

Unlike Clojure’s iterate, which generates an infinite lazy sequence that can be passed to (usually) take, Elisp’s dash’s --iterate takes a number of iterations. The closest to Clojure’s iterate is --unfold.

But unlike Clojure, this construct won’t work:

(defun rover-map-all (m)
  "Given a rover initial map, list all its maps, up to the last change."
  (take (-> m  (h-get :cs)  length  1+)
        (--unfold (cons it (rover-map-next it)) m)))

The infinite list that’s being --unfold’ed is only available to take when it finishes unfolding — which it doesn’t. So it freezes. It’s not lazy.

So, in Elisp, --unfold begs for a termination statement — like this:

(defun rover-map-all (m)
  "Given a rover initial map, list all its maps, up to the last change."
  (--unfold (unless (s-blank? (h-get it :cs))
              (cons it (rover-map-next it)))
            m))

But this one has an off-by-one error: the last map (whose :cs is always "") is missing. It won’t cons it.

We could fix it by -snoc’ing it, but it’s not elegant. Better to -iterate, because we already know the number of iterations we need from the very length of :cs.

Line-splitting

Suppose we had this input:

5 5
1 2 N

In this case, the second line of the rover, corresponding to its commands, is empty. The logical output is this:

1 2 N

That is: since there were no commands, the rover ended in the same position it started.

Although a bit of an edge case, each rover has two lines, and its command line could be empty. It’s a legitimate input.

So when parsing the input we want to end up with :cs "" in our rover map. The most natural way for this to happen would be for the trailing newline to be detected when spliting the string.

But consider.

In Emacs Lisp, only s.el’s s-lines can do that directly. The native string-lines can’t:

(s-lines      "5 5\n1 2 N\n")       => '("5 5" "1 2 N" "")
(string-lines "5 5\n1 2 N\n")       => '("5 5" "1 2 N")
(string-lines "5 5\n1 2 N\n" t t)   => '("5 5\n" "1 2 N\n")
(string-lines "5 5\n1 2 N\n" nil t) => '("5 5\n" "1 2 N\n")

And clojure.string/split-lines can’t do it either:

(s/split-lines "5 5\n1 2 N\n")      => '["5 5" "1 2 N"]

So I added an empty space at the end of the input:

(s/split-lines "5 5\n1 2 N\n ")     => '["5 5" "1 2 N" " "]

and then the empty command string (later trimmed to "") got in.

See next

Mars Rovers V: The Solutions — Bash

📆 2026-W16-6📆 2026-04-18