Sherlock Homes y el problema del caballo

Después de un rato jugar el videojuego The testament of Sherlock Holmes me encontré con este acertijo conocido.

Se trata del tour del caballo como las máquinas sirven para hacer prueba y error dejé la consola y encendí el PC para escribir la solución a este.

Hay que decir que este problema es bastante sencillo de resolver para tableros pequeños y basta con un dfs o backtracking y se obtienen no sólo una sino todas las soluciones posibles :)

Así pues la idea básica del algoritmo es:


Guardar los deltas de los movimientos en alguna estructura puede ser un arreglo.

función solución(f, c, cam, vis):
  si ya visitó todas las casillas imprima cam y retorne
  para cada movimiento:
    si es posible(no se ha realizado y no se sale del tablero)
      movf = f+deltaf iésimo
      movc = c+deltac iésimo
      solución(movf, movc, cam+(movf+movc), vis+(movf+movc))
      remover movf y movc de cam y de vis

y la llamada inicial sería algo como

solucíon(0,0,'',estruc)
donde estruc es alguna estructura que permita eficientemente controlar qué casillas ya se han visitado.


Si se usa un conjunto se puede saber cuántas se han visitado aunque con una matriz también funcionaría se necesitaría un contador como parámetro adicional.

Que se diviertan!

Exponenciacion binaria y modular

Hola, estuve haciendo un par de cosas y tuve que usar un algoritmo de exponenciacion binaria y modular pero no queria que fuera recursivo asi que luego de algunos intentos, esto fue lo que consegui, espero les pueda servir de ayuda, tanto como a mi(aunque esta en java se entiende si manejas otro lenguaje :P) :

public static int expomod(int a, long b,int mod){
    int res = 1;
    while(b>0){
        if((b&1)==1)
            res=(a*res)%mod;
    b>>=1;
    a=((a%mod)*(a%mod))%mod;
    }
return res;
}

y el algoritmo en python es:

def ex(a, b,m):
     r = 1
     while(b):
             if(b&1):
                     r = (r*a)%m
             b>>=1
             a = ((a%m)*(a%m))%m
     return r

La verdad luego de ver el algoritmo recursivo, se entiende este. Lo que se hace es cambiar la recursividad a las variables, por decirlo de alguna forma. Saludos y espero sus comentarios!

Un buen tutorial donde se tratan a fondo otros algoritmos relacionados es este de topcoder.

Nota: un problema en donde se puede aplicar este algoritmo es este.

Generar particiones de un numero

Hola, a veces necesitamos generar las particiones de un numero, una partición es una forma de escribir un numero entero positivo como la suma de otros numeros enteros positivos. Por ejemplo:

Para 3, las particiones serian:
1+1+1, 2+1, 3

Ahora, podemos necesitar los numeros que conforman las particiones o simplemente cuantas particiones tiene. Para este caso, explicare como obtener el numero de particiones con programacion dinamica y modificando este algoritmo se puede obtener que numeros conforman cada una de las particiones.

La pregunta es como llegamos a que las particiones de 3, en este caso, son esas. Bien, luego de ver varios ejemplos(el 4 y el 5) si ordenamos las particiones nos daremos cuenta de algo:

Particiones hasta 5:
N. 1:
1

N. 2:
11
2

N. 3:
1 11
1 2
3

N. 4:
1 111
2 11
2 2
3 1
4

N. 5:
1 1111
2 111
2 21
3 11
3 2
4 1
5

Si nos damos cuenta, las particiones del 3 tienen a las del 2. Las del 4 tienen las del 3 y las del 2 y asi sucesivamente.

En otras palabras, podemos formar un numero de la siguiente forma(para el 4 por ejemplo):

1 + alguna forma de escribir el tres (4-1)
2 + alguna forma de escribir el dos (4-2)
3 + alguna forma de escribir el uno (4-3)
4 (solo hay una forma de escribir el numero con el mismo)

Entonces si quisieramos hacerlo para un numero y obtener todas las particiones hariamos algo como:

1+p(numero-1)
2+p(numero-2)
...
(n-1)+p(numero-(n-1)) es decir p(3) para el caso de las particiones de 4
n
p(numero) serian las particiones o el numero de particiones del numero
Y estas serian todas las particiones de n

El algoritmo para hacer esto en python seria:

numero = 5
particiones = [1] + [0] *numero
for i in xrange(1,numero+1):
    for j in xrange(i, numero+1):
        particiones[j] +=particiones[j-i]
    #print(particiones)
print(particiones[numero])

La ejecucion de este programa daria lo siguiente:
[1, 1, 1, 1, 1, 1]
[1, 1, 2, 2, 3, 3]
[1, 1, 2, 3, 4, 5]
[1, 1, 2, 3, 5, 6]
[1, 1, 2, 3, 5, 7]

y en cada iteracion sucede, tomamos un valor y anadimos las particiones del valor que falta para completar el numero.

particiones[j] = particiones que lleve + formas de hacer el valor que falta (j-i)

Podriamos modificar este algoritmo y en vez de solo sumar, agregar cada una de las particiones y asi obtendriamos los valores que conforman estas particiones

Tambien hay una formula recursiva dada por Euler para obtener las particiones de un numero.

Nota: este problema esta relacionado con un problema muy conocido que consiste en saber de cuantas formas diferentes se puede devolver una cantidad de dinero usando solo las denominaciones dadas.

Nota2: una pregunta interesante es como hacer para que en las particiones un valor no aparezca mas de una vez, sin necesidad de validar luego de haber obtenido las particiones.

Espero les sirva!