Construye un solucionador de celdas libres de pocos movimientos

54

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 1través 8), o una celda libre ( Aa D), que representa la pila fuente.
  • Otro número o letra que representa la pila de destino o la celda libre, o Fpara 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

Joe Z.
fuente
1
Ahora solo necesito atrapar el generador de números aleatorios que usaron para generar esos 32,768 juegos. : S
Joe Z.
3
El generador está aquí: rosettacode.org/wiki/Deal_cards_for_FreeCell
nutki
1
Ese es un buen punto. ¿Cómo abordaría el caso en el que, por ejemplo, dos tarjetas del mismo color y número (como 7C y 7S) están en celdas libres? Entonces, si te mueves de "C" a un 8 negro, podría ser cualquiera de esas dos cartas.
Joe Z.
2
Posiblemente podría obtener algunas respuestas eliminando la restricción de que todas las ofertas solucionables deben resolverse mediante el envío. Luego, puntúa en función del número de acuerdos resueltos, luego por la menor cantidad de movimientos.
mbomb007
1
¿Se pueden indexar las tarjetas?
tuskiomi

Respuestas:

22

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:

Descargue la fuente original aquí . Use GCC y corra makeluego 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.

Christopher
fuente
Es posible que pueda usar esto para evitar la restricción de longitud de respuesta y tener todo su código dentro de la respuesta, en lugar de necesitar una descarga externa.
Mego
@Mego quiero decir sí, pero está en varios archivos
Christopher
Es fácil combinar múltiples archivos C en uno solo.
Mego
Aquí hay un fragmento de pila que muestra el código combinado en un solo archivo.
Mego
@mego, ¿puedes editar eso? En el móvil
Christopher el