Un juego muy chido de gotmilk.com hecho en Flash. Es como un juego de mesa con “miniretos” que van apareciendo dependiendo de la casilla en la que te encuentres.

El juego se trata de que tienes que ayudar a la familia Adachi (que se ha quedado sin leche) a irrumpir dentro de un fuerte que resguarda El Vaso.

Lo que más me gustó fueron las animaciones que contiene y la forma de interacción con el dado. Simplemente impresionante.

Para jugarlo haz click aquí o en la imagen.

Aunque hace un buen tiempo que salió el proyecto RainbowCrack y estas (y otras) tablas están disponibles en algunos otros sitios, siempre es bueno tener una fuente más en caso de que se nos olvide nuestro propio password.
Las tablas solo cubren un espacio muestral de contraseñas con una longitud de entre 1 y 7 caracteres alfanuméricos con una efectividad de 99.04%. Cada tabla mide 283 MB (comprimida).

lm_alpha-numeric_0_2400×40000000_table
lm_alpha-numeric_1_2400×40000000_table
lm_alpha-numeric_2_2400×40000000_table
lm_alpha-numeric_3_2400×40000000_table
lm_alpha-numeric_4_2400×40000000_table

Nota: Para mantenerme fuera de líos. No me hago responsable de cuantacosa crean que pueden hacer con esta información. Los archivos aquí publicados tienen un propósito puramente educacional y no deben ser utilizados para fines ilegales.

El algoritmo de Dijkstra sin duda es el más popular entre los algoritmos de caminos mínimos en un grafo. Este algoritmo se enfrenta a un problema complejo. La complejidad del problema radica en el tamaño del espacio de búsqueda.

Ciertamente los grafos son de las estructuras de datos que tienden a hacer explotar combinatoriamente la complejidad de los algoritmos que intentan trabajar sobre ellos. Con una cantidad creciente de nodos, los problemas de grafos tienden rápidamente a ser intratables

Algoritmo básico: Calcula la longitud del camino mínimo desde el nodo especificado hasta todos los demás nodos.

Dijkstra(Nodo root) {

	if (!root.hasChildren()) {
		return;
	}
	else {
		for (Edge e : root.getEdges()) {
			int dist = root.getTotalDistance() + e.getDistance();
			if (e.getTargetNode().getTotalDistance() > dist) {
				e.getTargetNode().setTotalDistance(dist);
			}
		}
	}
}

QuickSort es un algoritmo de ordenamiento muy eficiente. Es de naturaleza recursiva y utiliza la filosofía divide y vencerás.
La idea principal de QuickSort es hacer que el conjunto de elementos que se desea ordenar cuente con una característica especial: El arreglo debe tener un elemento δ que se encuentre en su posición final. Todos los elementos menores a δ están a su izquierda y todos los elementos mayores a δ están a su derecha.
Este elemento δ servirá como pivote que indica donde debe ser realizada la división del arreglo.

Sin embargo, es muy improbable encontrar dicha característica en todos los arreglos. Peor aún, resulta muy costoso comprobar si un arreglo dado posee la propiedad. Por lo tanto, en lugar de buscar un pivote natural, elegimos un elemento al azar (para evitar mayores complejidades al elegir un pivote) y reordenamos el arreglo alrededor de dicho elemento de forma tal que cumpla con nuestras necesidades.

Algoritmo básico:

QuickSort(arr[], int left, int right) {

	if ((right - left) >= 1) {
		int i = split(arr, left, right);
		QuickSort(arr, left, i - 1);
		QuickSort(arr, i + 1, right);
	}
}

split(arr[], int left, int right) {

	int i = left;
	int v = random();
	swap(arr, left, v);

	for (int j = left; j <= right; j++) {
		if (arr[j] < arr[i]) {
			swap(arr, i, j);
			i++;
			swap(arr, i, j);
		}
	}
	return i;
}

Nota: Algunas funciones están omitidas debido a que son muy sencillas de implementar y no son centrales para el funcionamiento del algoritmo QuickSort.

Actualización: Código funcional en Java. Esta pequeña aplicación implementa el algoritmo antes descrito y contiene una comparación de desempeño con la implementación del API. Sorprendentemente nuestro algoritmo tan básico solo es 4 veces más lento que el de Java 5.