Google Foobar Challenge: Lucky Triples

Question

Note: Since my time has passed for this challenge, I do not remember exactly the stipulations but will attempt to recapitulate them to the best of my knowledge.

Essentially, the challenge was this:

Given a list (from 1 to 2000 elements) of random integers (from 1 to 999999) write a function, answer(l) that accepts a list as input and returns the number of "lucky triples" present in the list.

For this purpose, a lucky triple is defined as a list of three numbers \$(x, y, z)\$ such that \$x\$ divides \$y\$, \$y\$ divides \$z\$, and \$x \le y \le z\$. So, for instance, \$(2, 4, 8)\$ is a lucky triple and so is \$(1, 1, 1)\$.

Test cases:

input: [1, 1, 1]
ouput: 1

input: [1, 2, 3, 4, 5, 6]
output: 3

Theory

First, a brief explanation about the theory behind my answer. I first noticed that for any list of multiples where each element \$n\$ is a factor of element \$n + 1\$, for example 1, 2, 4, 8, 16, the number of lucky triples in the list is equal to the summation from x = 0 to x = length - 2. So, for the previous example, the number of lucky triples in the list is equal to 3 + 2 + 1 or 6:

• 1, 2, 4
• 1, 2, 8
• 1, 2, 16
• 2, 4, 8
• 2, 8, 16
• 4, 8, 16

My idea, then, was to construct a tree of from the list, each branch representing a list of factors, and record the depth of each branch in the tree. From there, the number of lucky triples in each branch could be readily calculated with sum(). Unfortunately, I was a little too late and can therefore no longer validate my code. I've tested it on rather trivial cases, but have no way of knowing:

1. If my code is optimized;
2. If it returns the correct answer in more intricate examples, say a list from 1 to 2000.

I preemptively apologize for any ambiguity in my explanation - feel free to ask for clarification - (this is the first time I've submitted code for review) as well as for the formatting of my code (if it is not readily comprehensible/Pythonic). But feedback would be much appreciated!

Code

# {{{ Imports

from collections import Counter
from itertools import imap, izip

# }}}

# {{{ LuckyTriples(object)

class LuckyTriples(object):

    # {{{ __init__(self, list_of_random_int)

    def __init__(self, list_of_random_int):
        self._node_pool = set(sorted(list_of_random_int))
        self._tree_space_parents = {}
        self._tree_space_children = {}
        self._roots = []
        self._depths = []
        map(self.build_tree_space, self._node_pool)
        map(self.get_all_roots, self._node_pool)
        for root in self._roots:
            self.embark(root, [1])
        self._lucky_triple_count = 0
        self.enumerate_lucky_triples(list_of_random_int)

    # }}}

    # {{{ build_tree_space(self, node_pool)

    def build_tree_space(self, node):
        parents = self.get_all_parents(node, self._node_pool)
        self._tree_space_parents[node] = parents
        children = self.get_all_children(node, self._node_pool)
        self._tree_space_children[node] = children
        return

    # }}}

    # {{{ get_all_parents(self, node, node_pool)

    def get_all_parents(self, node, node_pool):
        parents = [
                parent for parent in node_pool
                if parent < node and node % parent == 0
                ]
        return parents

    # }}}

    # {{{ get_all_roots(self, node_pool)

    def get_all_roots(self, node):
        parents = self.get_all_parents(node, self._node_pool)
        if not parents:
            self._roots.append(node)
        return

    # }}}

    # {{{ get_all_children(self, node, node_pool)

    def get_all_children(self, node, node_pool):
        children = [
                child for child in node_pool
                if child > node and child % node == 0
                ]
        return children

    # }}}

    # {{{ get_children_to_visit(self, nodes)

    def get_children_to_visit(self, nodes):
        nodes = [
             subbranch for branches in nodes for subbranch in
             branches
             ]
        children_to_visit = []
        for node in nodes:
            immediate_children = set(
                              self._tree_space_children.get(node)
                              )
            descendants = set()
            nodes_to_visit = list(immediate_children)
            while nodes_to_visit:
                node = nodes_to_visit.pop()
                children = self._tree_space_children.get(node)
                descendants.update(children)
            children_to_visit.append(list(
                immediate_children - descendants)
                )
        return children_to_visit

    # }}}

    # {{{ branch_off(self, branches, depths)

    def branch_off(self, branches, depths):
        for subbranch in branches:
            depths.extend(depths[0] for i in 
                range(len(subbranch) - 1)
                )
        return depths

    # }}}

    # {{{ explore_deeper(self, depths)

    def explore_deeper(self, level, depths):
        branches = [node for branch in level for node in branch]
        explore_deeper = [1] * len(branches)
        explore_deeper += [0 for i in 
            range(len(depths) -   len(explore_deeper))
            ]
        new_depths = map(sum, izip(depths, explore_deeper))
        return new_depths

    # }}}

    # {{{ def embark(self, node, depths)

    def embark(self, node, depths):
        nodes_to_visit = [[node]]
        while any(nodes_to_visit):
            children = self.get_children_to_visit(nodes_to_visit)
            depths = self.branch_off(children, depths)
            depths = self.explore_deeper(children, depths)
            nodes_to_visit = children
        self._depths.extend(depths)
        return

    # }}}

    # {{{ enumerate_lucky_triples(self, list_of_random_int)

    def enumerate_lucky_triples(self, list_of_random_int):
        for depth in self._depths:
            tmp = range(1, depth - 1)
            self._lucky_triple_count += sum(tmp)
        multiples = [
                 node for node in list_of_random_int
                 if list_of_random_int.count(node) > 1
                 ]
        multiples = Counter(multiples)
        for multiple in multiples:
            parents = self._tree_space_parents[multiple]
            children = self._tree_space_children[multiple]
            nodes_in_branch = len(parents) + len(children)
            if multiples[multiple] == 2:
                self._lucky_triple_count += nodes_in_branch
            elif multiples[multiple] >= 3:
                self._lucky_triple_count += nodes_in_branch + 1

    # }}}

# }}}

# {{{ answer(l)

def answer(l):
    lock_codes = LuckyTriples(l)
    return lock_codes._lucky_triple_count

# }}}

Answer 1

1. Testing

Let's take a look at your second problem:

I've tested it on rather trivial cases, but have no way of knowing [...] if it returns the correct answer in more intricate examples

A good strategy in this kind of situation, where you have a complex implementation that you are not sure is correct, is to implement a simple and clearly correct (but slow) solution. Then you can generate some test data and compare the outputs of the two implementations.

But before doing that, I have to confront an ambiguity in the problem description: am I supposed to count all the triples satisfying the "lucky" condition, or only the distinct triples? The examples in the problem description don't make this clear. So the only thing I have to go on is your implementation, and you've used the "distinct triples" interpretation:

>>> answer([1, 1, 1, 1])
1

(In the "all triples" interpretation, the result here would be 4.)

So, back to writing a slow-but-correct implementation. Let's write a function that loops over all the triples, checks each one to see if it is lucky, and builds a set (to ensure distinctness):

from itertools import combinations

def lucky_triples(iterable):
    """Return the set of distinct triples x, y, z from an iterable of
    numbers, such that x <= y <= z and x divides y and y divides z.

    """
    return set((x, y, z)
               for x, y, z in combinations(sorted(iterable), 3)
               if y % x == 0 and z % y == 0)

Then we can use this as an oracle for our tests:

from random import randrange

def test(m, n):
    data = [randrange(1, m) for _ in range(n)]
    if answer(data) != len(lucky_triples(data)):
        print("Failed on {!r}".format(data))

Let's try it:

>>> test(10, 10)
Failed on [4, 5, 2, 8, 5, 9, 2, 2, 7, 1]

Oops. What's gone wrong here? Our oracle function shows that there are nine distinct lucky triples here:

>>> sorted(lucky_triples([4, 5, 2, 8, 5, 9, 2, 2, 7, 1]))
[(1, 2, 2), (1, 2, 4), (1, 2, 8), (1, 4, 8), (1, 5, 5), (2, 2, 2),
 (2, 2, 4), (2, 2, 8), (2, 4, 8)]

But the code from the post only counts eight of them:

>>> answer([4, 5, 2, 8, 5, 9, 2, 2, 7, 1])
8

So, it's back to the drawing board, I'm afraid.

2. Analysis

If the problem isn't immediately clear, it often helps to perform test case reduction — that is, to remove superfluous elements from the failing test case until no more elements can be removed without causing the test to pass. In this case we get following minimal test case:

>>> answer([1, 2, 4, 8])
3
>>> sorted(lucky_triples([1, 2, 4, 8]))
[(1, 2, 4), (1, 2, 8), (1, 4, 8), (2, 4, 8)]

It's clear that the problem is here:

for any list of multiples where each element \$n\$ is a factor of element \$n+1\$, for example 1, 2, 4, 8, 16, the number of lucky triples in the list is equal to the summation from x = 0 to x = length - 2.

Suppose that the list has length \$k\$, then you'd calculate the count of lucky triples as $$ \sum_{0 \le x \le k-2} x = {(k-1)(k-2) \over 2}.$$ But actually in such a list any combination of three numbers form a lucky triple, so the count we need is $${k \choose 3} = {k(k-1)(k-2) \over 6}.$$ You'll see that these are the same when \$k=3\$, but that's just a coincidence.

So let's try replacing this code:

    for depth in self._depths:
        tmp = range(1, depth - 1)
        self._lucky_triple_count += sum(tmp)

with this code:

    for k in self._depths:
        self._lucky_triple_count += k * (k - 1) * (k - 2) // 6

Now the result is correct for the test case that failed:

>>> answer([1, 2, 4, 8])
4

So that fixes one problem. But might there be any other problems? Let's test lots of cases:

>>> for i in range(2, 20):
...     test(i, i)
Failed on [7, 4, 2, 15, 14, 11, 10, 1, 13, 3, 6, 4, 12, 15, 5, 11]

What's the problem here?

>>> answer([7, 4, 2, 15, 14, 11, 10, 1, 13, 3, 6, 4, 12, 15, 5, 11])
25
>>> len(lucky_triples([7, 4, 2, 15, 14, 11, 10, 1, 13, 3, 6, 4, 12, 15, 5, 11]))
23

In this case, the code is counting too many triples! After removing superfluous elements, we get this minimal test case:

>>> answer([1, 2, 4, 6, 12])
8
>>> len(lucky_triples([1, 2, 4, 6, 12]))
7

Now it is clear what the problem is: we have two divisibility chains here, both of length four, namely \$1 \mid 2 \mid 4 \mid 12\$ and \$1 \mid 2 \mid 6 \mid 12\$:

>>> LuckyTriples([1, 2, 4, 6, 12])._depths
[4, 4]

Each of these chains contributes four lucky triples to the sum — but this leads to double-counting, because the lucky triple \$(1, 2, 12)\$ belongs to both divisibility chains but must be counted just once.

It's clear, I think, from this example, that the whole approach (of searching for divisibility chains and counting their length) is not going to work. That's because some lucky triples are going to appear on multiple divisibility chains and it is not clear how to avoid double-counting.

3. Alternative implementation

So here's an alternative implementation that runs in time \$Θ(n^2)\$. For each number \$x\$ in the input, it counts the number of distinct proper divisors of \$x\$, \$d(x)\$, and the number of distinct proper multiples of \$x\$, \$m(x)\$. Then the number of distinct lucky triples \$(w, x, y)\$ with \$w < x < y\$ is \$d(x)m(x)\$. If there are at least 2 occurrences of \$x\$, then there are also \$d(x)\$ lucky triples \$(w, x, x)\$ with \$w < x\$ and \$m(x)\$ lucky triples \$(x, x, y)\$ with \$x < y\$. Finally, if there are at least 3 occurrences of \$x\$, then there is one lucky triple \$(x, x, x)\$.

from collections import Counter
from itertools import combinations

def lucky_triple_count(iterable):
    """Return the number of distinct triples x, y, z from an iterable of
    numbers, such that x <= y <= z and x divides y and y divides z.

    """
    counts = Counter(iterable)  # {x: occurrences of x}
    divisors = Counter()        # {x: distinct proper divisors of x}
    multiples = Counter()       # {x: distinct proper multiples of x}
    for x, y in combinations(sorted(counts), 2):
        if y % x == 0:
            divisors[y] += 1
            multiples[x] += 1
    result = 0
    for x, n in counts.items():
        result += divisors[x] * multiples[x]
        if n >= 2:
            result += divisors[x] + multiples[x]
            if n >= 3:
                result += 1
    return result

Answer 2

• Initialising an attribute empty and then mutating it in a function is hard to understand. Instead make the functions create the object, and then assign it to the attribute.

• Your comments # {{{ are abnormal, but are A-OK. But I'd reduce the amount of lines between them and other code. So they 'hug' the functions.

• map is disliked by many. So try to use comprehensions instead.
  Also your usage of it in the __init__ is bad. You shouldn't use map for side effects; you're using it to change the data. a = map(lambda x: 2*x, range(10)) is OK, but what you're doing is not. Instead use a for loop.

• Some of your variables are unreasonably long. If you make a dict of parents, then you can just call it parents, rather than _tree_space_parents. This makes code easier to read too:

   self._parents[node] = self.get_parents(node, self._node_pool)
  

• You start new lines inconsistently. Look at get_children_to_visit and you'll see the nodes list comprehension doesn't go on a new line after the return data in the first loop, but it does in the middle of the second loop. You also write immediate_children as if it's a comprehension, which is confusing as it's passed a single value. And children_to_visit.append's brackets are mismatched: one finishes after the subtraction, the other on a new line. Also if you look at explore_deeper comprehension you'll see it's yet another style.

  This removes consistency and makes the code significantly harder to read.

• If you can return straight away, do so. Reading var = [...]; return var is slower than return [...] and takes up more lines.

• get_all_roots should utilize filter not map if you were to pick one of the two. Instead you can just make it a list comprehension which is readable whichever you pick.

• You can iterate through sets, and so there is no need to change one to a list in get_children_to_visit. And you definitely don't need to pop from the new list.

• You can merge branch_off and explore_deeper to keep the changes to depths in the same function.

  You can then go onto change what was branch_off to a single comprehension that's added to depths. After this you can loop through the length - len(branches) - and add one to them. This can make the code easier to understand then using izip.

• You should change embark to contain the for loop, and to create and return depths. This keeps the logic in one function and makes it more readable. Rather than having to jump between __init__ and embark.

• You can change enumerate_lucky_triples to use a comprehension, rather than a for. This can be done by passing the comprehension to sum. After that you can make the other part of the function a comprehension too. It's easier to filter all the single occurrences if you pass list_of_random_int to Counter as then you can just add if amount > 1:. You can also change the two ifs to a single comparison. This is because if amount, multiples[multiple], is 2 you add 0, otherwise 1. This is equivalent to amount != 2. And so you can merge this all into a single comprehension. So you're left with two comprehensions passed to sums.

• Using the above you can remove all bar one class attributes. This keeps privates, actually private. And leaves only lucky_triple_count, which is the class's 'return'.

  I'd later go on to change the class to only be private functions, as there is now no longer so much of a need for the class.

Using the above you can change your code to be much more readable. I'd always aim for readability before performance, and normally over it too. And so you can achieve:

from collections import Counter

class _LuckyTriples(object):
    def __init__(self, list_of_random_int):
        node_pool = set(list_of_random_int)
        parents, children = self.build_relationships(node_pool)
        roots = self.build_roots(node_pool, parents)
        depths = self.build_depths(roots, children)
        self.lucky_triple_count = self.count_lucky_triples(list_of_random_int, depths,
                                                           parents, children)

    def build_relationships(self, node_pool):
        parents, children = {}, {}
        for node in node_pool:
            parents[node] = [
                parent
                for parent in node_pool
                if parent < node and node % parent == 0
            ]
            children[node] = [
                child
                for child in node_pool
                if child > node and child % node == 0
            ]
        return parents, children

    def build_roots(self, node_pool, parents):
        return [
            node
            for node in node_pool
            if not parents[node]
        ]

    def get_children_to_visit(self, nodes, depths, children_):
        nodes = [
            subbranch
            for branches in nodes
            for subbranch in branches
        ]
        children = []
        for node in nodes:
            immediate_children = set(children_.get(node))
            descendants = set()
            for node in immediate_children:
                descendants.update(children_.get(node))
            children.append(list(immediate_children - descendants))

        depths += [depths[0] for subbranch in children for _ in range(len(subbranch) - 1)]
        for i in range(sum(len(child) for child in children)):
            depths[i] += 1
        return children, depths

    def build_depths(self, roots, children_):
        depths_ = []
        for root in roots:
            children, depths = [[root]], [1]
            while any(children):
                children, depths = self.get_children_to_visit(children, depths, children_)
            depths_.extend(depths)
        return depths_

    def count_lucky_triples(self, numbers, depths, parents_, children_):
        lucky_triple_count = sum(sum(range(1, depth - 1)) for depth in depths)
        lucky_triple_count += sum(
            len(parents_[multiple]) + len(children_[multiple]) + (amount != 2)
            for multiple, amount in Counter(numbers).items()
            if amount > 1
        )
        return lucky_triple_count


def lucky_triples(l):
    return _LuckyTriples(l).lucky_triple_count

Answer 3

Peilonrayz already mentioned this, but I feel this needs more emphasis:

I'd argue that the problem is not well suited for implementation as a class.

First hint: The challenge says "write a function".

Second hint: Your answer function creates an instance of your class and then discards it after getting the one information that is needed, it's "return value".

When still opting for implementation as a class, having the instances do all the work in their __init__ method is bad style (and also a hint to write a function instead). Imagine creating many of those objects and then having to get the lucky triple count of only some of those. Now you have done a lot of calculation for nothing.

Also, naming the "return value" with a leading underscore is bad style. The leading underscore is a convention to indicate private attributes or methods. Your "return value" is meant to be read from code outside of your class, and is thus not to be considered private.

Answer 4

The accepted answer is great, but it's probably important to note that the suggested solution doesn't actually pass the actual test cases because the prompt specifies that order must be maintained.

So solution([1,2,4)] = 1 but solution([4,2,1]) = 0.

Regardless, here is my ELI5 of the accepted answer:

"""
First, we must recognize that any "lucky triple" (i.e. 1,2,4) is atomically composed of
pairs of multiples. 1,2,4 is a lucky triple because 1,2 and 2,4 are multiples.

Having previously attempted recursive solutions, that don't approach the problem from the
perspective of multiple pairs, easily time out at the more extreme-sized test cases.

In order to find a more heuristic solution that can be more efficient, let's approach some
test cases from the perspective of our atomic multiple pairs.

l = [1, 2, 4, 8] # simple test case with all unique numbers that are all multiples

multiple_pairs = [(1, 2), (1, 4), (1, 8), (2, 4), (2, 8), (4, 8)]

now let's work out the answer by hand first.

solution = sum([(1, 2, 4), (1, 2, 8), (1, 4, 8), (2, 4, 8)]) = 4

the first thing we might notice, however seemingly insignificant, is that every gateway
number (middle) is always a 2 or a 4. Never 1 or 8, which also happen to be the min and max.

Another interesting aspect of 1 and 8 are that they either have no multiples(8) or it's not
a multiple of anything else (1). These numbers can't be gateway numbers.

To derive this fact from our multiple_pairs, we can count every number's multiples and the
numbers they're multiples of.

has_multiples = {1: 3, 2: 2, 4: 1, 8: 0}
multiples_of = {1: 0, 2: 1, 4: 2, 8: 3}

1 has no multiples_of and 8 has no multiples. Let's take a closer look at the numbers that
have both, and see how we can connect them to the concept of gateway numbers.

A gateway number, by definition, needs to have numbers that can come both before and after.
In terms of multiples, a gateway number needs to have both multiples and multiples_of.

Let's take 2 for example. There is one number (1) that can come before 2 and two numbers
(4, 8) that can come after 2. Only knowing this information, we can deduce that 2 will be
the gateway number twice in our solution set, reusing the multiples_of twice and both
has_multiples to create two unique triples [(1, 2, 4), (1, 2, 8)].

Likewise for 4 [(1, 4, 8), (2, 4, 8)].

What's interesting here is that if take their respective has_multiples and multiples_of,
we can also come up with the same number of gateway triples by multiplying them.

has_multiples[2] * multiples_of[2] = 2
has_multiples[4] * multiples_of[4] = 2

If we apply this same formula to 1 and 8, they both result in 0, which makes sense.
If we extrapolate this formula to something more generic, we can conclude that for the
test case [1, 2, 4, 8], the formula has_multiples[n] * multiples_of[n] for every number in l
summed, results in the right number of lucky triples! (0 + 2 + 2 + 0 = 4)

Now let's apply a more nuanced test case, say

l = [1, 1, 2, 4] # with duplicates

multiple_pairs = [(1, 2), (1, 4), (2, 4)]

has_multiples = {1: 2, 2: 1, 4: 0}
multiples_of = {1: 0, 2: 1, 4: 0}

The answer should be...

solution = sum([(1, 1, 2), (1, 1, 4), (1, 2, 4)]) = 3

Unfortunately, this invalidates the equation derived from the previous test case.
0 + 1 + 0 = 1

Sure, there is still legitimately one triple with 2 as a gateway number, but now with
duplicates introduced we see 1 (the duplicate) as a gateway number as well.

In both cases of 1 as a gateway number, 1 is using its duplicate as a multiples_of, along
with both has_multiples. This pattern is not very different from the previous formula,
since in this case we can still add 1's has_multiples and multiples_of to get the number
of triples where 1 is a valid gateway number. (2 + 0 = 2)

Combining this with the last formula, we arrive at the correct answer 3.

Lastly, and we won't have to get into the subject with much detail, but a test case like
[1, 1, 1] breaks both formulas from above, so we can treat it as a base case, where 3 or
more of one number contributes one triple.
"""
from collections import Counter
from itertools import combinations


def solution(l):
    triples = 0
    l_counter, has_multiples, multiples_of = Counter(l), Counter(), Counter()
    for n, m in combinations(sorted(l_counter), 2):
        if m % n == 0:
            has_multiples[n] += 1
            multiples_of[m] += 1
    for unique_number, count in l_counter.items():
        triples += has_multiples[unique_number] * multiples_of[unique_number]
        if count > 1:
            triples += has_multiples[unique_number] + multiples_of[unique_number]
            if count > 2:
                triples += 1
    return triples

Answer 5

I'm afraid that all of these answers are wrong.

Not because they provide invalid results, but because author of the question didn't recall two major details, so people were actually solving different problems.

1. The solution must count all possible combinations. Thus, answer for [1,1,1,1] is 4, not 1.
2. 𝑥≤𝑦≤𝑧 is correct, but it also demands that positions of these numbers should go up. Given i is a position of a number this must be satisfied: xᵢ < yᵢ < zᵢ

Here's the actual description:

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 the Commander 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, Lambda has confided to you that all the access codes are "lucky triples" in order to make it easier to 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 solution(l) that takes a list of positive integers l and counts the number of "lucky triples" of (lᵢ, lⱼ, lₖ) where the list indices meet the requirement i < j < k. The length of l is between 2 and 2000 inclusive. The elements of l are between 1 and 999999 inclusive. The solution 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 solution 3 total.