47 lines
1.7 KiB
Common Lisp
47 lines
1.7 KiB
Common Lisp
;;; Approach: the 3 candidate shortest paths are just selecting the
|
|
;;; dimension that is one full side of the shortest path right
|
|
;;; triangle, with the sum of the other two lengths being the other
|
|
;;; side of the right triangle. This triangle needs to have a perfect
|
|
;;; square as the hypotenuse, as per the problem statement.
|
|
|
|
(defun square (n)
|
|
"Returns the square of N"
|
|
(* n n))
|
|
|
|
(let ((max-root 0)
|
|
(max-square 0)
|
|
(squares (make-hash-table)))
|
|
(defun squarep (n)
|
|
"Returns non-NIL if N is a perfect square, tracking all squares in a hash set"
|
|
(when (> n max-square)
|
|
(loop for i upfrom (1+ max-root)
|
|
for square = (square i)
|
|
do (setf (gethash square squares) t)
|
|
(setf max-root i)
|
|
(setf max-square square)
|
|
(when (>= square n)
|
|
(return))))
|
|
(gethash n squares)))
|
|
|
|
(defun integer-shortest-path-p (width height depth)
|
|
"Returns non-NIL if a cuboid of the given dimensions's shortest path is an integer"
|
|
;; Try each of the 3 shortest path combinations
|
|
(let ((min-square (min (+ (square width) (square (+ height depth)))
|
|
(+ (square height) (square (+ width depth)))
|
|
(+ (square depth) (square (+ height width))))))
|
|
(squarep min-square)))
|
|
|
|
(defun cuboid-route (&optional (min-solutions 1000000))
|
|
;; Order dimensions descending to avoid double-counting rotations
|
|
(loop with sum = 0
|
|
for width upfrom 1
|
|
do ;; Note that WIDTH is the max dimension, i.e. M, so just
|
|
;; keep adding until reaching the desired total
|
|
(incf sum (loop for height from 1 upto width
|
|
sum (loop for depth from 1 upto height
|
|
sum (if (integer-shortest-path-p width height depth)
|
|
1
|
|
0))))
|
|
(when (> sum min-solutions)
|
|
(return width))))
|