Google Foobar Challenge 3 - Find the Access Codes
<h1>Find the Access Codes</h1>

<p>Write a function answer(l) that takes a list of positive integers l and counts the number of "lucky triples" of (lst[i], lst[j], lst[k]) where i &lt; j &lt; k.  The length of l is between 2 and 2000 inclusive.  The elements of l are between 1 and 999999 inclusive.  The answer fits within a signed 32-bit integer. Some of the lists are purposely generated without any access codes to throw off spies, so if no triples are found, return 0. </p>

<p>For example, [1, 2, 3, 4, 5, 6] has the triples: [1, 2, 4], [1, 2, 6], [1, 3, 6], making the answer 3 total.</p>

<h1>Test cases</h1>

<p>Inputs:
    (int list) l = [1, 1, 1]
Output:
    (int) 1</p>

<p>Inputs:
    (int list) l = [1, 2, 3, 4, 5, 6]
Output:
    (int) 3</p>

<h1>My Attempt</h1>

<pre><code>from itertools import combinations

def answer(l):
    if len(l) &lt; 3:
        return 0
    found = 0
    for val in combinations(l,3):
        # Ordering Check
        if (val[0] &lt;= val[1] &lt;= val[2]) != True:
            continue
        # Answer Size Check against size of signed integer 32 bit
        if int(val[0].__str__() + val[1].__str__() + val[2].__str__()) &gt; 2147483647:
            continue
        # Division Check
        if (val[1] % val[1] != 0) or (val[2] % val[1] != 0):
            continue
        # Increment 'found' variable by one
        found += 1
    return found
</code></pre>

<p>I tried implementing this in python. It isn't quite fast enough to pass the test, but it runs 50x faster then uoyilmaz's solution ported to python. The code for that is below:</p>

<pre><code>#!/usr/bin/env python2.7

from bisect import insort_left
from itertools import combinations


def answer_1(l):
    """My own solution."""
    indices = {}
    setdefault_ = indices.setdefault
    for i, x in enumerate(l):
        setdefault_(x, []).append(i)

    out = 0
    highest_value = max(l)
    for i, x in enumerate(l):
        multiples = []
        for m in xrange(1, int(highest_value / x) + 1):
            if x * m in indices:
                for j in indices[x * m]:
                    if i &lt; j:
                        insort_left(multiples, (j, x * m))

        if multiples:
            multiples = [m[1] for m in multiples]
            for pair in combinations(multiples, 2):
                out += pair[1] % pair[0] == 0

    return out


def answer_2(l):
    """@uoyilmaz's solution ported from Java."""
    out = 0
    pair_counts = [0] * len(l)
    for i in xrange(1, len(l) - 1):
        for j in xrange(i):
            if l[i] % l[j] == 0:
                pair_counts[i] += 1

    for i in xrange(2, len(l)):
        for j in xrange(1, i):
            if l[i] % l[j] == 0:
                out += pair_counts[j]

    return out


answer = answer_1

# -----------------------------------------------------------------------------

_SEED = 1.23


def benchmark(sample_count):
    from random import seed, randint
    import timeit
    clock = timeit.default_timer

    seed(_SEED)
    samples = [[randint(1, 999999) for _ in xrange(randint(2, 2000))]
                for _ in xrange(sample_count)]

    start = clock()
    for sample in samples:
        answer(sample)

    end = clock()
    print("%.4f s elapsed for %d samples." % (end - start, sample_count))


def test():
    # Provided test cases.
    assert(answer([1, 1, 1]) == 1)
    assert(answer([1, 2, 3, 4, 5, 6]) == 3)

    # Custom test cases.
    assert(answer([1]) == 0)
    assert(answer([1, 2]) == 0)
    assert(answer([2, 4]) == 0)
    assert(answer([1, 1, 1, 1]) == 4)
    assert(answer([1, 1, 1, 1, 1]) == 10)
    assert(answer([1, 1, 1, 1, 1, 1]) == 20)
    assert(answer([1, 1, 1, 1, 1, 1, 1]) == 35)
    assert(answer([1, 1, 2]) == 1)
    assert(answer([1, 1, 2, 2]) == 4)
    assert(answer([1, 1, 2, 2, 2]) == 10)
    assert(answer([1, 1, 2, 2, 2, 3]) == 11)
    assert(answer([1, 2, 4, 8, 16]) == 10)
    assert(answer([2, 4, 5, 9, 12, 34, 45]) == 1)
    assert(answer([2, 2, 2, 2, 4, 4, 5, 6, 8, 8, 8]) == 90)
    assert(answer([2, 4, 8]) == 1)
    assert(answer([2, 4, 8, 16]) == 4)
    assert(answer([3, 4, 2, 7]) == 0)
    assert(answer([6, 5, 4, 3, 2, 1]) == 0)
    assert(answer([4, 7, 14]) == 0)
    assert(answer([4, 21, 7, 14, 8, 56, 56, 42]) == 9)
    assert(answer([4, 21, 7, 14, 56, 8, 56, 4, 42]) == 7)
    assert(answer([4, 7, 14, 8, 21, 56, 42]) == 4)
    assert(answer([4, 8, 4, 16]) == 2)


def main():
    test()
    benchmark(100)


if __name__ == '__main__':
    main()
</code></pre>

<p>Now if anyone has an idea on how to speed this up further, I'm open for suggestions.</p>

java python combinations