zero wrote:P(5)=18,651,552,840
(defparameter *invertor* (vector 1 0))
(defun count-paths (so-far target)
(declare (optimize (speed 3) (safety 0)))
(let ((dims (length (car so-far)))
(cur (car so-far)))
(if (equalp cur target)
1
(do ((ii 0 (1+ ii))
(sum 0))
((= ii dims) sum)
(let ((next (copy-seq cur)))
(setf (elt next ii) (elt *invertor* (elt next ii)))
(unless (member next so-far :test #'equalp)
(push next so-far)
(incf sum (count-paths so-far target))
(pop so-far)))))))
(defun cube-vector (nn &rest dirs)
(let ((ret (make-array nn :initial-element 0)))
(dolist (dd dirs)
(setf (elt ret dd) 1))
ret))
(defun count-paths-in-n-dimensions (nn)
(let ((c000 (cube-vector nn))
(goal (make-array nn :initial-element 1)))
(if (>= nn 3)
(let ((c000 (cube-vector nn))
(c001 (cube-vector nn 0))
(c011 (cube-vector nn 0 1))
(c010 (cube-vector nn 1))
(c110 (cube-vector nn 1 2))
(c111 (cube-vector nn 0 1 2)))
(+
(* nn (- nn 1) (- nn 2)
(count-paths (list c111 c011 c001 c000) goal))
(* nn (- nn 1) (- nn 2)
(count-paths (list c110 c010 c011 c001 c000) goal))))
(count-paths (list c000) goal))))
(do ((ii 1 (1+ ii)))
((> ii 5))
(format t "~a-d = ~a~%" ii (count-paths-in-n-dimensions ii)))
Return to Where Should I Post This?
Users browsing this forum: No registered users and 34 guests