Solving the product & sum riddle

Followup to Product & Sum.

Contradicting what was said in the previous post, the blue eyed islanders puzzle will be solved in a future post to avoid making this post excessively long. 😀

Product & Sum

One way to visualize the structure of this problem is to take each assertion by P and S as a filter to be applied over the initial set of integer pairs. This solution will then represent each of these filters as a block of Python code, with additional text explaining how each filter is connected with the associated assertion.

Given are X and Y, two integers, greater than 1, are not equal, and their sum is less than 100. S and P are two mathematicians; S is given the sum X+Y, and P is given the product X*Y of these numbers.

It is clear that we can restrict the first number to be strictly less than the second number, as the order of the numbers cannot be determined from the given data. Then we can get all the allowed pairs with the following Python code:

all_pairs = [(x, y)
             for y in range(2, 100) for x in range(2, y)
             if x + y < 100]

– P says “I cannot find these numbers.”

This implies that there are multiple allowed pairs whose products match the value that was given to P. We can start counting the number of pairs with each possible product:

num_pairs_by_prod = {}
for x, y in all_pairs:
    if x * y not in num_pairs_by_prod:
        num_pairs_by_prod[x * y] = 0
    num_pairs_by_prod[x * y] += 1

The pairs allowed by P’s assertion are those whose product is shared with other pairs:

pairs_1 = [(x, y) for x, y in all_pairs if num_pairs_by_prod[x * y] > 1]

– S says “I was sure that you could not find them.”

Then we know that the value of the sum is enough to know that the product cannot identify the pair of integers. The set of sums of integer pairs that can be identified by their products is:

identif_by_prod_pairs_sums = set(x + y for x, y in all_pairs
                                 if num_pairs_by_prod[x * y] == 1)

As the sum is enough to know that the integer pair cannot be identified by its product, the sum of the pair cannot be in the above set:

pairs_2 = [(x, y) for x, y in pairs_1
           if x + y not in identif_by_prod_pairs_sums]

– P says “Then, I found these numbers.”

This indicates that in pairs_2, the list of pairs restricted by the first two assertions, the correct pair can be identified by its product. Then we can do essentially the same we did in the first step but now keeping the pairs identifiable by their products:

num_pairs_by_prod_2 = {}
for x, y in pairs_2:
    if x * y not in num_pairs_by_prod_2:
        num_pairs_by_prod_2[x * y] = 0
    num_pairs_by_prod_2[x * y] += 1
pairs_3 = [(x, y) for x, y in pairs_2 if num_pairs_by_prod_2[x * y] == 1]

– S says “If you could find them, then I also found them.”

This implies that the pair can be identified by its sum from the list restricted by the first three assertions. We can get the final pairs list repeating the previous step, but now searching for a unique sum:

num_pairs_by_sum_3 = {}
for x, y in pairs_3:
    if x + y not in num_pairs_by_sum_3:
        num_pairs_by_sum_3[x + y] = 0
    num_pairs_by_sum_3[x + y] += 1
pairs_4 = [(x, y) for x, y in pairs_3 if num_pairs_by_sum_3[x + y] == 1]

Putting the code together, adding a print statement to get the final list of pairs and running the code we get

[(4, 13)]

matching the results in the literature.

Advertisement

400 teracycles, 200 gigabytes, 7 collisions

(Follow-up to Sumando subconjuntos – La respuesta.)

Introduction

In a previous post (and in a comment from Guille [ɡiˈʒe] 😀 ) we have seen how the pigeonhole principle implies that a set of 70 numbers in the range [10¹⁸, 10¹⁹) must have two subsets with equal sum. But this is a non-constructive proof, as it doesn’t give us the two subsets with the same sum. To rectify this omission, in this post we will see how this “sum collision” can be obtained.

Finding collisions: simple cases

We can start by defining the problem in a more general way: given a sequence of elements x_i and a function f(), find two elements of the sequence, x_j and x_k, such that f(x_j) = f(x_k). In this way the sum collision problem can be reduced to finding a duplicate in the associated sequence of sums, f(x_i).

Two common ways to get duplicates in a sequence are the following:

def find_duplicate_sort(g):
    sl = sorted(g)
    prev = None
    for e in sl:
        if e == prev:
            return e
        prev = e
    return None

def find_duplicate_set(g):
    es = set()
    for e in g:
        if e in es:
            return e
        es.add(e)
    return None

The first one has O(n log n) complexity and the second one has O(1) complexity if we use a hash-based set. As the set-based approach also has a lower constant, we will use this approach in the rest of this post.

This algorithm works well if the sequences to be inspected for duplicates can be fit entirely in RAM, but in this case we have seen that tens of billions of elements must be inspected to have a high probability of finding a collision. In the next section we will analyse how this restriction can be evaded.

Finding collisions in big sets

Each of the subsets to be evaluated in this problem can be encoded using 70 bits and, to allow a simple and fast sum calculation algorithm to be used, this was rounded up to 10 bytes. Then, if we want to inspect 20 billion subsets of 35 elements to get a very high probability of not wasting the calculation time, we will need 200 GB to store the whole sequence. 200 GB of data cannot be stored in the RAM of an usual machine, but it’s quite easy to store this amount of data in a hard disk nowadays.

To allow a fast hash-set based RAM collision search while keeping the bulk of the data in disk, we can take the following approach:

1. Generate in RAM a big number of random subsets and sort them by their sums.
2. Find a vector of numbers (to be called “pivots”) aplitting the sorted subsets vectors by their sums in approximately equal-sized segments. (The segment n will be composed by all the subsets whose sum is between pivot n-1 and pivot n).
3. Generate in RAM a big number of random subsets and sort them by their sums.
4. Split the sorted subset vector in segments using the previously generated pivots and append each segment to an associated segment file (for example, append segment 3 to 0003.bin).
5. Repeat steps 3 and 4 until getting enough subsets.
6. Check each segment file at a time for collisions.

If we choose enough pivots, the size of each segment file will be small enough to allow easily doing step 6 with a hash-based set (each segment file won’t have the same size, as the generated subsets are random; but the law of large numbers ensures that their sizes won’t be very different).

Source code & parameters

The (ugly) C code that checked for collisions can be found in the repository associated with this blog. The chosen parameters were:

• Number of subsets: 2·10¹⁰.
• Number of subsets in RAM: 10⁷.
• Number of elements in each subset: 35 (constant).
• Number of segments: 1000.
• Number of slots in the hash-set: 2²⁷.

Results

The first stage (segment file generation) elapsed time was approximately 41 hours, somewhat over my original estimation of 36 hours, and the segment file range ranged from 194827630 bytes to 206242980 bytes. The second stage (collision detection inside each segment file) lasted for 12-18 hours.

The output of the second stage (discarding files where no collisions were found) was:

Processing file 218...  Collision between identical elements.
 DONE in 40.754850s.
Processing file 363...  Collision between different elements!!!
  ed940f4f5710c6351a00
  a35377a5a74a03961c00
 DONE in 38.585990s.
Processing file 394...  Collision between different elements!!!
  9ab5dfa6312e090e2a00
  6558c9c8eab667233400
 DONE in 35.570039s.
Processing file 409...  Collision between different elements!!!
  2429d70f6ff500ab2c00
  423cf8c758740ac73b00
 DONE in 34.499926s.
Processing file 434...  Collision between different elements!!!
  5a8bf5a532915f213100
  496ebc281e9958713e00
 DONE in 32.610608s.
Processing file 475...  Collision between different elements!!!
  c35d3f427a7c488c0e00
  4e37132b717a287a1900
 DONE in 21.971667s.
Processing file 655...  Collision between different elements!!!
  4653023676ea8e5f1900
  6abb914e641ba45a3900
 DONE in 21.514123s.
Processing file 792...  Collision between different elements!!!
  8a4a63d85de377130600
  853d3d45b15e0c471e00
 DONE in 21.506716s.

Each set is represented as a byte string with bit number increasing when advancing through the byte string. For example, ed940f4f5710c6351a00 represents the bit string 10110111001010011111000011110010111010100000100001100011101011000101100000000000 and, consequently, the subset with indices 0, 2, 3, 5, 6, 7, 10, 12, 15, 16, 17, 18, 19, 24, 25, 26, 27, 30, 32, 33, 34, 36, 38, 44, 49, 50, 54, 55, 56, 58, 60, 61, 65, 67, 68. Its elements are

5213588008354709077 9115813602317594993
1796745334760975384 3579709154995762145
2312952310307873817 3627590721354606439
5763055694478716846 2730952213106576953
4868653895375087301 9737387704190733086
9262565481673300485 5968266991171521006
6752113930489992229 3772194655144630358
9029836747496103755 3318990262990089104
9205546877037990475 9849598364470384044
1376783969573792128 1108556560089425769
7820574110347009988 6951628222196921724
4776591302180789869 7999940522596325715
2290598705560799669 7835010686462271800
8998470433081591390 9131522681668251869
9096632376298092495 5295758362772474604
5953431042043343946 3151838989804308537
8643312627450063997 3624820335477016277
3782849199070331143

and its sum is 203743882076389458417.

In the same way, the set a35377a5a74a03961c00 has elements

5213588008354709077 9011219417469017946
3579709154995762145 3627590721354606439
5941472576423725122 4317696052329054505
2730952213106576953 5014371167157923471
9737387704190733086 9262565481673300485
5968266991171521006 5917882775011418152
5866436908055159779 9233099989955257688
3772194655144630358 3318990262990089104
9990105869964955299 2664344232060524242
1376783969573792128 1108556560089425769
7820574110347009988 9889945707884382295
7652184907611215542 8082643935949870308
4271233363607031147 6415171202616583365
6393762352694839041 2290598705560799669
7481066850797885510 5295758362772474604
5953431042043343946 9929081270845451034
7207546018039041794 3624820335477016277
3782849199070331143

and 203743882076389458417 as its sum, the same value as the previous different subset. 😀

JS puzzle

The previous post asked what happened when the JS code

(function(f){f(f)})(function(g){g(g)})

was executed. In first place we can observe that the two anonymous functions are really the same, as they only differ in the name of a dummy parameter. Let’s call this function u() and observe what happens when we apply u() over a function f():

u(f) -> f(f)

It’s clear that u() applies its argument over itself. As in this case we are applying u over itself, the result will be

u(u) -> u(u)

giving us an infinite recursion.

JS recursive puzzle

What happens when we execute the following Javascript code and why does it happen?

(function(f){f(f)})(function(g){g(g)})

In the next post, I will show the answer to this problem and the results of the subset sum collision detection. Stay tuned 🙂

Sumando subconjuntos – La respuesta

Solución “no constructiva”

(Esencialmente es la misma que Guillermo presentó en un comentario del post anterior, solo difiere en la forma de acotar 🙂 )

La solución es mucho más simple de lo que podría parecer a primera vista y se basa en el el crecimiento exponencial de la cantidad de subconjuntos respecto al tamaño del conjunto “base”.

Consideremos los posibles valores que puede tomar la suma de un subconjunto de los números: como todos los elementos son positivos, la mínima suma es 0 y corresponde al subconjunto vacío, mientras que la máxima corresponde al conjunto completo. Al tener todos los elementos 19 dígitos, si llamamos S a la suma de los elementos de un subconjunto cualquiera, tendremos:

0 ≤ S < 70·10¹⁹ < 10²¹.

Aprovechando la relación 10³ < 2¹⁰, vemos que

S < 10²¹ < 2⁷⁰.

Pero, como la cantidad de subconjuntos de un conjunto de 70 elementos es exactamente 2⁷⁰, acabamos de probar que hay más subconjuntos que posibles valores de la suma de sus elementos. Por lo tanto es inevitable que haya al menos dos subconjuntos con el mismo valor de la suma de sus elementos.

Un punto interesante es que la solución es la misma si agregamos el requerimiento de que los conjuntos sean disjuntos. Para ver esto, supongamos que tenemos dos subconjuntos distintos A y B con la misma suma:

sum(A) = sum(B).

Si analizamos los conjuntos A\B y B\A, observaremos que

sum(A\B) = sum(A) – sum(A∩B)

sum(B\A) = sum(B) – sum(A∩B)

sum(A\B) = sum(B\A).

Como obviamente A\B y B\A no pueden compartir elementos, entonces cada par de subconjuntos distintos con igual suma tiene asociado un par de subconjuntos disjuntos con igual suma.

Una solución constructiva?

Este problema es conocido como NP-completo, por lo que no cabe esperar una solución eficiente y general. Pero podría ser que con estos valores de parámetros fuera factible encontrar una solución particular por lo que realizaremos un análisis probabilístico.

Consideremos una distribución aleatoria uniforme en el intervalo (0, 10¹⁹): claramente tendrá una densidad de probabilidad constante e igual a 10^-19. Esto implica que si elegimos un número aleatoriamente de esa distribución, considerándola ahora discreta, la probabilidad sería de 10^-19, lo que concuerda con nuestra intuición.

Si analizamos ahora la distribución de probabilidad de la suma de 35 variables elegidas uniformemente de dicho intervalo, tendremos una distribución de probabilidad conocida como Irwin Hall. Pero para nuestros fines podemos aproximarla por una normal con media igual a 35 veces el promedio de los números, 2.08·10²⁰, y desviación estándar igual a la desviación estándar de los números multiplicada por la raíz cuadrada de 35, 1.57·10¹⁹. Comparando la distribución normal con un histograma obtenido mediante simulación,

Comparación de un histograma de las sumas de combinaciones de 35 números con la aproximación normal.

se observa que, aunque la coincidencia de la media es muy buena, la desviación estándar de la normal es significativamente superior a la que se observa en el histograma. Esto se debe a que, a diferencia de lo que se supone en una distribución Irwin Hall, las variables sumadas no son independientes (podemos verlo más claramente pensando en el caso de 70 variables: la suma es única, pero la distribución de Irwin Hall nos daría una desviación estándar aún mayor que en el caso de 35 variables). Como este error nos lleva a sobrestimar la dificultad de encontrar una colisión, podemos ignorar esta discrepancia por el momento, ya que nos llevará a una aproximación conservadora.

Lo que necesitaríamos ahora es calcular la probabilidad de encontrar dos combinaciones con igual suma. Aunque queda claro que las probabilidades son mayores que en el caso de que las sumas estuvieran distribuidas uniformemente en el intervalo (0, 70·10¹⁹), no es tan simple calcular un valor exacto para esta probabilidad. Pero podemos hacer una estimación suponiendo a los valores distribuidos uniformemente en el intervalo ±1σ, lo que implica descartar menos del 35% de los valores.

Aplicando la expresión derivada en el “problema del cumpleaños” para una probabilidad de colisión p:

.

Aceptando un 95% de probabilidad de éxito en la búsqueda de una colisión:

.

.

Tomando en cuenta que se está desechando el 30% de los puntos, podemos concluir que examinar unos 2·10¹⁰ puntos nos debería dar una probabilidad elevada de encontrar una colisión.

Si bien es bastante complejo buscar una colisión entre más de 10¹⁰ valores, no es infactible. Pero sería mejor realizar algunas pruebas preliminares para ver si el resultado obtenido es razonable.

Prueba a escala

A modo de verificación podemos realizar una simulación a escala, empleando la suma de 30 números de 7 dígitos para disminuir la carga computacional. En este caso sigue estando garantizada la existencia de una colisión, ya que

0 ≤ S < 30·10⁷ < 10⁹ < 2³⁰.

Aplicando la aproximación normal, la suma de 15 números distribuidos seguirá una distribución de media 7.5·10⁷ y varianza 15·10¹⁴/12. Por lo tanto la cantidad de sumas ensayadas para tener un 95% de probabilidad de encontrar una colisión (usando solo sumas dentro de 1σ) será:

.

O sea que la probabilidad de requerir más de unos 14000 ( = 8200 / 0.6) intentos para encontrar una colisión debería ser pequeña. Y estos valores son mucho más simples de comprobar experimentalmente que los originales, ya que puede hacerse mediante un pequeño script:

import math, random

N = 1000

NUMBERS = [4401501, 1984319, 1064736, 6495167,
           6402639, 7578056, 9301342, 6042069,
           1144375, 5680006, 7450344, 9099174,
           2011586, 8039920, 3010493, 1658370,
           5927190, 3880633, 1318068, 9594698,
           2877906, 1792394, 9120086, 7372216,
           2141103, 7256943, 6603598, 8565018,
           1698346, 3004879]

def run_until_collision():
    combs_dict = {}
    i = 0
    while True:
        comb = random.sample(NUMBERS, 15)
        s = sum(comb)
        if s in combs_dict:
            return i, comb, combs_dict[s]
        combs_dict[s] = comb
        i += 1

def show_stats():
    total = 0.0
    sq_total = 0.0
    print 'Please wait until the count reaches 100...'
    for i in range(N):
        tries, dum, dum = run_until_collision()
        total += tries
        sq_total += tries ** 2
        if i % math.ceil(N / 100.0) == 0:
            print '%d' % (i * 100.0 / N),
    print '\n\nTries statistics'
    print '  Average: %f' % (total / N)
    print '  SD: %f' % math.sqrt(sq_total / N -
                                 (total / N) ** 2)

if __name__ == '__main__':
    show_stats()

La salida obtenida al ejecutar este script (descartando indicaciones de progreso) es:

Tries statistics
  Average: 6123.049000
  SD: 3360.260149

Conclusiones

Para poder encontrar una colisión en forma explícita en el problema original deberá ser necesario buscarla entre aproximadamente 10¹⁰ valores. Como cada subconjunto con su suma ocupará en el orden de 16 bytes y una PC suele tener menos que 100 GB de RAM, sería práctico buscar un método que permita buscar colisiones sin tener todos los valores previamente analizados en memoria (otra opción sería usar datos en disco, pero es menos elegante 😀 ).

En un próximo post analizaremos como implementar una solución a este problema y veremos si pueden encontrarse resultados.

Porqué no se puede ganar siempre

Respuesta al post anterior

La técnica mostrada en el post anterior se denomina martingala y es muy antigua. Obviamente, a pesar de lo que puedan decir algunos, no funciona. Pero porqué la simulación anterior parecía mostrar lo contrario?

El motivo principal del fallo de la simulación es no limitar la cantidad de dinero del jugador disponible para apostar. Como la cantidad que se requiere apostar crece exponencialmente con la cantidad de jugadas, en una cantidad relativamente pequeña de estas se excederán las reservas del jugador y no podrá continuar apostando.

Otro problema de la simulación es que, incluso una cantidad grande de simulaciones, puede obviar acontecimientos muy improbables. Esto no es problemático cuando los eventos en cuestión no tienen consecuencias excepcionales pero, cuando conducen a un impacto proporcional a su improbabilidad, puede distorsionarse mucho el valor esperado (probar la nueva simulación Javascript con M = 100000 para N = 1000 y N = 1000000; observar las diferencias en los valores esperados estimados).

Pero puede objetarse (con razón!) que solo demostramos el fallo de una estrategia de apuesta, no de todas las posibles. Por lo tanto, a continuación, demostraremos que esto se aplica a cualquier estrategia.

Porqué los sistemas no funcionan

Como en toda demostración matemática, necesitaremos hacer ciertas suposiciones sobre el problema en cuestión:

1. El juego consiste en una cierta serie de jugadas, cada una asociada con una variable aleatoria . Asumimos que todas las variables tienen la misma distribución.
2. En la jugada el jugador apuesta una cantidad a un evento aleatorio (donde tomamos como un subconjunto de lso valores que podría tomar ).
3. Si el evento ocurre al que el jugador apostó ocurre, este recibe el monto apostado multiplicado por una constante dependiente del evento al que apostó. En caso contrario, pierde lo apostado.
4. .
5. Los valores de las variables aleatorias no aportan información sobre el valor de .

Las primeras 3 suposiciones son simplemente una descripción general de un juego de azar, mientras que 5 nos indica que las anteriores jugadas no nos dan información sobre la jugada actual. La suposición 4 parece más compleja, pero esencialmente nos indica que los factores han sido correctamente elegidos por el casino.

Para ver esto, supongamos que existe un evento tal que . Entonces, si elegimos una estrategia de apostar veces al evento un monto unitario, nuestro balance esperado será:

,

donde es el balance general del jugador y el balance de la jugada .

Eso implicaría que podríamos ganar simplemente repitiendo una apuesta una y otra vez (puede demostrarse sin mucha dificultad que ni siquiera necesitaríamos reservas muy grandes, solo de orden ). Como eso claramente no ocurre en los casinos, es obvio que los multiplicadores están elegidos correctamente (de hecho, por ejemplo en la ruleta, están elegidos “a favor” del casino por la existencia del cero).

Busquemos ahora el valor esperado de una estrategia de apuestas :

siendo y las funciones anteriormente descritas. Pero la suposición 5 nos dice que

,

es decir que esa información no nos modifica la probabilidad de ningún evento y, en particular, de . Combinando con la suposición 4 llegamos a

,

siempre que sea positivo, como es razonable.

Caminos de escape

Aunque una demostración fuera perfecta, sus conclusiones nunca será más fuertes que sus hipótesis. En esta sección analizaremos algunas formas en las que las hipótesis pueden ser falsas:

m_i < 0: Este es esencialmente el método utilizado por los casinos. Suele ser bastante complejo de seguir, pero muy redituable 🙂

Fallo en la hipótesis 4: Los multiplicadores son fáciles de determinar conociendo las probabilidades y generalmente se utilizan probabilidades “nominales” (por ejemplo, suponer equiprobables a los 37 o 38 números de la ruleta). Pero si algún observador encuentra evidencia que lo mueva a probabilidades distintas de las nominales, puede que existan apuestas con valor esperado positivo.

Fallo en la hipótesis 5: Pueden existir correlaciones no esperadas entre las variables aleatorias. Esto es más común en los juegos por computadora, que suelen usar números pseudoaleatorios y, en algunos casos, tienen errores de implementación que vuelven predecibles las secuencias generadas.

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… 😀

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).

Una respuesta y otro problema

[Continuacion de Excusas et cetera]

Además de las soluciones de Demian y Guille, armé 5 soluciones propias con distintas características. Pueden verse todos los tests realizados a estas soluciones en el repositorio SVN “asociado” a este blog.

La solución de Guille fallaba a causa del problema identificado por Demian y puede verse a mi solución 4 como una adaptación del algoritmo recursivo de Guille para realizar el bubble sort completo. Aunque bubble sort suele ser duramente criticado, es de hecho óptimo (en las circunstancias apropiadas, ver Improved Bounds on Sorting by Length-Weighted Reversals, Lemma 59 😀 ).

Mis soluciones

A continuación muestro las distintas soluciones que planteé, cada una demostrando algo en particular.

Solución 1 – Arrays

Esta es una solución simple, esencialmente idéntica a la primera de Demian.

void f1(int* a, size_t n)
{
    size_t i = 0, j;
    for (j = 0; j < n; j++)
        if (a[j])
            a[i++] = a[j];
    for (; i < n; i++)
        a[i] = 0;
}

Solución 2 – Punteros

Esta es una adaptación simple de la Solución 1 para utilizar punteros.

void f2(int* p, size_t n)
{
    int *q, *r;
    for (q = p, r = p + n; q < r; q++)
        if (*q)
            *p++ = *q;
    for (; p < r; p++)
        *p = 0;
}

Solución 3 – Obfuscated

Esta es una versión optimizada para ser difícil de entender, empleando solo una definición y un “statement”.

void f3(int* p, size_t n)
{
    int *q = p, *r = p + n;
    while ((r - p) *
           (r - q ? *q ? (*p++ = *q++) : ++q - p : (*p++ = 0) + 1));
}

Solución 4 – Recursiva

Esta es la solución de Guille, adaptada para realizar una pasada completa de “burbujeo” en cada llamada recursiva. De las soluciones que encontré, es la única que no requiere variables adicionales (aunque obviamente utiliza múltiples instancias del stack frame).

void f4(int* p, size_t n)
{
    if (n == 0)
        return;
    f4(p + 1, n - 1);
    while (n >= 2)
    {
        if (!p[0] && p[1])
        {
            /* xor swap */
            /* Proof:
               p0' = p0 ^ p1
               p1f = p1 ^ p0'
                   = p1 ^ p0 ^ p1
                   = p0
               p0f = p0' ^ p1f
                   = p0 ^ p1 ^ p0
                   = p1
            */
            p[0] ^= p[1];
            p[1] ^= p[0];
            p[0] ^= p[1];
        }
        p++;
        n--;
    }
}

Solución 5 – Utilizando solo una variable extra

Esta solución es una “mezcla” de las soluciones 1 y 2 modificada para utilizar solo una variable temporal. Dudo que sea posible resolver el problema sin variables temporales extras (aparte de los parámetros), pero no parece simple probarlo…

void f8(int* a, size_t n)
{
    size_t j;
    for (j = 0; j < n; j++)
    {
        if (a[j])
            a[0] = a[j], a++, j--, n--;
    }
    for (j = 0; j < n; j++)
        a[j] = 0;
}

Un problema matemático

Hace unos días vi en el blog de Michael Nielsen un interesante problema:

Dado un conjunto de 51 números dentro del intervalo 1-100 (incluyendo los extremos), demostrar que existen al menos dos números en ese conjunto que no comparten ningún divisor (a excepción de 1, obviamente).

(No, no vi inmediatamente la respuesta 😀 )

Excusas et cetera

Originalmente tenía pensado publicar la primera parte de la respuesta al post sobre detección de cubos este fin de semana pasado, pero los videos de Susskind y Coleman sobre QFT se interpusieron 😀

Siempre creí que las clases expositivas eran bastante redundantes pero, cuando el material es dificultoso como en este caso, el inevitable “unpacking” que ocurre al explicar los temas “en vivo” se vuelve una ventaja importante. Los videos de Susskind son bastante fáciles de seguir para los que fueron siguiendo la serie en general, pero a veces pueden resultar un poco “handwavy”. Los de Coleman son bastante más rigurosos pero tienen mala calidad de filmación (incluso para 1975) y presuponen más conocimientos matemáticos y de mecánica cuántica de los que tengo, lo que me dificulta seguirlos.

Para no dejar todo en la nada, ofrezco un problema de programación C inspirado en uno visto (si no recuerdo mal) en algún comentario en el blog de Eric Raymond:

Enunciado:

Dado un vector de enteros, implementar una función que mueva “en el lugar” los ceros al final del vector dejando los otros enteros en el orden original. El prototipo de la función deberá ser:

void foo(int* a, size_t n).

Ejemplos de efectos sobre el vector pasado por parámetro:

{5, 0, 4, 0, 0, 3, 0, 0, 0, 2} --> {5, 4, 3, 2, 0, 0, 0, 0, 0, 0}
{0, 0, 0, 1, 2, 3, 0, 4} --> {1, 2, 3, 4, 0, 0, 0, 0}

Algunas respuestas a esto, salvando fuerza mayor, este fin de semana. Ustedes pueden dejar otras respuestas en los comentarios que serán debidamente analizadas… 😀

Detectando los cubos

Para romper el largo lapso sin posts, presento el siguiente problema (robado de inspirado en uno visto en el blog de Petr Mitrichev):

Desarrollar un algoritmo que, dados 8 puntos en el plano , determine si existen valores tales que los puntos forme un cubo en el espacio. O, en otras palabras, que determine si los 8 puntos en el plano pueden formar la proyección paralela de un cubo.

Figura 1. 8 puntos en el plano que pueden verse como la proyección paralela de un cubo.

Figura 2. 8 puntos en el plano que no pueden verse como la proyección paralela de un cubo.

El algoritmo debe poder determinar que 8 puntos tales como (-0.343731, 0.404338), (-0.383761, 0.233634), (0.582329, -0.512121), (0.474738, 0.331386), (-0.236140, -0.439169), (0.622359, -0.341416), (-0.276170, -0.609873) y (0.514768, 0.502091) pueden verse como la proyección de un cubo (ver figura 1); por otro lado, tiene que clasificar al conjunto de puntos (0.085135, -0.025253), (-0.196956, 0.110847), (0.098387, -0.104055), (-0.091524, 0.268373), (0.051493, -0.111503), (-0.183703, 0.032046), (0.190567, 0.132272) y (-0.289135, -0.125480) como incapaz de ser la proyección de un cubo (ver figura 2).

En no menos de una semana, propondré una respuesta (no robada 😀 ) al problema.