IDs únicas

Publicado por LaNsHoR el 26/05/2014 en Problemas | 5 comentarios

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?