No jogo Freecell, você tem a tarefa de construir quatro estacas de fundação do naipe ao ás, em um layout em que você constrói para baixo em cores alternadas. No entanto, você pode criar apenas um cartão de cada vez; portanto, você recebe quatro "células livres", cada uma das quais pode conter um cartão para ajudá-lo a mover seqüências inteiras. A idéia é que você troque cartas individuais dentro e fora das células livres, conforme necessário, para ajudá-lo a resolver o jogo.
Sua tarefa é criar um programa que resolva esses jogos com o menor número de movimentos possível.
Seu programa terá como entrada uma sequência de 52 cartões, no seguinte formato:
2S 9H 10C 6H 4H 7S 2D QD KD QC 10S AC ...
O qual será tratado no layout inicial nesta ordem:
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
E devolva uma lista de movimentos para resolver o jogo. Cada movimento estará neste formato:
- Um número que representa o número da pilha (
1
através8
) ou uma célula livre (A
paraD
), representando a pilha de origem. - Outro número ou letra representando a pilha de destino ou célula livre, ou
F
para a fundação desse processo.
A saída será mais ou menos assim:
18 28 3A 8B 8C 85 B5 35 4F etc.
Depois que um cartão é colocado na base, ele não pode ser removido. Como apenas uma carta é movida por vez, mover uma sequência de 3 cartas requer 5 movimentos e uma sequência de 5 cartas requer 9 movimentos.
Se um jogo for insolúvel, seu programa deve indicar como tal. No entanto, seu programa deve ser capaz de resolver qualquer jogo solucionável.
Seu programa será julgado pelas 32.768 ofertas encontradas no programa original do Microsoft FreeCell. Para ser válido, seu programa deve resolver com êxito todas as transações , exceto a transação nº 11.982 , que é insolúvel. Sua pontuação será o número total de movimentos necessários para resolver essas 32.767 transações, com códigos mais curtos sendo um empate.
Um arquivo com todos os decks no formato exigido pela especificação acima está disponível para download aqui (arquivo de 5,00 MB): https://github.com/joezeng/pcg-se-files/raw/master/freecell_decks
fonte
Respostas:
C 64.643 bytes, Pontuação: ~ 6,5 milhões
O seguinte Snippet de pilha (cortesia de Mego) gera todo o código como um único arquivo C independente:
Mostrar snippet de código
Faça o download da fonte original aqui . Use o GCC e execute, em
make
seguida, usando a diretriz no leia-me.Minha formatação está incorreta (todos os arquivos diferentes estão em um bloco de código) e isso pode ter mais golfe (12k bytes). Qualquer ajuda seria amada!
Parte do código não é meu. Eu usei de uma fonte sem direitos autorais. No entanto, eu fixei o método de entrada / saída para estar dentro do desafio (uma tarefa longa, pois sou horrível em C (5 horas)). Eu também tive que reescrever grande parte do código e depurar tudo. Muito obrigado ao meu pai por ajudar e ser um pato de borracha (e apontar meus erros de gerenciamento de memória) e por todos na TNB que lidaram com os meus comentários furiosos sobre segfaults e C.
fonte