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

I felt like exploring this challenge... this solution passes your tests by avoiding the modulus operation sometimes. Unfortunately there's no way to test if it is fast enough, though.

import itertools

from collections import defaultdict

def answer(l):    
    result = 0

    n = len(l)

    divides = defaultdict(list)

    for i, v in enumerate(l[:-1]):
        for j, nv in enumerate(itertools.islice(l, i + 1, n), i + 1):                        
            if isFactorOf(nv, v):
                divides[j].append((v, i))

    numDivisors = { k: len(v) for k, v in divides.iteritems() }

    for i in xrange(n - 1, -1, -1):                
        if not i in divides:
            continue

        val = l[i]

        for (v, vi) in divides[i]:            
            if vi in divides:
                result += numDivisors[vi]

    return result

def isFactorOf(n, m):
    if n == m:
        return True

    if n - m < m:
        return False

    return n % m == 0

Cool @yantor3d! It indeed pass the tests but it's a bit slower—for 100 samples my code takes ~0.25 s on my laptop while your version runs in ~15 s.

Modulos seems to be quite expensive operations, which is why I decided to avoid them as much as possible by retrieving the multiples of a number instead of retrieving the divisors. The main issue remaining in my version is, I believe, the nested loops.

I have updated the code so the benchmark doesn't rely on a JSON file cache of the samples. Plus it now should generate the same samples for everyone based on a fixed seed. It's just a tad slower to initialize but it shouldn't affect the timings.

Hi Christopher,
Your solution really gets some incredible performance on average but unfortunately it doesn't do well in worst case scenario and I believe that is why it didn't pass.

Worst case test would be [1] * 2000, in this case you end up with 2000 - i pairs per iteration so performance is completely degraded.

Hi Serguei, thanks for contributing!

I thought about such worst-case scenarios but decided to discard the idea because I considered them to be “unrealistic”. Indeed, there wouldn't be much value for Commander Lambda in coming up with such a fancy algorithm to hide the passcodes of the day if the generated numbers were so dull, right?? :) But who knows, you could be right—it would be nice if I still had access to the test to try out a new solution while keeping this in mind.

On a side note, I found a question recently posted on StackOverflow where I guess that the accepted answer has been accepted because passing the test but, when converting the algorithm to Python, it ends up running 50x slower than my version above. And it doesn't seem to efficiently deal with such worst-case scenarios neither. Maybe the solution was just a matter of using Java for performance-critical code!

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.