# # 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)