(defun count-triangles (filename) (multiple-value-bind (points lines) (read-triangle-file filename) (/ (loop for p in points sum (loop for q in points sum (loop for r in points count (is-triangle p q r lines)))) 6))) (defun is-triangle (p q r lines) (let ((lp (gethash p lines)) (lq (gethash q lines)) (lr (gethash r lines))) (and (intersection lp lq) (intersection lp lr) (intersection lq lr) (not (intersection (intersection lp lq) lr))))) (defun read-triangle-file (filename) (let ((points nil) (lines (make-hash-table))) (with-open-file (f filename :direction :input) (loop for id upfrom 0 for line = (read f nil nil) while line do (loop for v in line do (pushnew v points) (pushnew id (gethash v lines))))) (values points lines))) #| Input file for your sample problem: (p0 p5 p8 p10) (p0 p3 p7 p9) (p0 p2 p4 p6) (p0 p1) (p1 p6 p9 p10) (p1 p4 p7 p8) (p1 p2 p3 p5) Vertex names should be things that Lisp will treat as literals that can safely be compared using EQL. That includes, e.g., anything that would be a legal identifier in languages like C; it also includes numbers. This isn't a very efficient program; there are several ways in which it could be improved. But I'm lazy :-). There aren't any comments because I was trying to write the code quickly (seeing the list of solutions I thought "I'm sure I could solve this faster than that"), but here's a brief description of what's going on: we number the input lines (as in "lines of points", not as in "lines of text") and build a map LINES saying which lines a point is on. Then three points form a triangle if each pair has a line in common; it's degenerate if all three have a line in common. We count triangles in the simplest possible way: run through all triples (p,q,r) of points and see whether each one is a triangle. This counts each triangle 3!=6 times, so we need to divide the result by 6. The only other possibly unfamiliar thing is the (READ F NIL NIL) bit. The first NIL means "EOF isn't an error". The second means "return NIL at end of file". This means that an empty "line" in the input will make it stop reading, which seems OK to me. |#