;;; We need a representation for the figure ;;; It strikes me as pretty arbitary what ;;; lines are in, and which omitted, so ;;; I fancy entering the figure into the ;;; program as a list of lines. (defvar figure '((p0 p5 p8 p10) (p0 p3 p7 p9) (p0 p2 p4 p6) (p0 p1) (p10 p9 p6 p1) (p8 p7 p4 p1) (p5 p3 p2 p1))) (defvar nodes (remove-duplicates (apply #'append figure))) ;;; I'm going to need a predicate to tell if ;;; a figure is a triangle (defun triangle-p (a b c) (and (line a b) (line b c) (line c a) (not (co-linear a b c)))) (defun line (x y) (dolist (line figure nil) (if (and (member x line) (member y line)) (return-from line t)))) (defun co-linear (a b c) (dolist (line figure nil) (if (and (member a line) (member b line) (member c line)) (return-from co-linear t)))) ;;; Now I can attempt the puzzle (defun solve1 () (let ((count 0)) (dolist (i nodes) (dolist (j nodes) (dolist (k nodes) (when (triangle-p i j k) (incf count))))) count)) ;;; That counts every triangle 6 times (defun solve2 () (do ((count 0) (i nodes (cdr i))) ((endp i) count) (do ((j (cdr i) (cdr j))) ((endp j)) (do ((k (cdr j) (cdr k))) ((endp k)) (when (triangle-p (car i) (car j) (car k)) (incf count)))))) ;;; That gets me 27 in 25 minutes coding time ;;; but fixing it this way, instead of ;;; just dividing by six, has spoiled the ;;; look of my code ;;; I want #| (docarlist (x y '(a b c)) (format t "~&~A ~A." x y)) to print A (B C). B (C). C NIL. |# (defmacro docarlist ((head-var tail-var list-form) &body code) (let ((list-var (gensym "LIST"))) `(do ((,list-var ,list-form (cdr ,list-var)) ,head-var ,tail-var) ((endp ,list-var)) (setq ,head-var (car ,list-var) ,tail-var (cdr ,list-var)) ,@code))) (defun solve3 () (let ((count 0)) (docarlist (x after-x nodes) (docarlist (y after-y after-x) (dolist (z after-y) (when (triangle-p x y z) (incf count))))) count)) ;;; 39 minutes, (solve3) => 27 triangles. ;;; Whoops, I missed #| (loop for (x . y) on '(a b c) do (format t "~a ~A~%" x y)) A (B C) B (C) C NIL => NIL |# ;;; I should have just written (defun solve4 () (loop with count = 0 for (x . after-x) on nodes do (loop for (y . after-y) on after-x do (loop for z in after-y when (triangle-p x y z) do (incf count))) finally (return count))) ;;; which brings it up to 49 minutes coding, ;;; but still 27 triangles.