En el juego de Freecell, tienes la tarea de construir cuatro pilas de cimientos en traje de as a rey, en un diseño donde construyes hacia abajo en colores alternos. Sin embargo, solo puede construir una carta a la vez, por lo que se le dan cuatro "celdas libres", cada una de las cuales puede contener una carta para ayudarlo a mover secuencias enteras. La idea es tejer tarjetas individuales dentro y fuera de las celdas libres según sea necesario para ayudarlo a resolver el juego.
Su tarea es crear un programa que resuelva estos juegos en la menor cantidad de movimientos posibles.
Su programa tomará como entrada una secuencia de 52 tarjetas, en el siguiente formato:
2S 9H 10C 6H 4H 7S 2D QD KD QC 10S AC ...
Que se tratará en el diseño inicial en este orden:
01 02 03 04 05 06 07 08
09 10 11 12 13 14 15 16
17 18 19 20 21 22 23 24
25 26 27 28 29 30 31 32
33 34 35 36 37 38 39 40
41 42 43 44 45 46 47 48
49 50 51 52
Y devuelve una lista de movimientos para resolver el juego. Cada movimiento tendrá este formato:
- Un número que representa el número de pila (a
1
través8
), o una celda libre (A
aD
), que representa la pila fuente. - Otro número o letra que representa la pila de destino o la celda libre, o
F
para la base de ese palo.
La salida se verá así:
18 28 3A 8B 8C 85 B5 35 4F etc.
Una vez que una tarjeta se coloca en la base, no se puede quitar. Como solo se mueve una carta a la vez, mover una secuencia de 3 cartas requiere 5 movimientos, y una secuencia de 5 cartas requiere 9 movimientos.
Si un juego no tiene solución, su programa debería indicarlo como tal. Sin embargo, su programa debe ser capaz de resolver cualquier juego solucionable.
Su programa será juzgado por las 32,768 ofertas encontradas en el programa original de Microsoft FreeCell. Para ser válido, su programa debe resolver con éxito cada acuerdo, excepto el acuerdo # 11,982 , que no se puede resolver . Su puntaje será el número total de movimientos necesarios para resolver estas 32,767 ofertas, con un código más corto que es un factor decisivo.
Puede descargar un archivo con todas las cubiertas en el formato requerido por la especificación anterior aquí (archivo de 5.00 MB): https://github.com/joezeng/pcg-se-files/raw/master/freecell_decks
fuente
Respuestas:
C 64,643 bytes, puntaje: ~ 6.5 millones
El siguiente fragmento de pila (cortesía de Mego) genera todo el código como un único archivo C independiente:
Mostrar fragmento de código
Descargue la fuente original aquí . Use GCC y corra
make
luego usando la guía en el archivo Léame.Mi formato es malo (todos los archivos diferentes están en un bloque de código) y esto podría ser más golfizado (12k bytes aunque). Cualquier ayuda sería amada!
Parte del código no es mío. Lo usé de una fuente sin derechos de autor. Sin embargo, arreglé el método de entrada / salida para estar dentro del desafío (una tarea larga ya que soy horrible en C (5 horas)). También tuve que volver a escribir gran parte del código y depurar todo. Muchas gracias a mi papá por ayudarme y ser un pato de goma (y señalar mis errores de administración de memoria) y por todos en TNB que lidiaron con mis disgustos enojados sobre segfaults y C.
fuente