Mars Rovers V: The Solutions — Bash
This is part of the Mars Rovers series.
“We have to choose a programming language to calculate our Mars rovers’ paths. Can you help us, flandrew?”
“Sure, Ms. Space Agency Person. Have you considered Bash?”
“Bash? Wow, nobody has suggested that so far — and I think it’s a splendid idea! Bash it is.”
The above is part of a conversation that is likely to happen not at all.
Then again, according to Aditya Athalye:
That said (or um, sed), under 1K LoC clean FP-style Bash can do a crazy amount of work sufficiently fast.
Heretic! Amen to that.
The code
Speaking of which, my simplest solution, ending in output-1(), has less than 50 LoCs.
#!/usr/bin/env bash ## Rover --- Mars Rovers Problem # SPDX-FileCopyrightText: © flandrew <https://flandrew.srht.site/listful> # SPDX-License-Identifier: GPL-3.0-or-later #---------------------# # Author: flandrew # # Updated: 2026-04-17 # #---------------------# # Version: 0.1.0 # #---------------------# ## Commentary # # My solutions to the Mars Rovers Problem. # # Usage: # chmod +x rover.sh # and then: # echo "$inputstring" | ./rover.sh output-3 # or: output-1, output-2 # cat "$inputfile" | ./rover.sh output-3 # ############################################################################# #⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯ ## Code ### Common to all solutions #### Settings set -eo pipefail hash grep sed xargs || exit 127 #⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯ #### Parse input parse-input() { local x y; read -r x y; echo "0 0 $x $y" # rectangle limits sed 's/^ *//; N; s/\n/ /' | nl | sed -E 's/[\t ]+/ /g; s/^ //' ;} #⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯ #### Make maps deltas() { local h="$1" c="$2" case "$c" in R) : "0 0 1" ;; L) : "0 0 -1" ;; M) case "$h" in N) : " 0 1 0" ;; E) : " 1 0 0" ;; S) : " 0 -1 0" ;; W) : "-1 0 0" ;; esac ;; esac; printf -- "%s" "$_" ;} new-head() { local h="$1" i="$2" case "$i" in (-1) : "WNES" ;; ( 0) : "NESW" ;; ( 1) : "ESWN" ;; esac; sed "y/NESW/$_/" <<< "$h" ;} rover-map-next() { local id x y h cs dx dy dh read -r id x y h cs if [[ "$cs" ]] then read -r dx dy dh < <(deltas "$h" "${cs::1}") ((x+=dx, y+=dy)); h=$(new-head "$h" "$dh"); cs="${cs:1}" fi; printf -- '%s' "$id $x $y $h $cs" ;} rover-map-all() { local prev all next read -r prev; all="$prev" while : do next=$(rover-map-next <<< "$prev") if [[ "$next" != "$prev" ]] then all+=":$next"; prev="$next" else break; fi; done printf -- '%s\n' "${all@E}" ;} #⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯ #### Utilities last-maps() { grep -oE "[^:]+$" ||:;} maplines() { while read -r line; do printf -- '%s\n' "$line" | "$@"; done ;} xyh() { local x y h; read -r _ x y h _; printf -- '%s\n' "$x $y $h" ;} #⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯ ### Used only by Solution 1 #### Output with neither map validation nor collision detection output-1() { parse-input | (read -r _xm _ym _xM _yM maplines rover-map-all | last-maps | maplines xyh) ;} #⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯ ### Common to Solutions 2 and 3 #### Validate validations() { local id x y h cs xm="$1" ym="$2" xM="$3" yM="$4" read -r id x y h cs [[ "$id" =~ ^[1-9][0-9]*$ && "$x" =~ ^[0-9]+$ && "$y" =~ ^[0-9]+$ && "$h" =~ ^[NESW]$ && "$cs" =~ ^[LRM]*$ ]] && ((xm<=x && x<=xM && ym<=y && y<=yM)) ;} valid-map() { local m; read -r m if validations "$@" <<< "$m" then echo "$m" else echo >&2 "Invalid rover map: $m" fi ;} #⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯ #### Utilities mapitems() { tr : '\n' | maplines "$@" | tr '\n' : | sed 's/:$/\n/' ;} mapcells() { maplines mapitems "$@" ;} #⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯ ### Used only by Solution 2 #### Output with validation of each map output-2() { parse-input | (read -r xm ym xM yM maplines rover-map-all | mapcells valid-map "$xm" "$ym" "$xM" "$yM" | last-maps | maplines xyh) ;} #⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯ ### Used only by Solution 3 #### Utilities init-maps() { grep -oE "^[^:]+" ||:;} take() { : "$1"; sed "$((_+1)),$ d" ;} nth() { : "$1"; sed -n "$_ p" ;} # 1-indexed drop() { : "$1"; sed -n "$((_+1)),$ p" ;} xy() { local x y; read -r _ x y _ _; printf -- '%s\n' "$x,$y" ;} #⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯ #### Look for collisions rover-zip() { local row="$1" xys xys=$(</dev/stdin) # Lines for left, node, right: <<<"$xys" take "$((row-1))" | last-maps | xargs <<<"$xys" nth "$row" | tr : " " # whole path <<<"$xys" drop "$row" | init-maps | xargs ;} assert-no-collisions() { local l n r lnr rv read -r l; read -r n; read -r r read -ra lnr <<<"$l N $r" # N fixes indexing (and never matches) for rv in "${!lnr[@]}"; do if grep -q "\b${lnr[rv]}\b" <<<"$n" then : "${#l[@]}" # <--moving-rover's number = size(l)+1 printf -- 'Collision! Rover %s into %s at %s\n' \ "$((_+1))" "$((rv+1))" "${lnr[rv]}" >&2; fi; done ;} no-collisions() { local all xys wcl row all=$(</dev/stdin) xys=$(<<<"$all" mapcells xy) wcl=$(<<<"$all" wc -l) for ((row=0; row++ < wcl;)) { <<<"$xys" rover-zip "$row" | assert-no-collisions ;} printf -- '%s\n' "$all" ;} #⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯ #### Output with validation of each map and collision detection output-3() { parse-input | (read -r xm ym xM yM maplines rover-map-all | mapcells valid-map "$xm" "$ym" "$xM" "$yM" | no-collisions | last-maps | maplines xyh) ;} #⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯ ### Run it "$@" # Local Variables: # coding: utf-8 # indent-tabs-mode: nil # sentence-end-double-space: nil # outline-regexp: "###* " # End: ## Rover ends here
The tests
#!/usr/bin/env bash ## Rover --- Mars Rovers problem: Tests #⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯ ## Code ### Variables good_input="\ 5 5 1 2 N LMLMLMLMM 3 3 E MMRMMRMRRM" bad_input_2a="\ 5 5 1 2 N LLMMMMRR 3 3 E MMRMMRMRRM" bad_input_2b="\ 5 5 1 2 N LMLMLMLMM 3 3 E MMMMMR" bad_input_3a="\ 5 5 1 2 N LMLMLMLMM 3 3 W MMRMMRMRRM" bad_input_3b="\ 5 5 1 2 N LMLMLMLMM 3 3 E MMRMMRMRRM 0 0 N MMMMRM 5 2 W MMMLM" inputs=(good_input bad_input_2a bad_input_2b bad_input_3a bad_input_3b) #⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯ ### Functions # ++ Rover output functions # - output-1: Neither map validation nor collision-checking # - output-2: Map validation # - output-3: Map validation and collision-checking run-tests() for n do echo "++ Testing: output-$n" for inp in "${inputs[@]}" do echo "================================" echo -e "$inp:\n${!inp}\n" echo "$ output-$n <<< \"\$$inp\"" output-"$n" <<< "${!inp}" done; echo; done #⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯ ### Run it! . ./rover.sh : || exit 5 run-tests "$@" exit 0
Let’s now run the above for each.
Output 1
./tests.sh 1 2>&1
++ Testing: output-1 ================================ good_input: 5 5 1 2 N LMLMLMLMM 3 3 E MMRMMRMRRM $ output-1 <<< "$good_input" 1 3 N 5 1 E ================================ bad_input_2a: 5 5 1 2 N LLMMMMRR 3 3 E MMRMMRMRRM $ output-1 <<< "$bad_input_2a" 1 -2 N 5 1 E ================================ bad_input_2b: 5 5 1 2 N LMLMLMLMM 3 3 E MMMMMR $ output-1 <<< "$bad_input_2b" 1 3 N 8 3 S ================================ bad_input_3a: 5 5 1 2 N LMLMLMLMM 3 3 W MMRMMRMRRM $ output-1 <<< "$bad_input_3a" 1 3 N 1 5 W ================================ bad_input_3b: 5 5 1 2 N LMLMLMLMM 3 3 E MMRMMRMRRM 0 0 N MMMMRM 5 2 W MMMLM $ output-1 <<< "$bad_input_3b" 1 3 N 5 1 E 1 4 E 2 1 S
Output 2
./tests.sh 2 2>&1
++ Testing: output-2 ================================ good_input: 5 5 1 2 N LMLMLMLMM 3 3 E MMRMMRMRRM $ output-2 <<< "$good_input" 1 3 N 5 1 E ================================ bad_input_2a: 5 5 1 2 N LLMMMMRR 3 3 E MMRMMRMRRM $ output-2 <<< "$bad_input_2a" Invalid rover map: 1 1 -1 S MRR Invalid rover map: 1 1 -2 S RR Invalid rover map: 1 1 -2 W R Invalid rover map: 1 1 -2 N 1 0 S 5 1 E ================================ bad_input_2b: 5 5 1 2 N LMLMLMLMM 3 3 E MMMMMR $ output-2 <<< "$bad_input_2b" Invalid rover map: 2 6 3 E MMR Invalid rover map: 2 7 3 E MR Invalid rover map: 2 8 3 E R Invalid rover map: 2 8 3 S 1 3 N 5 3 E ================================ bad_input_3a: 5 5 1 2 N LMLMLMLMM 3 3 W MMRMMRMRRM $ output-2 <<< "$bad_input_3a" 1 3 N 1 5 W ================================ bad_input_3b: 5 5 1 2 N LMLMLMLMM 3 3 E MMRMMRMRRM 0 0 N MMMMRM 5 2 W MMMLM $ output-2 <<< "$bad_input_3b" 1 3 N 5 1 E 1 4 E 2 1 S
Output 3
./tests.sh 3 2>&1
++ Testing: output-3 ================================ good_input: 5 5 1 2 N LMLMLMLMM 3 3 E MMRMMRMRRM $ output-3 <<< "$good_input" 1 3 N 5 1 E ================================ bad_input_2a: 5 5 1 2 N LLMMMMRR 3 3 E MMRMMRMRRM $ output-3 <<< "$bad_input_2a" Invalid rover map: 1 1 -1 S MRR Invalid rover map: 1 1 -2 S RR Invalid rover map: 1 1 -2 W R Invalid rover map: 1 1 -2 N 1 0 S 5 1 E ================================ bad_input_2b: 5 5 1 2 N LMLMLMLMM 3 3 E MMMMMR $ output-3 <<< "$bad_input_2b" Invalid rover map: 2 6 3 E MMR Invalid rover map: 2 7 3 E MR Invalid rover map: 2 8 3 E R Invalid rover map: 2 8 3 S 1 3 N 5 3 E ================================ bad_input_3a: 5 5 1 2 N LMLMLMLMM 3 3 W MMRMMRMRRM $ output-3 <<< "$bad_input_3a" Collision! Rover 2 into 1 at 1,3 1 3 N 1 5 W ================================ bad_input_3b: 5 5 1 2 N LMLMLMLMM 3 3 E MMRMMRMRRM 0 0 N MMMMRM 5 2 W MMMLM $ output-3 <<< "$bad_input_3b" Collision! Rover 2 into 4 at 5,2 1 3 N 5 1 E 1 4 E 2 1 S
The comments
Used as I am to seeing Bash lifting things that it’s not supposed to, I keep being surprised. For example:
Have a look at the conciseness of
parse-input(), having in mind that it could be smaller: that trailingsedisn’t essential, asreadwould read it all the same. I only added that for “pretty-printing” purposes, if running only that function; say, on the sample input, it’d give us this:
0 0 5 5 1 1 2 N LMLMLMLMM 2 3 3 E MMRMMRMRRM
- Then we have two dispatchers, in which the tiny
sed "y/NESW/$_/"takes care of selecting a new heading. - Then in a dozen lines we have functions to generate the next map and all maps.
- Map validation, here, is a bit simpler than in both Lisps.
- Then
mapcells() { maplines mapitems "$@" ;}suggests that Bash can handle higher-order functions. Who’d have thought? - In spite of the rather noisy array syntax that you see in
assert-no-collisions()(or, perhaps, because of it), in about two dozen lines and a few functions we can solve collision detection using a “zipper-inspired” structure.
I found it quite enjoyable to write this.
The conclusion is clear: we must put more Lisp and Bash on Mars.
📆 2026-W16-6📆 2026-04-18