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?

spring-boot-modulesEl otro día me pregunté el cómo hacía Spring para tener tantos @EnableFoo, @EnableBa, etc… y viendo lo sencillo que es me he decido por compartirlo con vosotros.

Todo surge ante una necesidad, que es la de tener alguna configuración común que queramos reutilizar entre distintos proyectos. Imaginemos que todos nuestros proyectos hacen uso de la misma Base de Datos, la cual tenemos configurada con Spring Data JPA, pero queremos hacer la configuración de la misma muy sencilla (añadir dependencia y listo).

Lo primero que hacemos es crearnos un módulo de Spring Boot aparte, pero a este le borramos la clase de Application que nos genera, más que nada no es una aplicación. Y le vamos a añadir toda la configuración de Spring Data JPA: dependencias y propiedades que ya teníamos (estamos moviendo las cosas de sitio).

Eso sí, antes cuando levantábamos la aplicación Spring Boot hacia toda la magia, pero ahora eso no sucederá, tendremos que hacerlo nosotros. Para ello, definimos una clase de configuración que cargue todo.

@Configuration
@EnableAutoConfiguration
@PropertySource(value = {"classpath:jpa-${spring.profiles.active}.properties"}, ignoreResourceNotFound = true)
public class JpaSupportConfiguration {
}

Se utilizan ficheros properties en vez de yml porque con Spring no existe una forma tan sencilla de cargarlos y que spring data coja la configuración correcta.

Tendremos un fichero de propiedades por entorno y lo cargamos dependiendo del perfil activo de Spring (spring.profiles.active). A destacar, que todas las propiedades se podrán sobrescribir con tan solo añadirla al application.yml de nuestro proyecto.

Una vez en este punto, tenemos tres opciones para cargar nuestro módulo:

Uso de @Import

Eso es dentro de alguna clase de configuración de nuestra aplicación hacer un

@Import(JpaSupportConfiguration.class)

Uso de @EnableJpaSupport

Para ello creamos en el módulo una anotación que lo único que hará es el @Import de más arriba.

@Retention(RetentionPolicy.RUNTIME)
@Target({ElementType.TYPE})
@Documented
@Import(JpaSupportConfiguration.class)
@Configuration
public @interface EnableJpaSupport {
}

De esta forma podemos sustituir el @Import por:

@EnableJpaSupport

Auto configuración

Por último, está la opción de que se auto-configure por el simple hecho de añadir la dependencia. Para ello añadimos dentro del classpath el fichero META-INF/spring.factories en el cual añadiremos una línea con nuestra clase de configuración:

org.springframework.boot.autoconfigure.EnableAutoConfiguration=\
edu.cinfantesa.config.JpaSupportConfiguration

Conclusiones

Como hemos podido ver, es muy sencillo crear módulo con Spring Boot. De forma que si nuestro proyecto es grande, nos permite tener cada configuración en su sitio y no replicada entre las distintas aplicaciones.

A mi personalmente, el modo de importar un módulo que más me gusta es el segundo, tal y como hace Spring con sus @EnableFoo….

Para temas más técnicos si que nos puede aportar algo más la parte de auto-configuración.

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 »

A %d blogueros les gusta esto: