13
\$\begingroup\$

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

# }}}
\$\endgroup\$
  • 4
    \$\begingroup\$ Are the # {{{ and # }}} comments a habit of yours? Where does it come from? \$\endgroup\$ – Mathias Ettinger Oct 18 '16 at 7:10
  • \$\begingroup\$ No comment on the code you wrote (except that those comments are weird). The code you should have written is a simple form of dynamic programming: the question How many lucky triples are present in the list? reduces to How many lucky triples end with the kth element of the list? reduces to How many lucky doubles end with the kth element of the list?. Should be about 10 or 20 lines, I'd say, and it would run in O(n^2) time. \$\endgroup\$ – Quuxplusone Oct 18 '16 at 8:08
  • 2
    \$\begingroup\$ Those are likely fold markers, but it's not specific to Vim. \$\endgroup\$ – ferada Oct 18 '16 at 8:59
  • 1
    \$\begingroup\$ For 1, 2, 4, 8, 16 don't you have C(5,3) possibilities to form different sets of 3? That is 10 and not 6. You're missing entries like 1,4,8 - 1,4,16 - 1,8,16 etc \$\endgroup\$ – Adrian Iftode Oct 18 '16 at 19:07
  • \$\begingroup\$ I provided my analysis and solution here: stackoverflow.com/questions/39846735/… \$\endgroup\$ – Joe Oct 31 '17 at 6:17
22
+500
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ Thank you very much for your informative answer. Indeed, you interpreted the ambiguity correctly - only distinct lucky triples should be counted. After reviewing my code, I've discovered what I was missing. However, after timing both your lucky_triples function and my answer function it seems yours achieves the correct answer in a comparable amount of time. So, it seems I have much more to learn. \$\endgroup\$ – Edwin Rice Oct 18 '16 at 13:45
  • \$\begingroup\$ This answer has been selected as the winner of Best of Code Review 2016 — Diplomat. \$\endgroup\$ – 200_success Jan 18 '17 at 19:13
  • \$\begingroup\$ Your alternative implementation doesn't work for a list containing only '1's, like [1, 1, 1, 1, 1] \$\endgroup\$ – Trauer Oct 27 '18 at 19:22
  • \$\begingroup\$ @Trauer: I used the "distinct triples" interpretation of the problem statement (see discussion in §1) and so there is only one distinct triple in [1, 1, 1, 1, 1]. \$\endgroup\$ – Gareth Rees Oct 27 '18 at 19:55
7
\$\begingroup\$
  • Initialing 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 don't use map for side effects, you use 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 go on 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, the first loop, but 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 miss-matched, 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. 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 lengeth 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 as 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 classes 'return'.

    I'd later go on to change the class to only be private functions, as there is now no longer as much of a need on 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
\$\endgroup\$
  • \$\begingroup\$ Thank you for the advice! I'm working on implementing your suggestions and even just beginning to write it as private functions makes it much more readable. \$\endgroup\$ – Edwin Rice Oct 19 '16 at 14:29
  • \$\begingroup\$ Possibly the {{{ comments are for Emacs folding-mode? \$\endgroup\$ – Toby Speight Mar 17 '17 at 14:54
6
\$\begingroup\$

Joe Wallis 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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.