No puedo pasar este desafío de codificación: Desafío de código: https://www.codewars.com/kata/550f22f4d758534c1100025a/train/javascript
porque mi código es DEMASIADO LENTO . No estoy seguro de qué parte de mi código está causando el problema. Por eso necesito ayuda para optimizarlo.
function dirReduc(arr){ if (arr.length === 0 || arr.length === 1) return []; let lengthTracker = arr.length; for (let i = 0; i < arr.length; i++) { if (lengthTracker > arr.length) { lengthTracker = arr.length; i = 0; } switch(arr[i]) { case "NORTH": arr[i-1] === "SOUTH"? arr.splice(i-1,2) : arr[i+1] === "SOUTH"? arr.splice(i,2) : null break; case "SOUTH": arr[i-1] === "NORTH"? arr.splice(i-1,2) : arr[i+1] === "NORTH"? arr.splice(i,2) : null break; case "EAST": arr[i-1] === "WEST"? arr.splice(i-1,2) : arr[i+1] === "WEST"? arr.splice(i,2) : null break; case "WEST": arr[i-1] === "EAST"? arr.splice(i-1,2) : arr[i+1] === "EAST"? arr.splice(i,2) : null break; } i===arr.length-1? i=0:null } return arr; }Veo varios problemas con esto. Primero, como mencioné en los comentarios, empalmar matrices largas es costoso y hace que su algoritmo sea O(n^2) . Sencillo y más rápido sería usar un punto de lectura y un punto de escritura para copiar los elementos en sí mismo una celda a la vez, simplemente saltándose las aniquilaciones y luego usar el empalme una vez al final para recortar las celdas no copiadas del final de la matriz Esto lo haría O(n) .
En segundo lugar, su código busca coincidencias tanto hacia adelante como hacia atrás, lo que es innecesario y puede ser confuso. Finalmente, no hay necesidad de switch (...) ya que todas las ramas hacen lo mismo.
Así es como usaría su código para lograr esto, cambiando las cosas mencionadas anteriormente y anotadas en los comentarios.
function dirReduc(arr){ if (arr.length === 0 || arr.length === 1) return []; let lengthTracker = 0; // the write-point for(let i = 0; i < arr.length; i++) { // i is the read-point if(lengthTracker == 0) { // if no output, copy readpoint to write-point and advance arr[lengthTracker++] = arr[i]; } else { // replaces switch() if (((arr[lengthTracker-1] === "NORTH") && (arr[i] === "SOUTH")) || ((arr[lengthTracker-1] === "SOUTH") && (arr[i] === "NORTH")) || ((arr[lengthTracker-1] === "EAST") && (arr[i] === "WEST")) || ((arr[lengthTracker-1] === "WEST") && (arr[i] === "EAST"))) { lengthTracker--; // annihilate by decrementing the writepoint } else { // copy readpoint to writepoint and advance arr[lengthTracker++] = arr[i]; } } } //trim the array to only include what was written arr.splice(lengthTracker); return arr; }El empalme puede ser costoso. Podemos formar una recurrencia que asume que la función ya ha reducido correctamente la siguiente parte de la lista:
function matches(a, b){ return (a == "NORTH" && b == "SOUTH") || (b == "NORTH" && a == "SOUTH") || (a == "EAST" && b == "WEST") || (b == "EAST" && a == "WEST"); } function f(A, i=0){ if (i == A.length) return []; const rest = f(A, i + 1); const [head,...tail] = rest; if (head){ if (matches(A[i], head)) return tail; else return [A[i]].concat(rest); } return [A[i]]; }