Espacio desperdiciado en un contenedor lleno de pelotas

Muchos de los concursos que hay hoy día es el acertar cuántas pelotas caben en un coche último modelo de cierta marca en particular. Alguien me ha preguntado por Internet al respecto, considerando que he participado en este tipo de concursos y que me he acercado bastante al resultado correcto, aunque no lo suficiente como para ganar.

La pregunta ocurre cuando se trata precisamente de pelotas en un contenedor que contiene un volumen específico. Este sería el caso general y la cuestión específica es cuánto espacio se desperdicia. Hay varias formas de hacer este cálculo. Supongamos que tenemos una espera dentro de un cubo. Digamos que el radio de la esfera es de 4 cms. Así, si tomamos el cubo, el volumen se expresará como lado x lado x lado, es decir, lado^3. Si consideramos la imagen (ver enseguida, más abajo)

con un radio de 4 cms, tenemos que cada lado es de 8 cms. Entonces, 8^3 = 512 cms cúbicos. Esta cantidad es el volumen de un cubo en donde dentro del mismo hay una esfera que toda todas las paredes del mismo.

Ahora bien, ¿cuál es el volumen de la esfera nada más? La fórmula es:

Vol esfera = (4/3) (pi) (radio^3) 

Por lo que, tomando radio = 4 cms, tenemos que el volumen de la esfera es 268.08 cms cúbicos. Esto quiere decir que la esfera ocupa 52.34% del total del cubo. El espacio desperdiciado es 243.92 cms cúbicos, es decir 47.64%

Si colocamos en una caja cada pelota como en la figura siguiente:

tendremos que se desperdicia 47.64% exactamente.

Sin embargo, en los concursos de acertar cuántas pelotas caben en un auto, no se acomodan las mismas, simplemente se echan dentro de la cabina del auto hasta llenar todo el espacio habitable. (ver siguiente figura).

Esto implica que se desperdicia menos espacio. ¿Cuánto menos? Como es algo que tiene que ver con el azar, habrá algunas pelotas que quedan entre las intersecciones de otras mientras que habrá pelotas que estén de frente a otras como si fuesen espejo. Sin ir demasiado lejos en estas especulaciones, mi aproximación (a ojo de buen cubero), es que se desperdicia algo así como el 50%. No he hecho los cálculos necesarios por dos razones, porque no sé muy bien por dónde empezar y además, porque creo que hay un factor al azar que no me permite la precisión que quisiese. Sin embargo, el número que doy suena razonablemente bueno, quizás con una incertidumbre del 0.5% para arriba y para abajo.

Reto de la programación lúdica: protector de pantalla

Todos sabemos que los protectores de pantalla surgieron de la necesidad de evitar que las pantallas de rayos catódicos, como en las televisiones de hace unos años, “quemaran”  el fósforo de las pantallas y las dejara “marcadas”. Por ejemplo, me tocó ver monitores con las marcas típicas de los programas como las hojas de cálculo, en donde se observaba claramente una imagen fantasmal de cómo se veía el programa en cuestión cuando se utilizaba.

Por ello los protectores de pantalla existen, buscando resolver esta dificultad. Esto llevó, como evolución básica quizás, a la creación de protectores de pantalla que ponían imágenes en movimiento, animaciones, gráficas muilticolores que iban cambiando, etcétera, cuando finalmente el mejor protector de pantalla es el que se apague la pantalla hasta que el usuario toque alguna tecla, mueva el ratón o bien, toque el monitor en estas posmodernas interfaces táctiles.

Así entonces, en este reto de la programación lúdica buscamos un protector de pantalla orioginal, moderno, que aparte de cumplir con la tarea de evitar el desgaste innecesario del monitor, nos presente algo artístico, divertido tal vez. Ustedes -programadores- son quien deciden.

El reto implica hacer no solamente un programa que haga algo en la pantalla, sino que se pueda poner en el listado de los protectores de pantalla de Windows. No se trata de que me pasen un enlace a uno de los miles y miles de protectores de pantalla que ya han sido escritos, sino que la idea es que se programe,en el lenguaje que quieran, su propio protector.

En este caso no hay dificultades ni problemas para usar bibliotecas en su propia herramienta de programación. La condición sine qua non (es decir, obligatoria), es que el programa pueda ponerse en la carpeta donde residen los protectores de pantalla de Windows y pueda usarse como tal. Igualmente, el protector de pantallas debe ser para el sistema operativo Windows 7 en adelante.

Los protectores de pantalla son programas que en términos generales funcionan como cualquier ejecutable, aunque tienen un par de especificaciones que hay que tomar en cuenta.Una de ellas es que los archivos no son .exe sino .scr, pero me parece hay un par de cosas que hay que contemplar para hacer un protector de pantalla.  Sugiero le echen un vistazo a este enlace para resolver los detalles técnicos que tiene este tipo de programas.

Este tipo de programas, probablemente puedan encontrarlo en la red. No se trata pues de copiarlo de algún sitio. Si descubro una copia o si tengo dudas, me tomo la libertad de preguntarle al autor directamente cómo hizo, para garantizar así que la solución fue escrita y no copiada por el autor del programa. Juguemos pues limpiamente y aprendamos todos de estos retos.

¿El premio? Una taza con el logotipo de la Morsa a la mejor solución, en donde ganará el que visualmente sea más atractivo. Como esto es una cuestión subjetiva, un jurado calificado por los articulistas de unocero (más otros personajes externos [sus nombres se mencionarán al terminar el concurso]), serán quienes tomen la decisión y ésta es inapelable. Hay también una gorra y una libreta de notas, cortesía de Qualcomm (sólo para quienes residan en el DF). Habrá probablemente más premios, pero estos son los que están asegurados.

El premio de la taza (con el añadido de la gorra y el cuaderno de notas), solamente aplica a los programadores que vivan en el DF (mandar a provincia o a otros países una taza es estúpidamente costoso). En caso de que los concursantes sean de otros países o de la provincia mexicana, el premio será una memoria USB de 8 GBytes al menos y se les enviará por correo certificado.

Así que ¡manos a la obra! Sorpréndanme…

Ya tenemos ganador del reto de la programación lúdica sobre los laberintos

Hace ya un par de semanas pusimos en el reto de la programación lúdica, la creación de un laberinto. Hubo una discreta participación, la cual quiero creer, se debió en parte a que el reto sonaba demasiado complejo y aunque no lo era tanto, requería quizás de más horas de las que muchos podrían haberse ocupado para resolverlo. Se recibieron algunas participaciones que invalidé porque parecían copia de algún programa de Internet y ante mi petición de aclarar el asunto hubo incluso silencio. Y que conste, no estoy acusando a nadie, solamente que la idea de los retos es que los que participan los resuelvan porque ése es el chiste, amén de que en eso reside la diversión. Finalmente, hubo tres finalistas. Uno usó Java (Salvador González), otro Javascript (Gabriel Martínez), con ayuda de JQuery y un tercero, escrito en Delphi. La decisión no fue fácil pero me parece que el ganador hizo la versión más manejable y visualmente más adecuada a la interfaz gráfica. El ganador es pues Guillermo Cañedo y este es su código (en Delphi):

unit Unit1;

interface

uses
  Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
  Dialogs, ExtCtrls, StdCtrls, Spin;

type
  TMurosSet = set of (arriba, abajo, derecha, izquierda);

  PCelda = ^TCelda;
  TCelda = record
      i, j, pos: Integer;
      visitado: Boolean;
      etiqueta: String;
      muros: TMurosSet;
      adyacentes: TList;
  end;

  PRef = ^TRef;
  TRef = record
      pos: Integer;
      muroComun: TMurosSet;
  end;

  TForm1 = class(TForm)
    Panel1: TPanel;
    Panel2: TPanel;
    Button1: TButton;
    Lienzo: TPaintBox;
    rens: TSpinEdit;
    cols: TSpinEdit;
    Label1: TLabel;
    Label2: TLabel;
    Button2: TButton;
    Label4: TLabel;
    procedure LienzoPaint(Sender: TObject);
    procedure rensChange(Sender: TObject);
    procedure FormCreate(Sender: TObject);
    procedure Button1Click(Sender: TObject);
    procedure FormDestroy(Sender: TObject);
    procedure Button2Click(Sender: TObject);
    procedure FormResize(Sender: TObject);
  private
    { Private declarations }
  public
    { Public declarations }
    dx, dy: Integer;
    Q: TList;
    solucion: TStringList;
    verSol: Boolean;
    procedure calcTamCeldas;
    function ObtieneListaDeNodos: TList;
    function obtieneNodo(i, j: Integer): PCelda;
    function obtieneNodosAdyacentes(i, j: Integer): TList;
    function refCelda(i, j: Integer): Integer;
    procedure DFS(nodo: PCelda);
    procedure DerribarMuro(A, B: PCelda);
    function obtieneNodosPorDondePuedePasar(nodo: PCelda): TStringList;
    function HayHabitacionesF: Boolean;
    function getMuroRandom(nodo: Pcelda): PCelda;
    function obtieneHabitacionF: PCelda;
    procedure etiquetar(nodo: pCelda; etq: String);
    function obtieneMuroQueIntercepta(A, B: PCelda): TMurosSet;
    function Regresa: PCelda;
  end;

var
  Form1: TForm1;

implementation

{$R *.dfm}


procedure TForm1.LienzoPaint(Sender: TObject);
var
   i, j, rx, ry: integer;
   R: TRect;
   celda: PCelda;
begin
    R.Left := 0;
    R.Top := 0;
    R.Right := Lienzo.Width;
    R.Bottom := Lienzo.Height;
    Lienzo.Canvas.Brush.Color := clWhite;
    Lienzo.Canvas.Brush.Style := bsSolid;
    Lienzo.Canvas.FillRect(R);

    Lienzo.Canvas.Pen.Color := clBlack;
    Lienzo.Canvas.Pen.Width := 1; 
    if Q <> Nil then
      begin
          for i := 0 to (Q.Count - 1) do
               begin
                   celda := Q[i];

                   rx := celda^.j*dx;
                   ry := celda^.i*dy;
                   
                   if arriba in celda^.muros then
                       begin
                           Lienzo.Canvas.MoveTo(rx, ry);
                           Lienzo.Canvas.LineTo(rx + dx, ry);
                       end;
                       
                   if abajo in celda^.muros then
                       begin
                           Lienzo.Canvas.MoveTo(rx, ry + dy);
                           Lienzo.Canvas.LineTo(rx + dx, ry + dy);
                       end;

                   if derecha in celda^.muros then
                       begin
                           Lienzo.Canvas.MoveTo(rx + dx, ry);
                           Lienzo.Canvas.LineTo(rx + dx, ry + dy);
                       end;

                   if izquierda in celda^.muros then
                       begin
                           Lienzo.Canvas.MoveTo(rx, ry);
                           Lienzo.Canvas.LineTo(rx, ry + dy);
                       end;

               end;

           if (verSol) and (solucion.Count > 0) then
               begin
                   Lienzo.Canvas.Pen.Color := clRed;
                   Lienzo.Canvas.Brush.Style := bsClear;
                   Lienzo.Canvas.Pen.Width := round(dy/3); 
                   celda := Q[StrToInt(solucion[0])];
                   rx := celda^.j*dx;
                   ry := celda^.i*dy;
                   Lienzo.Canvas.MoveTo(round(rx), round(ry + dy/2));

                   for i := 0 to (solucion.Count - 1) do
                       begin
                           celda := Q[StrToInt(solucion[i])];
                           rx := celda^.j*dx;
                           ry := celda^.i*dy;
                           Lienzo.Canvas.LineTo(round(rx + dx/2), round(ry + dy/2));
                       end;
                       
                   Lienzo.Canvas.LineTo(round(rx + dx), round(ry + dy/2));

               end;
      end
    else
      begin

           for j := 0 to cols.Value do
               begin
                   Lienzo.Canvas.MoveTo(dx*j, 0);
                   Lienzo.Canvas.LineTo(dx*j, Lienzo.Height);
               end;

           for j := 0 to rens.Value do
               begin
                   Lienzo.Canvas.MoveTo(0, dy*j);
                   Lienzo.Canvas.LineTo(Lienzo.Width, dy*j);
               end;
            
      end;
end;

function TForm1.ObtieneListaDeNodos: TList;
var
   i, j: integer;
   P: PCelda;
begin
   Result := TList.Create;
   for i := 0 to rens.Value - 1 do
       for j := 0 to cols.Value - 1 do
           begin
              New(P);
              P^.i := i;
              P^.j := j;
              P^.visitado := false;
              P^.etiqueta := 'u';
              P^.muros := [arriba, abajo, derecha, izquierda];
              P^.pos := refCelda(i, j);
              P^.adyacentes := obtieneNodosAdyacentes(i, j);
              Result.Add(P);
           end;
end;


function TForm1.obtieneNodo(i, j: Integer): PCelda;
var
   k: integer;
   P: PCelda;
begin
   Result := nil;
   for k := 0 to (Q.Count - 1) do
       begin
           P := Q.Items[k];
           if (P^.i = i) and (P^.j = j) then
               begin
                   Result := P;
                   Exit;
               end;
       end;
end;


function TForm1.refCelda(i, j: Integer): Integer;
begin
  Result := i*cols.Value + j;
end;


function TForm1.obtieneNodosAdyacentes(i, j: Integer): TList;

    procedure Add(k: Integer; muro: TMurosSet);
    var
        P: PRef;
    begin
        New(P);
        P^.pos := k;
        P^.muroComun := muro;
        Result.Add(P);
    end;

begin

    Result := TList.Create;
    if i - 1 >= 0 then Add(refCelda(i - 1, j), [arriba]);
    if i + 1 <= rens.Value - 1 then Add(refCelda(i + 1, j), [abajo]);     if j - 1 >= 0 then Add(refCelda(i, j - 1), [izquierda]);
    if j + 1 <= cols.Value - 1 then Add(refCelda(i, j + 1), [derecha]);
end;

procedure LimpiaLista2(MyList: TList);
var
   i: Integer;
   ARecord: PRef;
begin
   if MyList <> Nil then
      begin
           for i := 0 to (MyList.Count - 1) do
               begin
                   ARecord := MyList.Items[i];
                   Dispose(ARecord);
               end;
           MyList.Free;
       end;
end;


procedure LimpiaLista(MyList: TList);
var
   i: Integer;
   ARecord: PCelda;
begin
   if MyList <> Nil then
      begin
           for i := 0 to (MyList.Count - 1) do
               begin
                   ARecord := MyList.Items[i];
                   LimpiaLista2(ARecord^.adyacentes);
                   Dispose(ARecord);
               end;
           MyList.Free;
       end;
end;

procedure TForm1.rensChange(Sender: TObject);
begin
   Button2.Enabled := false;
   verSol := false;
   LimpiaLista(Q);
   Q := nil;
   solucion.Clear;
   calcTamCeldas;
   FormResize(Sender);
   Lienzo.Refresh;
end;

procedure TForm1.calcTamCeldas;
begin
   // dx := Round(Lienzo.Width/cols.Value);
   // dy := Round(Lienzo.Height/rens.Value);
   dx := 12;
   dy := 12;
   Lienzo.Width := dx*cols.Value + 1;
   Lienzo.Height := dy*rens.Value + 1;
end;


procedure TForm1.FormCreate(Sender: TObject);
begin
   solucion := TStringList.Create;
   calcTamCeldas;
end;

function TForm1.HayHabitacionesF: Boolean;
var
   i: Integer;
   P: PCelda;
begin
    Result := False;
    for i := 0 to (Q.Count - 1) do
        begin
            P := Q[i];
            if P^.etiqueta = 'F' then
                begin
                    Result := true;
                    Exit;
                end;
        end;
end;


function TForm1.obtieneHabitacionF: PCelda;
var
   i: Integer;
   P: PCelda;
   L : TStringList;
begin

   L := TStringList.Create;
   for i := 0 to (Q.Count - 1) do
       begin
           P := Q[i];
           if P^.etiqueta = 'F' then L.Add(IntToStr(i));
       end;
       
   if L.Count > 0 then
       Result := Q[StrToInt(L[Random(L.Count)])]
   else
       Result := nil;
   L.Free;
end;

function TForm1.getMuroRandom(nodo: Pcelda): PCelda;
var
   i: Integer;
   Ref: Pref;
   vecino: PCelda;
   L : TStringList;
begin
   L := TStringList.Create;
   for i := 0 to nodo^.adyacentes.Count - 1 do
       begin
           Ref := nodo^.adyacentes[i];
           vecino := Q[Ref^.pos];
           if vecino^.etiqueta = 'I' then L.Add(IntToStr(i));
       end;

   if L.Count > 0 then
       begin
           Ref := nodo^.adyacentes[StrToInt(L[Random(L.Count)])];
           Result := Q[Ref^.pos];
       end
   else
       Result := nil;
   
   L.Free;
end;

procedure TForm1.etiquetar(nodo: pCelda; etq: String);
var
   i: integer;
   Ref: PRef;
   hijo: PCelda;
begin
   for i := 0 to nodo^.adyacentes.Count - 1 do
       begin
           Ref := nodo^.adyacentes[i];
           hijo := Q[Ref^.pos];
           if hijo^.etiqueta <> 'I' then hijo^.etiqueta := etq;
       end;
end;


function TForm1.obtieneMuroQueIntercepta(A, B: PCelda): TMurosSet;
var
    i: Integer;
    Ref: PRef;
begin
    Result := [];
    for i := 0 to A^.adyacentes.Count - 1 do
        begin
            Ref := A^.adyacentes[i];
            if B^.pos = Ref^.pos then
                begin
                    Result := Ref^.muroComun;
                    Exit;
                end;
        end;
end;

procedure TForm1.DerribarMuro(A, B: PCelda);
begin
    A^.muros := A^.muros - obtieneMuroQueIntercepta(A, B);
    B^.muros := B^.muros - obtieneMuroQueIntercepta(B, A);
end;

function TForm1.obtieneNodosPorDondePuedePasar(nodo: PCelda): TStringList;
var
   i: Integer;
   Ref: PRef;
   adyacente: PCelda;
begin
   Result := TStringList.Create;
   for i := 0 to nodo^.adyacentes.Count - 1 do
       begin
           Ref := nodo^.adyacentes[i];
           adyacente := Q[Ref^.pos];
           if (not adyacente^.visitado) and (Ref^.muroComun * nodo^.muros = []) then Result.Add(IntTostr(Ref^.pos));
       end;
end;

function TForm1.Regresa: PCelda;
var
   L: TStringList;
begin
   L := TStringList.Create;
   Result := nil;
   while (solucion.Count > 0) and (L.Count = 0) do
       begin
           Result := Q[StrToInt(solucion[solucion.Count - 1])];
           L.Free;
           L := obtieneNodosPorDondePuedePasar(Result);
           solucion.Delete(solucion.Count - 1);
       end;

   L.Free;
end;


procedure TForm1.DFS(nodo: PCelda);
var
   celda: PCelda;
   Childs: TStringList;
begin
   nodo^.visitado := true;
   solucion.Add(IntToStr(nodo^.pos));
   Childs := obtieneNodosPorDondePuedePasar(nodo);
   if Childs.Count > 0 then
      begin
          celda := Q[StrToInt(Childs[Random(Childs.Count)])];
          DFS(celda);
      end;
   Childs.Free;
end;


procedure TForm1.Button1Click(Sender: TObject);
var
  vecino, I, F: PCelda;
  Ref: PRef;
  k: Integer;
  val: Boolean;
begin
    Button1.Enabled := false;
    Button2.Enabled := false;
    verSol := false;
    if verSol then Button2.Caption := 'Ocultar Solución' else Button2.Caption := 'Ver Solución';
    Randomize;
    LimpiaLista(Q);
    Q := ObtieneListaDeNodos;


    I := obtieneNodo(Random(rens.Value), Random(cols.Value));
    I^.etiqueta := 'I';
    for k := 0 to I^.adyacentes.Count - 1 do
        begin
            Ref := I^.adyacentes[k];
            vecino := Q[Ref^.pos];
            vecino^.etiqueta := 'F';
        end;

    repeat
        F := obtieneHabitacionF;
        I := getMuroRandom(F);
        DerribarMuro(I, F);
        F^.etiqueta := 'I';
        etiquetar(F, 'F');
    until not HayHabitacionesF;


    //// BUSCA LA SOLUCION ////
    solucion.Clear;
    I := obtieneNodo(Random(rens.Value), 0);
    I^.muros := I^.muros - [izquierda];

    repeat
        DFS(I);
        F := Q[StrToInt(solucion[solucion.Count - 1])];
        val := (F^.j = cols.Value - 1);
        if not val then I := Regresa;
    until val;
    
    F^.muros := F^.muros - [derecha];


    Lienzo.Refresh;
    Button1.Enabled := true;
    Button2.Enabled := solucion.Count > 0;
end;


procedure TForm1.FormDestroy(Sender: TObject);
begin
    solucion.Free;
    LimpiaLista(Q);
end;

procedure TForm1.Button2Click(Sender: TObject);
begin
    verSol := not verSol;
    Lienzo.Refresh;
    if verSol then Button2.Caption := 'Ocultar Solución' else Button2.Caption := 'Ver Solución';
end;

procedure TForm1.FormResize(Sender: TObject);
begin
    Lienzo.Left := Round((Panel2.ClientWidth - Lienzo.Width)/2);
    Lienzo.Top := Round((Panel2.ClientHeight - Lienzo.Height)/2);
end;

end.

Cabe indicar que Guillermo mandó versiones mejoradas de tanto en tanto, las cuales optimizaron la solución, lo cual fue lo que finalmente decidió que se le otorgara el primer lugar. Guillermo Cañedo Ramírez, 44 años, estudió Ingeniería Eléctrica y una maestría en Sistemas Eléctricos de Potencia en el Instituto Tecnológico de Morelia. He aquí la descripción de lo que hizo: "La estrategia que seguí", nos dice, "está basada en 2 algoritmos:" Dependiendo del número de renglones y columnas que se quieran del laberinto, se define una matriz de m renglones y n columnas y se almacena toda la información en una lista dinámica con TList (disponible en Delphi) de apuntadores a una estructura de datos TCelda.

TMurosSet = set of (arriba, abajo, derecha, izquierda);

  PCelda = ^TCelda;
  TCelda = record
      i, j, pos: Integer;
      visitado: Boolean;
      etiqueta: String;   
      muros: TMurosSet;
      adyacentes: TList;
  end;

y la lista de habitaciones adyacentes apunta a una estructura de datos del tipo TRef.

  PRef = ^TRef;
  TRef = record
      pos: Integer;
      muroComun: TMurosSet;
  end;

Primero se etiquetan todas las celdas o habitaciones de la matriz con 'u'

 1) El Algoritmo de Prim's para generar el laberinto, es como sigue:

• a) Elegir una celda o habitación al azar y etiquetarla como I,
• b) Etiquetar las habitaciones adyacentes de I con F
• c) Obtener al azar una habitación etiquetada como F y derribar el muro que colinda con la habitación I,
• d) Etiquetar F como I y
• e) Etiquetar las adyacentes del nuevo I pero que no sean I como F
• f) Repetir del c) al e) hasta que ya no haya mas habitaciones F

2) El Algoritmo de Búsqueda Primero en Profundidad con retroceso para hallar la solución:

• a) Etiquetar todas las habitaciones del laberinto como no visitadas.
• b) Elegir al azar una habitación de entrada de la primer columna y se establece como entrada del laberinto, eliminando su muro izquierdo
• c) Establecer la habitación como nodo raíz y marcarla como visitada y guardar la posición del nodo en una lista que sera la solución.
• d) Obtener las habitaciones adyacentes que no estén visitadas y que no tengan muro colindante para poder pasar.
• e) Elegir al azar una de ellas y de manera recursiva repetir de c) a e) hasta que ya no haya habitaciones adyacentes sin visitar y sin muro o que la columna del nodo raíz sea igual al total de columnas del laberinto
• f) si e) no se cumple entonces ir en sentido inverso con nuestra lista de la solución e ir eliminando el ultimo elemento hasta que haya un camino por donde pasar.
• g) Al finalizar se marca el último nodo de la lista con la solución como salida del laberinto derribando el muro derecho.

Actualmente desarrolla aplicaciones educativas y juegos para tabletas y smartphones en forma independiente en Taos Games. Felicitamos a Guillermo y vienen más retos, con más premios. Hemos estado trabajando con algunas empresas para que nos den apoyo, así que ahora, a redoblar esfuerzos porque los premios empezarán a ponerse más atractivos... Poco a poco, pero verán que empezarán a incrementarse.

A quien le interese el código de Guillermo y el de los otros dos concursantes, poueden escribirme a morsa@la-morsa.com y se los mandaré por si les interesa estudiarlo.

Programación lúdica: ¿Cuántas palabras diferentes tiene “El Quijote”?

Una obra monumental de la literatura española es el Quijote, escrito por Miguel de Cervantes hace ya muchos años. Se tienen versiones impresas en rústica, en pasta dura, en ediciones de lujo, etcétera. Desde luego que en formato electrónico hace rato que está y el Quijote puede leerse en formatos PDF, ePub y en textos normal, sin formato especial, pues.

Después del reto pasado, el de contar palabras, en donde se usaron dos libros unidos (Los Miserables y el Quijote), para hacer un archivo relativamente grande (unos 5 MBytes), se me ocurre ahora plantear el siguiente problema: Tomemos el archivo del Quijote (el cual puede descargarse de este sitio), y la tarea a resolver, es la de hacer una lista de todas las palabras diferentes que tiene la obra de Cervantes y la frecuencia de las mismas (ordenado alfabéticamente). ¿Cuál será la palabra más veces escrita por el manco de Lepanto? ¿Cuál será la palabra que solamente se escribió una sola vez? Estas dudas no me dejan dormir.

Aquí tomaremos en cuenta dos criterios: el primero será el de la velocidad, es decir, qué programa llega a hacer esta lista (que se debe guardar en un archivo de texto) de manera más rápida y el segundo, que dé la frecuencia de cada palabra usada. El resultado debe entregarse mostrando por línea la palabra hallada y al lado, la frecuencia de la misma, es decir, las veces que ocurrió en el texto. Los criterios se toman en cuenta de forma indistinta. Por ejemplo, alguien puede entregar un programa que halla todas las palabras y sus frecuencias, y se tarda 2 minutos (por decir algo), mientras que otro entrega un programa que es muy veloz, pero que no entrega todas las palabras o que el conteo está mal. Evidentemente el ganador será aquí el que entregue el resultado más cercano al que debe ser.

Las restricciones usuales en el reto son: No se vale usar una biblioteca para hacer búsquedas, ordenar, o cualquier otra labor que sea parte del reto, es decir, solamente puede usarse el lenguaje tal cual viene definido con las bibliotecas de entrada/salida, por ejemplo.

Cabe señalar que el reto no es sencillo, porque antes de empezar hay que discurrir qué estructura de datos vamos a usar. De acuerdo a Word (e incluyendo los anuncios legales del Proyecto Gutenberg), el Quijote contiene unas 384,262 palabras. Pensemos, solamente para ilustrarlo, que todas ellas fuesen diferentes (que no es cierto), y que cada palabra ocupa unos 10 caracteres en promedio (suena razonable asumir eso), tendríamos que tener una estructura que conteniera  unos 4 MBytes, cosa que no es muy complicada. A eso hay que añadirle el conteo de las palabras, lo cual debe ponerse de alguna manera. Por favor, no se les ocurra hacer un arreglo de 4 MBytes para contener palabras y números. Eso, aunque s epueda hacer y el compilador no proteste, no es una técnica aceptable de programación. En mi opinión, hay que hacer un árbol de registros que contengan, las palabras y la frecuencia hallada. La ventaja de esta estructura es que el ordenamiento se puede hacer simplemente recorriendo el árbol de una manera en particular. No se requiere pues ordenarlo directamente. Pero estos son sólo tips, no tienen que seguirse si no se desea.

Quienes programan en Python, Ruby on Rails o cualquier lenguaje interpretado, la parte de procesar más rápido que los demás la tienen perdida. Esto no quiere decir que ya no puedan ganar el reto, pero claramente quedan en desventaja ante los programas compilados a código nativo x86.

¿El premio? Una taza con el logotipo de la Morsa a la mejor solución. Además hay una libretita y una gorra, cortesía de los buenos amigos de Qualcomm que se añade al premio. Pudiese ser que se incorporaran más premios pequeños (estamos trabajando en eso), como pudiesen ser camisetas, etcétera. Esto solamente aplica a los programadores que vivan en el DF (mandar a provincia o a otros países una taza es estúpidamente costoso). En caso de que los concursantes sean de otros países o de la provincia mexicana, el premio será una memoria USB de al menos 8 GBytes y se les enviará por correo certificado. Y sí, sé que no son los grandes premios pero esto es lo que hay por el momento. Evidentemente quien gane será anunciado aquí y hasta tendrá sus quince minutos de fama.

Los resultados finales son inapelables. Cabe señalar que este concurso busca simplemente alentar el trabajo de la programación y mostrar que puede ser lúdica. Es un concurso de buena fe. El ganador cede su código fuente a la comunidad. Es decir, se promueve el código abierto. Programas copiados de la web o que tengan ese sabor sospechoso de plagio podrán ser eliminados sin mayores consideraciones. El chiste de estos retos es que los programadores se animen a resolverlos, no que busquen la manera de hacer trampa. ¡Así que a afilar sus habilidades de programación y pasar un buen rato intentando resolver el problema propuesto!

Ganador del reto de contar palabras

Con una buena participación por parte de los programadores/lectores binarios del sitio unocero, damos por concluido el reto de la programación lúdica que trataba de contar letras, espacios y palabras de un texto. Cabe decir que enfrenté un problema. Los programas eran en su mayoría muy rápidos (un par de segundos en el caso de los ejecutables), mientras que los que usaron Python, por ser un intérprete, fueron extremadamente lentos. Por ende, como el rato originalmente era de velocidad, los intérpretes (a excepción de Java, que casi tiene un desempeño como el de un ejecutable nativo), palidecen frente a código compilado de máquina x86.

Debido a que las diferencias en tiempos entre algunos programas eran demasiado cortos, decidí tomar otro criterio: Qué tanto se acercaban a las cifras originales dada por Microsoft Word. De hecho, comparé el resultado contra el que dio OpenOffice 4.1.0 y fueron exactamente los mismos. Vamos ambos programas toman en cuenta las mismas consideraciones para contar palabras. Así, debido a que los programas corrían muy rápido y las diferencias eran a veces de centésimas de segundos, no era posible discriminar realmente quién había sido el más rápido. Además, se buscaba que el resultado fuese “correcto”.

Los valores que entrega Ms-Word y OpenOffice

Esto en algún sentido fue una sorpresa. La mayoría de los programas entregan resultados diferentes en sus conteos. Las razones son los criterios que cada uno de ellos estableció para definir lo que era una palabra. Por ejemplo, para Word “–Y” son dos palabras. Por eso hay divergencias.

Por otra parte, tuve que descalificar, valga la expresión, a José Gabriel Acosta, que usó una biblioteca de funciones para ayudarse en esta tarea. Le indiqué que eso no se valía, porque entonces todo se resume a que se haga la llamada adecuada sin haber programado realmente el reto. Les dije que podían reescribir su código y que me lo mandara. No recibí nada y tuve que descalificarlo.

El ganador fue Diego Iván García Leyva, (ver foto al lado), de 27 años, Culiacán, Sinaloa. Estudió ingeniería electrónica en el Tecnológico de Culiacán, actualmente desarrolla sistemas biométricos de Coppel. Maneja los proyectos de huella en línea y reconocimiento de rostro.

De acuerdo a la tabla que sigue (si quieren el archivo de Excel, pídanmelo), mostró que se acercó más a los demás en promedio -contra el estándar definido por Word y OpenOffice (que dan los mismos resultados). Sólo falló por 0.08. No me importó si se acercaban “por arriba o por abajo” del resultado correcto, sino el valor absoluto de la diferencia.


Desde luego que el código de todos los que concursaron pueden pedírmelo y les mandaré un enlace para que bajen el archivo comprimido. Escríbanme los interesados a morsa@la-morsa.com. El archivo de texto que se usó contiene unos 5 megabytes. Es la combinación del texto de los Miserables y del Quijote. Aún con 5 Megabytes, repito, algunos programas fueron muy rápidos.

Felicidades a Diego y ya le estaré mandando su premio.

Programación lúdica: Contemos letras, palabras y espacios

El pasado reto de la programación lúdica sigue abierto (el de los laberintos), pero hasta ahora he recibido dos programas y en mi opinión no cumplen con los requisitos pedidos. Así pues, lo dejaremos una semana más abierto a ver si hay algún programa que cumpla con lo pedido: que genere y que resuelva el laberinto.

Mientras tanto, abramos el siguiente reto de la programación lúdica. Se trata de tomar un texto -no necesita ningún formato especial, simple ASCII- y que el programa cuente cuantas palabras, espacios y letras tiene. Se calificará el programa que lo haga en el menor tiempo posible dado un texto especifico, el cual puede consultarse más abajo. Así, el software debe poder leer a memoria cualquier texto y contar lo que tiene que contar, desplegándolo cuando termine.Considérese que el archivo a procesar pueda ser de algunos megas, cuyo límite máximo lo pondremos en 10 megabytes, por lo que el software debe poder leer el documento ASCII sin problemas. Se buscará un texto lo suficientemente largo para que los tiempos de medición no sean tan cortos que sea difícil saber quién ganó, pero se pueden hacer algunas pruebas con los textos que aparecen en los enlaces más abajo.

Los tiempos los mediré en mi computadora y los resultados son inapelables.

¿El premio? Una taza con el logotipo de la Morsa a la mejor solución. Además hay una libretita y una gorra, cortesía de los buenos amigos de Qualcomm que se añade al premio. Esto solamente aplica a los programadores que vivan en el DF (mandar a provincia o a otros países una taza es estúpidamente costoso). En caso de que los concursantes sean de otros países o de la provincia mexicana, el premio será una memoria USB de al menos 8 GBytes y se les enviará por correo certificado. Y sí, sé que no son los grandes premios pero esto es lo que hay por el momento. Evidentemente quien gane será anunciado aquí y hasta tendrá sus quince minutos de fama.

Cabe señalar que este concurso busca simplemente alentar el trabajo de la programación y mostrar que puede ser lúdica. Es un concurso de buena fe. Si hay, por ejemplo, dos o más respuestas satisfactorias, ganará quien la haya mandado primero. El ganador cede su código fuente a la comunidad. Es decir, se promueve el código abierto. Programas copiados de la web o que tengan ese sabor sospechoso de plagio podrán ser eliminados sin mayores consideraciones. El chiste de estos retos es que los programadores se animen a resolverlos, no que busquen la manera de hacer trampa. ¡Así que a afilar sus habilidades de programación!

Textos con los que se pueden hacer pruebas, pueden descargarse de aquí, aquí o aquí.

Programación lúdica: el juego de NIM

Dice la Wikipedia: "En este juego, dos jugadores a los que llamaremos David y Vicente, colocan un número arbitrario de fichas (cerillas, palillos, guijarros) sobre una superficie, separadas en filas o grupos. Tanto el número de filas como el número de fichas en cada fila son también arbitrarios. El primer jugador, supongamos que es David, toma cualquier número de fichas de una fila, entre uno y el total de la fila, pero sólo de una fila. El jugador Vicente hace su jugada de manera similar, retirando algunos de las fichas que quedan, y los jugadores van alternándose en sus jugadas. Se puede jugar de modo que gane el que retire la última ficha".

Para limitar el problema, pensemos en la siguiente configuración inicial:

Un jugador puede eliminar de una de las cuatro filas, las bolitas que quiera. No importa el orden, es decir, si elimina las tres primeras bolitas de la última fila (la que contiene siete bolitas) o si lo hace salteado, una sí y uno no, alternadamente, da lo mismo. Si quita tres de la última fila, el rival podria, por ejemplo, quitar las cuatro restantes, aunque quedasen en grupos separados dentro de la misma línea.. El objetivo del juego, repito, es que quien tenga que eliminar la última bolita, pierde. Nótese que en cada turno solamente se pueden eliminar bolitas de una sola fila.

Este juego ha sido muy estudiado y se conoce un algoritmo para la solución. Aquí sin embargo, el reto se trata de lo siguiente. Por ejemplo, la configuración 1-2-3 es ganadora (esto quiere decir que en una línea quede una bolita, en la siguiente dos y en la tercera línea tres bolitas) Si hay esta configuración, quien juega pierde. De hecho, 1-2-3 es equivalente a 3-2-1 o 2-1-3, etcétera. Configuraciones que tienen que ver con la mencionada son 2-2 y 1-1-1. Por ejemplo, si llego a tener la configuración 2-2, si el rival quita una bolita de cualquiera de las dos líneas, yo quito dos y mi rival tiene que quitar la última. Si mi rival quita dos bolitas de la línea, yo quito de la línea restante una bolita y de nuevo gano, pues el contrario tiene que eliminar la última.

El reto pues consiste en hallar todas estas configuraciones ganadoras. Ya di algunas:

1-1-1
1-2-3
3-3
2-2
4-4

¿Cuántas configuraciones ganadoras hay? ¿Es 1-3-5-7 una configuración ganadora o perdedora? El resultado del programa que escriban debe dar todas las configuraciones ganadoras en el formato A-B-C-D, por ejemplo:

1-1-1
2-2
3-3
4-4

una configuración en cada línea (pueden omitirse las líneas que no contengan bolitas, que den cero, pues).

¿El premio? Una taza con el logotipo de la Morsa a la mejor solución. Esto solamente aplica a los programadores que vivan en el DF (mandar a provincia o a otros países una taza es estúpidamente costoso). En caso de que los concursantes sean de otros países o de la provincia mexicana, el premio será una memoria USB de al menos 16 GBytes y se les enviará por correo certificado. Y sí, sé que no son los grandes premios pero mientras no tengamos patrocinadores, esto es lo que hay.

Evidentemente quien gane será anunciado en unocero y hasta tendrá sus quince minutos de fama. Sus programas me los pueden mandar a morsa@la-morsa.com y pueden escribirse en cualquier lenguaje. Es importante señalar que hay que mandar el código fuente, el ejecutable (si procede) y el archivo de resultados pedido.

Cabe señalar que este concurso busca simplemente alentar el trabajo de la programación y mostrar que puede ser lúdica. Es un concurso de buena fe. Si hay, por ejemplo, dos o más respuestas satisfactorias, ganará quien la haya mandado primero. El ganador cede su código fuente a la comunidad. Es decir, se promueve el código abierto. Así que “en sus marcas, listos, ¡arrraaaaancan!”

Ganadores del reto del gato

Sorprendido alegremente por la respuesta de los programadores que visitan unocero, a escasas horas de empezar el reto, a eso de las 10 de la noche del sábado -cuando se publicó el artículo- recibí a la 1:30 am del domingo la primera respuesta. Dos más llegaron a eso de las 2:15 am y 4:40 am. En el transcurso de hoy llegaron un par más.

 El ganador fue Adán Enrique Aguilar, que escribió un programa en Java, el cual pongo a consideración de todos: Enrique es de Xalapa, Veracruz y en un par de días le mando su memoria USB de 16 GBytes, ¡Felicidades!

Debido al interés que presentaron los siguientes dos programas, se dan dos premios más, uno fue para Manuel Alcántara Juárez. Él me mandó, además, los siguientes datos: El programa genera 255168 posiciones donde 131,184 juegos los gana X, 77,904 los gana O y 46080 terminan en empate. El programa inicia con las "o" pero como dice mi tocayo, es isomorfo.

Finalmente, Charles López resolvió el problema. Su código llegó a eso de las 4 40 am. El ganador se lleva la memoria USB y los otros dos se llevan una taza con el logotipo de La_Morsa.

 

De izquierda a derecha: Adán Enrique, Manuel Alcántara y Charles López   

Es importante decir que aún no me queda claro cuántas son las posibles posiciones legales. Muchos sitios web dan cifras pero en todos los casos no coinciden. Cuando tenga un rato verificaré esto.

Agradezco realmente el esfuerzo realizado. No pensé que iba a tener estas respuestas y tan rápido. Quien quiera los archivos zipeados de los ganadores, con el respectivo código fuente, escríbame a morsa@la-morsa.com y se los mando de inmediato. (No los puse aquí porque tuve problemas en el formateo).