Unos colegas que estudian telecos vinieron a pedirme consejo sobre un ejercicio que les propusieron en clase. El caso, es que me moló tanto que me he viciado y estoy tratando de optimizar cada vez más el resultado.
Antes de nada, os expongo el problema.
Simulando al juego de hundir la flota, sobre un tablero de 14x14 se presentan 10 barcos.
Hay un barco de 4, dos barcos de 3, tres barcos de 2 y cuatro barcos de 1.
Los barcos de 2 pueden aparecer tanto en horizontal, como en vertical.
Los barcos de 3 pueden aparecer tanto rectos, en horizontal y vertical; o en forma de "L", con sus cuatro orientaciones posibles.
El barco de 4 puede adoptar cualquier forma de las que puede adoptar una ficha de tetris, con todas sus orientaciones de rotación. Es decir: Rectas, L, Z, S, L invertida, T, o Cuadrado. giradas 90º de cualquier manera.
Ahora el reto, es almacenar la posición de todos los barcos en una cadena inferior a 128 bits.
(Obviamos la parte del ejercicio que es crear el código que codifica y decodifica esta cadena de bits, que también mola, pero no me parece tanto reto.)
Dado que el tablero es de 14x14, existen 196 casillas, si usáramos un bit para cada casilla (1 si hay barco, 0 si es agua) gastaríamos 196 bits, suspendidos 
Para reducir bits, una manera es utilizar 4 bits para marcar el eje Y y 4 para el eje X.
Por ejemplo A, sería 0000, B 0001, C 0010, etc... y lo mismo para los números (1=0000,2=0001...) así que C4 sería 0010 0011.
Los barcos ocupan 20 casillas en total, si usáramos el método de X e Y gastaríamos 8x20=160bits en total, suspendidos 
Así que el reto está ahí, cuando menor sean los bits empleados, mayor será la nota.
Yo he conseguido dejarlo de momento en 94 bits. Si alguien se interesa contaré mi método, pero no quiero "contaminaros" para ver si podéis encontrar algún método mejor vosotros.
Tengo una teoría que podría bajarlo a 83 bits, pero mis capacidades matemáticas no dan más de sí y necesitaré consejo experto... pero para no liar más la cosa de momento, dejo así el enunciado.
¡Animaros! Yo llevo un par de días muy divertidos con el asunto xD
