Instantly share code, notes, and snippets.

# PEZ/rich4clojure_hard_problem_117.clj

Last active December 19, 2022 10:15
Show Gist options
• Save PEZ/5476ec0b709661a0f20937546efd630b to your computer and use it in GitHub Desktop.
For Science! – Rich 4Clojure Problem 117 – See: https://github.com/PEZ/rich4clojure
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 (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))))

``````