Dans le jeu Freecell, vous êtes chargé de construire quatre piles de fondation en costume allant d’as au roi, sur un tracé où vous construisez en alternant les couleurs. Toutefois, vous ne pouvez créer qu'une carte à la fois. Vous disposez ainsi de quatre "cellules libres" pouvant chacune contenir une carte pour vous aider à déplacer des séquences entières. L'idée est de tisser des cartes individuelles dans les cellules libres au besoin pour vous aider à résoudre le jeu.
Votre tâche consiste à créer un programme capable de résoudre ces jeux en un minimum de mouvements.
Votre programme prendra en entrée une séquence de 52 cartes, au format suivant:
2S 9H 10C 6H 4H 7S 2D QD KD QC 10S AC ...
Ce qui sera traité dans la mise en page initiale dans cet ordre:
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
Et retourne une liste de mouvements pour résoudre le jeu. Chaque mouvement sera dans ce format:
- Un nombre représentant le numéro de pile (à
1travers8) ou une cellule libre (AàD) représentant la pile source. - Un autre numéro ou une lettre représentant la pile ou la cellule libre de destination ou
Fla fondation de cette couleur.
La sortie ressemblera à ceci:
18 28 3A 8B 8C 85 B5 35 4F etc.
Une fois qu'une carte est mise dans la base, elle ne peut pas être retirée. Puisqu'une seule carte est déplacée à la fois, déplacer une séquence de 3 cartes nécessite 5 mouvements et une séquence de 5 cartes nécessite 9 mouvements.
Si un jeu est insoluble, votre programme devrait l'indiquer comme tel. Cependant, votre programme doit être capable de résoudre n'importe quel jeu résoluble.
Votre programme sera jugé sur les 32 768 offres trouvées dans le programme Microsoft FreeCell d'origine. Pour être valide, votre programme doit résoudre avec succès toutes les transactions, à l'exception de la transaction n ° 11 982 , qui est insoluble. Votre score correspondra au nombre total de déplacements nécessaires pour résoudre ces 32 767 offres, le code plus court constituant une égalité.
Un fichier contenant tous les decks dans le format requis par la spécification ci-dessus est disponible au téléchargement ici (fichier de 5,00 MB): https://github.com/joezeng/pcg-se-files/raw/master/freecell_decks
la source
Réponses:
C 64 643 octets, résultat: ~ 6,5 millions
L'extrait de pile suivant (avec la permission de Mego) affiche tout le code sous la forme d'un fichier C autonome:
Afficher l'extrait de code
Téléchargez la source originale ici . Utilisez GCC et exécutez
makeensuite en suivant les instructions du fichier Lisez-moi.Ma mise en forme est mauvaise (tous les différents fichiers sont dans un bloc de code) et cela pourrait être plus joué au golf (12k octets). Toute aide serait aimée!
Une partie du code ne m'appartient pas. Je l'ai utilisé à partir d'une source sans copyright. J'ai toutefois corrigé la méthode d'entrée / sortie pour qu'elle soit à la hauteur du défi (une tâche longue puisque je suis horrible à 5 heures). J'ai également dû réécrire une grande partie du code et tout déboguer. Un grand merci à mon père pour son aide et son statut de canard en caoutchouc (et pour avoir signalé mes erreurs de gestion de la mémoire), ainsi qu’à toutes les personnes de TNB qui ont géré mes incendies de colère à propos de sefafaults et de C.
la source