En mi opinión, el katapotter es el problema de las torres de Hanoi para las nuevas generaciones.
Si no conocéis el problema, os pego aquí (en inglés) la descripción, sacada de codingdojo.org:
Once upon a time there was a series of 5 books about a very English hero called Harry. (At least when this Kata was invented, there were only 5. Since then they have multiplied) Children all over the world thought he was fantastic, and, of course, so did the publisher. So in a gesture of immense generosity to mankind, (and to increase sales) they set up the following pricing model to take advantage of Harry's magical powers.One copy of any of the five books costs 8 EUR. If, however, you buy two different books from the series, you get a 5% discount on those two books. If you buy 3 different books, you get a 10% discount. With 4 different books, you get a 20% discount. If you go the whole hog, and buy all 5, you get a huge 25% discount. Note that if you buy, say, four books, of which 3 are different titles, you get a 10% discount on the 3 that form part of a set, but the fourth book still costs 8 EUR. Potter mania is sweeping the country and parents of teenagers everywhere are queueing up with shopping baskets overflowing with Potter books. Your mission is to write a piece of code to calculate the price of any conceivable shopping basket, giving as big a discount as possible. For example, how much does this basket of books cost? 2 copies of the first book 2 copies of the second book 2 copies of the third book 1 copy of the fourth book 1 copy of the fifth book (answer: 51.20 EUR) Clues You’ll find that this Kata is easy at the start. You can get going with tests for baskets of 0 books, 1 book, 2 identical books, 2 different books… and it is not too difficult to work in small steps and gradually introduce complexity. However, the twist becomes apparent when you sit down and work out how much you think the sample basket above should cost. It isn’t 5*8*0.75+3*8*0.90. It is in fact 4*8*0.8+4*8*0.8. So the trick with this Kata is not that the acceptance test you’ve been given is wrong. The trick is that you have to write some code that is intelligent enough to notice that two sets of four books is cheaper than a set of five and a set of three. You will have to introduce a certain amount of clever optimization algorithm. But not too much! This problem does not require a fully fledged general purpose optimizer. Try to solve just this problem well in order to share it for everyone or even in the ??? . Trust that you can generalize and improve your solution if and when new requirements come along.
Como podéis ver, es un bonito ejercicio de recursividad.
Recientemente me he dado cabezazos contra el teclado haciendo el problema, y aunque en un primer momento me sentí muy satisfecha de mi misma, ahora odio el código y pienso cambiarlo en cuanto tenga tiempo.
El código está en este enlace (en Github, porque he decidido empezar a usar la cuenta que me creé cuando los dinosaurios dominaban la tierra): https://github.com/freaktiful/KataPotter
Si queréis echarle un ojo, os comento por encima el código, qué partes me parecen mejorables, y qué partes me he dado cuenta de que están MUY MAL:
- Tenemos la clase con el main, que te pide qué libros quieres comprar y te calcula el precio.
- Una clase Cesta, que tiene un Map <Libro, Integer>, donde se meten los libros a comprar y qué cantidad de cada libro. También tiene la llamada a calcular el precio.
- Una clase CombinacionesLibros, que tiene la función con la llamada recursiva y – una cosa que no me gusta nada y que en su momento no sabía cómo solventar pero que mas adelante comento – un vector de CombinacionesLibros. No me gusta que una clase tenga un atributo que sea un vector de elementos de esa clase, pero al menos controlé que el vector no se inicializara en el constructor no fuera a liarla más parda aún de lo que ya la estaba liando.
- Una clase CombinacionLibros, que simplemente te calcula una combinación de n tamaño de libros sin repetir entre m libros.
- Una clase Libro, que ni me voy a molestar en explicar.
Bien. Ahora pasemos a lo bonito del asunto:
- Los descuentos están declarados como BigDecimal. Recientemiente ha llegado a mi conocimiento que es un desperdicio de memoria importante, para decimales de dos cifras, gastar tanta memoria por variable. Con haberlas declarado float habría bastado.
- He declarado una clase “Libro” y le he puesto como constantes los cinco títulos. Probé con un tipo enumerado pero me llevó más tiempo del que había calculado y cuando terminé el tipo vi que me había costado más el collar que el perro – la gracia del problema es la recursividad, no los tipos, creo yo – y lo borré con las mismas. Tengo pendiente volver a crear el tipo enumerado y modificar el código para que lo use.
- La llamada recursiva. En la universidad nos enseñaron, PORQUE LO HE ESTUDIADO ASÍ, que para las llamadas recursivas modificas el “campo intermedio”, haces la llamada, y restauras el campo intermedio. BIEN, pues cuando hice el código esa parte de mi memoria debió caerse, porque lo que hice fue clonar el campo intermedio para hacer la llamada, generando ochocientas mil copias innecesarias de algo en el proceso.
- Primero el bucle calcula todas las combinaciones, y luego calcula el precio de cada una y se queda con la más barata. De nuevo debí tener un derrame cerebral, porque me habría bastado con calcular el precio de cada combinación según se acaba, y si es más barata que la anterior, se guarda en UNA ÚNICA VARIABLE aplastando la anterior más barata. Pero yo soy especial y me creo que el heap es algo así como un agujero negro en el que cabe todo.
Como os he comentado, este código es una primera versión, con bastantes errores, pero bueno, funciona para los tests que le he puesto (parco consuelo). Pretendo actualizar el código, y lo comentaré por aquí cuando lo haga, explicando cómo he cambiado el código. También pretendo – por consejo de un amigo – comenzar a hacer problemitas de estos y compartirlos por el blog, con la esperanza de mejorar como programadora y contaros mi vida en el proceso 😛
………………………………………………
Espero que esta entrada pueda ser interesante, y si no, como siempre, aquí tenéis un gato para compensar:
