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.

el bug de multiplicacion de Excel 2007

Acabo de aterrizar de Ibiza de unas minivacaciones impresionantes (y en las cuales de paso he escrito un par de problemas nuevos para programancia101!) asi que no he podido seguir en directo la serie de articulos que han aparecido en la blogosfera acerca de un bug en Excel 2007. Afortunadamente, mi amigo Chema «el maligno» me ha mandado un correito para asegurarse que nos haciamos eco de esta noticia.

 Para los que no lo hayais visto ya, resulta que se ha encontrado un pequeño bug en Excel 2007 (noticia en español en Microsiervos) con algunas multiplicaciones. Podeis encontrar mas ejemplillos por la web, pero el aviso original se referia a la multiplicacion 850 * 77.1, que en vez de 65535, que es el resultado correcto, se muestra como 100000.

 

Como buenos lectores de programancia101 y revisando algunos de nuestros articulos anteriores (como este y este), seriais capaces de adivinar cual es la hipotesis razonable mas probable que puede causar este tipo de fallo?

Para los que quieran directamente «la solucion», podeis mirar este post del equipo de Excel, que se puso manos a la obra para arreglarlo el dia despues del aviso.
 

arrejuntando listas

Antes de que nadie me comente nada: prometo que «arrejuntarse» es un verbo español perfectamente valido! Pese a que suene un poco «brutito» en realidad se refiere a vivir vida de casados sin estarlo. Tengo de hecho un par de amigos que estaban haciendo eso mismo hasta que hace unos meses se les fue la pinza cambiaron de idea y decidieron casarse, asi que este finde nos tocara boda! (y vistos los ejemplos de algunos miembros de geeks, parece que este año hay ida de olla general tendencia al tema)

Pero en fin, nosotros a lo que es el codigo, que es lo nuestro…

 

 Vamos a proponer hoy un par de variaciones de problemas con listas:

Para empezar, imaginemos que tenemos dos listas previamente ordenadas y que queremos generar una tercera lista que tenga todos los elementos de las dos anteriores, pero tambien ordenados. Asi por ejemplo si una lista es (1,4,7) y la otra (2,5,6) el resultado debe ser la lista (1,2,4,5,6,7)

Podrias escribir una funcion que reciba como entrada las dos listas y que devuelva la lista resultante, segun la descripcion anterior? Se te ocurre una forma de crear una funcion generalizada que haga lo mismo para un numero N de listas?

Y ahora imaginemos que tenemos un sentido del orden un poco extraño, y que lo que queremos es ordenar las listas de modo que en la lista resultado los elementos impares esten ordenados ascendentemente partiendo desde el centro y hacia la izquierda, y los pares desde el centro, hacia la derecha. Es decir, en el ejemplo anterior con (1,4,7) y (2,5,6) nuestro resultado deberia ser (7,5,1,2,4,6)

Podrias escribir una funcion que cree la lista resultante en este caso?

que tal vuestra vuelta al cole?

Buenas a todos!

Esto no es ninguna noticia pero… se acabaron las vacaciones! Agh! Que sufrir! Hay que volver al trabajo, verle la cara al jefe otra vez, reunirnos con unos clientes que necesitan algo «para ya» porque se les ha ido el verano y nadie se acordaba que habia que entregar en septiembre, pasar la semana releyendo el codigo que dejamos «a medias» y que no recordamos muy bien lo que hace porque con las prisas se nos «olvido» documentar y comentar… os suena? (el caso peor de esto ultimo es cuando al volver miras tu codigo y dices: «seguro que esto lo escribi yo?»)

Para haceroslo mas leve, os recomiendo que empeceis leyendo algo gracioso como este clasico sobre comentarios en el sistema UNIX (que incluye uno de mis favoritos: «no hace falta que entiendas esto» };D) Si conoceis algun otro ejemplo, de esos dignos de salir en worsethanfailure.com… compartidlo!

En fin, solo queria avisar que en breve comenzamos el nuevo curso en programancia101, con nuevos problemas de todos los niveles y los ocasionales truquitos divertidos. Este curso ademas contaremos con un par de «articulos invitados» y algunas recomendaciones de libros. Y por supuesto, si teneis alguna otra idea que podamos añadir, hacedmelo saber! }:)

Feliz vuelta al cole! 

volvemos a la carga: rellenando espacios

Hola de nuevo, crases! Mil perdones por mi desconexion del mundo estas ultimas semanas. He tenido algunos lios que atender que han ido postponiendo la publicacion de mas problemas. La buena noticia es que me ha dado tiempo a pensar algunos problemas mas asi que… espero resarcirme publicando a un ritmo mas acelerado en los proximos dias!


Como deciamos en los ultimos posts, habia pensado seguir con algunos ejercicios de algoritmia basica y que nos permitan repasar conceptos como la ordenacion, la insercion y distintas tecnicas que nos serviran mas adelante. Para empezar a calentar despues de esta pausa, os propongo un problema sencillo:


Imaginemos que tenemos un array de caracteres que representa una cadena de texto formada por palabras separadas por espacios. Imaginemos que tenemos una cantidad N de caracteres de subrayado (‘_’) por los que queremos sustituir los espacios, de una forma uniforme. Es decir: si tenemos los caracteres que representan «una frase cualquiera» y tenemos 4 caracteres de subrayado, querriamos algo como «una__frase__cualquiera» (2 signos de subrayado por espacio). Si solo tuvieramos 3 caracteres, tanto «una_frase__cualquiera» (un subrayado primero, dos en el segundo) como «una__frase_cualquiera»  (dos subrayados en el primero, uno en el segundo) serian validas.



taken from http://flickr.com/photos/ashleylynn/252023013/)


Asi que en resumidas cuentas: podrias escribir una funcion que dado el array de caracteres que representa la cadena, y un numero N de caracteres de subrayado, devuelva la cadena resultante de sustituir los espacios por subrayados de forma uniforme?


Si quieres complicarlo un poco mas podrias intentar tambien devolver todas las posibles cadenas (si hay mas de una) 


Actualizacion: Parece ser que no me explique del todo bien en este problema, lo siento. Para que no haya equivocos sobre que quiere decir «distribucion uniforme» una definicion «formal» seria: no puede haber una diferencia de mas de 1 entre el numero de subrayados que asignamos a cada espacio. Asi por ejemplo:



  • Si tenemos «frase con tres espacios» y 7 signos de subrayado, la distribucion «frase__con__tres___espacios» (2 al primero, 2 al segundo y 3 al tercero) es uniforme, pero la distribucion «frase___con___tres_espacios» (3 al primero, 3 al segundo y uno al tercero) no lo es

  • Si tenemos «frase mas larga que la anterior», la distribucion «frase_mas_larga_que__la__anterior» (1-1-1-2-2 signos de subrayado) es uniforme, pero la distribucion «frase___mas_larga_que_la_anterior» (3-1-1-1-1 signos de subrayado) no lo es

Asimismo, para efectos de «precondiciones» podeis suponer que la frase siempre tiene al menos un espacio, y que solo hay un espacio entre palabra y palabra.

dandole al interruptor

El fin de semana pasado prometi a varios amigos que de esta semana no pasaba que publicara un nuevo problemilla de programancia101, porque ya veo que a la que uno se descuida, le sale competencia! Mirad si no a mi camarada Kartones, que se esta animando a publicar problemas en su blog.


Como me ha gustado la idea, se me ha ocurrido dejar otro problema que podeis resolver con un algoritmo sencillito, o bien usando «trucos»:



Imaginemos que tenemos una fila con 64 interruptores, cada uno de los cuales conectamos a una bombilla. Supongamos que partimos de una posicion en la que todas las bombillas estan apagadas y procedemos a pasar por todas ellas y cambiar el estado del interruptor. Una vez hecho esto, volvemos al principio y volvemos a cambiar la posicion del interruptor pero solo para las bombillas en posiciones que sean multiplos de 2 (la segunda, la cuarta, la sexta, …) De nuevo volvemos al principio y volvemos a cambiar la posicion del interruptor pero solo para posiciones multiplos de 3 (la tercera, la sexta, la novena, …) Y seguimos repitiendo el procedimiento para posiciones multiplos de 4, de 5, de 6… asi hasta los multiplos de 64.


Que algoritmo usarias para saber cuales de las bombillas permaneceran encendidas al terminar? Y, si te apetece complicarte un poco mas: Como podriamos hacerlo utilizando la menor cantidad de memoria posible? 

ordenando a montones

Como algunos de vosotros sabreis, esta semana tengo a Chema de visita en casa, asi que escribir se nos esta haciendo mucho mas dificil (porque claro, la fiesta y los blogs no son muy compatibles). Sin embargo, tenia pensado empezar a anyadir mas tipos de problemas esta semana, asi que… alla vamos!

En este problema vamos a intentar subir un poco el nivel… de abstraccion, quiero decir. Vamos a desempolvar un poco esos libros de algoritmos y ver un problema muy basico: la ordenacion. Pero claro, esto es programancia101 y aqui no podemos ordenar cualquier cosa. Al igual que en otras ocasiones, vamos a plantear este problema por fases:

  • La primera parte seria algo como: sabrias decir cual es la forma mas rapida de ordenar diez mil (10.000) numeros? Que tiempo (aproximadamente) llevaria hacerlo en tu ordenador?
  • La segunda, continuando con la idea: cual es la forma mas rapida de ordenar un millon (1.000.000) de numeros? Que tiempo (aproximadamente) llevaria hacerlo en tu ordenador? Se comporta de forma lineal con el caso anterior? Por que?
  • La tercera, partiendo de este segundo caso: imaginemos que la maquina en la que vamos a ordenar nuestro millon de numeros solo tiene 2 megabytes de memoria, una cantidad ilimitada de disco duro y que nuestros numeros son enteros sin signo de 32 bits. Supon que disponemos de un flujo de entrada para leer los enteros de forma secuencial y un flujo de salida en el que podemos escribir enteros, ambos accesibles mediante las funciones/metodos:
    // Devuelve el siguiente entero a ordenar
    int LeerSiguiente();
    // Escribe el entero en el stream de salida
    void Escribir(int numero);

    NOTA: a efectos de complejidad, podemos suponer que las llamadas a estas funciones/metodos son de orden constante
    Cual seria la mejor forma en este caso?
  • Y finalmente, la cuarta, rizando el rizo: imaginemos que los numeros anteriores proceden de un listado sin repeticiones de numeros de telefono de exactamente 7 digitos y que NO tenemos acceso a disco (y si, seguimos teniendo solo 2 megabytes de memoria): serias capaz de ordenarlos de la forma mas rapida posible?

Como siempre, estais invitados a comentar vuestras soluciones en los comentarios, o bien publicarlas en vuestro blog y dejar un enlace! }:)

NOTAS: Como orientacion de dificultad: las dos primeras partes deberian ser sencillas para un nivel basico/medio y repasando un poco algo de algoritmos de ordenacion. La tercera es un poco mas intermedia y la cuarta requiere un poco mas de pensar (asi que la he puesto como avanzada).

testeando en el cuarto de baño

(y pondria lo de «testeando» entre comillas porque no se como traducir «bonitamente» el anglicismo, pero es que entonces suena sospechoso)

Ya comente que una de las cosas que queria poner en programancia101, aparte de problemas, son recomendaciones de «buenas practicas». En este caso, no es que vaya a decir que testear es una buena idea, eso lo sabeis todos (verdad?)… solo queria compartir este programa que usamos en Google para dar a conocer buenas practicas para la fase de pruebas entre los desarrolladores. La idea basica es: coloca la informacion donde TODOS puedan leerla }:)

Asi surgio la idea de «Testing On The Toilet» (lo que viene a traducirse en español como el titulo de este articulo). Si colocamos semanalmente una hoja con problemas sobre testing en uno de los lugares mas visitados de la oficina, la gente acaba por leerla. Desde hace unos dias, estos bonitos ejemplos de cultura Googley estan disponibles para descarga desde el Google Testing Blog (solo en ingles, eso si)

Asi que ya sabes: bajatelo, imprime y… difunde el conocimiento alla donde sea necesario! }:)