12
\$\begingroup\$

I am trying to solve a puzzle in a performant way. This is the puzzle.

Simply explained: you have a String and you must reduce it to one character with the given rules. This is the solution to the simple variant.

COLORS = set("RGB")
def triangle(row):
    while len(row) > 1:
       row = ''.join(a if a == b else (COLORS-{a, b}).pop() for a, b in zip(row, row[1:]))
    return row

In the harder variant the task is to do the same, but performance is asked. I thought adding a dictionary and "remembering" already solved words would boost the performance. But actualy it is not performing faster than the simple variation. Is there a way to boost one of my codes? Do I have an efficiency lack in my code? Is there maybe a efficiency lack in the algorithm?

COLORS = set("RGB")
mapping_simple = {}
def triangle_simple(row):
    result = ['']
    while True:
        if len(row) == 1:
            result[0] = row
            return result[0]
        if row in mapping_simple:
            result[0] = mapping_simple[row][0]
            return result[0]
        mapping_simple[row] = result
        row = ''.join(a if a == b else (COLORS-{a, b}).pop() for a, b in zip(row, row[1:]))
    return result[0]
\$\endgroup\$
21
\$\begingroup\$

First I would choose a different representation of the colors during the computation, to avoid the “expensive” COLORS-{a, b}).pop() operation, which is executed $$ (n-1) + (n-2) + \ldots + 1 = \frac{(n-1)n}{2} $$ times for an input string of length \$ n \$. It becomes simpler if we represent the colors as numbers instead, for example $$ \text{Red} = 0, \text{Green} = 1, \text{Blue} = 2 \, . $$ Now the combination of two colors a and b can be computed as

a if a == b else 3 - a - b

without requiring any set or dictionary lookup. This leads to the following implementation:

def color_to_num(col):
    """ Translate the colors 'R', 'G', 'B' to the numbers 0, 1, 2. """
    return 0 if col == 'R' else 1 if col == 'G' else 2


def num_to_color(num):
    """ Translate the numbers 0, 1, 2 to the colors 'R', 'G', 'B'. """
    return 'R' if num == 0 else 'G' if num == 1 else 'B'


def triangle(row):
    numbers = [color_to_num(col) for col in row]
    while len(numbers) > 1:
       numbers = [ a if a == b else 3 - a - b for a, b in zip(numbers, numbers[1:])]
    return num_to_color(numbers[0])

In my test (on a 1.2 GHz Intel Core m5 MacBook) this reduces the time for an input string with 10,000 characters from (approximately) 18 seconds to 5.5 seconds.

But one can do better. The above solution still has a \$ O(n^2) \$ complexity. In order to get rid of that, we need some mathematics (compare Three Color Triangle Challenge on Mathematics Stack Exchange).

The are two key observations:

  • If all (numeric) colors are viewed “modulo 3” then the combination of \$ a \$ and \$ b \$ is just \$ -(a+b) \$.
  • The final color can be computed “directly” from the initial row, using binomial coefficients (the numbers from Pascal's triangle).

Here is an example for the first observation: The combination of Red and Blue is computed as $$ - (0 + 2) \bmod 3 = -2 \bmod 3 = 1 $$ and that is Green.

And an example for the second observation with an initial row of 4 colors: $$ a_0, a_1, a_2, a_3 \\ -(a_0 + a_1), -(a_1 + a_2), -(a_2 + a_3) \\ a_0 + 2a_1 + a_2, a_1 + 2a_2 + a_3 \\ -(a_0 + 3a_1 + 3 a_2 + a_3) $$

The general formula for an initial row of \$ n+1 \$ colors $$ a_0, a_1, \ldots, a_n $$ is $$ \text{FinalColor} = (-1)^n \sum_{k=0}^n \binom{n}{k} a_k \bmod 3 \, . $$

There is still one problem: the calculation of the binomial coefficients. Using the definition $$ \binom{n}{k} = \frac{n(n-1) \cdots (n-k+1)}{k!} $$ can lead to large intermediate results and has complexity \$ O(k) \$, so that the total complexity is still \$ O(n^2) \$.

Here we need mathematics again: Lucas's theorem provides a way to calculate \$ \binom{n}{k} \bmod p \$ efficiently if \$ p \$ is a prime number. Luckily, 3 is a prime number!

This gives the following code:

def binomial_mod3(n, k):
    """ Compute the binomial coefficient C(n, k) modulo 3.

    It is assumed that 0 <= k <= n.

    The implementation uses Lucas's theorem, see for example
    https://en.wikipedia.org/wiki/Lucas%27s_theorem .
    """
    result = 1
    while n > 0:
        n3 = n % 3
        k3 = k % 3
        # 'Ad hoc' computation of C(n3, k3):
        if k3 > n3:
            return 0  # Return immediately if a factor is zero.
        temp = 1 if k3 == 0 or k3 == n3 else 2
        result = (result * temp) % 3
        n = n // 3
        k = k // 3
    return result


def color_to_num(col):
    """ Translate the colors 'R', 'G', 'B' to the numbers 0, 1, 2. """
    return 0 if col == 'R' else 1 if col == 'G' else 2


def num_to_color(num):
    """ Translate the numbers 0, 1, 2 to the colors 'R', 'G', 'B'. """
    return 'R' if num == 0 else 'G' if num == 1 else 'B'


def triangle(row):
    # Compute the sum of C(n, k) * col[k] modulo 3:
    n = len(row) - 1
    result = 0
    for k, col in enumerate(row):
        temp = binomial_mod3(n, k) * color_to_num(col)
        result = (result + temp) % 3
    # Invert the result if n is odd:
    if n % 2 == 1:
        result = (- result) % 3
    return num_to_color(result)

Note that we iterate over the given input string, so that no additional lists are created.

In my test this computes the final color for an input string with 10,000 characters in approximately 0.1 seconds, and for 100,000 characters in about 0.2 seconds.

\$\endgroup\$
  • 4
    \$\begingroup\$ Very nice answer! I'd love to see more of these \$\endgroup\$ – яүυк Jul 2 '18 at 8:40
  • \$\begingroup\$ Very smart answer! I think the performance could be improved by using divmod. \$\endgroup\$ – Josay Jul 2 '18 at 9:26
  • \$\begingroup\$ Also, from what I understand, the "result = (result * temp) % 3" could be optimised out: the modulo operation can probably done at the very end and we keep only "result *= temp" in the loop. Also, once temp == 0, we could probably return 0 directly. \$\endgroup\$ – Josay Jul 2 '18 at 9:31
  • 1
    \$\begingroup\$ @Josay: I tried n, n3 = divmod(n, 3) etc, and that decreased the performance. For the 100,000 character input the time increased from 0.45 to 0.72 seconds. – The immediate reduction result = (result * temp) % 3 is done to avoid large intermediate results. – Returning immediately if temp == 0 is an excellent suggestion! I'll do some tests and then update the code. \$\endgroup\$ – Martin R Jul 2 '18 at 9:36
  • 2
    \$\begingroup\$ @Josay @MartinR Maybe divmod is slow due to global lookup... perhaps try caching the function in a local variable? \$\endgroup\$ – gyre Jul 4 '18 at 3:27
9
\$\begingroup\$

string conversion

You convert the row to a string at each iteration, there is no need for that. You can shave off a few µs by using a tuple

def triangle_tuple(row):
    while len(row) > 1:
        row = tuple(a if a == b else (COLORS-{a, b}).pop() for a, b in zip(row, row[1:]))
    return row[0]
%timeit triange_OP: 60µs
%timeit triange_tuple: 58µs

This is not a huge difference, but all small bits can help

your mapping_simple

only keeps complete rows in memory, so it is of no use in descending a triangle, since you will never come upon the same row (since the length decreases).

dictionary

since the combinations stay the same, you can generate a dict with a tuple as key to help you solve this:

from itertools import product
def generate_dict(colors):
    for c1, c2 in product(colors, repeat=2):
        if c1 == c2:
            yield (c1, c1,), c1
        else:
            yield (c1, c2), (colors-{c1, c2}).pop()

%timeit dict(generate_dict) takes 4µs

COMBINATIONS = dict(generate_dict(COLORS))
def triangle_dict(row, COMBINATIONS):
    while len(row) > 1:
        row = tuple(COMBINATIONS[(a, b)] for a, b in zip(row, row[1:]))
    return row[0]
%timeit triangle_dict: 40µs (+4µs)

Hard-coding

COMBINATIONS={
 ('B', 'B'): 'B',
 ('B', 'G'): 'R',
 ('B', 'R'): 'G',
 ('G', 'B'): 'R',
 ('G', 'G'): 'G',
 ('G', 'R'): 'B',
 ('R', 'B'): 'G',
 ('R', 'G'): 'B',
 ('R', 'R'): 'R',
}

will even decrease the extra 4 µs

Cache

If the tests are done repeatedly, instead of implemeting your own cache, you can use the built-in functools.lru_cache

from functools import lru_cache
@lru_cache(None)
def next_row(row):
    return tuple(COMBINATIONS[(a, b)] for a, b in zip(row, row[1:]))
def triangle_dict_cache(row, COMBINATIONS):
    while len(row) > 1:
        row = next_row(row)
    return row[0]

To test this you need a way to make a random combination

from random import choice
def make_combination(n):
    return tuple(choice('RGB') for _ in range(n))
%timeit  make_combination(19)
13.7µs
def test_cache():
    combination = make_combination(19)
    triangle_dict_cache(combination)
%timeit test_cache()
51.3µs 

minus the 13.7µs, the speed increase from the caching is limited

\$\endgroup\$
  • \$\begingroup\$ About "your mapping_simple". The test is running 100 times for length 100,1000 and 10000. So it runs about 300 times through the same length. \$\endgroup\$ – Predicate Jul 1 '18 at 23:48
  • \$\begingroup\$ Wow, thanks!!! It reduced the time by half! But can you say something to the previous point about the mapping? is "string in mapping" time expensive? I assumed it's not because it should create a hashmap, correct? \$\endgroup\$ – Predicate Jul 2 '18 at 5:57
  • 3
    \$\begingroup\$ Good answer, I would use itertools.pairwise instead of zip(row, row[1:]) to avoid the cost of duplicating the (almost) entire input. \$\endgroup\$ – Mathias Ettinger Jul 2 '18 at 8:56
  • \$\begingroup\$ I have done calculations. After the first 100 loops, the usage of the dictinary is 100%! That means the dictionary fills with values and is used for computing future results every iteration. \$\endgroup\$ – Predicate Jul 2 '18 at 8:57
  • 1
    \$\begingroup\$ @S.G. from the documentation I linked: If maxsize is set to None, the LRU feature is disabled and the cache can grow without bound. \$\endgroup\$ – Maarten Fabré Jul 3 '18 at 6:54
5
\$\begingroup\$

I have made a few minor improvements to the answer by R Martin and as such will not go through all the improvements made there. I would post this as a comment but am currently unable.

The main changes I have made are to not bother calculating the modulus of the intermediate results which was discussed in the comments above. This change improved the speed from roughly 20 seconds to 15 seconds for a test using a random selection of strings with lengths between 100 and 10000. As the main worry was the size of the intermediate result I checked exactly how big the intermediate result could get and show the calculation below.

The other change I made was to only calculate the binomial coefficient if the colour wasn't 'R' which translates to 0 as those terms will always give a contribution of 0 whatever the binomial evaluates to.


The theoretical limit for how big the intermediate can get if no moduli are calculated to the very end can be calculated by assuming that all letters in the string is 'B' which translates to 2 and that every factor in every factorial calculation is 2. This gives a maximum intermediate size for an \$n\$ character string of $$ n\times 2^{\left\lfloor\log_3(n-1)\right\rfloor}\times2 $$ where the factors are due to the \$n\$ terms, the \$\left\lfloor\log_3(n-1)\right\rfloor\$ factors of two in each binomial calculation and the extra two for each colour being 'B'.

However after testing this numerically this limit was found to be very much over the actual limit. The actual limit is found to be $$ 2^{2\left\lfloor\log_3(n)\right\rfloor}\times\left\lfloor{\frac{n}{3^{\left\lfloor\log_3(n)\right\rfloor}}}\right\rfloor\times2 $$ where the factor \$\left\lfloor{\frac{n}{3^{\left\lfloor\log_3(n)\right\rfloor}}}\right\rfloor\$ is either 1 or 2 and corresponds to the first non-zero digit in the ternary representation of \$n\$. This limit increases for number that are of the form of a single non-zero digit followed by zeros (e.g. 1, 2, 10, 20, 100, 200, ...).

From this we can show that if the intermediate is limited to be less than or equal to \$L\$ then all inputs of length less than or equal to $$ 2^\left(\left\lfloor\log_2\frac{L}{2}\right\rfloor\mod 2\right)\times3^{\left\lfloor\frac{\left\lfloor\log_2\frac{L}{2}\right\rfloor}{2}\right\rfloor}-1 $$ which for a 32 bit signed integer gives a limit of 14,348,906 which is way more than the maximum size of input the challenge asks you to handle.


def binomial_mod3(n, k):
    """ Compute the binomial coefficient C(n, k) modulo 3.

    It is assumed that 0 <= k <= n.

    The implementation uses Lucas's theorem, see for example
    https://en.wikipedia.org/wiki/Lucas%27s_theorem .
    """
    result = 1
    while n > 0:
        n3 = n % 3
        k3 = k % 3
        # 'Ad hoc' computation of C(n3, k3):
        if k3 > n3:
            return 0  # Return immediately if a factor is zero.
        if k3 == 1 and n3 == 2:
            result = result * 2
        n = n // 3
        k = k // 3
    return result


def color_to_num(col):
    """ Translate the colors 'R', 'G', 'B' to the numbers 0, 1, 2. """
    return 0 if col == 'R' else 1 if col == 'G' else 2


def num_to_color(num):
    """ Translate the numbers 0, 1, 2 to the colors 'R', 'G', 'B'. """
    return 'R' if num == 0 else 'G' if num == 1 else 'B'


def triangle(row):
    # Compute the sum of C(n, k) * col[k] modulo 3:
    n = len(row) - 1
    result = 0
    for k, col in enumerate(row):
        temp = color_to_num(col)
        if temp != 0:
            result = (result + temp * binomial_mod3(n,k))
    # Invert the result if n is odd:
    if n % 2 == 1:
        result = - result
    return num_to_color(result % 3)
\$\endgroup\$
  • \$\begingroup\$ Very nice addition to an already nice answer! Your trick about computing the binomial only when the corresponding color value is not 0 is simple and brilliant, especially on inputs containing only "R"s. In that case, half the time can be shaved of by using a dictionnary instead of a function for color_to_num/num_to_color. Another improvement could be to convert n to base 3 once and for all in triangle but this makes for a much dirtier code... \$\endgroup\$ – Josay Jul 4 '18 at 17:05
  • \$\begingroup\$ Also, I am wondering if it is possible to make use of the symmetry for binomial_mod3 to go from a situation where we call it on average 2 out of 3 color to a situation where we call it on average 1 every 3 color (we call it 2 times out of 3 at each iteration which handles a pair of colors). \$\endgroup\$ – Josay Jul 4 '18 at 17:16
  • \$\begingroup\$ A dummy implementation leads to worse performance. mid = n//2 + 1, coefs = [color_to_num[a] + color_to_num[b] for a, b in zip(row[:mid], row[::-1])], result = sum(coef * binomial_mod3(n, k) for k, coef in enumerate(coefs) if coef) and it is not that much better with coefs = [color_to_num[row[i]] + color_to_num[row[n-i]] for i in range(n//2 + 1)]. \$\endgroup\$ – Josay Jul 4 '18 at 17:25

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.