Recompensas
Nº 1 ( concedido )
Vou jogar 50 rep para a primeira resposta válida
No. 2 ( concedido )
Vou colocar mais 100 representantes para a resposta mais curta válida.
Nº 3 ( aberto para inscrições )
Vou colocar 200 repetições para o primeiro com uma resposta válida mais curta e significativa. Significativo sendo no máximo 45% da resposta mais curta atualmente ( 564 bytes x 0,45 = máximo 254 bytes ).
O jogo
Você se lembra do clássico jogo " Nine Men's Morris " ou simplesmente " Mill "? Há uma variação chamada Morris de Três Homens que é um pouco como um tic-tac-toe mutável.
Regras
Este é o quadro em branco do jogo:
a b c
1 [ ]–[ ]–[ ]
| \ | / |
2 [ ]–[ ]–[ ]
| / | \ |
3 [ ]–[ ]–[ ]
[ ]
é um campo e |–/\
representa rotas entre esses campos.
O jogo é jogado por dois jogadores 1
e 2
cada um coloca 3 fichas no tabuleiro. Isso já aconteceu e estamos no jogo. O jogo é ganho se um jogador puder formar ummill
linha vertical ou horizontal dos três tokens do jogador.
Os tokens podem ser movidos no tabuleiro ao longo das linhas de conexão, de acordo com esta regra:
Para qualquer posição vazia adjacente (ou seja, de uma posição de borda para o centro, ou do centro para uma posição de borda, ou de uma posição de borda para uma posição de borda adjacente
Um jogador deve fazer uma jogada, a menos que não haja uma posição vazia adjacente; nesse caso, a jogada é pulada.
O desafio
Você é jogador 1
e sua jogada é a próxima. Escreva um programa ou uma função que determine se:
- você pode forçar uma vitória com 2 ou menos jogadas ( vitória definitiva )
- você pode ganhar com 2 ou menos jogadas, se o seu oponente cometer um erro ( vitória possível )
- você não pode vencer com 2 ou menos jogadas, porque precisará de mais jogadas ou porque jogadas forçadas levam seu oponente a vencer ( impossível vencer )
Exigências
- Mesmo que você definitivamente ganhe quando matou seu oponente até a morte, seu programa deve terminar em um tempo finito.
- Você pode escrever um programa ou uma função.
Entrada
Os jogadores são representados por 1
e 2
.0
define um campo livre. Você pode receber entrada como uma matriz ou uma matriz.
Definido
A B C D
2 1 0 | 2 1 0 | 1 0 1 | 1 2 2
2 1 2 | 0 1 0 | 1 0 2 | 2 1 O
0 0 1 | 2 2 1 | 0 2 2 | O O 1
A: [2,1,0,2,1,2,0,0,1]
B: [2,1,0,0,1,0,2,2,1]
C: [1,0,1,1,0,2,0,2,2]
D: [1,2,2,2,1,0,0,0,1]
Possível
A B C
1 0 1 | 1 0 1 | 1 2 2
1 2 2 | 1 2 0 | 0 0 1
2 0 0 | 2 0 2 | 2 1 0
A: [1,0,1,1,2,2,2,0,0]
B: [1,0,1,1,2,0,2,0,2]
C: [1,2,2,0,0,1,2,1,0]
Impossível
A B
1 0 0 | 1 2 0
1 2 2 | 2 1 0
2 0 1 | 1 2 0
A: [1,0,0,1,2,2,2,0,1]
B: [1,2,0,2,1,0,1,2,0]
Resultado
Seu programa deve gerar / retornar um smiley:
- Vitória definitiva:
:)
- Possível vitória:
:|
- Impossível ganhar:
:(
Exemplos
Vitória definitiva em dois movimentos:
[2][1][ ] 1. [2][1][ ]
[2][1][2] -> [2][1][2]
[ ][ ][1] [ ][1][ ]
[2][1][ ] 1. [2][1][ ] [ ][1][ ] 2. [ ][ ][1]
[ ][1][ ] -> [ ][ ][1] -> [2][ ][1] -> [2][ ][1]
[2][2][1] [2][2][1] [2][2][1] [2][2][1]
[1][ ][1] 1. [ ][1][1] [ ][1][1] 2. [1][1][1]
[1][ ][2] -> [1][ ][2] -> [1][ ][2] -> [ ][ ][2]
[ ][2][2] [ ][2][2] [2][ ][2] [2][ ][2]
Possível vitória em duas jogadas:
[1][ ][1] 1. [ ][1][1] [ ][1][1] 2. [1][1][1]
[1][2][ ] -> [1][2][ ] -> [1][2][2] -> [ ][2][2]
[2][ ][2] [2][ ][2] [2][ ][ ] [2][ ][ ]
[1][ ][1] 1. [ ][1][1] [ ][1][1] 2. [1][1][1]
[1][2][ ] -> [1][2][ ] -> [1][2][2] -> [ ][2][2]
[2][ ][2] [2][ ][2] [2][ ][ ] [2][ ][ ]
[1][2][2] 1. [ ][2][2] [2][ ][2] 2. [1][2][2]
[ ][ ][1] -> [1][ ][1] -> [1][ ][1] -> [1][1][1]
[2][1][ ] [2][1][ ] [2][1][ ] [2][ ][ ]
Impossível vencer em duas jogadas:
[1][ ][ ]
[1][2][2]
[2][ ][1]
Bônus
Caso seja possível uma vitória definitiva e o seu programa produza os movimentos de uma maneira para o sucesso, como a1:a2
(1 movimento) ou a1:a2,a3:b2
(2 movimentos), você pode retirar 30% da sua contagem de bytes.
Este é o código de golfe - a resposta mais curta em bytes vence. As brechas padrão não são permitidas.
Agradecemos a Peter Taylor, que corrigiu algumas falhas e melhorou a redação na Sandbox .
fonte
[1,0,0,2,1,0,2,2,1]
, no , o jogador 2 não pode se mover - isso é uma vitória para o jogador 1?Respostas:
Haskell,
580564441 bytesÉ assim que eu posso jogar golfe por enquanto. Não tenho certeza se os outros idiomas podem vencê-lo.
Ligue
m
para uma lista de listas como[[2,1,0],[2,1,2],[0,0,1]]
(Definido A).Código do teste:
mapM_ m al
retorna:fonte
C # -
739663 bytesPrograma completo, lê a entrada do argv e parece funcionar. Execute como
Se esse método de entrada for inaceitável, ficarei feliz em alterá-lo (nunca como usar o argv).
Eu não estava disposto a postar isso ontem, porque não consegui jogar muito (não tive muito tempo e posso estar fora de prática), mas como ainda não houve resposta, eu ' vou postá-lo de qualquer maneira, eu certamente não espero a recompensa, prefiro que alguém tenha se esforçado um pouco mais antes de postar!
Edit: substituiu todos os bools por ints, o que significava que eu poderia usar melhor o Linq e consegui recolher os dois loops de foreach, dando grandes economias. Estou um pouco surpreso que o
h
contador funcione ... ++ é um utilitário tão sutil.O programa é muito simples, apenas explora todos os conjuntos de movimentos possíveis (armazena o estado do quadro em uma string []). Ele repete todos os nossos movimentos possíveis (os painéis que resultam disso) e conta o número de respostas de nosso oponente que podemos vencer com êxito (
G
) (ou seja, aquelas que vencemos e ele não). Também conta o número de respostas possíveis (h
) Se podemos ganhar alguma, é possível e adicionamos 1 à soma; se podemos vencer todas, é definitivo e adicionamos 2 à soma. O máximo de alguns é, portanto, o nosso melhor resultado possível, e indexamos na string "(|))" para retornar a face apropriada. Observe que precisamos do extra ")" porque a soma pode ser 2 ou 3, se for definitiva (é possível que não pareçamos ser capazes de vencer nenhuma resposta que já tenha vencido na primeira tentativa, portanto, a verificação possível é um pouco enganador).O programa procura uma vitória produzindo uma sequência do tabuleiro, que é linhas e colunas separadas por espaço, e apenas procura uma sequência de 3 caracteres do jogador nessa sequência (por exemplo, "201 201 021 220 002 111" é um ganhar para nós)
Aqui está o meu script de teste:
Quais saídas
fonte
PowerShell
576550 bytesNão serei tão facilmente intimidado - se não conseguir C # abaixo de 631 bytes, terei que usar um idioma diferente! Espero que Leif Willerts retire 5 bytes de sua resposta, porque decidi que não gosto muito do PowerShell, talvez apenas precise examiná-lo objetivamente em termos de contagem de bytes ...
Este é um script, você o executa
. .\mill.ps1 "201102021"
. É muito bem uma cópia da minha resposta em C #, apenas em um idioma com o qual tenho pouca experiência. Não fiz muito esforço para jogar golfe, porque demorou tanto tempo para começar a trabalhar em primeira instância e já é razoavelmente compacto.Editar: não era possível simplesmente deixar essas
[Math]::Floor
chamadas láSe você faz uma descrição de como funciona ... a resposta em C # é para você, mas espero que os comentários deixem claro o suficiente. Os pontos e vírgulas podem não corresponder perfeitamente ao comando de linha única, ainda não tenho certeza de onde eles são necessários e não são, e não os copiei novamente quando coloquei tudo em uma linha.
Script de teste (PowerShell):
Saída do mesmo:
fonte
Python 3,
566557 bytesVou ter que ver se consigo jogar mais, ou se consigo o bônus de 30%, mas depois de muita procrastinação, aqui está a minha resposta.
Ungolfed:
fonte