(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.
|#