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:
- Darle la vuelta a la cadena completa
- Ir palabra a palabra, dándole la vuelta nuevamente.
Es decir, si seguimos con el ejemplo anterior, las transformaciones serían:
- En un lugar de La Mancha
- ahcnaM aL ed ragul nu nE
- 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.
El otro día me pregunté el cómo hacía Spring para tener tantos 
Veamos pues 