#
# Copyright (C) 2004 Marco Wahl
#
# No warranty.
#
"""
Call:
python trianglecount.py
Output:
E.g.
python trianglecount.py 2 2
returns 27.
This module has its root at the Triangle Challenge, found by accident
on the web.
Scenario:
Let there be a triangle with a base-side with the endpoints left- and
right-base-point and a left and a right side.
There can be points on the left and/or the right side.
Obtain a net of lines by drawing the lines between the points on the
right side and the left-base-point and the lines between the points
on the left side and the right-base-point.
A triangle of interest is one that can be found in the net.
Question:
How many triangles of interest are there?
Observation:
There are three kinds of triangles of interest.
1. The triangle has the base a side.
2. The triangle shares the left base-side-vertex with the base-side
and nothing else.
3. The triangle shares the right base-side-vertex with the base-side
and nothing else.
Algorithm: count(L, R)
----------
L: number of points on the left (excluding the top-point)
R: number of points on the right (excluding the top-point)
count(0, 0) = 1
R > 0:
count(0, R) = count(0, R-1) + no of those who use the top line
= R + 1 + count(0, R-1)
= (R + 1) + R + ... + 1
= (R + 1)*(R + 2)/2
l > 0:
count(L, 0) = count(0, L)
L, R > 0:
count(L, R) = count(L, R-1)
+ #{no fo those who use any part of the left-side}
+ #{no of those including the upmost part on the right side but not use the left part}
= count(L, R-1)
+ #{no fo those who use any part of the left-side, type 1.}
+ #{no fo those who use any part of the left-side, type 2.}
+ #{no fo those who use any part of the left-side, type 3.}
+ 0
= count(L, R-1)
+ L + 1
+ R*(L + 1)
+ count(L-1, 0)
"""
def count(le, ri):
"See the modules documentation for documentation."
if (0, 0) == (le, ri):
return 1
elif 0 == le:
return ri + 1 + count(le, ri - 1)
elif 0 == ri:
return count(ri, le)
else:
return count(le, ri - 1) \
+ le + 1 \
+ ri * (le + 1) \
+ count(le - 1, 0)
import sys
left, right = int(sys.argv[1]), int(sys.argv[2])
print "Number of triangles: ", count(left, right)