Entradas en "problemas"

PHP: Ejemplo de mal lenguaje

Supongamos que tenemos 5 variables a, b, c, d y e. Y que todas y cada una de las siguientes evaluaciones devuelven TRUE.

$a === $b
$b === $c
$c === $d
$d === $e

Además si hacemos lo siguiente:

var_dump($a);
var_dump($b);
var_dump($c);
var_dump($d);
var_dump($e);

Obtenemos exactamente la misma definición, repetida 5 veces, por salida estándar.

Llegados a este punto, hemos analizado -todo lo que el lenguaje nos permite- nuestras 5 variables. Todas parecen ser idénticas, no hay ninguna propiedad en ellas que podamos medir y que nos permitan diferenciar unas de otras.

Sin embargo, al hacer lo siguiente:

$b = new stdClass;

Al volver a repetir las evaluaciones iniciales el resultado es el siguiente:

$a === $b //FALSE
$b === $c //TRUE
$c === $d //TRUE
$d === $e //TRUE

En conclusión: 5 entidades que según el lenguaje son idénticas y por lo tanto, deben comportarse de la misma forma, tienen un comportamiento diferente; debido a propiedades internas imposibles de discernir en la capa de código.

Este es un claro ejemplo de pésimo diseño a nivel de lenguaje y, por supuesto, una fuente potencial de fuertes dolores de cabeza para cualquier programador.

Como pequeño ejercicio: ¿alguien sabe cómo hay que inicializar las 5 variables para que se comporten de la forma descrita?

Leer más

IDs únicas

Volvemos con los problemas de la semana. Este es uno de mis favoritos, muy útil para usar en una entrevista de trabajo si queréis poner a prueba al candidato 😉 (debería hacer una colección con este tipo de problemas, porque son simples, pero demuestran mucho de quien los resuelve; me gustan mucho!).

Pregunta: En cualquier lenguaje de programación, escribe una función UID que devuelva un ID (número) único cada vez que se ejecute.

Consideraciones: La función no puede hacer uso de datos o variables globales de ninguna forma ni aceptar parámetros. Toda su funcionalidad debe quedar encapsulada. Tampoco puede ser el método de un objeto.

Ejemplo de ejecución:

x=UID(); //x vale 1
x=UID(); //x vale 2
x=UID(); //x vale 3
/* Nota: Los números pueden o no ser secuenciales,
 el único requisito es que nunca se repitan. */

Expansión (para los que quieran sumar puntos extra): Escribe en cualquier lenguaje de programación, una función GUID que devuelva una función (o puntero a función en lenguajes como C++) según las especificaciones del problema anterior pero que funcionen de forma independiente.

Ejemplo de ejecución:

UID1=GUID();
UID2=GUID();
UID3=GUID();
x=UID1(); //x vale 1
x=UID1(); //x vale 2
x=UID2(); //x vale 1
x=UID1(); //x vale 3
x=UID2(); //x vale 2
x=UID1(); //x vale 4
x=UID3(); //x vale 1

*** SOLUCIÓN ***

El enunciado era sencillo pero la solución puede complicarse si no tomamos una primera decisión correcta. Erful consiguió resolverlo en Javascript (aunque no tenía Internet y no pudo responder con su código) y StormByte iba muy bien encaminado con la solución.

La primera decisión correcta e importante es la elección lenguaje de programación; en algunos lenguajes la solución es trivial… por eso es importante, cuando leemos “en cualquier lenguaje de programación”, no interpretarlo como “nuestro favorito” o “el que más dominamos”; si no “el más adecuado” para el problema.

Necesitamos un lenguaje que soporte clausuras o cálculo lambda.

Con esto, vamos con las soluciones:

Solución Simple en Javascript:

var UID = (function() {
   var id=0; return function() {
      return ++id;
   }
})();
//===========================
var x;
x=UID(); //x vale 1
x=UID(); //x vale 2
x=UID(); //x vale 3

Lo que tenemos es la creación de una función anónima que se ejecuta conforme es definida. Esta función forma la clausura que contiene a una variable id inicializada a 0. Además la función devuelve otra función que retorna e incrementa el valor de id, esta función es la que se asigna a UID, y que cada vez que se ejecuta, tiene acceso a la variable id de ámbito superior que pertenece a la clausura de la función anónima.

Con esta idea, hacer un generador de funciones UID es trivial:

Solución Expandida en Javascript:

function GUID() {
   var id=0;
   return function() {
      return ++id;
   }
};
//===========================
var UID1=GUID();
var UID2=GUID();
x=UID1(); //x vale 1
x=UID1(); //x vale 2
x=UID2(); //x vale 1
x=UID1(); //x vale 3
x=UID2(); //x vale 2

La diferencia es que la función anónima de clausura original, ya no es anónima, si no que se llama GUID y se ejecuta creando una nueva clausura cada vez, devolviendo la función que incrementa y devuelve el valor de id.

En otros lenguajes de programación el planteamiento es el mismo:

Solución Expandida PHP

function GUID() {
   $id=0;
   return function() use (&$id) {
      return ++$id;
   };
}
//===========================
$UID1=GUID();
$UID2=GUID();
echo $UID1(); //1
echo $UID1(); //2
echo $UID2(); //1
echo $UID1(); //3
echo $UID2(); //2

Fijaos en la sintaxis, para ejecutar UID1 y UID2 no se utiliza la sintaxis de llamada a función normal; si no que es necesario indicar que son variables: así a() != $a(). Requiere PHP >= 5.3 para funcionar.

Solución Expandida C++

#include <iostream>
#include <functional>

//===========================
std::function<int()> GUID()
{
    return []()->std::function<int()>
    {
        int id=0;
        return [=]() mutable -> int { return ++id; };
    }();
}
//===========================

int main(int argc, char * argv[])
{
    auto UID1= GUID();
    auto UID2= GUID();

    std::cout << UID1() << std::endl; //1
    std::cout << UID1() << std::endl; //2
    std::cout << UID2() << std::endl; //1
    std::cout << UID1() << std::endl; //3
    std::cout << UID2() << std::endl; //2
    return 0;
}

Para simplificar y evitar el uso de punteros a funciones usamos el tipo function de c++11 (la última versión del estándar C++, requiere G++>=4.7). Usamos el cálculo lambda para crear la clausura necesaria y devolver la función. Si queréis aprender sobre la sintaxis del cálculo lambda en C++ está bien explicada en la documentación de referencia de MSDN.

¿Os animáis a hacer la prueba en otros lenguajes? 😉 ¿Quién nos enseña una solución en LISP o SCHEME?

Leer más

Maestros de la indirección

Este problema lo diseñé hace unos años, cuando le daba clases a mi amiga Marta para preparar su examen final de programación en la universidad. En cuestiones de punteros en C++ soy de los que piensan que no hay medias tintas; o eres capaz de resolver este ejercicio en unos minutos (cuatro o cinco de media, aunque el tiempo no es importante), o no te has enterado de nada.

Esta vez no hay premio porque para obtener la solución sólo hay que compilarlo y ejecutarlo. Papel, lápiz y 300 segundos: ¿Cuál es la salida del programa?

PS: Marta por supuesto sacó un 10!
PS2: No hay punteros a funciones porque esta vez no entraban en el temario.

#include <iostream>

int main()
{
   void *x[2];
   char *y=(char*)new void*[3];
   void *z=y;
   *x=&z;
   *(void**)y=(((char*)x)+sizeof(void*));
   y+=2*sizeof(void*);
   x[1]=(void*)y;
   *((void**)x[1])=(void**)z+1;
   *((char**)z+1)=new char[1<<4];
   ((void**)z)[0x2]=((void**)z)+1;
   y=((char**)z)[1];
   y[0]=y[1]=*(y+2)=*&y[3]=0140;
   y[3]+=&x[1]-x;
   y[2]+=(((void**)x[1])-(void**)z)*0x6;
   *(&(*(&(*(&(*y))))))+=8;
   *(&(*(&(*(&(*(y+1)))))))+=017;
   y[4]=(1<<5)%(1<<6);
   y[5]='6'*2+1;
   *(y+0x6)=*((**(char***)*(x+1))+3);
   y[(1<<3)-1]=*y==228?*y/(char)2:(char)57*2;
   y[(1<<3)-0]=y[(1<<3)-1]+2;
   y[(1<<3)+1]=*(y+6);
   y[012]=0x21;
   y[013]=y[012]-23;
   y[014]=y[013]-10;
   std::cout<<******(char*******)x;
}
Leer más

Un hogar de cera y miel

Este problema lo propuse el 20 de abril en Twitter. Mientras estaba en la playa. Es un problema muy sencillo, aunque sólo una persona de mi TL logró resolverlo… ( @erful )

hexágonos playa

Problema: En una teselación hexagonal regular, ¿cuál es la distancia entre dos circuncentros adyacentes en función del radio de una circunferencia cincunscrita a uno de los hexágonos?

* Sólo se necesitan matemáticas de la ESO… aunque sorprendente pocos acaban llegando a la solución correcta.

Problema (extra):  Utiliza la solución para escribir una función en cualquier lenguaje de programación para dibujar sobre un buffer, plano, canvas, textura… una teselación como la del problema (dimensiones arbitrarias NxM).

* La solución la publicaré el domingo.

Leer más

Rompiendo la pared

Tercer problema, esta vez un poco de C++, y además muy fácil. Este es un problema clásico de mi carpeta de problemas a plantear en entrevistas de trabajo (yo personalmente nunca contrataría a alguien que no supiera resolverlo).

Este problema vino inspirado cuando, una vez, escuché a una persona A decirle a una persona B que no había forma de acceder a un miembro privado de una clase sin un getter, sin ser friend, etc…

Vamos a demostrarle todos a A que sí se puede:

class Locked
{
   public:
      int number;
   private:
      int secret;
   public:
      Locked() {number=-7;secret=85;}
};

int main()
{
   Locked black_box;
   int x = /* solución aquí */ ;
}

Tenemos un clase “Locked” con un entero público (number) y otro privado (secret). Tenemos que guardar en la variable “x” el valor del entero “secret” de la instancia “black_box” de la clase “Locked”. La solución cabe en una línea y por supuesto no puede escribirse nada fuera del main.

¿Voy abriendo ya la cerveza? 😀

Leer más