Como ganar siempre :-)

Un sistema de apuestas, muy utilizado por lo que puede verse en Google, sigue el siguiente esquema (donde lo aplicamos a una apuesta doble o nada con una moneda “justa”):

1. Empezar apostando una unidad.
2. Apostar a “cara”.
3. En caso de ganar, retirarse.
4. En caso de perder, doblar la apuesta y volver al paso 2.

Analicemos este sistema mediante un millón de simulaciones de la técnica, utilizando 3 lenguajes de programación: C++ (codepad), Python (codepad, N = 1000) y Javascript.

Como puede observarse, los resultados son esencialmente idénticos:

Number of simulations: 1000000
Minimum player balance: 1
Maximum player balance: 1
Average number of rounds before winning: 2.000831

En todas las ejecuciones observamos una ganancia fija de una unidad y que se obtiene en promedio en una pequeña cantidad de tiradas.

Donde está el problema con este sistema? En el próximo post la respuesta… 😀

Advertisement

Detectando… paralelepípedos

(Continuación de Detectando los cubos.)

En esta primera parte veremos como detectar configuraciones de puntos que pueden formar la proyección paralela de los vértices de un paralelelepípedo, resolviendo parte del problema planteado anteriormente. Analizaremos como determinar si corresponden a un cubo en un posterior post.

La idea básica detrás del algoritmo de detección es observar que las caras de un paralelepípedo son paralelogramos y que estos preservan el paralelismo de sus lados al ser proyectados en forma paralela.

Puede dividirse a este algoritmo en cinco pasos:

1. Buscar el punto que se encuentre más a la izquierda (menor valor de X) y, dentro de ellos más arriba (menor valor de Y, en nuestro caso). Ese punto será denominado p0 y será tomado como referencia.
2. Imaginando un semieje en dirección +X partiendo desde p0, se eligen los dos puntos que posean el mayor y el menor ángulo (teniendo en cuenta el signo!) respecto a ese eje. Estos puntos son denominados p1 y p2 y formarán la base para identificar la primera cara del paralelepípedo.
3. Se busca un punto p12 que cierre el paralelogramo formado por p0, p1 y p2. Estos puntos formarán la que podemos denominar “cara -X” del paralelepípedo.
4. Opuesta a la “cara -X” debe existir una “cara +X”, que además debe poseer vértices “análogos” a cada uno de los hallados anteriormente, solo que trasladados en forma paralela. Podemos buscar el análogo de p0 repitiendo el procedimiento utilizado para hallar p0 pero omitiendo los puntos p0, p1, p2 y p12.
5. Una vez hallado p3, conocemos el desplazamiento relativo entre ambas caras (-X y +X). Por lo tanto podemos buscar los “análogos” a p1, p2 y p12: p13, p23 y p123. Si todos estos puntos pueden ser hallados, entonces la serie de puntos puede ser la proyección paralela de un paralelepípedo.

En la siguiente figura podemos ver el funcionamiento del algoritmo:

Funcionamiento normal del algoritmo (detección exitosa).

Los únicos pasos donde el algoritmo puede fallar, detectando que no estamos trabajando con la proyección de un paralelepípedo, son los pasos 3 y 5:

Funcionamiento con fallo en la detección del algoritmo (paso 3).

Funcionamiento con fallo en la detección del algoritmo (paso 5).

El código correspondiente en Python, que es una traducción casi directa de los pasos mencionados anteriormente, puede encontrarse en el repositorio SVN de este blog. La única diferencia digna de mención es la adición de un “paso 0” que comprueba la cantidad de vértices.

Para probarlo basta con ejecutar el generador de casos de prueba (que creará dos archivos: input.txt y key.txt), luego el detector de paralelepípedos (que creará un archivo de salida output.txt) y, por último, el comparador (que comparará el archivo output.txt y el archivo key.txt, indicando la cantidad de falsos negativos y falsos positivos).