Dado o tamanho do tabuleiro de xadrez e a posição inicial do cavaleiro, calcule a probabilidade de que após os k
movimentos o cavaleiro esteja dentro do tabuleiro de xadrez.
Nota:
O cavaleiro faz todos os seus 8 movimentos possíveis com igual probabilidade.
Uma vez que o cavaleiro está fora do tabuleiro de xadrez, ele não pode voltar para dentro.
Entrada
As entradas são separadas por vírgula no formato:
l,k,x,y
onde l
é o comprimento e a largura do tabuleiro de xadrez, k
é o número de movimentos que o cavaleiro fará, x
é a posição x da posição inicial do cavaleiro e y
é a posição y da posição inicial do cavaleiro. Observe que 0,0
é o canto inferior esquerdo do quadro e l-1,l-1
o canto superior direito do quadro.
Algoritmo:
Comece com as coordenadas iniciais do cavaleiro. Faça todos os movimentos possíveis para esta posição e multiplique esses movimentos com sua probabilidade, pois cada movimento chama recursivamente a função continue esse processo até que a condição final seja atendida. A condição de término é se o cavaleiro estiver fora do tabuleiro de xadrez, neste caso, retornar 0 ou se o número desejado de movimentos for esgotado, nesse caso, retornar 1.
Como podemos ver, o estado atual da recursão depende apenas das coordenadas atuais e do número de etapas realizadas até o momento. Portanto, podemos memorizar essas informações de forma tabular.
Crédito
Esse desafio é originalmente de um post do crazyforcode.com publicado sob a licença CC BY-NC-ND 2.5 IN . Foi ligeiramente modificado para torná-lo um pouco mais desafiador.
Respostas:
Pitão, 38 bytes
Experimente online: Demonstração
Explicação:
fonte
Ruby 134
Experimente online: http://ideone.com/ZIjOmP
O código não-golfe equivalente:
fonte
Haskell - 235
Implementa uma função
f
com parâmetrosl k x y
fonte
Matlab,
124119Implementa exatamente o algoritmo descrito.
Consegui encurtá-lo em 5 bytes com a ajuda de @sanchises, obrigado!
Expandido:
Versão antiga
fonte
s
é inicializado pelo MATLAB, para que você possa fazers(l,l)=0
; Pena que o MATLAB não possui fibonnaci como uma função interna, o que seria uma ótima otimização param
.m
por uma decomposição da matriz ...m+m'+fliplr(m+m')
parece haver um aumento de bytecount, assim como todas as minhas outras opções.Mathematica - 137
Uso:
Resultado:
fonte
MATLAB - 106
Melhora a solução @ flawr por ser mais MATLAB-y.
Expandido:
fonte
> <> - 620 (sem contar espaços em branco)
A pilha inicial deve ser
l,k,x,y
Teste
fonte