gistfile1.txt

"""
https://www.reddit.com/r/lpmc/comments/2eblaq/challenge_list_of_numbers_0_valid_triangles/
author: wei2912

This solution assumes that the values can be taken from the list with 
replacement and the order of the side lengths matter.

To determine if a triangle is valid, the sum of each 2 sides must be greater 
than the other side.

We'll assume that for every tuple `(a, b, c)`, `a <= b <= c`.
"""

"""
It's easy to write the naive solution which has a time complexity of ~n^3.

This solution loops through the list 3 times and checks if the combination 
gives a valid triangle.

"""
def triangles_naive(lst):
    results = []
    for a in lst:
        for b in lst:
            for c in lst:
                # when a <= b <= c
                # a+c > b and b+c > a will always hold true.
                # we just need to check for a+b > c
                if a <= b and b <= c and a+b > c:
                    results.append((a, b, c))
    return results

"""
Since a <= b and b <= c, we can reduce our searching space if the list is sorted.

Take the following list:
[1, 2, 3, 4, 5, 6]

If a = 2, we know that b >= 2 and can continue to iterate from the index of a.
If b = 5, we know that c >= 5 and can continue to iterate from the index of b.

The time complexity of the algorithm is:

  sum_(i=1)^n(sum_(j=i)^n(sum_(k=j)^n C))
= 1/6 C n (n^2 + 3n + 2)

which is somewhat faster than the previous algorithm.

"""
def triangles_better_naive(lst):
    assert(sorted(lst))

    results = []
    for i in xrange(len(lst)):
        a = lst[i]
        for j in xrange(i, len(lst)):
            b = lst[j]
            for k in xrange(j, len(lst)):
                c = lst[k]
                if a+b > c:
                    results.append((a, b, c))
    return results

"""
If we know a and c, we can truncate our search space even further.

Take the following list:
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

For a = 3 & c = 9, we know that:

  a+b > c and b <= c
  c-a < b <= c
  6 < b <= c

With this knowledge we could speed up our algorithm if there was a way
to find all values within this range.

Since we know the indices of the variable c, we can move backwards till
the inequality no longer holds true. By doing so, we get all the possible
values of b.

As this algorithm only goes through the elements of the list which the
combination is valid, we can conclude that this algorithm is optimal.

The worst time complexity is:

  sum_(i=1)^n(sum_(j=i)^n(sum_(k=i)^j C))
= 1/6 C n(n^2 + 6n + 5)

which is worse than the previous.

However, in most cases, this algorithm should run faster.
"""
def triangles_smart(lst):
    assert(sorted(lsts))

    results = []
    for i in xrange(len(lst)):
        a = lst[i]
        for j in xrange(i, len(lst)):
            c = lst[j]

            # iterating backwards, from j to i.
            for k in xrange(j, i-1, -1):
                b = lst[k]
                if c-a >= b:
                    # all values from this point onwards
                    # will not satisfy the inequality
                    break
                results.append((a, b, c))
    return results

"""
Time for some benchmarking...
"""

if __name__ == '__main__':
    import timeit
    print(timeit.timeit(
        'triangles_naive(range(1, 200))',
        setup='from __main__ import triangles_naive',
        number=10
    ))
    print(timeit.timeit(
        'triangles_better_naive(range(1, 200))',
        setup='from __main__ import triangles_better_naive',
        number=10
    ))
    print(timeit.timeit(
        'triangles_smart(range(1, 200))',
        setup='from __main__ import triangles_smart',
        number=10
    ))

"""
wei2912@localhost ~> python triangles.py 
6.79532504082
2.54251599312
1.8894469738

Benchmarks may vary on different systems.
"""