-
-
Save christophercrouzet/421fc9bdf646c93d099c109d6740cea1 to your computer and use it in GitHub Desktop.
| #!/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. LOLdef 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.
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!