Three colors triangles

Question

I am trying to make a code for this problem:

(Source: https://www.codewars.com/kata/insane-coloured-triangles/train/c)

A coloured triangle is created from a row of colours, each of which is red, green or blue. Successive rows, each containing one fewer colour than the last, are generated by considering the two touching colours in the previous row. If these colours are identical, the same colour is used in the new row. If they are different, the missing colour is used in the new row. This is continued until the final row, with only a single colour, is generated.

For example, different possibilities are:

Colour here:            G G        B G        R G        B R 
Becomes colour here:     G          R          B          G 

With a bigger example:
   R R G B R G B B  
    R B R G B R B
     G G B R G G
      G R G B G
       B B R R
        B G R
         R B
          G

You will be given the first row of the triangle as a string and its your job to return the final colour which would appear in the bottom row as a string. In the case of the example above, you would be given 'RRGBRGBB', and you should return 'G'.

Constraints:

1 <= length(row) <= 10 ** 5

The input string will only contain the uppercase letters 'B', 'G' or 'R'.

The exact number of test cases will be as follows:

100 tests of 100 <= length(row) <= 1000 
100 tests of 1000 <= length(row) <= 10000 
100 tests of 10000 <= length(row) <= 100000

Examples:

triangle('B') == 'B'
triangle('GB') == 'R'
triangle('RRR') == 'R'
triangle('RGBG') == 'B'
triangle('RBRGBRB') == 'G'
triangle('RBRGBRBGGRRRBGBBBGG') == 'G'

So I have made this code and it works for all the sample tastes but when it comes for length of row > 25 it fails due my factorial function,and the length in some cases is up to 100,000, so any suggestion to fix this problem at least any mathematic formula that can solve the problem or a small hint.

by the way I have made this code after I found a mathematic way to solve the problem in this site :

https://math.stackexchange.com/questions/2257158/three-color-triangle-challenge

long long factorial(long long num)     
{
    long long fact = num;

    if (fact == 0)
        fact = 1;

    while (num > 1)
    {
        num--;
        fact *= num;
    }
    return (fact);
}

long long combination(long long n, long long k, long long fact_n)
{
    long long fact_k = factorial(k);
    long long comb = ( fact_n / (fact_k * factorial(n - k)) );
    return (comb);
}

char triangle(const char *row)
{
    long long len = strlen(row);
    long long n = len - 1;
    long long k = 0;
    int sign = pow(-1,n);
    long long sum = 0;
    char *result = "RGB";
    int a;
    long long fact_n = factorial(n);

    while (k < len)                 //This while calculate Segma (∑). 
    {
        if (row[k] == 'R')
            a = 0;
        else if (row[k] == 'G')
            a = 1;
        else if (row[k] == 'B')
            a = 2;

        if (a != 0)
            sum = sum + (combination(n,k,fact_n) * a); 
        k++;
    }

    sum = sign * (sum % 3);

    if (sum == -1 || sum == -2)
        sum += 3;

  return (result[sum]);
}

Answer 1

I will assume that the formula in the link you provided is correct:

---

In order to avoid integer overflow, we will need to apply these modulo arithmetic rules:

(a * b) mod c = ((a mod c) * (b mod c)) mod c

(a ± b) mod c = ((a mod c) ± (b mod c)) mod c

Applying them to the formula:

---

But how do we calculate

... without directly calculating the coefficient itself (which can cause overflow)?

Since 3 is a prime number, this can be accomplished with Lucas's theorem:

... where n_i, m_i are the i-th digits of n, m in base-3.

---

Conversion to base-3 is easy with integer division:

// convert a number to base 3
// and returns the number of digits
unsigned conv_base_3(unsigned n, unsigned max, unsigned* out)
{
    unsigned i = 0;
    while (i < max && n > 0)
    {
        out[i] = n % 3;
        n /= 3;
        i++;
    }
    return i;
}

Note that since n_i, m_i are always in the range [0, 2] (because they are base-3 digits), C(n_i, m_i) are very easy to calculate:

// calculate the binomial coefficient for n < 3
unsigned binom_max_2(unsigned n, unsigned k)
{
    if (n < k)
        return 0;
    switch (n)
    {
        case 0:
        case 1:
            return 1;
        case 2:
            return 1 + (k == 1);

        // shouldn't happen
        default:
            return 0;
    }
}

And now the theorem itself:

// Lucas's theorem for p = 3
unsigned lucas_3(
    unsigned len_n, const unsigned * dig_n,
    unsigned len_k, const unsigned * dig_k
)
{
    // use modulo product rule:
    // prod[i] % 3 = ((prod[i - 1] % 3) * value[i])      
    unsigned prod = 1;
    for (unsigned i = 0; i < len_n; i++) {
        unsigned n_i = dig_n[i];
        unsigned k_i = (i < len_k) ? dig_k[i] : 0;
        prod = (prod * binom_max_2(n_i, k_i)) % 3;
    }
    return prod % 3;
}

Character conversion:

// convert from 012 to RGB
char int_2_char(int i)
{
    switch (i) {
        case 0: return 'R';
        case 1: return 'G';
        case 2: return 'B';

        // shouldn't happen
        default:
            return '\0';
    }
}

// convert from RGB to 012
unsigned char_2_int(char c)
{
    switch (c) {
        case 'R': return 0;
        case 'G': return 1;
        case 'B': return 2;

        // shouldn't happen
        default:
            return 3;
    }
}

Finally, the triangle algorithm:

// the problem constraints state that n <= 10 ** 5
// max number of base-3 digits
#define MAX_N_LOG_3 11

// main algorithm function
char triangle(const char * input)
{
    unsigned sum = 0;
    const int n = strlen(input);

    // calculate digits of n - 1
    unsigned dig_n[MAX_N_LOG_3];
    unsigned len_n = conv_base_3(n - 1, MAX_N_LOG_3, dig_n);

    for (unsigned km1 = 0; km1 < n; km1++)
    {
        // calculate digits of k - 1
        unsigned dig_k[MAX_N_LOG_3];
        unsigned len_k = conv_base_3(km1, MAX_N_LOG_3, dig_k);

        // calculate C(n - 1, k - 1) mod 3
        unsigned Cnk_mod3 = lucas_3(len_n, dig_n, len_k, dig_k);

        // add using the modulo rule
        sum = (sum + Cnk_mod3 * char_2_int(input[km1])) % 3;
    }

    // value of (-1) ** (n - 1)
    // (no need for pow; just need to know if n is odd or even)
    int sign = (n % 2) * 2 - 1;

    // for negative numbers, must resolve the difference
    // between C's % operator and mathematical mod
    int sum_mod3 = (3 + (sign * (int)(sum % 3)) % 3;
    return int_2_char(sum_mod3);
}

The above code passes all tests; note that it was written in favor of clarity, not performance.

---

So why was this code able to pass all tests in the allocated time, whereas the simple table-based approach wasn't? Because of its time complexity:

• The table-based approach processes all levels of the triangle, which is O(n^2) (see Triangle Numbers).

• Of course, using Lucas's algorithm, only the top level has to be processed; however the algorithm itself is O(log n), because it loops through every digit of n (regardless of the base). The overall complexity is O(n log n), which still represents a significant improvement.

Answer 2

Recursion is of little use here^(a) since you never have to return to a previous state. Iteration is a better solution and can be done rather simply.

First, receive the initial string of colors and create another one of the same size.

Then, for each set of two characters (overlapping) in the original, set the equivalent character in the new string based on your rules. Finally, once the new string is fully formed (one character shorter than the original), copy it back to the original and, unless it's one character long, keep going (go back to the start of this paragraph).

Here's some sample code that shows this in action:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// Helper function to output nicely spaced string.

static void output(int gap, char *str) {
    // Spaces at line start.

    for (int i = 0; i < gap; ++i)
        putchar(' ');

    // Actual string with spaces between letters, end line following.

    for (int i = 0, len = strlen(str); i < len; ++i)
        printf(" %c", str[i]);
    putchar('\n');
}

// The meat of the solution.

int main(int argc, char *argv[]) {
    // Check parameter count and content.

    if (argc != 2) {
        fprintf(stderr, "*** Needs one argument\n");
        return 1;
    }

    for (int i = 0, len = strlen(argv[1]); i < len; ++i) {
        if (strchr("RGB", argv[1][i]) == NULL) {
            fprintf(stderr, "*** Bad character '%c' found\n", argv[1][i]);
            return 1;
        }
    }

    // Allocate strings with check, prepare first.

    char *first = malloc(strlen(argv[1]) + 1);
    char *second = malloc(strlen(argv[1]) + 1);
    if (first == NULL || second == NULL) {
        fprintf(stderr, "*** Memory allocation error\n");
        free (first);
        free (second);
        return 1;
    }
    strcpy(first, argv[1]);

    // Continue until you have a short enough string.

    int spaces = 0;
    while (strlen(first) > 1) {
        // Output current string, update spaces for next.

        output(spaces++, first);

        // Process each overlapping pair in string.

        for (int i = 0, len = strlen(first); i < len - 1; ++i) {
            // Select what goes in new string, based on pair.

            char newCh = '?';

            if (first[i] == 'R' && first[i+1] == 'R') newCh = 'R';
            if (first[i] == 'G' && first[i+1] == 'G') newCh = 'G';
            if (first[i] == 'B' && first[i+1] == 'B') newCh = 'B';

            if (first[i] == 'G' && first[i+1] == 'R') newCh = 'B';
            if (first[i] == 'R' && first[i+1] == 'G') newCh = 'B';

            if (first[i] == 'B' && first[i+1] == 'G') newCh = 'R';
            if (first[i] == 'G' && first[i+1] == 'B') newCh = 'R';

            if (first[i] == 'B' && first[i+1] == 'R') newCh = 'G';
            if (first[i] == 'R' && first[i+1] == 'B') newCh = 'G';

            // Sanity check, should never be true.

            if (newCh == '?') {
                fprintf(stderr, "*** Bad data %c/%c\n", first[i], first[i+1]);
                free (first);
                free (second);
                return 1;
            }

            // Place in new string and add terminator.

            second[i] = newCh;
            second[i+1] = '\0';
        }

        // Transfer second back to first for next cycle.

        strcpy(first, second);
    }

    // Output final one-character string, clean up.

    output(spaces, first);

    free (first);
    free (second);
    return 0;
}

The output of that code when run with the argument RRGBRGBB is, as expected:

 R R G B R G B B
  R B R G B R B
   G G B R G G
    G R G B G
     B B R R
      B G R
       R B
        G

It also works with:

RRGBRGBBRRGBRGBBRRGBRGBBRRGBRGBBRRGBRGBBRRGBRGBBRRGBRGBBRRGBRGBBRRGBRGBBRRGBRGBBRRGBRGBBRRGBRGBBRRGBRGBBRRGBRGBBRRGBRGBBRRGBRGBBRRGBRGBBRRGBRGBBRRGBRGBBRRGBRGBBRRGBRGBBRRGBRGBBRRGBRGBBRRGBRGBBRRGBRGBBRRGBRGBBRRGBRGBB

which is substantially longer than 25 characters but I won't show the output since it's horrendously wide :-)

---

^(a) To be honest (and I'm not trying to be unnecessarily critical here), the whole use of math/factorials is dubious as well. I'm not sure why you thought this would be necessary for what is, at its heart, a text processing problem.

Answer 3

I will assume that the formula in the link you provided is correct:

---

In order to avoid integer overflow, we will need to apply these modulo arithmetic rules:

(a * b) mod c = ((a mod c) * (b mod c)) mod c

(a ± b) mod c = ((a mod c) ± (b mod c)) mod c

Applying them to the formula:

---

But how do we calculate

... without directly calculating the coefficient itself (which can cause overflow)?

Since 3 is a prime number, this can be accomplished with Lucas's theorem:

... where n_i, m_i are the i-th digits of n, m in base-3.

---

Conversion to base-3 is easy with integer division:

// convert a number to base 3
// and returns the number of digits
unsigned conv_base_3(unsigned n, unsigned max, unsigned* out)
{
    unsigned i = 0;
    while (i < max && n > 0)
    {
        out[i] = n % 3;
        n /= 3;
        i++;
    }
    return i;
}

Note that since n_i, m_i are always in the range [0, 2] (because they are base-3 digits), C(n_i, m_i) are very easy to calculate:

// calculate the binomial coefficient for n < 3
unsigned binom_max_2(unsigned n, unsigned k)
{
    if (n < k)
        return 0;
    switch (n)
    {
        case 0:
        case 1:
            return 1;
        case 2:
            return 1 + (k == 1);

        // shouldn't happen
        default:
            return 0;
    }
}

And now the theorem itself:

// Lucas's theorem for p = 3
unsigned lucas_3(unsigned len_n, const unsigned * dig_n,
                 unsigned len_k, const unsigned * dig_k)
{
    // use modulo product rule:
    // prod[i] % 3 = ((prod[i - 1] % 3) * value[i])      
    unsigned prod = 1;
    for (unsigned i = 0; i < len_n; i++) {
        unsigned n_i = dig_n[i];
        unsigned k_i = (i < len_k) ? dig_k[i] : 0;
        prod = (prod * binom_max_2(n_i, k_i)) % 3;
    }
    return prod % 3;
}

Character conversion:

// convert from 012 to RGB
char int_2_char(int i)
{
    switch (i) {
        case 0: return 'R';
        case 1: return 'G';
        case 2: return 'B';

        // shouldn't happen
        default:
            return '\0';
    }
}

// convert from RGB to 012
unsigned char_2_int(char c)
{
    switch (c) {
        case 'R': return 0;
        case 'G': return 1;
        case 'B': return 2;

        // shouldn't happen
        default:
            return 3;
    }
}

Finally, the triangle algorithm:

// the problem constraints state that n <= 10 ** 5
// max number of base-3 digits
#define MAX_N_LOG_3 11

// main algorithm function
char triangle(const char * input)
{
    unsigned sum = 0;
    const int n = strlen(input);

    // calculate digits of n - 1
    unsigned dig_n[MAX_N_LOG_3];
    unsigned len_n = conv_base_3(n - 1, MAX_N_LOG_3, dig_n);

    for (unsigned km1 = 0; km1 < n; km1++)
    {
        // calculate digits of k - 1
        unsigned dig_k[MAX_N_LOG_3];
        unsigned len_k = conv_base_3(km1, MAX_N_LOG_3, dig_k);

        // calculate C(n - 1, k - 1) mod 3
        unsigned Cnk_mod3 = lucas_3(len_n, dig_n, len_k, dig_k);

        // add using the modulo rule
        sum = (sum + Cnk_mod3 * char_2_int(input[km1])) % 3;
    }

    // value of (-1) ** (n - 1)
    // no need for pow; just need to know if n is odd or even
    int sign = (n % 2) * 2 - 1;

    // for negative numbers, must resolve the difference
    // between C's % operator and mathematical mod
    int sum_mod3 = (3 + (sign * (int)(sum % 3))) % 3;
    return int_2_char(sum_mod3);
}

The above code passes all tests. Note that it was written in favor of clarity, not performance.

---

So why was this code able to pass all tests in the allocated time, whereas the simple table-based approach wasn't? Because of its time complexity:

• The table-based approach processes all levels of the triangle, which is O(n^2) (see Triangle Numbers).

• Of course, using Lucas's algorithm, only the top level has to be processed; however the algorithm itself is O(log n), because it loops through every digit of n (regardless of the base). The overall complexity is O(n log n), which still represents a significant improvement.

Answer 4

const triangle = row => {
  let reduced = row.length > 1 ? '' : row;
  for (let i = 0; i < row.length - 1; i += 1) {
    reduced += row[i] == row[i + 1] ? row[i] : 'RGB'.replace(row[i], '').replace(row[i + 1], '');
  }
  return reduced.length > 1 ? triangle(reduced) : reduced;
}

triangle('B') == 'B'
triangle('GB') == 'R'
triangle('RRR') == 'R'
triangle('RGBG') == 'B'
triangle('RBRGBRB') == 'G'
triangle('RBRGBRBGGRRRBGBBBGG') == 'G'

const triangle = row => {
  let reduced = row.length > 1 ? '' : row;
  for (let i = 0; i < row.length - 1; i += 1) {
    reduced += row[i] == row[i+1] ? row[i] : 'RGB'.replace(row[i], '').replace(row[i+1], '');
  }
  return reduced.length > 1 ? triangle(reduced) : reduced;
}