Google Foobar Challenge: Lucky Triples

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:

• If my code is optimized;

• 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

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.

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

1. Alternative implementation

So her

StackExchange Code Review Q#144510, answer score: 26