Failed attempt at the exercise level 3.1 “Find the Access Codes“ from Google's Foobar challenge.

google_foobar-3_1_find_the_access_codes.py

#!/usr/bin/env python2.7

"""Find the Access Codes

In order to destroy Commander Lambda's LAMBCHOP doomsday device, you'll need
access to it. But the only door leading to the LAMBCHOP chamber is secured with
a unique lock system whose number of passcodes changes daily. Commander Lambda
gets a report every day that includes the locks' access codes, but only she
knows how to figure out which of several lists contains the access codes. You
need to find a way to determine which list contains the access codes once
you're ready to go in.

Fortunately, now that you're Commander Lambda's personal assistant, she's
confided to you that she made all the access codes "lucky triples" in order to
help her better find them in the lists. A "lucky triple" is a tuple (x, y, z)
where x divides y and y divides z, such as (1, 2, 4). With that information,
you can figure out which list contains the number of access codes that matches
the number of locks on the door when you're ready to go in (for example, if
there's 5 passcodes, you'd need to find a list with 5 "lucky triple" access
codes).

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 < j < 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.

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.

Note
----
    This solution won't pass the test because deemed too slow.
"""

from bisect import insort_left
from itertools import combinations


def answer(l):
    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 < 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

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

_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()

Hi Christopher,

Here's a solution that passed all 5 tests, it's way slower than yours on average, but solves the worst case in 0.5 seconds.
I think the key is that it's done in a single pass so it stays at O(n^2), where as the pairs approach can have a worse performance if number of pairs is large enough.

def answer(l):
    count = 0
    size = len(l)
    if size < 3: return 0

    cache = [0] * size
    for x in xrange(size):
        for y in xrange(x + 1, size):
            if l[y] % l[x] == 0:
                cache[y] += 1
                count += cache[x]

    return count

Hi Serguei, thanks for sharing this solution, it's a relief to finally know what I was missing to pass the test!

I was kinda hoping for something else though—it's a bit sad to see that I've been misled all this time thinking that I had to somehow figure out a blazingly fast algorithm, haha. That's my bad anyways—I initially did implement more “naive” solutions but still couldn't think of using such a shortcut like you did to count the triples, nice one!

Anyhow, good job man and keep rockin' these challenges! :)

I eventually got this, which did pass all the tests and run-time requirement by Google. :)
Just as fast as Serguei's on [1] * 2000. Took some ~30s to run 100 samples though. LOL

def answer(l):    
    col, row = [], []
    for i in range(1, len(l)):
        col.append(sum([1 if (l[i]%l[q]==0) else 0 for q in range(i)]))
        row.append(sum([1 if (l[q]%l[i]==0) else 0 for q in range(i+1, length)]))
        
    return sum([a*b for a,b in zip(col, row)])

Nice one! Also thanks for contributing in making me feel even dumber than what I thought :P
Best wishes for the rest of the challenges, have fun!

Just got passed, figured out a very straightforward method. The key here is to loop through the seconde number in the triple.

def answer(l):
    if len(l) < 3:
        return 0

    cnt = 0
    for i in range(1, len(l) - 1):
        cnt_x = len([x for x in l[:i] if l[i] % x == 0])   # Count possible x in (x, y, z)
        cnt_z = len([z for z in l[i + 1:] if z % l[i] == 0])   # Count possible z in (x, y, z)

        cnt += cnt_x * cnt_z  # Possible combination should be the product
    return cnt

Edding, the solution was absolutely correct.

I eventually got this, which did pass all the tests and run-time requirement by Google. :)
Just as fast as Serguei's on [1] * 2000. Took some ~30s to run 100 samples though. LOL

def answer(l):    
    col, row = [], []
    for i in range(1, len(l)):
        col.append(sum([1 if (l[i]%l[q]==0) else 0 for q in range(i)]))
        row.append(sum([1 if (l[q]%l[i]==0) else 0 for q in range(i+1, length)]))
        
    return sum([a*b for a,b in zip(col, row)])

how did you managed to make 100 test cases??

Why is my Solution not working? It is passing 4/5 tests

def solution(l):
  if len(l)<3:
    return 0
  sols=0
  l=np.array(l)
  for i in range(len(l)-2):
    n1=l[i]
    l1=l[i+1:]
    l1=l1[l1%n1==0]
    for x in range(len(l1)-1):
      n2=l1[x]
      l2=l1[x+1:]
      sols += np.sum(l2%n2==0)
  return sols

I'm getting 4/5 as well. I think the longer you find the bug, the sillier it gets.

def solution(l):
    possible_ys = []
    result = 0

    for i in range(len(l)):
        for y in possible_ys:
            z = l[i]
            if z % y == 0:
                result += 1

        possible_xs = l[:i]
        for x in possible_xs:
            y = l[i]
            if y % x == 0:
                possible_ys.append(y)

    return result

@DhruvDutta Did you find out why? I have a feeling (like someone mentioned) there is a hidden time constraint.