For Science! – Rich 4Clojure Problem 117 – See: https://github.com/PEZ/rich4clojure

rich4clojure_hard_problem_117.clj

(ns rich4clojure.hard.problem-117
  (:require [hyperfiddle.rcf :refer [tests]]))

;; = For Science! =
;; By 4Clojure user: amcnamara
;; Difficulty: Hard
;; Tags: [game]
;; 
;; A mad scientist with tenure has created an experiment
;; tracking mice in a maze. Several mazes have been
;; randomly generated, and you've been tasked with writing
;; a program to determine the mazes in which it's possible
;; for the mouse to reach the cheesy endpoint. Write a
;; function which accepts a maze in the form of a
;; collection of rows, each row is a string where:
;; * spaces represent areas where the mouse can walk
;; freely
;; * hashes (#) represent walls where the mouse can not
;; walk
;; * M represents the mouse's starting point
;; * C represents the cheese which the mouse must reach
;; The mouse is not allowed to travel diagonally in the
;; maze (only up/down/left/right), nor can he escape the
;; edge of the maze. Your function must return true iff
;; the maze is solvable by the mouse.

(def __ :tests-will-fail)

(comment
  
  )

(tests
  true :=  (__ ["M   C"])
  false := (__ ["M # C"])
  true :=  (__ ["#######"
              "#     #"
              "#  #  #"
              "#M # C#"
              "#######"])
  false := (__ ["########"
              "#M  #  #"
              "#   #  #"
              "# # #  #"
              "#   #  #"
              "#  #   #"
              "#  # # #"
              "#  #   #"
              "#  #  C#"
              "########"])
  false := (__ ["M     "
              "      "
              "      "
              "      "
              "    ##"
              "    #C"])
  true :=  (__ ["C######"
              " #     "
              " #   # "
              " #   #M"
              "     # "])
  true :=  (__ ["C# # # #"
              "        "
              "# # # # "
              "        "
              " # # # #"
              "        "
              "# # # #M"]))

;; To participate, fork:
;; https://github.com/PEZ/rich4clojure

;; Post your solution below, please!

Solution from the Dutch Meetup online event:

(ns dutch-meetup.core
  (:require [clojure.string :as str]))

(def maze ["########"
           "#M  #  #"
           "#   #  #"
           "# # #  #"
           "#   #  #"
           "#  #   #"
           "#  # # #"
           "#  #   #"
           "#  #  C#"
           "########"])

(defn neighbours [state x y]
  (-> (for [[xn yn] [[-1 0]
                     [1 0]
                     [0 1]
                     [0 -1]]]
        (get-in state [(+ y yn) (+ x xn)]))
      set))

(defn solution1 [maze]
  (let [width (count (first maze))
        height (count maze)
        [xm ym] (-> (apply str maze)
                    (str/index-of "M")
                    ((juxt rem quot) width))
        [xc yc] (-> (apply str maze)
                    (str/index-of "C")
                    ((juxt rem quot) width))]
    (loop [state maze]
      ;; Is there a mouse near the cheese?
      (if (contains? (neighbours state xc yc) \M)
        true
        (let [new-state (-> (for [y (range 0 height)]
                              (->> (for [x (range 0 width)
                                         :let [current-cell (get-in state [y x])]]
                                     (if (and (= current-cell \space)
                                              ;; Is there a mouse near this empty space?
                                              (contains? (neighbours state x y) \M))
                                       \M
                                       current-cell))
                                   (apply str)))
                            vec)]
          ;;(clojure.pprint/pprint new-state)
          (if (= state new-state)
            false
            (recur new-state)))))))

(solution1 maze)

(defn shortest-path
  "Generalised pathfinding algorithm.
   possible-xform represents possible transforms from one state to another
   legal-state? tests is this a legal transitional or final state 
   start is the beginning state
   end is the desired end state
   Returns length of minimum number of steps to end or nil if none found."
  [possible-xform legal-state? start end]
  (loop
   [i 0
    previous-states #{start}
    current-states #{start}]
    (let [possible-next-states (mapcat possible-xform current-states)
          new-states (into #{}
                              (comp (remove previous-states)
                                    (filter legal-state?))
                              possible-next-states)
          new-previous-states (into previous-states new-states)]
      (if (current-states end)
        i
        (if (seq new-states)
          (recur (inc i) new-previous-states new-states)
          nil)))))

(defn find-in-2d-vec [needle vec]
  (first (for [row-no (range (count vec))
               col-no (range (count (get vec row-no)))
               :when (needle (get-in vec [row-no col-no]))]
           [row-no col-no])))

(tests (find-in-2d-vec #{\M} ["#######"
                              "#     #"
                              "#  #  #"
                              "#M # C#"
                              "#######"]) := [3 1]
       (find-in-2d-vec #{\C} ["#######"
                              "#     #"
                              "#  #  #"
                              "#M # C#"
                              "#######"]) := [3 5]
       (some #{\ } " ") := \ 
)

(defn shortest-path-through-maze [maze]
  (let [start (find-in-2d-vec #{\M} maze)
        end (find-in-2d-vec #{\C} maze)
        possible-moves (juxt #(vector (inc (first %)) (second %))
                             #(vector (first %)       (inc (second %)))
                             #(vector (dec (first %)) (second %))
                             #(vector (first %)       (dec (second %))))
        legal-position #(#{\C \ } (get-in maze %))]
    ((complement nil?)
     (shortest-path possible-moves legal-position start end))))