Some days back, I had come across this at Slashdot. On Sunday, I had nothing better to do and I decided to give it a shot. It was easy. Took me some 10 minutes to come up with a brute-force algorithm and and another 20 minutes to implement it in perl. Today morning I tried doing it in Python and it looked so much better.
The algorithm is simple:
1) Find out all the possible vertex-triplets. In mathematical lingo, it is nCr.
2) For each triplet, confirm that all the vertices are not on the same line.
3) For each triplet, confirm that a line exits between first and second vertex
4) For each triplet, confirm that a line exits between first and third vertex.
5) For each triplet, confirm that a line exits between third and second vertex.
6) if all the criteria are matched then the triangle exists.
Simple, isnt it?
Heres the python solution:
#!/usr/bin/python2.3
same_line = 0
ab = 0
bc = 0
ac = 0
vertex = ["p0","p1","p2","p3","p4","p5","p6","p7","p8","p9","p10"]
line = {1:["p0","p5","p8","p10"], 2:["p1","p6","p9","p10"], 3: ["p0","p1"],
4:["p1","p2","p3","p5"], 5:["p1","p4","p7","p8"], 6:["p0","p3","p7","p9"],
7:["p0","p2","p4","p6"]}
for a in vertex:
for b in vertex[vertex.index(a)+1:]:
for c in vertex[vertex.index(b)+1:]:
for lines in line.items():
if a in lines[1] and b in lines[1] and c in lines[1]: same_line = 1
if a in lines[1] and b in lines[1]: ab = 1
if b in lines[1] and c in lines[1]: bc = 1
if c in lines[1] and a in lines[1]: ac = 1
if ab == 1 and bc == 1 and ac == 1 and same_line == 0: print a,b,c
same_line = 0
ab = 0
bc = 0
ac = 0
Yours Sinerely,
