a veces, las cosas cambian

Esta semana estaré de reunión en Santiago de Chile, preparando la próxima edición de IEEEXtreme, el concurso de programacion de IEEE, pero prometo mandar algun problemilla desde allá en cuanto tenga conexion.

De momento, por dejar algo mas ligero que el ultimo problema que puse, para que no se me queje nadie, os dejo un pequeño puzzler, en el que (como ya comentamos) lo que queremos es adivinar que función realiza un determinado programa pero SIN ejecutarlo. La idea subyacente es que, si lo que pasa no es lo que esperábamos, siempre podemos investigar por qué.

En nuestro caso, sea el siguiente programa:

using System;

public class MusicStar {
string name;
Style style;

protected MusicStar() {
// utilizado solo para las herencias
}

public MusicStar(String name, Style style) {
this.name = name;
this.style = style;
}

public override string ToString() {
return "nombre: " + name + " (estilo:" + style + ")";
}

public class Style {
string stylename;

public Style() {
}

public void SetStyleName(string name) {
this.stylename = name;
}

public override string ToString() {
return stylename;
}
}
}

public class HardRockStar : MusicStar {

public HardRockStar(String name, Style style) : base(name, style) {
if(style.ToString() != "Hard Rock") {
throw new ArgumentException(
"Nada de mariconadas! Solo me gusta el rock!");
}
}
}

public class Changes {

public static void Main(String[] args) {
MusicStar.Style style = new MusicStar.Style();

style.SetStyleName("Hard Rock");
HardRockStar slash = new HardRockStar("Slash", style);

style.SetStyleName("CutrePop");
MusicStar paulina = new MusicStar("Paulina Rubio", style);
MusicStar marta = new MusicStar("Marta Sanchez", style);

Console.WriteLine("nuestras estrellas de esta noche son:");
Console.WriteLine(slash.ToString());
Console.WriteLine(paulina.ToString());
Console.WriteLine(marta.ToString());
}
}

¿Cual seria la salida al ejecutar la funcion principal (Main) de MainProgram? ¿Por que?

NOTA: para el que quiera alguna pista adicional, aqui os dejo dos en forma de videos: Paulina y Marta (para ahorraros el tiempo de ver el resto de la basurilla musical, os recomiendo pasar directamente a los minutos 2:30 y 2:45 respectivamente) 

ACTUALIZACION: me di cuenta tarde que habia pegado la version del codigo que no era! Os he dejado la version actualizada, pero abajo pongo un comentario para los que ya os animasteis a enviar respuestas. Mil perdones! 

todos por igual

Este es otro problema de algoritmia generica, antes de que sigamos analizando algoritmos y tecnicas de diseño, para intentar pensar “out-of-the-box”.

Imaginemos que tenemos un array de enteros, de tamaño K, y un flujo del que vamos leyendo enteros, hasta un numero N. No conocemos N de antemano, pero sabemos que sera igual o mayor que K. Lo que queremos es tener en nuestro array de K posiciones una muestra equiprobable de los enteros del flujo.

¿Que quiere decir esto? Imaginemos que nuestro array tiene K=5 elementos y supongamos una notacion (a-b-c) para un flujo que contenga los elementos a, b y c.

Si nuestro flujo fuera todo de unos, como en (1-1-1-1-1-1-1), nuestro array final debe contener 5 unos siempre.

Si en cambio nuestro flujo fuera algo como (1-1-1-1-2-1-1-1-1-2), debe haber 4 veces mas posibilidades de tener unos que doses, con lo que nuestros posibles resultados serian: un array con todo unos (aproximadamente un 22.2% de las veces), un array con 4 unos y 1 dos (el dos puede estar en distintas posiciones, pero ocurrira aproximadamente un 55.6% de las veces) y un array con 3 unos y 2 doses (de nuevo pudiendo estar los doses en distintas posiciones, y que ocurrira aproximadamente el 22.2% de las veces)

Supongamos que nuestro flujo de entrada esta modelado mediante las funciones:

boolean hasNext(): devuelve true si quedan elementos por leer, false en otro caso
int getNext(): obtiene el siguiente entero del flujo mientras queden elementos, o un valor indeterminado en otro caso

Dado un numero K de posiciones para el array, y un flujo de entrada de longitud N indeterminada (pero finita): ¿serias capaz de construir el algoritmo para devolver una muestra equiprobable tal como la hemos definido anteriormente?

nota: las funciones que modelan el flujo estan dadas en notacion estilo C. Podeis cambiarlas a algo apropiado en el lenguaje que utiliceis, siempre y cuando conserven la semantica, claro 

ejercicio y números confusos

Supongo que no hace falta que os diga que el ejercicio es bueno para la salud. Todo el mundo deberia practicarlo a menudo: te hace sentir bien, te pones menos enfermo… A mi hasta me parece que piensas mejor si haces ejercicio de cuando en cuando! Y eso sin contar con que supone una muy buena “desconexion” del mundo, que ayuda a dar otro punto de vista a las cosas.

Yo suelo tener por costumbre hacer ejercicio a mediodia, antes de la hora de comer. Despues de la jornada de la mañana, una pausa para nadar te da una hora de relajacion que ademas puedes aprovechar al volver para repensar aquello en lo que estabas trabajando.. y a veces darle a las cosas un giro en el que no habias caido antes.

De hecho, este problema se me ocurrio en una de estas visitas a la piscina antes de trabajar, y tiene que ver bastante con “cambiar el punto de vista”. A ver que os parece:

En el centro al que yo voy, como en muchos otros, hay un sistema de taquillas para dejar la bolsa mientras nadas. simplemente pides una taquilla en la puerta y te dan una llavecita con un numero. Vas a la taquilla, dejas tus cosas, cierras, te vas a nadar y posiblemente cuando vuelvas aun este todo alli. El caso esta en que esa tarde a mi me dieron la llave numero 89. Yo fui tan contento a cambiarme y cuando estaba buscando… me di cuenta que solo veia 80 taquillas.

“Se me debe estar pasando algo”, me dije. Conte el numero de armarios, vi cuantas taquillas cabian… y no, no podia ser. Ademas, no hay mas sitio para armarios. “¿Sera que a lo mejor a partir de la 80 estan en el vestuario de las chicas y me han dado la llave que no es?” Estaba yo pensando en dar la vuelta e ir a preguntar a recepcion cuando me dije… “mmm… dar la vuelta… podia ser…” Y claro, es que un llavero no tiene un derecho ni un reves, y los numeros escritos a mano son dificiles de leer, asi que mi llave numero 89, dada la vuelta, bien podria ser la numero 68, ¿no? Pues efectivamente… ¡asi de simple era! Asi que abri mi taquilla, deje mis cosas y me fui a nadar

Pero claro, ya iba pensando en lo siguiente: imaginemos que hacemos un sistema de OCR limitado, que usaremos para reconocer numeros a partir de imagenes de video. Como no conocemos la orientacion de la camara, esos numeros podrian estar en un momento cualquiera tanto al derecho como al reves. Asi, esfacil leer un 6 como si fuera un 9, o viceversa. Ademas, si estos numeros estan escritos a mano y las imagenes son de baja resolucion es facil confundir algunos incluso sin tener orientacion: por ejemplo el 8 con el 0 (especialmente si escribis el cero con una barra cruzada, como yo)

Imaginemos entonces que hemos definido las siguientes posibles confusiones:

  • 0 se puede confundir con 8, tanto al derecho como al reves
  • 1 se puede confundir con 7, tanto al derecho como al reves
  • 2 se puede confundir con 7, al reves
  • 3 se puede confundir con 8, tanto al derecho como al reves
  • 4 y 5 no se confunden con nada, son asi de majos
  • 6 se puede confundir con 9, al reves
  • 7 se puede confundir con 1, tanto al derecho como al reves, y con 2, al reves
  • 8 se puede confundir con 0 y con 3, tanto al derecho como al reves
  • 9 se puede confundir con 6, al reves

¿Podrias crear una funcion que reciba un array de caracteres con lo que hemos leido del OCR y devuelva un array de enteros con todos los posibles valores que pueden representar leidos al derecho o al reves (si se puede), teniendo en cuenta que pueden ocurrir las confusiones que hemos citado antes? En el ejemplo de mi llave de la taquilla, recibiriamos el array [‘8′,’9’] y tendriamos que devolver [89, 68, 09, 60, 39, 63]

Suponemos que la entrada siempre es un array de caracteres que representa un numero entero positivo.