三色三角形
Three colors triangles
我正在尝试为这个问题编写代码：
(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'
所以我编写了这段代码，它适用于所有示例口味，但是当它用于 length of row > 25 时，由于我的阶乘函数而失败，并且在某些情况下长度可达 100,000 ，所以任何解决此问题的建议至少可以解决问题的任何数学公式或小提示。
顺便说一下，我在找到解决该站点问题的数学方法后编写了这段代码：
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]);
}
递归在这里没什么用处(a)，因为您永远不必return到以前的状态。迭代是更好的解决方案，而且可以相当简单地完成。
首先，接收初始颜色字符串并创建另一个相同大小的字符串。
然后，对于原始字符串中的每组两个字符（重叠），根据您的规则在新字符串中设置等效字符。最后，一旦新字符串完全形成（比原始字符串短一个字符），将其复制回原始字符串，除非它是一个字符长，否则继续（返回到本段的开头）。
下面是一些示例代码，展示了这一点：
#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] = '[=10=]';
}
// 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;
}
当 运行 带有参数 RRGBRGBB 时，该代码的输出如预期的那样：
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
它也适用于：
RRGBRGBBRRGBRGBBRRGBRGBBRRGBRGBBRRGBRGBBRRGBRGBBRRGBRGBBRRGBRGBBRRGBRGBBRRGBRGBBRRGBRGBBRRGBRGBBRRGBRGBBRRGBRGBBRRGBRGBBRRGBRGBBRRGBRGBBRRGBRGBBRRGBRGBBRRGBRGBBRRGBRGBBRRGBRGBBRRGBRGBBRRGBRGBBRRGBRGBBRRGBRGBBRRGBRGBB
基本上 超过 25 个字符，但我不会显示输出，因为它太宽了:-)
(a) 老实说（我不想在这里过分挑剔），math/factorials 的整个使用也是可疑的。我不确定您为什么认为这对于文本处理问题的核心是必要的。
我假设您提供的 link 中的公式是正确的：
为了避免整数溢出，我们需要应用这些 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
将它们应用于公式：
But how do we calculate
... without directly calculating the coefficient itself (which can cause overflow)?
因为 3 是质数，所以可以用 Lucas's theorem:
... 其中 n_i, m_i 是 base-3 中 n, m 的第 i 位。
通过整数除法很容易转换为 3 进制数：
// 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;
}
请注意，由于 n_i, m_i 始终在 [0, 2] 范围内（因为它们是 base-3 数字），C(n_i, m_i) 非常容易计算：
// 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;
}
}
现在定理本身：
// 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;
}
字符转换：
// 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 '[=14=]';
}
}
// 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;
}
}
最后，三角算法：
// 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);
}
以上代码通过了所有测试；请注意，它是为了清晰而不是性能而编写的。
那么为什么这段代码能够在分配的时间内通过所有测试，而简单的 table-based 方法却不能？由于其时间复杂度:
table-based方法处理三角形的所有层次，即O(n^2)（见Triangle Numbers）。
当然，使用Lucas的算法，只需要处理顶层；但是算法本身是 O(log n)，因为它循环遍历 n 的每个数字（不管基数如何）。整体复杂度为O(n log n)，仍然代表着显着的提升。
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;
}
def triangle(x):
l =len(x)
v=l
R=""
for j in range(v-1):
for i in range(l-1):
la=[x[i],x[i+1]]
if x[i]==x[i+1]:
R+=x[i]
else:
if "R" not in la:
R+= "R"
elif "G" not in la:
R+= "G"
else:
R+= "B"
x=R
R=""
l=len(x)
return (x)
我正在尝试为这个问题编写代码：
(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 GYou 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 ** 5The 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) <= 100000Examples:
triangle('B') == 'B' triangle('GB') == 'R' triangle('RRR') == 'R' triangle('RGBG') == 'B' triangle('RBRGBRB') == 'G' triangle('RBRGBRBGGRRRBGBBBGG') == 'G'
所以我编写了这段代码，它适用于所有示例口味，但是当它用于 length of row > 25 时，由于我的阶乘函数而失败，并且在某些情况下长度可达 100,000 ，所以任何解决此问题的建议至少可以解决问题的任何数学公式或小提示。
顺便说一下，我在找到解决该站点问题的数学方法后编写了这段代码：
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]);
}
递归在这里没什么用处(a)，因为您永远不必return到以前的状态。迭代是更好的解决方案，而且可以相当简单地完成。
首先，接收初始颜色字符串并创建另一个相同大小的字符串。
然后，对于原始字符串中的每组两个字符（重叠），根据您的规则在新字符串中设置等效字符。最后，一旦新字符串完全形成（比原始字符串短一个字符），将其复制回原始字符串，除非它是一个字符长，否则继续（返回到本段的开头）。
下面是一些示例代码，展示了这一点：
#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] = '[=10=]';
}
// 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;
}
当 运行 带有参数 RRGBRGBB 时，该代码的输出如预期的那样：
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
它也适用于：
RRGBRGBBRRGBRGBBRRGBRGBBRRGBRGBBRRGBRGBBRRGBRGBBRRGBRGBBRRGBRGBBRRGBRGBBRRGBRGBBRRGBRGBBRRGBRGBBRRGBRGBBRRGBRGBBRRGBRGBBRRGBRGBBRRGBRGBBRRGBRGBBRRGBRGBBRRGBRGBBRRGBRGBBRRGBRGBBRRGBRGBBRRGBRGBBRRGBRGBBRRGBRGBBRRGBRGBB
基本上 超过 25 个字符，但我不会显示输出，因为它太宽了:-)
(a) 老实说（我不想在这里过分挑剔），math/factorials 的整个使用也是可疑的。我不确定您为什么认为这对于文本处理问题的核心是必要的。
我假设您提供的 link 中的公式是正确的：
为了避免整数溢出，我们需要应用这些 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
将它们应用于公式：
But how do we calculate
... without directly calculating the coefficient itself (which can cause overflow)?
因为 3 是质数，所以可以用 Lucas's theorem:
... 其中 n_i, m_i 是 base-3 中 n, m 的第 i 位。
通过整数除法很容易转换为 3 进制数：
// 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;
}
请注意，由于 n_i, m_i 始终在 [0, 2] 范围内（因为它们是 base-3 数字），C(n_i, m_i) 非常容易计算：
// 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;
}
}
现在定理本身：
// 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;
}
字符转换：
// 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 '[=14=]';
}
}
// 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;
}
}
最后，三角算法：
// 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);
}
以上代码通过了所有测试；请注意，它是为了清晰而不是性能而编写的。
那么为什么这段代码能够在分配的时间内通过所有测试，而简单的 table-based 方法却不能？由于其时间复杂度:
table-based方法处理三角形的所有层次，即
O(n^2)（见Triangle Numbers）。当然，使用Lucas的算法，只需要处理顶层；但是算法本身是
O(log n)，因为它循环遍历n的每个数字（不管基数如何）。整体复杂度为O(n log n)，仍然代表着显着的提升。
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;
}
def triangle(x):
l =len(x)
v=l
R=""
for j in range(v-1):
for i in range(l-1):
la=[x[i],x[i+1]]
if x[i]==x[i+1]:
R+=x[i]
else:
if "R" not in la:
R+= "R"
elif "G" not in la:
R+= "G"
else:
R+= "B"
x=R
R=""
l=len(x)
return (x)