Llenando el tetris

propuesto por josejuan

Realmente no se si resultará fácil o difícil. Consiste en, dando un precio (un coste) a cada tipo de ficha del tetris, obtener la forma más barata de llenar todo el tablero.

Enunciado
(Realmente no se si resultará fácil o difícil; he puesto dificultad normal)

Consiste en, dando un precio (un coste) a cada tipo de ficha del tetris, obtener la forma más barata de llenar todo el tablero.

Lo más importante es cubrir el tablero lo más posible (dejando los menos huecos posibles) y después lo más importante es con el menor coste total posible.

Lógicamente las piezas no pueden solaparse, no pueden sobresalir del tablero, no pueden ponerse "en vertical", diagonal, ...

En principio, debe suministrarse una implementación que pueda ejecutarse "tal cual", para que todos podamos ejecutar con el menor esfuerzo posible y comparar las diferentes implementaciones.

http://en.wikipedia.org/wiki/Tetris

Aclaraciones adicionales

No es requisito implementar siquiera todas las piezas del tetris, pero idealmente, lo deseable es que se puedan configurar las piezas que intervienen y sus precios.

Del mismo modo, no es requisito que puedan modificarse las dimensiones pero, si no hay una razón para ello (ej. optimización), lo ideal es que la implementación permita indicar las dimensiones a rellenar.

El desafío no tiene "nada" que ver con el tetris, no hay piezas aleatorias ni tienen que caer ni nada parecido; se trata únicamente, de llenar un tablero (plano) con las fichas del tetris de forma que no queden huecos (o los menos posibles).

Por ejemplo, una solución para un tablero de 4x4 y en el que todas las piezas tienen el mismo coste es, trivialmente, la solución

  |X|X|X|X|
  |X|X|X|X|
  |X|X|X|X|
  |X|X|X|X|
  +-------+


En un Tetris "estándar" con sus 7 piezas, 10 columnas y 20 filas considerando todos los costes iguales da el siguiente recubrimiento:
    L L L L M M M M K K 
    H F E E E N N N N K 
    H F F F E 1 1 1 C K 
    H H 9 9 A A 1 6 C C 
    2 9 9 A A 4 6 6 6 C 
    2 2 0 0 0 4 4 J J O 
    2 D D 0 8 4 B B J O 
    3 D D 8 8 B B I J O 
    3 3 5 8 G I I I 7 O 
    3 5 5 5 G G G 7 7 7 
    L L L L M M M M K K 
    H F E E E N N N N K 
    H F F F E 1 1 1 C K 
    H H 9 9 A A 1 6 C C 
    2 9 9 A A 4 6 6 6 C 
    2 2 0 0 0 4 4 J J O 
    2 D D 0 8 4 B B J O 
    3 D D 8 8 B B I J O 
    3 3 5 8 G I I I 7 O 
    3 5 5 5 G G G 7 7 7 


Otra solución con otra representación

········································
·▒▒▒▒▒▒▒▒▒▒··▒▒▒▒▒▒▒▒▒▒··▒▒▒▒▒▒··▒▒▒▒▒▒·
·▒▒··········▒▒··········▒▒······▒▒·····
·▒▒··········▒▒··········▒▒······▒▒·····
·▒▒··▒▒▒▒▒▒··▒▒··▒▒··▒▒▒▒▒▒··▒▒··▒▒··▒▒·
·····▒▒··········▒▒··········▒▒··▒▒··▒▒·
·····▒▒··········▒▒··········▒▒··▒▒··▒▒·
·▒▒▒▒▒▒··▒▒▒▒▒▒▒▒▒▒··▒▒▒▒▒▒▒▒▒▒··▒▒··▒▒·
·····································▒▒·
·····································▒▒·
·▒▒▒▒▒▒··▒▒▒▒▒▒▒▒▒▒··▒▒▒▒▒▒▒▒▒▒··▒▒▒▒▒▒·
·▒▒··········▒▒··········▒▒·············
·▒▒··········▒▒··········▒▒·············
·▒▒··▒▒▒▒▒▒··▒▒··▒▒··▒▒··▒▒··▒▒▒▒▒▒▒▒▒▒·
·▒▒······▒▒······▒▒··▒▒··············▒▒·
·▒▒······▒▒······▒▒··▒▒··············▒▒·
·▒▒··▒▒··▒▒▒▒▒▒··▒▒··▒▒▒▒▒▒▒▒▒▒··▒▒··▒▒·
·····▒▒··········▒▒··············▒▒·····
·····▒▒··········▒▒··············▒▒·····
·▒▒▒▒▒▒··▒▒··▒▒▒▒▒▒··▒▒▒▒▒▒▒▒▒▒··▒▒▒▒▒▒·
·▒▒······▒▒··········▒▒··············▒▒·
·▒▒······▒▒··········▒▒··············▒▒·
·▒▒··▒▒··▒▒▒▒▒▒▒▒▒▒··▒▒··▒▒··▒▒··▒▒··▒▒·
·····▒▒··················▒▒··▒▒··▒▒·····
·····▒▒··················▒▒··▒▒··▒▒·····
·▒▒▒▒▒▒··▒▒··▒▒▒▒▒▒▒▒▒▒··▒▒··▒▒··▒▒▒▒▒▒·
·▒▒······▒▒······▒▒······▒▒··▒▒······▒▒·
·▒▒······▒▒······▒▒······▒▒··▒▒······▒▒·
·▒▒··▒▒▒▒▒▒▒▒▒▒··▒▒··▒▒▒▒▒▒··▒▒▒▒▒▒··▒▒·
········································
········································
·▒▒▒▒▒▒▒▒▒▒··▒▒▒▒▒▒▒▒▒▒··▒▒▒▒▒▒··▒▒▒▒▒▒·
·▒▒··········▒▒··········▒▒······▒▒·····
·▒▒··········▒▒··········▒▒······▒▒·····
·▒▒··▒▒▒▒▒▒··▒▒··▒▒··▒▒▒▒▒▒··▒▒··▒▒··▒▒·
·····▒▒··········▒▒··········▒▒··▒▒··▒▒·
·····▒▒··········▒▒··········▒▒··▒▒··▒▒·
·▒▒▒▒▒▒··▒▒▒▒▒▒▒▒▒▒··▒▒▒▒▒▒▒▒▒▒··▒▒··▒▒·
·····································▒▒·
·····································▒▒·
·▒▒▒▒▒▒··▒▒▒▒▒▒▒▒▒▒··▒▒▒▒▒▒▒▒▒▒··▒▒▒▒▒▒·
·▒▒··········▒▒··········▒▒·············
·▒▒··········▒▒··········▒▒·············
·▒▒··▒▒▒▒▒▒··▒▒··▒▒··▒▒··▒▒··▒▒▒▒▒▒▒▒▒▒·
·▒▒······▒▒······▒▒··▒▒··············▒▒·
·▒▒······▒▒······▒▒··▒▒··············▒▒·
·▒▒··▒▒··▒▒▒▒▒▒··▒▒··▒▒▒▒▒▒▒▒▒▒··▒▒··▒▒·
·····▒▒··········▒▒··············▒▒·····
·····▒▒··········▒▒··············▒▒·····
·▒▒▒▒▒▒··▒▒··▒▒▒▒▒▒··▒▒▒▒▒▒▒▒▒▒··▒▒▒▒▒▒·
·▒▒······▒▒··········▒▒··············▒▒·
·▒▒······▒▒··········▒▒··············▒▒·
·▒▒··▒▒··▒▒▒▒▒▒▒▒▒▒··▒▒··▒▒··▒▒··▒▒··▒▒·
·····▒▒··················▒▒··▒▒··▒▒·····
·····▒▒··················▒▒··▒▒··▒▒·····
·▒▒▒▒▒▒··▒▒··▒▒▒▒▒▒▒▒▒▒··▒▒··▒▒··▒▒▒▒▒▒·
·▒▒······▒▒······▒▒······▒▒··▒▒······▒▒·
·▒▒······▒▒······▒▒······▒▒··▒▒······▒▒·
·▒▒··▒▒▒▒▒▒▒▒▒▒··▒▒··▒▒▒▒▒▒··▒▒▒▒▒▒··▒▒·
········································

Ver todo el enunciado

Preguntas sobre el desafío
  • Hola. Una duda.....cada pieza tiene siempre el mismo valor o va variando ese valor a lo largo de la partida. El tablero tendra una "profundidad" digo yo. Y dicho esto....en el tetris no controlamos que pieza va a salir a continuacion. No se si lo he entendido mal. Gracias

    Hola @ricky, el coste de cada pieza es constante, pero cada pieza puede tener un coste diferente. Lo normal sería que permitieras configurar (hardcoded o no) las piezas que hay y su coste. En cuanto a la profundidad pasa lo mismo, idealmente (hardcoded o no) lo suyo es que se pueda configurar las dimensiones. Modificaré el enunciado para dejarlo más claro. ¡Gracias!

Plantea tu pregunta

1 Solución

Dar mi solución