(defparameter *lines* '((p0 p5 p8 p10) (p0 p3 p7 p9) (p0 p2 p4 p6) (p0 p1) (p1 p2 p3 p5) (p1 p4 p7 p8) (p1 p6 p9 p10)) "The lines in the figure. Each list corresponds to one line, with the member symbols being the points on that line.") (defparameter *points* (delete-duplicates (loop for l in *lines* append l) :test #'eq) "The points in the figure. Generated from *lines*.") (defun symbol< (sym1 sym2) "Ordering predicate for symbols, based on SYMBOL-NAME." (string< (symbol-name sym1) (symbol-name sym2))) (defun canonicalize (triangle) "Return a \"canonical\" representation of the triangle." (sort triangle #'symbol<)) (defun on-line-p (point line) "True if point is on line." (member point line :test #'eq)) (defun collinear-p (point1 point2 point3) "True if all three points are on the same line." (some (lambda (line) (and (on-line-p point1 line) (on-line-p point2 line) (on-line-p point3 line))) *lines*)) (defun find-endpoints (fixed-point) "Find all the \"other\" endpoints of lines starting at fixed-point." (loop for line in *lines* when (on-line-p fixed-point line) nconc (remove fixed-point line))) (defun find-all-triangles (point) "Find all triangles with point as one apex." (loop with endpoints = (find-endpoints point) for point2 in endpoints for endpoints-2 = (find-endpoints point2) nconc (loop for point3 in (intersection endpoints endpoints-2) unless (collinear-p point point2 point3) collect (canonicalize (list point point2 point3))))) (defun find-triangles () "Return a list of all triangles based on *lines*." (delete-duplicates (mapcan #'find-all-triangles *points*) :test #'equal)) ;; Actually, due to the nature of the figure we only need to call ;; find-all-triangles on p0 and p1. This makes the solution more ;; efficient but less general. (defun find-triangles-2 () "Return a list of all triangles based on *lines*." (delete-duplicates (mapcan #'find-all-triangles '(p0 p1)) :test #'equal))