here is the question (https://www.codewars.com/kata/5a331ea7ee1aae8f24000175)
I've been searching for 2 days about this. I saw an essay (https://www.ijpam.eu/contents/2013-85-1/6/6.pdf). In codewars discussion, they say we can solve the question without using mat rules, if we design the code for complexity O(n).I did try that too but it doesnt work. I've tried my best but it didnt pass. Here is my code.
I did read this (Three colors triangles) I wonder, is there any way to solve this without completely using Math ?
function triangle(row) {
let nextRow = []
let result = row.split("")
for(var j = 0; j < row.length-1; j++) {
nextRow= []
for(var i = 0; i < result.length - 1; i++) {
nextRow.push(nextColor(result[i],result[i+1]))
}
result = nextRow.slice(0)
}
return result.join("")
}
function nextColor(s1,s2) {
let colors = {"R": 1, "B": 2, "G": 3};
if(colors[s1] + colors[s2] == 6) return "G"
else if(colors[s1] + colors[s2] == 5) return "R"
else if(colors[s1] + colors[s2] == 4) return "B"
else if(colors[s1] + colors[s2] == 3) return "G"
else if(colors[s1] + colors[s2] == 2) return "R"
}
This solution solves it using < O(n2) with = O(n2) as a max. It uses two loops. One a while loop that ends so long as there is no new row to process. And an inner loop that iterates the colors of the current array.
This is not a solution to increase efficiency. It is a solution to show a non-efficient way with clarity on how the rules would work. Technically you could replace my use of "strings" with arrays, to increase efficiency, but that is not the point to illustrate on how an algorithm could work, albeit, inefficiently.
All other comments are in code comments:
function reduceTriangle( firstRow ) {
// from rules: You will be given the first row of the triangle as a string --> firstRow
let triangle = [];
// seed the triangle so we can loop it until the process is done
triangle.push( firstRow );
// lets loop this
let onRow = 0;
while (onRow < triangle.length) {
// lets determine the next generated row
// the rules given for adjacent colors are:
// Colour here: G G B G R G B R
// Becomes colour here: G R B G
// We'll also assume that order of the two-pattern doesn't matter: G B -> R, too! (from example)
let newRow = "";
for (let c = 0; c < triangle[onRow].length - 1; c++) {
let twoPattern = triangle[onRow].substring(c, c + 2); // GG, BG, etc.
// console.log(twoPattern);
let onePattern = false; // hmmm?
if (twoPattern == "RR" || twoPattern == "GG" || twoPattern == "BB") {
onePattern = twoPattern.substring(0, 1); // R || G || B
}
else {
if (twoPattern == "BG" || twoPattern == "GB") {
onePattern = "R"; // frome rules
}
else if (twoPattern == "RG" || twoPattern == "GR") {
onePattern = "B"; // frome rules
}
if (twoPattern == "BR" || twoPattern == "RB") {
onePattern = "G"; // frome rules
}
}
// hmmm cont'd:
if (onePattern !== false) {
newRow += onePattern;
}
}
if (newRow.length > 0) {
triangle.push( newRow.toString() ); // toString so we get a deep copy to append to triangle
}
// lets move to the next row, if none added, then the loop will end next cycle
onRow++;
}
return triangle;
}
console.log( reduceTriangle( "RRGBRGBB" ) );
console.log( reduceTriangle( "RBRGBRBGGRRRBGBBBGG" ) );