aquí está la pregunta ( https://www.codewars.com/kata/5a331ea7ee1aae8f24000175 )
He estado buscando durante 2 días sobre esto. Vi un ensayo ( https://www.ijpam.eu/contents/2013-85-1/6/6.pdf ). En la discusión de codewars, dicen que podemos resolver la pregunta sin usar reglas mat, si diseñamos el código para la complejidad O (n). Lo intenté también pero no funciona. Hice mi mejor esfuerzo pero no pasó. Aquí está mi código.
Leí esto ( Triángulos de tres colores ) Me pregunto, ¿hay alguna forma de resolver esto sin usar completamente 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" }
Esta solución lo resuelve usando < O(n 2) con = O(n 2) como máximo. Utiliza dos bucles. Un ciclo while que finaliza siempre que no haya una nueva fila para procesar. Y un bucle interno que itera los colores de la matriz actual.
Esta no es una solución para aumentar la eficiencia. Es una solución para mostrar una forma no eficiente con claridad sobre cómo funcionarían las reglas. Técnicamente, podría reemplazar mi uso de "cadenas" con matrices, para aumentar la eficiencia, pero ese no es el punto para ilustrar cómo podría funcionar un algoritmo, aunque de manera ineficiente.
Todos los demás comentarios están en los comentarios del código:
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: GGBGRGBR // Becomes colour here: GRBG // We'll also assume that order of the two-pattern doesn't matter: GB -> 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" ) );