Archivos Por autor

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?

Pues me encuentro en fase de pensar substituir unos websockets que tenemos por server-sent events (SSE). Lo utilizamos sólo para recibir eventos, con lo que para nuestro caso de uso nos podemos olvidar de la bidireccionalidad que ofrece el websocket.

Si alguien se encuentra en un caso similar, puede ver el código fuente en este enlace.

El ejemplo se compone de tres piezas:

API Node.js

Hacer estas cosas en Node.js me encanta por su sencillez, y no tener necesidad de importar ninguna dependencia externa ni nada. Si no fuera una PoC el código sería hasta más bonito. Esta api simplemente abre un stream de datos, donde se envía un número aleatorio cada segundo (uno distinto para cada request), siempre y cuando la petición esté abierta.

Cliente Angular

Una sencilla aplicación creada con el CLI de Angular.

Dispone cuatro componentes iguales que se suscriben a los eventos enviados por la API Node.js. El EventSource se crea en la primera suscripción, y se cierra cuando ya no hay más observers. Podemos ver cómo se ha impementado en este servicio.

API Gateway

Realizado con Spring Cloud Gateway, utiliza el RouteLocatorBuilder. para mapear las peticiones contra el servicio Node.js (ruta /sse) o contra el cliente web (ruta /*).

Y bueno, el ejemplo funcionando tiene esta pinta.

sse.gif

Recomiendo descargarlo y trastear con él. Incluye un docker-compose.yml para que sea más fácil montarlo.

¡Ah! Y para seguir cacharreando, node y java utilizan las imágenes distroless de Google.

Quiero hacer también otra versión en que los SSE se emitan desde un proyecto Spring Boot, pero es que es taaan fácil hacer esto con Node…

Cuando estén las dos, quiero hacer una versión para utilizarlo en conjunción con Protocol Buffers, que también venimos usándolo, aunque sólo con JavaScript. Así veremos su uso en varios lenguajes.

El otro día estuve haciendo un sencillo editor de markdown para una formación de Angular.

Aunque está disponible en Github Pages, también hay una imagen de Docker con una versión de la aplicación servida a través de un nginx.

Dado que no es una aplicación universal, una vez construida la aplicación realmente se trata de contenidos estáticos. Así que para servirlos no necesito node.js ni nada que se le parezca. Es por ello que la imagen de Docker se genera a través de un proceso de construcción multi-etapa.

En la primera de ellas, el CLI de Angular genera un entregable de producción.

En la segunda, utilizamos nginx para servir el contenido generado previamente.

Las construcciones multi-etapa son muy útiles, porque podemos necesitar unos recursos para construir, y otros para servir, como es el caso que se presenta aquí. Además, nos eliminamos muchas etapas intermedias (recordemos que cada RUN engorda nuestra imagen un poquito más), consiguiendo así que nuestras imágenes “pesen” menos.

Vamos a ver cómo realizar un backup de una base de datos mongo y restaurarlo en otra instancia.

Para ello, haremos uso combinado de los comandos mongodump y mongorestore.

Un ejemplo de uso del comando mongodump sería el siguiente:

mongodump \
  --host ip.direccion.origen \
  --port 27017 \
  --username miUsuario \
  --password M1P455W0rD \
  --db nombre_bd \
  -o bd_dump

Donde el parámetro -o hace referencia al directorio donde se almacenarán los backups.

En el caso de mongorestore, indicaremos el host donde queremos recuperar los datos, así como la carpeta bd_dump, donde están los backups:

mongorestore \
  --host ip.direccion.destino\
  --port 27017\
  --username miUsuario \
  --password M1P455W0rD \
  --db nombre_bd\
  bd_dump

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 »

I’m doing a personal project that uses ionic framework, firestore and part of the @ngrx platform. One of de decisions I’ve made is to use Effects to perform navigation.

On that use case, it’s useless for an effect to dispatch an action.
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 »

We are currently doing some spike applications that involve part of the Spring Cloud Netflix stack.

One of them is a Zuul edge server to proxy some microservices and handle authentication. On these microservices we need some special, custom headers. So we are going to see how to create a custom Zuul filter in our Spring context that add the user’s name on a header before proxying:
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 »

A %d blogueros les gusta esto: