Berechnen Sie anhand der Größe des Schachbretts und der Ausgangsposition des Ritters die Wahrscheinlichkeit, dass ksich der Ritter nach Zügen innerhalb des Schachbretts befindet.

Hinweis:

• Der Ritter macht alle 8 möglichen Züge mit gleicher Wahrscheinlichkeit.

• Sobald sich der Ritter außerhalb des Schachbretts befindet, kann er nicht mehr hinein kommen.

Eingang

Eingaben werden in folgender Form durch Kommas getrennt:

l,k,x,y

Wo list die Länge und Breite des Schachbretts, kist die Anzahl der Züge, die der Ritter machen wird, xist die x-Position der Ausgangsposition des Ritters und yist die y-Position der Ausgangsposition des Ritters. Beachten Sie, dass dies 0,0die untere linke Ecke der Tafel und l-1,l-1die obere rechte Ecke der Tafel ist.

Algorithmus:

Beginnen Sie mit den Anfangskoordinaten des Ritters. Machen Sie alle möglichen Züge für diese Position und multiplizieren Sie diese Züge mit ihrer Wahrscheinlichkeit. Rufen Sie die Funktion für jeden Zug rekursiv auf und setzen Sie diesen Vorgang fort, bis die Abbruchbedingung erfüllt ist. Die Abbruchbedingung ist, wenn sich der Springer außerhalb des Schachbretts befindet, in diesem Fall 0 zurückgeben, oder die gewünschte Anzahl von Zügen erschöpft ist, in diesem Fall 1 zurückgeben.

Wie wir sehen können, hängt der aktuelle Status der Rekursion nur von den aktuellen Koordinaten und der Anzahl der bisher ausgeführten Schritte ab. Daher können wir uns diese Informationen in tabellarischer Form merken.

Anerkennung

Diese Challenge stammt ursprünglich aus einem Blog- Eintrag von crazyforcode.com, der unter der CC BY-NC-ND 2.5 IN- Lizenz veröffentlicht wurde. Es wurde leicht modifiziert, um es etwas herausfordernder zu machen.

Pyth, 38 Bytes

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

Probieren Sie es online aus: Demonstration

Erläuterung:

                                        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

Rubin 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(:+)}

Probieren Sie es online aus: http://ideone.com/ZIjOmP

Der äquivalente Code ohne Golf:

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

Haskell - 235

Implementiert eine Funktion fmit Parameternl 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)

Matlab, 124, 119

Implementiert genau den beschriebenen Algorithmus.

Ich konnte es mit Hilfe von @sanchises um 5 Bytes kürzen, danke!

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(:))

Erweitert:

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(:))

Alte Version

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(:));

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]
]

Verwendung:

g[5,5,1,2]

Ausgabe:

9/64

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)

Verbessert die @ flawr-Lösung durch mehr MATLAB-y.

Erweitert:

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)

> <> - 620 (ohne Leerzeichen)

Der Anfangsstapel sollte sein 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;

Probieren Sie es aus