Skip to content

Instantly share code, notes, and snippets.

@christophercrouzet

christophercrouzet/google_foobar-3_1_find_the_access_codes.py

Last active June 12, 2023 23:41
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save christophercrouzet/421fc9bdf646c93d099c109d6740cea1 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save christophercrouzet/421fc9bdf646c93d099c109d6740cea1 to your computer and use it in GitHub Desktop.
Download ZIP
Failed attempt at the exercise level 3.1 “Find the Access Codes“ from Google's Foobar challenge.
Raw
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()
@rejoycesong
Copy link

rejoycesong commented Jan 3, 2017 •
edited
Loading

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

@christophercrouzet
Copy link
Author

christophercrouzet commented Jan 5, 2017 •
edited
Loading

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!

@edding
Copy link

edding commented Feb 16, 2017

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

@Rishikesh-12
Copy link

Rishikesh-12 commented May 27, 2020

Edding, the solution was absolutely correct.

@edusanketdk
Copy link

edusanketdk commented Jun 30, 2020

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??

@DhruvDutta
Copy link

DhruvDutta commented Apr 12, 2022 •
edited
Loading

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

@Hunkoys
Copy link

Hunkoys commented Nov 16, 2022 •
edited
Loading

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

@Hunkoys
Copy link

Hunkoys commented Nov 16, 2022

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

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment