Archivos para las entradas con etiqueta: javascript

El otro día mi amigo Carlos nos propueso este problema: dar la vuelta a las palabras de una frase. Es decir, convertir En un lugar de La Mancha en Mancha La de lugar un En. La restricción del algoritmo es que tienes que hacer la modificación in place: puedes usar variables auxiliares para todo lo que quieras, menos para transformar la cadena.

Voy a plantear la solución en nuestro buen amigo JavaScript, y asumir que en lugar de una cadena, a nuestro algoritmo le llega un array de bytes (algo que se puede hacer sencillamente con un TextEncoder).

Tras una primera aproximación fallida, la solución por la que opté fue realizar los siguientes pasos:

  1. Darle la vuelta a la cadena completa
  2. Ir palabra a palabra, dándole la vuelta nuevamente.

Es decir, si seguimos con el ejemplo anterior, las transformaciones serían:

  1. En un lugar de La Mancha
  2. ahcnaM aL ed ragul nu nE
  3. Mancha La de lugar un En

Darle la vuelta a la cadena

Es la clásica solución. Para darle la vuelta a la cadena, recorrmos el array hasta la mitad e intercambiamos elementos por delante y por detrás. Aun así, le he dado una vueltecilla añadiendo una cosa chula: no utilizo variables auxiliares para intercambiar elementos del array. ¿Cómo? Gracias a la magia y al poderío de las operaciones XOR. Así, dado un array y dos posiciones, podemos definir una operación switchItems como la siguiente:

const switchElements = (item, from, to) => {
  item[from] = item[from] ^ item[to];
  item[to] = item[from] ^ item[to];
  item[from] = item[from] ^ item[to];
};

Así, dado un array de bytes, podemos darle la vuelta de la siguiente manera:

const reverse = item => {
  for(
    let i = 0, j = item.length - 1; 
    i < item.length >> 1;
    i++, j--
  ) {
    switchElements(item, i, j);  
  }
};

Aquí otra cosa chula: en lugar de dividir la longitud entre dos, podemos desplazar un bit a la derecha para obtener el mismo resultado.

Ya que estamos, voy a aprovechar en esta parte para lo siguiente: una vez intercambiados los elementos de la cadena, cuando me tope con un espacio en blanco (ASCII 32) me guardaré sus posiciones anterior y siguiente, y así tendré una colección con las delimitaciones de todas las palabras en la cadena:

const BLANK = 32;

const reverse = item => {
  let wordLimits = [0];

  for(
    let i = 0, j = item.length - 1; 
    i < item.length;
    i++, j--
  ) {
    if(i < item.length >> 1) {
      switchElements(item, i, j);  
    }

    if(BLANK === item[i] && i !== item.length - 1) {
      wordLimits.push(i - 1);
      wordLimits.push(i + 1);
    }
  }

  wordLimits.push(item.length - 1);
};

Poniendo las palabras nuevamente al derecho

Como tenemos todas las palabras delimitadas, podemos recorrer el array nuevamente para darles la vuelta y dejarlas al derecho:

for(let i = 0; i < wordLimits.length - 1; i+=2) {
  for(
    let from = wordLimits[i], to = wordLimits[i+1];
    from < (wordLimits[i+1] + wordLimits[i] + 1) >> 1;
    from++, to--
  ) {
    switchElements(item, from, to);
  }
}

Un bucle for dentro de otro bucle for no tiene por qué indicar complejidad exponencial. En el fragmento de código recorremos menos elementos que el total de ítems en la cadena porque nos saltamos los espacios en blanco.

Solución completa

Ya sólo nos queda juntarlo todo para tener listo nuestro algoritmo (si no m e equivoco) de complejidad O(n):

const BLANK = 32;

const switchElements = (item, from, to) => {
  item[from] = item[from] ^ item[to];
  item[to] = item[from] ^ item[to];
  item[from] = item[from] ^ item[to];
};

const reverse = item => {
  let wordLimits = [0];

  for(
    let i = 0, j = item.length - 1; 
    i < item.length;
    i++, j--
  ) {
    if(i < item.length >> 1) {
      switchElements(item, i, j);  
    }

    if(BLANK === item[i] && i !== item.length - 1) {
      wordLimits.push(i - 1);
      wordLimits.push(i + 1);
    }
  }

  wordLimits.push(item.length - 1);

  for(let i = 0; i < wordLimits.length - 1; i+=2) {
    for(
      let from = wordLimits[i], to = wordLimits[i+1];
      from < (wordLimits[i+1] + wordLimits[i] + 1) >> 1;
      from++, to--
    ) {
      switchElements(item, from, to);
    }
  }
  
  return item;
};

Testeando

Para testearlo lo mejor será irse a stackblitz, donde he preparado algunos tests con Jasmine. Podemos jugar con el algoritmo y ponerle contadores si queremos para ver el número de iteraciones que se realizan.

Supongamos que tenemos un árbol binario representado en un array. Por ejemplo, el array [3, 6, 2, 9, -1, 10] representa el siguiente árbol (-1 indicaría que el nodo no existe):

Árbol representado por el array

Escribir una función que determine qué lado del árbol tiene más peso: si el izquierdo (devolviendo la cadena "Left") o el derecho ("Right"). Devolverá una cadena vacía "" en caso de que los pesos sean iguales o no tenga ramas.

Por ejemplo, para el array que hemos presentado el resultado sería "Left".

Vamos a intentar resolver este problema en JavaScript, de manera que tenga un coste lineal.

Solución

Para mi lo primero sería saber si un nodo pertenece al lado izquierdo o al lado derecho del árbol. Para eso, sería interesante saber en qué nivel de profundidad del árbol nos encontramos.

Por lo que vemos en el array del ejemplo:

[
  3, // raíz
  6, // nivel 1
  2, // nivel 1
  9, // nivel 2
  -1, // nivel 2
  10 // nivel 2
]

Podríamos recurrir a nuestros amigos los logaritmos para inferir que el nivel de una posición en el array es igual a log2(posición), lo que en JavaScript viene siendo:

const level = value => Math.floor(Math.log(value) / Math.log(2));

Una vez sabemos el nivel en que nos encontramos, la primera mitad de los ítems corresponderá al lado izquierdo del árbol, mientras la segunda mitad corresponderá al lado derecho. Cada nivel puede tener hasta 2nivel elementos, y de ahí podemos sacar el punto medio. Así, dado un índice i del array, podríamos decir que:

const currentLevel = levelOf(i + 1);
const levelStartIndex = Math.pow(2, currentLevel) - 1;
const levelEndIndex = levelStartIndex + Math.pow(2, currentLevel) - 1;
const iterationMiddle = (levelStartIndex + levelEndIndex) / 2;

if(i < levelMiddlePoint) {
  // estamos en el lado izquierdo
} else {
  // estamos en el lado derecho
}

Sabiendo si estamos en el lado izquierdo o derecho de árbol, ya podemos utilizar acumuladores para determinar qué lado del árbol pesa más.

Casos especiales

Tengamos en cuenta los siguientes casos especiales:

  • Si el array tiene cero o un elementos, podríamos considerar que los pesos son iguales.
  • Si el array tiene exactamente dos elementos: podríamos decir que pesa más el lado izquierdo, siempre que el elemento en la última posición no valga 0 o -1.

Con todo esto, a mi se me ocurrió esta solución:

const LEFT = "Left";
const RIGHT = "Right";
const EQUAL = "";

const levelOf = (value) => Math.floor(Math.log(value) / Math.log(2));

const solution = (arr) => {
  let left = 0;
  let right = 0;

  if (arr.length <= 1) {
    return EQUAL;
  }

  if (arr.length === 2) {
    return arr[1] >= 0 ? LEFT : EQUAL;
  }

  for (let i = 1; i < arr.length; i++) {
    const currentLevel = levelOf(i + 1);
    const levelStartIndex = Math.pow(2, currentLevel) - 1;
    const levelEndIndex = levelStartIndex + Math.pow(2, currentLevel) - 1;
    const iterationMiddle = (levelStartIndex + levelEndIndex) / 2;

    if (arr[i] <= 0) {
      continue;
    }

    if (i <= iterationMiddle) {
      left += arr[i];
    } else {
      right += arr[i];
    }
  }

  if (left === right) {
    return EQUAL;
  }

  if (left < right) {
    return RIGHT;
  }

  return LEFT;
};

He puesto la solución en stackBlitz con un par de tests que comprueban si funciona o no.

¿Qué te parece la solución? ¿Se te ocurre una manera similar de resolver el problema?

Serán incontables ya las muchas veces que he instalado paquetes globales de npm para ejecutarlos sólo una vez y luego desinstalarlos.

Es para gente como yo que, a partir de la versión 5.2.0 de npm, también tenemos npx.
Leer el resto de esta entrada »

After reading this Gil Fink’s post, I wanted to set context mode in StencilJS in order to determine whether the application is loaded on a Windows Phone, Android, iOS, or a Desktop the same way ionic framework does.
Leer el resto de esta entrada »

Recientemente leí este artículo de mi buen amigo Norman Coloma.

En él, introduce una mejora en el uso de validadores asíncronos con respecto a muchos de los ejemplos que verás por internet, llevándose su lógica a un servicio externo.

Aún así, y tras hablarlo con él, vimos que ese componente era demasiado listo:

  • ¿Por qué saber de servicios externos?
  • ¿Por qué saber de controles abstractos?
  • ¿Por qué hacer ese bind a la hora de validar?
  • ¿Por qué no introducir un validador asíncrono de una manera tan fácil como hacemos con los síncronos?

Leer el resto de esta entrada »

Mira que había visto varias veces que el uso de async/await era sencillo, pero aún me estaba resistiendo y optando por el uso de promesas. Viendo que está soportado en la mayoría de navegadores de escritorio actuales y en las versiones más recientes de node, he decidido hacer unas pruebas para enamorarme de esta feature al instante.
Leer el resto de esta entrada »

El otro día me estaba preguntando cómo hacer para enviar cabeceras de autenticación con Angular en todas mis peticiones HTTP. En AngularJS lo resolvía fácilmente con un interceptor, pero aquí ya no tenemos de eso. Leer el resto de esta entrada »

La semana pasada creé un par de directivas para drag&drop en Angular por dos motivos:

  • Pienso que resuelve un caso de uso bastante útil, aunque muy general.
  • Quería ver cómo funciona la subida a npm.

Leer el resto de esta entrada »

Tras una jornada navideño-vacacional, la apertura de la tienda de pegatinas y el inicio del taller de Angular de la UA… ¡Volvemos a la carga! Hoy he realizado un par de pruebas sencillas para comprender las dos estrategias de detección de cambios ofrecidas por Angular. Leer el resto de esta entrada »

Últimamente estoy viendo bastante potencia en usar Docker como contenedor de mis herramientas para el desarrollo. Tras dockerizar asciidoctor, y con el taller de introducción a Angular de la UA en pocas semanas, he creado una imagen con el CLI de Angular para facilitar el setup de los entornos en caso de llevarse uno su propio equipo. Leer el resto de esta entrada »

A %d blogueros les gusta esto: