Growth rate of the children of Israel in Egypt

Reading the bible I've found some things that I'd like to share, about the growth rate of the children of Israel ein Egypt.

According to Genesis 46:27: "And the sons of Joseph who were born to him in Egypt were two persons. All the persons of the house of Jacob who went to Egypt were seventy."

And Numbers 1:45-46: " So all who were numbered of the children of Israel, by their fathers' houses, from twenty years old and above, all who were able to go to war in Israel--all who were numbered were six hundred and three thousand five hundred and fifty."

And Numbers 1:1: "Now the Lord spoke to Moses in the Wilderness of Sinai, in the tabernacle of meeting, on the first day of the second month, in the second year after they had come out of the land of Egypt, saying:"

So, taking this data it is not hard to see that in 430 years, 70 were multiplied to 603550, giving a growth rate of 0.0212982635902, it means 2,1%.

Today, wikipedia says: "The CIA World Factbook gives the world annual birthrate, mortality rate, and growth rate as 1.89%, 0.79%, and 1.096% respectively.[5] The last 100 years have seen a rapid increase in population due to medical advances and massive increase in agricultural productivity[6] made possible by the Green Revolution.[7][8][9]"

So, the growth rate of the children of Israel in Egypt was 2 times the current growth rate of world population taking account that today we have medical advances! Is it not amazing?

PD: as an attachment I've wrote some code in python to see the number of people of Israel in the 430 years

def fu(pob, grow, delta_t):
 i_delta_t = int(delta_t)
 for i in range(i_delta_t+1):
  if i%10==0:
   print "year",i,"->",pob
  pob*=grow

Here is the output(this is every 50 years):

year 0 -> 70.0
year 50 -> 200.783359284
year 100 -> 575.913676647
year 150 -> 1651.91260935
year 200 -> 4738.23661356
year 250 -> 13590.8437765
year 300 -> 38983.0752706
year 350 -> 111816.468686
year 400 -> 320726.945802
year 410 -> 395969.179647
year 420 -> 488863.169379
year 430 -> 603550.0

Upper bound en java

La funcion en c++ de upper_bound suele ser muy util. En java quedaria algo como lo que aparece en la siguiente imagen:

Asi tendriamos complejidad de O(log2(n))

Basicamente se trata de escribir una busqueda binaria y modificarla.

El if final es por si no encontramos ningun valor mayor que el dado, entonces al igual que en la funcion de C++ se devuelve la posicion final dada a la funcion.

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!

Búsqueda binaria

Hola, en muchas ocasiones tendremos que escribir una búsqueda binaria y deberemos tener el concepto claro, ya que no siempre se puede ver tan fácilmente que el problema que debemos solucionar, se puede resolver con una búsqueda binaria.

Primero que todo hay que aclarar, la búsqueda binaria, nos sirve para eso, buscar. Segundo, la restricción para usar la búsqueda binaria es que los elementos estén ordenados. Tercero, si queremos obtener un beneficio de esta, debe realizarse sobre una estructura a la cual se pueda acceder a cualquier elemento en tiempo constante, es decir O(1).

La idea del algoritmo está basado en el paradigma divide y vencerás. Divide y vencerás viene de los romanos, ya no recuerdo por qué, pero lo importante es la idea detrás. Se suele hablar de dividir un problema en subproblemas y de esta forma resolverlos más fácilmente. En la búsqueda binaria se aplica simplemente dividiendo el arreglo en dos, olvidando lo que no nos interesa y centrándonos en lo que sí.

Si tenemos un arreglo y sabemos que está ordenado, por ejemplo:

1 3 6 8 9 11 15

y necesitamos buscar el número 9 y hacemos una búsqueda lineal(iterar uno por uno) tendríamos que hacer 6 iteraciones. Sin embargo, si nos damos cuenta, no es necesario iterar por cada uno y verificar que sea el número que buscamos, por ejemplo, si estamos en la mitad(número 8) sabremos que si el valor que buscamos está en el arreglo tendría que estar a la derecha, y no es necesario buscarlo en la mitad de la izquierda. De esta forma ya nos habremos olvidado de la mitad del arreglo. Luego, podríamos, ¿por qué no?, hacer lo mismo con el arreglo resultante y verificar si el número está en este arreglo, ¿cómo? mirando si es el valor de la mitad el que buscamos. Se recomienda que se haga por cuenta propia el intento de escribir el código que realiza esto, lo cual no es muy complicado. A continuación el pseudocódigo:

Por la ley de la tricotomía, para los enteros se cumple que solo puede entrar a un if de los mostrados anteriormente, y como de una u otra forma, en los computadores sólo trabajamos con valores enteros, entonces podemos estar tranquilos.

Escribir esto en código no es muy complicado, solo hay que tener cuidado de no enredarse, ya sea por desesperación o apuro se pueden cometer errores tontos :)

Finalmente, al dividir el arreglo en dos cada vez, estamos obteniendo una complejidad de O(log(n)) lo cual es lo suficientemente rápido para valores muy grandes. Digamos 10**1000 tiene 1000 dígitos y aún así podríamos buscar un valor en 3321 iteraciones, lo cual no es nada comparado con la cantidad de elementos en total.

Si no tenemos los elementos ordenados, tendremos que pensarlo dos veces, ya que la forma más rápida de ordenar es lineal, es decir O(n), pero con ciertas restricciones y para propósito general tenemos O(n*log(n))

En el siguiente link pueden encontrar implementaciones en varios lenguajes de programación:  http://www.codecodex.com/wiki/Binary_search

Información adicional:
http://googleresearch.blogspot.com/2006/06/extra-extra-read-all-about-it-nearly.html
http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=binarySearch

Solucionando sudokus

Su Doku es un juego muy conocido, no entraré en detalles históricos. Este problema puede ser visto como el problema de colorear un grafo, de esta forma los colores son cada uno de los números del uno al nueve, los nodos son cada una de las casillas y están conectados si están en un mismo recuadro, en una misma fila o en una misma columna.

Pasando a la solución por backtracking bien se puede ver que la fuerza bruta consiste en ubicar las casillas vacias y poner un numero en cada una de ellas y ver cuando ya no hayan casillas vacias si el sudoku ha sido resuelto, de no ser así se vuelve a atrás y se intenta con otros números. El problema de este enfoque es que si hay n casillas vacías se tendrán n! (n factorial) formas de llenar estas casillas. Tal vez para unas 9 casillas vacías funcione, pero si se intenta con 10 o más en un ordenador común en la actualidad, puede tardar mucho tiempo.

Así que la mejor forma de hacerlo es ver cuál casillas de las vacías tiene menos posibilidades y optar por una de ellas y hacer lo mismo recursivamente hasta que no hayan casillas vacías, en este punto se verifica si el sudoku está bien, de ser así ya está, si no entonces se vuelve atrás y se opta por otra de las posibilidades en la casilla que tenia varias posibilidades. Finalmente, si el sudoku está bien construido se podrá llegar a una solución.

En pseudocódigo esto podría ser algo como (la implementación en java o cpp no va más de 80 líneas! :) )

Creo que esta es la forma mas simple de resolver este problema, otro enfoque es usando la ténica de Knuth de "Dancing links". El enfoque presentado aquí no es el más eficiente pero es bastante sencillo de programar y puede ser útil en un concurso de programación :)

Cualquier comentario o duda, comenten.

Nota: les dejo algunos problemas que se pueden resolver con este algoritmo.

https://icpcarchive.ecs.baylor.edu/index.php?option=onlinejudge&page=show_problem&problem=2246
http://projecteuler.net/problem=96

Mínimo común divisor

En algunos problemas se debe encontrar el divisor común mínimo de uno o más números. Sí, el divisor común mínimo, no el máximo. El mímimo común divisor es muy similar al máximo común divisor, en ocasiones es el mismo pero no se deben confundir. El GDC(máximo común divisor) entre 54 y 24 es 6 mientras que el mínimo común divisor es 2.

Para obtener el gcd se puede usar el algoritmo de euclides, el cual en código es:

static int gcd(int a, int b){
if(b==0)return a;
return gcd(b,a%b);
}

Una vez que se tiene el gcd se puede encontrar el divisor común mínimo.

Si r = gcd(a,b) y r = c*d entonces c y d dividen a y b.

De esta forma, lo que debemos hacer es descomponer el gcd en sus factores primos y sacamos el mínimo. De esta forma obtendríamos el mínimo común divisor.

Nota: un problema que se resuelve con esta idea es este.

Interfaz en java se congela

Hola, no se si alguna vez les haya pasado cuando están trabajando en alguna GUI en java y necesitan realizar una tarea mas o menos pesada, la GUI se bloquea y se queda congelada como si la aplicación hubiera muerto, pero en realidad esta haciendo el trabajo, en estos casos lo que se puede hacer para no dar la impresión que el programa ha muerto (e inhabilitar el botón mientras se hace la tarea, o poner un "loading...") es pasarle la tarea que se hacia en el botón a un hilo y tan pronto el hilo acabe que vuelva a activar el botón o que quite el "loading...".

Espero les sirva y si tienen algo que agregar o alguna duda no duden en preguntar.