-- count triadic couplings in a special set of edges.
-- Idea: three edges form a "triangle" iff they aren't linearly
-- dependent and if they connect exactly three points. This implies
-- an enclosed area > 0. (See the function procedure dep.)
program triads;
read(F); -- input F, a set of edges
-- F is like E, see below, which is the set of 11 - 2 points as
-- explained on http://www.frank-buss.de/challenge/index.html,
-- The program computes the Euclidean stuff like "What is the
-- fraction of the projection of P2 onto the y-axis of the
-- projection of P6 on the y-axis", but only as auxiliary
-- expressions, not in a core algorithm, which depends
-- on the representation of lines as sets of pairs.
-- (Apologies, I'm a mathematically challenged person...)
-- Measurement, height and width step 1:
--
-- 4
-- 3 5
-- 2 6
-- 1 7
E := { -- sets of connected points, each representing a line
{[1,1], [7,1]},
{[1,1], [6,2]},
{[1,1], [5,3]},
{[1,1], [4,4]},
{[1,1], [3,3]},
{[1,1], [2,2]},
{[2,2], [7,1]},
{[2,2], [2,4]},
{[2,2], [3,3]},
{[3,3], [7,1]},
{[3,3], [4,4]},
{[4,4], [7,1]},
{[4,4], [6,2]},
{[4,4], [5,3]},
{[5,3], [7,1]},
{[5,3], [6,2]},
{[6,2], [7,1]},
-- points in the middle, computed so they match the
-- graph on the web page
{[1,1], [4, 3/5.0]}, -- ht(P6) / 5 = ht(P2) / 3, see measure
{[4, 3/5.0], [7,1]}, -- line (P2, P1), similarly
{[1,1], [4, 3/2.0]},
{[4, 3/2.0], [7,1]}, -- (P7, P1)
-- P3 and P4 missing
};
assert( #(+/{line: line in E}) = 9 );
-- there are 9 points in the union of all sets in E
tri := {l3: l3 in 3 npow E | #(+/l3) = 3 and not dep((+/l3))};
-- set of all subsets of E of size 3, i.e. three line sets,
-- such that the ends of lines in l3 are connecting a total of
-- 3 points, not all on a straight line
print(#tri);
-- done, output is number of elements of "three liners"
-- enclosing an area
-- ad lib: print all triangles found:
for dbg in tri loop
print(dbg);
end loop;
procedure dep(triset);
-- three points in a line?
-- (a c)(x) = (e)
-- (b d)(y) = (f)
[a,b] from triset;
[c,d] from triset;
[e,f] from triset;
return a*(f - d) + b*(c - e) = 0;
end dep;
end triads;