Qual é a probabilidade de um cavaleiro permanecer no tabuleiro de xadrez?

16

Dado o tamanho do tabuleiro de xadrez e a posição inicial do cavaleiro, calcule a probabilidade de que após os kmovimentos 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.

insira a descrição da imagem aqui

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-1o 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.

Fino
fonte
14
Por que você prescreve um algoritmo exato? Não tenho certeza se existe realmente uma alternativa mais elegante, mas exigir um algoritmo específico pode potencialmente impedir outras abordagens inteligentes. Além disso, acho que você não precisa especificar o sistema de coordenadas com tantos detalhes - isso não afeta a probabilidade.
Martin Ender
2
"As entradas são separadas por vírgula no formato: l, k, x, y" - então a entrada é uma string que precisamos analisar? Não é aceitável escrever uma função com quatro parâmetros?
Cristian Lupascu
3
@Edi Não marque uma resposta como 'aceita' se não houver tempo para outras pessoas experimentarem - marcar algo como aceito, é basicamente dizer 'O desafio acabou' - enquanto a maioria do mundo provavelmente não até teve tempo de olhar!
Sanchises 25/05
3
@Edi Por favor, pare de postar desafios aleatórios que encontrar na web. O plágio é desaprovado por nossa comunidade. Os desafios das competições de programação em andamento não têm nada a ver com isso, pois podem ajudar alguém a vencer essa competição. E são desafios que são discutidos em uma postagem de blog, como este desafio de xadrez ( fonte original ), não serão bem recebidos aqui. Uma razão é que a fonte original pode ter algum tipo de copyright.
Jakube 26/05
2
@Edi Por exemplo, a fonte desse desafio permite copiar e redistribuir, mas somente se você der o crédito apropriado.
Jakube 26/05

Respostas:

10

Pitão, 38 bytes

M?smcgtGd8fq5sm^-Fk2C,TH^UhQ2G1g@Q1>Q2

Experimente online: Demonstração

Explicação:

                                        implicit: Q = evaluated input
M                                       define a function g(G,H): //G=depth, H=current cell
                         UhQ              the list [0,1,...,Q[0]-1]
                        ^   2             Cartesian product, gives all cells
          f                               filter for numbers numbers T, which satisfy:
                    C,TH                    zip(T,H)
              m                             map the two pairs k to:
                -Fk                           their difference
               ^   2                          squared
             s                              sum (distance squared)
           q5                               == 5           
   m                                      map each valid cell d to:
     gtHd                                   g(G-1,d)
    c    8                                  divided by 8
  s                                       return sum
 ?                           G          if G > 0 else
                              1           return 1

                               g@Q1>Q2  call g(Q[1],Q[2:]) and print
Jakube
fonte
Parece-me que, se vamos criar linguagens super-concisas com o único objetivo de jogar golfe, podemos implementar o algoritmo necessário como primitivo.
Mc0e 26/05
3
@ mc0e Não, isso seria uma brecha proibida padrão. Veja aqui .
Jakube 26/05
podemos obter o código não-golfe pls?
YaSh Chaudhary
11
@YaShChaudhary Você quer dizer a versão com 39 bytes ou a versão com 40 bytes. :-P Receio que nunca tenha existido uma versão verdadeiramente não-golfe. Eu escrevi esse código diretamente no Pyth, e os programas do Pyth são sempre curtos.
Jakube 9/11
@Jakube ohk np :)
YaSh Chaudhary
8

Ruby 134

->l,m,x,y{!((r=0...l)===x&&r===y)?0:m<1?1:(0..7).map{|i|a,b=[1,2].rotate i[2]
P[l,m-1,x+a*(i[0]*2-1),y+b*(i[1]*2-1)]/8.0}.inject(:+)}

Experimente online: http://ideone.com/ZIjOmP

O código não-golfe equivalente:

def probability_to_stay_on_board(board_size, move_count, x, y)
  range = 0...board_size
  return 0 unless range===x && range===y
  return 1 if move_count < 1

  possible_new_locations = (0..7).map do |i|
    dx, dy = [1,2].rotate i[2]
    dx *= i[0]*2-1
    dy *= i[1]*2-1

    [x+dx, y+dy]
  end

  possible_new_locations.map do |new_x, new_y| 
    probability_to_stay_on_board(board_size, move_count-1, new_x, new_y) / 8.0 
  end.inject :+
end
Cristian Lupascu
fonte
5

Haskell - 235

Implementa uma função fcom parâmetrosl k x y

import Data.List
g[]=[]
g((a,b):r)=[(a+c,b+d)|(c,d)<-zip[-2,-1,1,2,-2,-1,1,2][1,2,-2,-1,-1,-2,2,1]]++g r
h _ 0 a=a
h l a b=h l(a-1)$filter(\(a,b)->(elem a[0..l])&&(elem b[0..l]))$g b
f l k x y=(sum$map(\x->1.0) (h l k [(x,y)]))/(8**k)
jhwcb
fonte
5

Matlab, 124 119

Implementa exatamente o algoritmo descrito.

Consegui encurtá-lo em 5 bytes com a ajuda de @sanchises, obrigado!

function s=c(l,k,x,y);m=zeros(5);m([2,4,10,20])=1/8;s(l,l)=0;s(l-y,x+1)=1;for i=1:k;s=conv2(s,m+m','s');end;s=sum(s(:))

Expandido:

function s=c(l,k,x,y);
    m=zeros(5);
    m([2,4,10,20])=1/8;
    s(l,l)=0;s(l-y,x+1)=1;
    for i=1:k;
        s=conv2(s,m+m','s');
    end;
    s=sum(s(:))

Versão antiga

function s=c(l,k,x,y);
    m =zeros(5);m([1:3,5,8,10:12]*2)=1/8;
    s=zeros(l);
    s(l-y,x+1)=1;
    for i=1:k
        s=conv2(s,m,'s');
    end
    s=sum(s(:));
flawr
fonte
Uma dica: sé inicializado pelo MATLAB, para que você possa fazer s(l,l)=0; Pena que o MATLAB não possui fibonnaci como uma função interna, o que seria uma ótima otimização para m.
Sanchises
Esse é um truque super incrível, obrigado! Ainda estou tryting para encontrar um caminho mais curto de criar mpor uma decomposição da matriz ...
flawr
Sim, eu estava olhando por um tempo também. Talvez alguma indexação lógica inteligente, mas não consigo pensar em nada. m+m'+fliplr(m+m')parece haver um aumento de bytecount, assim como todas as minhas outras opções.
Sanchises 25/05
5

Mathematica - 137

q = # {1, 2} & /@ Tuples[{-1, 1}, 2]
q = Reverse /@ q~Union~q
g[l_, k_, x_, y_] :=

 Which[
  k < 1,
  1,

  !0 <= x < l || ! 0 <= y < l,
  0,

  0<1,
  Mean[g[l, k - 1, x + #[[1]], y + #[[2]]] & /@ q]
]

Uso:

g[5,5,1,2]

Resultado:

9/64
Tally
fonte
2

MATLAB - 106

function s=c(l,k,x,y);m(5,5)=0;m([2,4,10,20])=1/8;s=ones(l);for i=1:k;s=conv2(s,m+m','s');end;s=s(l-y,x+1)

Melhora a solução @ flawr por ser mais MATLAB-y.

Expandido:

function s=c(l,k,x,y)
    m(5,5)=0;
    m([2,4,10,20])=1/8;
    s=ones(l);
    for i=1:k
        s=conv2(s,m+m','s');
    end
    s=s(l-y,x+1)
Jared
fonte
1

> <> - 620 (sem contar espaços em branco)

A pilha inicial deve ser l,k,x,y

{:a2*0p   v
vp0*3a*}:{<
>{1+&a3*0g}v                   >          >       >          >~~01-01-v             >          >       >          >~~01-01-v             >          >       >          >~~01-01-v             >          >       >          >~~01-01-v
           >&1-:&?!v>:@@:@@:0(?^:a2*0g1-)?^2-$:0(?^:a2*0g1-)?^1-      >}}$:@@:@@:0(?^:a2*0g1-)?^2-$:0(?^:a2*0g1-)?^1+      >}}$:@@:@@:0(?^:a2*0g1-)?^2+$:0(?^:a2*0g1-)?^1-      >}}$:@@:@@:0(?^:a2*0g1-)?^2+$:0(?^:a2*0g1-)?^1+      >}}$:@@:@v
v1         ^}       ^!?=g0*3a:~~}}<      +2v?)-1g0*2a:v?(0:$+1v?)-1g0*2a:v?(0:@@:@@:$}}<      -2v?)-1g0*2a:v?(0:$+1v?)-1g0*2a:v?(0:@@:@@:$}}<      +2v?)-1g0*2a:v?(0:$-1v?)-1g0*2a:v?(0:@@:@@:$}}<-2      v?)-1g0*2a:v?(0:$-1v?)-1g0*2a:v?(0:@<
>a3*0g=   ?^\      &              ^-10-10~~<          <       <          <             ^-10-10~~<          <       <          <             ^-10-10~~<          <       <          <             ^-10-10~~<          <       <          <
\         :{/      
v                  >~{~l2,&0
>@:0(?v:a2*0g1-)?v$:0(?v:a2*0g1-)?v1>@~~+l1=?v
      >          >     >          >0^        >&,n;

Teste

JNF
fonte