[caracas-pm-list] Re: [l-linux] [OFF-TOPIC] SQL Puzzle

[Ernesto Hernandez-Novich]

On Mon, 8 Mar 2004, Victor Medina wrote:
> Hola a todos! espero que se distraigan un rato! =)
>
> SQL puzzle from the Informix mailing list:

¿SQL? Es un acertijo de teoría de números y lógica...

> Two mathematicians (Boris and Vladimir) met accidently for the first
> time in 20 years.
[...]
> "Yes" replies Vladimir, "I have three." >

Son tres, sean A, B, C sus edades (que son enteras).

> "The product of their ages is 36 and the sum of their ages is equal to
> the number of windows on that building across the street."

A * B * C = 36

De modo que deben ser tomadas desde el conjunto de divisores de 36. Los
divisores de 36 son 36, 18, 12, 9, 6, 4, 3, 2, 1 y las posibles
tripletas cuyo producto sea 36 son (generadas por un programa,
obviamente):

T1 =  4 3 3
T2 =  6 3 2
T3 =  6 6 1
T4 =  9 2 2
T5 =  9 4 1
T6 = 12 3 1
T7 = 18 2 1
T8 = 36 1 1

A + B + C = N

¿De dónde saco N? El valor de N es _irrelevante_, lo que importa es que
es conocido al momento de hacer la pregunta, y que es _fijo_.

> Boris looks at the building, counts the windows then says "Vladi, that
> still doesn't tell me the ages."

Esta frase es crucial. Obviamente hay _varias_ combinaciones A*B*C = 36
y cada una de ellas tiene una suma particular.

T1 =  4 3 3 => 10
T2 =  6 3 2 => 11
T3 =  6 6 1 => 13
T4 =  9 2 2 => 13
T5 =  9 4 1 => 36
T6 = 12 3 1 => 16
T7 = 18 2 1 => 21
T8 = 36 1 1 => 38

Boris las calculó mentalmente y miró el edificio, por lo tanto _conoce_ N.
Si aún no puede decir cuál es la edad de los niños es porque aún conociendo
N hay más de una combinación de números que suman N. Mirando las tripletas
que seleccionamos es obvio que la duda está entre T3 y T4.

> "Ah, says Vladi, then I must tell you that the eldest has red hair."

Esto indica que para desambigüar las posibles tripletas que tienen la
misma suma, debe buscarse aquella en la cual hay un "hijo mayor". El
hecho de que sea pelirrojo es simplemente para confundir a la audiencia
:-)

> "Oh", says Boris, "now I know their ages."
> What are the ages of Boris' children?

Obviamente, 9 2 2 que es la única con un "hijo mayor".

No hace falta SQL para ésto, de hecho mentalmente se resuelve en diez
segundos (no sé si algún cerebro corre SQL, en particular el mío no :-).

> Create a table, load it with data, and write a single SQL statement to
> produce the data set required to deduce the answer.

Nótese que hay que hacerlo con _una_ sola tabla. Esto es para determinar
si el que resuelve con SQL sabe de auto-proyecciones y de orden
topológico de la auto-relación.

create table divisors (
  value integer
)

insert into divisors values ( 36 );
insert into divisors values ( 18 );
insert into divisors values ( 12 );
insert into divisors values (  9 );
insert into divisors values (  6 );
insert into divisors values (  4 );
insert into divisors values (  3 );
insert into divisors values (  2 );
insert into divisors values (  1 );

¿Cómo encontrar las tripletas? Obviamente con un auto-join de la tabla
consigo misma. Para evitar los duplicados (porque (16,1,1) es lo mismo
que (1,1,16)...) se establecerá el orden "de edades" (primera mayor o
igual que segunda, mayor o igual que tercera; ésto establece un orden
topológico de precedencia que genera tripletas únicas). Entonces
simplemente necesito las tripletas cuyo producto es 36 y quiero calcular
su suma

select a.value + b.value + c.value as suma
  from divisors a, divisors b, divisors c
 where a.value * b.value * c.value = 36
   and a.value >= b.value
   and b.value >= c.value

¿Cómo encontrar aquellas sumas que aparecen más de una vez? Agrupando el
resultado de la anterior según el valor de cada suma, pero conservando
solamente aquellas cuya suma sea mayor que uno. Y aquí voy a necesitar
hacer una consulta con una sub-consulta

select    suma from ( <todo lo anterior> ) as suma
 group by suma
 having   count(suma) > 1

De modo que a partir de la consulta ya puedo saber cual es la suma que
está duplicada. Solamente me resta seleccionar la tripleta que coincide
con ésta suma y que al mismo tiempo su primera componente sea mayor que
las otras dos

select a.value as Edad1, b.value as Edad2, c.value as Edad3
  from divisors a, divisors b, divisors c
 where a.value * b.value * c.value = 36
   and a.value > b.value
   and a.value > c.value
   and a.value + b.value + c.value in
  (select suma from (select a.value + b.value + c.value as suma
                       from divisors a, divisors b, divisors c
		      where a.value * b.value * c.value = 36
		        and a.value >= b.value
			and b.value >= c.value) as suma
   group by suma
   having count(suma) > 1);

> Of course the problem cannot be solved with M$ SQLServer :-)

Ni en MySQL porque no soporta subqueries...

También presento una solución en Haskell (omitiendo las firmas de las
funciones)

divisors = [ x | x <- [1..36], 36 `mod` x == 0]
tys      = [ (a+b+c,(a,b,c)) | a <- divisors,
                               b <- divisors,
			       c <- divisors,
                               a * b * c == 36, a >= b, b >= c ]
count    = [ ((s,length (filter (s==) (map fst tys))),t) | (s,t) <- tys ]
edades   = head [ (a,b,c) | (_,(a,b,c)) <- filter ((>1) . snd . fst) count,
                            a > b, a > c ]

simplemente ejecuten 'edades' en Hugs (o completen el programa con la
función 'main' apropiada y lo compila con ghc). Si les parece similar en
estructura, no es casualidad: SQL es una forma muy particular de programación
funcional; aquél programador que domina las técnicas funcionales suele ser
mucho más hábil para escribir SQL eficiente en menos tiempo, que aquel que
solamente sabe programación imperativa/oo.

De paso, dificulto que puedan escribir el programa en cualquier otro
lenguaje y que resulte más compacto que en Haskell.

Sin embargo, les presento una solución funcional/imperativa escrita en
el mejor lenguaje de propósito general que conozco. Nótese que debo
mezclar componentes imperativos porque Perl no tiene listas por
comprensión [1] así que tengo que hacer los for

#!/usr/bin/perl
my @div = (1,2,3,4,6,9,12,18,36);
my $t   = undef;
for my $a (@div) {
  for my $b (@div) {
    for my $c (@div) {
      push @{$t},[ $a+$b+$c, $a, $b, $c]
        if (($a*$b*$c == 36) && ($a >= $b) && ($b >= $c))
    }
  }
my $c = undef;
for my $p (@{$t}) {
  my $s = $p->[0];
  push @{$c},[ (scalar (grep { $_->[0] == $s } @{$t})),
	       $p->[1], $p->[2], $p->[3] ];
my $r = [ grep { $_->[0] > 1 &&
                 $_->[1] > $_->[2] &&
		 $_->[1] > $_->[3] } @{$c} ];
for (1..3) {
  print $r->[0]->[$_]," ";
}
print "\n";

[1] Una lista por comprensión es lo mismo que la especificación de un
    conjunto según un generador y predicados, i.e. "pares menores que
    20" se escribe en Haskell como si uno escribiera la especificación
    matemática

    pares = [ x | x <- [1..20], x `mod` 2 == 0 ]

    y aunque "parece" que es una expresión imperativa, no lo es. De
    hecho está basado en el concepto de cómputo monádico derivado de la
    teoría de categorías... versión corta, eso _es_ una función y no hay
    ninguna iteración (más allá de la "implícita" que ven los ojos
    viciados por tanto escribir for... eso se cura :-).
-- 
Ernesto Hernández-Novich - On Linux 2.6.3 i686 - Unix: Live free or die!
Geek by nature, Linux by choice, Debian of course.
If you can't apt-get it, it isn't useful or doesn't exist.
GPG Key Fingerprint = 438C 49A2 A8C7 E7D7 1500 C507 96D6 A3D6 2F4C 85E3
------------------------------------------------------------------------
Enviar e-mail a <majordomo at pm.org> colocando en el cuerpo:
"UNSUBSCRIBE caracas-pm-list" para desuscribirse.
"INFO caracas-pm-list" para conocer las reglas de etiqueta.
------------------------------------------------------------------------