diff --git a/README.md b/README.md new file mode 100644 index 0000000..628cb65 --- /dev/null +++ b/README.md @@ -0,0 +1,51 @@ +# mazes +Curtis Lewis + +Maze examples from _Mazes For Programmers_ +written in Common Lisp + + + + +--- +Notes: + +------------------- +2023-04-15 08:07:33 +Saturday + +Attempting to make a branch in fossil. Apparently I need to make a change first. Thus the reason for this comment. + + +2023-03-24 Friday + +---- +(defgeneric link ((current-cell cell) (neighbor-cell cell) (bidi t)) + (:documentation "Links current cell with neighbor cell. If +bidi (bi-directional) is true both cells are updated")) + + +Execution of a form compiled with errors. +Form: + (DEFGENERIC LINK + ((CURRENT-CELL CELL) (NEIGHBOR-CELL CELL) (BIDI T)) + (:DOCUMENTATION "Links current cell with neighbor cell. If +bidi (bi-directional) is true both cells are updated")) +Compile-time error: + Required argument is not a symbol: (CURRENT-CELL CELL) +---- + +------------------- +2023-03-26 09:30:29 +Sunday + +Can not use constants to create array... +(setf matrix (make-array '(rows cols) :initial-element nil)) + +ref: https://stackoverflow.com/questions/19085980/why-cant-constants-be-used-as-array-dimensions-in-common-lisp-type-specifiers + +Last sentence in user797257 response + +1st tried '(,rows ,cols) then got an error unquote not backquoted + +Finally `(,rows ,cols) \ No newline at end of file diff --git a/binary-tree.lisp b/binary-tree.lisp new file mode 100644 index 0000000..2abe492 --- /dev/null +++ b/binary-tree.lisp @@ -0,0 +1,24 @@ +(in-package :mazes) + +(defclass binary-tree () + ((grid :initarg :grid :reader binary-tree-grid))) + +(defmethod initialize-instance :after ((bt binary-tree) &key) + (let* ((grid (binary-tree-grid bt)) + (matrix (grid-matrix grid)) + (rows (grid-rows grid)) + (cols (grid-cols grid)) + (neighbors ()) + (cell ())) + (dotimes (r rows) + (dotimes (c cols) + (setf neighbors ()) + (setf cell (aref matrix r c)) + (when (cell-north cell) (push (cell-north cell) neighbors)) + (when (cell-east cell) (push (cell-east cell) neighbors)) + (when (> (length neighbors) 0) + (link cell :neighbor-cell (elt neighbors (random (length neighbors))))))) + grid)) + +(defun make-binary-tree (grid) + (make-instance 'binary-tree :grid grid)) diff --git a/distances.lisp b/distances.lisp new file mode 100644 index 0000000..50d8a5c --- /dev/null +++ b/distances.lisp @@ -0,0 +1,25 @@ +(in-package #:mazes) + +(defclass distances () + ((root :initarg :root :accessor root-cell) + (cells :initarg :cells :initform (make-hash-table) :accessor distance-cells)) + (:documentation "Keeps track of the distance of each cell from the given root cell.")) + +(defmethod initialize-instance :after ((d distances) &key) + (setf (gethash (root-cell d) (distance-cells d)) 0)) + +(defgeneric set-distance (distance &key) + (:documentation "Set the distance of the given cell from the root cell")) + +(defmethod set-distance ((d distances) &key cell distance) + (let ((cells (distance-cells d))) + (setf (gethash cell cells) distance))) + +(defgeneric distance-all-cells (distances) + (:documentation "Return a list of cells with their respective distance from root")) + +(defmethod distance-all-cells ((d distances)) + (get-hash-keys (distance-cells d))) + +(defun make-distance (root) + (make-instance 'distances :root root)) diff --git a/grid.lisp b/grid.lisp new file mode 100644 index 0000000..d7b5c3c --- /dev/null +++ b/grid.lisp @@ -0,0 +1,108 @@ +(in-package #:mazes) + +(defclass grid () + ((rows :initarg :rows :reader grid-rows) + (cols :initarg :cols :reader grid-cols) + (matrix :initform nil :accessor grid-matrix)) + (:documentation "Initializes a grid of cells with dimension rows x cells")) + +#| + (print-unreadable-object (obj stream :type t) + (format stream "+~v{~a~:*~}~C" (grid-cols obj) '("---+") #\linefeed)) +|# +(defmethod print-object ((obj grid) stream) + (print-unreadable-object (obj stream :type t) + (format stream "(~a, ~a)" (grid-rows obj) (grid-cols obj))) + (format stream (to-string obj))) + +(defmethod initialize-instance :after ((g grid) &key) + (setf (grid-matrix g) (prepare-grid g)) + (configure-cells g)) + +(defun make-grid (rows cols) + "Constructor for grid class" + (make-instance 'grid :rows rows :cols cols)) + +(defgeneric prepare-grid (grid) + (:documentation "Create a grid of cells with dimension rows x cols. This should only be called by INTIALIZE-INSTANCE")) + +(defgeneric configure-cells (grid) + (:documentation "Set the neighbors of each cell")) + +(defgeneric cell-in-grid-p (grid &key) + (:documentation "Determine if a cell is inside the grid.")) + +(defgeneric random-cell (grid) + (:documentation "Return a random cell from the grid")) + +(defgeneric size (grid) + (:documentation "Return the size of the grid")) + +(defgeneric to-string (grid) + (:documentation "Return ASCII string of the maze.")) + +(defmethod to-string ((obj grid)) + + (let ((body "") + (top "") + (bottom "") + (east-boundary "") + (south-boundary "") + (sell ()) + (str (make-array 0 :element-type 'character :fill-pointer 0))) + (format str "~%+~v{~a~:*~}~C" (grid-cols obj) '("---+") #\Newline) + (dotimes (r (grid-rows obj)) + (setf top "|") + (setf bottom "+") + (dotimes (c (grid-cols obj)) + (setf sell (aref (grid-matrix obj) r c)) + (when (null sell) (setf sell (make-cell -1 -1))) + (setf body " ") ; three spaces + (if (linked-p sell :other-cell (cell-east sell)) + (setf east-boundary " ") + (setf east-boundary "|")) + (setf top (concatenate 'string top body east-boundary)) + (if (linked-p sell :other-cell (cell-south sell)) + (setf south-boundary " ") + (setf south-boundary "---")) + (setf bottom (concatenate 'string bottom south-boundary "+"))) + (format str "~a~%" top) + (format str "~a~%" bottom)) + str)) + +(defmethod prepare-grid ((g grid)) + (let* ((rows (grid-rows g)) + (cols (grid-cols g)) + (matrix (make-array `(,rows ,cols) :initial-element nil))) + (dotimes (r rows) + (dotimes (c cols) + (setf (aref matrix r c) (make-cell r c)))) + matrix)) + +(defmethod configure-cells ((g grid)) + "Assumes a square or rectangular grid" + (let ((rowz (grid-rows g)) + (colz (grid-cols g)) + (cell ())) + (dotimes (row rowz) + (dotimes (col colz) + (setf cell (aref (grid-matrix g) row col)) + (setf (cell-north cell) (cell-in-grid-p g :row (- row 1) :col col)) + (setf (cell-south cell) (cell-in-grid-p g :row (+ row 1) :col col)) + (setf (cell-east cell) (cell-in-grid-p g :row row :col (+ col 1))) + (setf (cell-west cell) (cell-in-grid-p g :row row :col (- col 1))) +)))) + +(defmethod cell-in-grid-p ((g grid) &key row col) + (let ((g-rows (- (grid-rows g) 1)) + (g-cols (- (grid-cols g) 1))) + (cond ((or (< row 0) (> row g-rows)) nil) + ((or (< col 0) (> col g-cols)) nil) + ; if cell is lies in the grid return the cell + (t (aref (grid-matrix g) row col))))) + +(defmethod random-cell ((g grid)) + (aref (grid-matrix g) (random (grid-rows g)) (random (grid-cols g)))) + +(defmethod size ((g grid)) + (* (grid-rows g) (grid-cols g))) diff --git a/mazes.asd b/mazes.asd new file mode 100644 index 0000000..1c398f1 --- /dev/null +++ b/mazes.asd @@ -0,0 +1,14 @@ +;;;; mazes.asd + +(asdf:defsystem #:mazes + :description "Describe mazes here" + :author "Your Name " + :license "Specify license here" + :version "0.0.1" + :serial t + :components ((:file "package") + (:file "mazes") + (:file "grid") + (:file "binary-tree") + (:file "side-winder") + (:file "distances"))) diff --git a/mazes.fossil b/mazes.fossil new file mode 100644 index 0000000..564d8a3 --- /dev/null +++ b/mazes.fossil Binary files differ diff --git a/mazes.lisp b/mazes.lisp new file mode 100644 index 0000000..9be1340 --- /dev/null +++ b/mazes.lisp @@ -0,0 +1,109 @@ +;;;; mazes.lisp + +(in-package #:mazes) + +(defclass cell () + ((row :initarg :row :reader cell-row) + (col :initarg :col :reader cell-col) + (north :initarg :north :initform nil :accessor cell-north) + (south :initarg :south :initform nil :accessor cell-south) + (east :initarg :east :initform nil :accessor cell-east) + (west :initarg :west :initform nil :accessor cell-west) + (links :initform (make-hash-table) :accessor cell-links) + (neighbors-list :initform () :accessor cell-neighbors)) + (:documentation "Defines a single cell in a maze")) + +(defmethod print-object ((obj cell) stream) + (print-unreadable-object (obj stream :type t) + (format stream "Cell(~a,~a)" (cell-row obj) (cell-col obj)))) + +(defgeneric link (cell &key &allow-other-keys) + (:documentation "Links current cell with neighbor cell. If +bidi (bi-directional) is true both cells are updated")) + +(defgeneric unlink (cell &key &allow-other-keys) + (:documentation "Unlinks current cell with neighbor cell. If +bidi (bi-directional) is true both cells are updated")) + +(defgeneric links (cell) + (:documentation "Return the list of all cells connected to given cell.")) + +(defgeneric linked-p (cell &key) + (:documentation "Returns if the current cell is linked to a given cell.")) + +(defgeneric neighbors (cell) + (:documentation "List of cells that adjoin this cell.")) + +(defgeneric cell-distances (cell) + (:documentation "Caluclate distance of each cell from root cell")) + +(defmethod link ((current-cell cell) &key neighbor-cell (bidi t)) + (setf (gethash neighbor-cell (cell-links current-cell)) t) + (when (eql bidi t) + (setf (gethash current-cell (cell-links neighbor-cell)) t))) + +(defmethod unlink ((current-cell cell) &key neighbor-cell (bidi t)) + (remhash neighbor-cell (cell-links current-cell)) + (when (eql bidi t) + (remhash current-cell (cell-links neighbor-cell)))) + +(defmethod links ((current-cell cell)) + (get-hash-keys (cell-links current-cell))) + +(defmethod linked-p ((current-cell cell) &key other-cell) + (gethash other-cell (cell-links current-cell))) + +(defmethod neighbors ((current-cell cell)) + (when (and (cell-north current-cell) (not (find (cell-north current-cell) (cell-neighbors current-cell)))) + (push (cell-north current-cell) (cell-neighbors current-cell))) + + (when (and (cell-south current-cell) (not (find (cell-south current-cell) (cell-neighbors current-cell)))) + (push (cell-south current-cell) (cell-neighbors current-cell))) + + (when (and (cell-east current-cell) (not (find (cell-east current-cell) (cell-neighbors current-cell)))) + (push (cell-east current-cell) (cell-neighbors current-cell))) + + (when (and (cell-west current-cell) (not (find (cell-west current-cell) (cell-neighbors current-cell)))) + (push (cell-west current-cell) (cell-neighbors current-cell))) + + (cell-neighbors current-cell)) + +#| +(defmethod distances ((root cell)) + ((let ((distances (make-distance root)) + (frontier '(root)) + (new-frontier ())) + ; DO..UNTIL frontier is empty + (do () ((null frontier) ()) + (mapcar #'(lambda (x) + (setf x (* x x)) + (+ x 2)) '(1 2 3)))))) +|# + +(defmethod cell-distances ((root cell)) + (let ((distance (make-distance root)) + (frontier `(,root)) + (new-frontier ())) + (do () ((null frontier) ()) + (mapcar #'(lambda (cell) + (mapcar #'(lambda (linked) + (format t "mapcar2: ~a~%" linked) + (when (distance-cell linked) + (setf (distance-cell linked) (incf (distance-cell linked))))) + (links cell)) + (format t "~a" cell) + (setf frontier ())) + frontier)))) +;; +;; cell constructor +;; +(defun make-cell (row col) + (make-instance 'cell :row row :col col)) + + + +;; +;; Util functions +;; +(defun get-hash-keys (hash-table) + (loop for key being the hash-keys of hash-table collect key)) diff --git a/package.lisp b/package.lisp new file mode 100644 index 0000000..a8bed49 --- /dev/null +++ b/package.lisp @@ -0,0 +1,4 @@ +;;;; package.lisp + +(defpackage #:mazes + (:use #:cl)) diff --git a/side-winder.lisp b/side-winder.lisp new file mode 100644 index 0000000..dd985cd --- /dev/null +++ b/side-winder.lisp @@ -0,0 +1,43 @@ +(in-package :mazes) + +(defclass sidewinder () + ((grid :initarg :grid :reader sidewinder-grid))) + +(defmethod initialize-instance :after ((sw sidewinder) &key) + (let* ((grid (sidewinder-grid sw)) + (matrix (grid-matrix grid)) + (rows (grid-rows grid)) + (cols (grid-cols grid)) + (run ()) + (cell ()) + (member ()) + (at-eastern-boundary nil) + (at-northern-boundary nil) + (should-close-out nil)) + (dotimes (r rows) + (setf run ()) + (dotimes (c cols) + (setf cell (aref matrix r c)) + (setf run (append run `(,cell))) + (if (null (cell-east cell)) + (setf at-eastern-boundary t) + (setf at-eastern-boundary nil)) + (if (null (cell-north cell)) + (setf at-northern-boundary t) + (setf at-northern-boundary nil)) + + (setf should-close-out + (or at-eastern-boundary + (equal 0 + (and (not at-northern-boundary) (random 2))))) + (if should-close-out + (progn + (setf member (elt run (random (length run)))) + (when (cell-north member) (link member :neighbor-cell (cell-north member))) + (setf run ())) + ; else + (link cell :neighbor-cell (cell-east cell))))) + grid)) + +(defun make-sidewinder (grid) + (make-instance 'sidewinder :grid grid))