17
\$\begingroup\$

Given the size of the chess board and initial position of the knight, calculate the probability that after k moves the knight will be inside the chess board.

Note:

  • The knight makes its all 8 possible moves with equal probability.

  • Once the knight is outside the chess board it cannot come back inside.

enter image description here

Input

Inputs are comma separated in the form:

l,k,x,y

where l is the length and width of the chess board, k is the number of moves the knight will make, x is the x-position of the initial position of the knight, and y is the y-position of the initial position of the knight. Note that 0,0 is the bottom-left corner of the board and l-1,l-1 is the top-right corner of the board.

Algorithm:

Start with the initial coordinates of the knight. Make all possible moves for this position and multiply these moves with their probability, for each move recursively call the function continue this process till the terminating condition is met. Terminating condition is if the knight is outside the chess board, in this case return 0, or the desired number of moves is exhausted, in this case return 1.

As we can see that the current state of the recursion is dependent only on the current coordinates and number of steps done so far. Therefore we can memorize this information in a tabular form.

Credit

This challenge is originally from a blog post of crazyforcode.com published under the CC BY-NC-ND 2.5 IN licence. It was slightly modified to make it a bit more challenging.

\$\endgroup\$
15
  • 14
    \$\begingroup\$ Why do you prescribe an exact algorithm? I'm not sure if there actually is a more elegant alternative, but requiring a specific algorithm could potentially prevent other clever approaches. Also, I don't think you need to specify the coordinate system in so much detail - it doesn't affect the probability at all. \$\endgroup\$ May 25, 2015 at 11:00
  • 2
    \$\begingroup\$ "Inputs are comma separated in the form: l,k,x,y" - so the input is a string that we have to parse? Is it not acceptable to write a function that takes 4 parameters? \$\endgroup\$ May 25, 2015 at 12:58
  • 3
    \$\begingroup\$ @Edi Don't mark an answer as 'accepted' if there has been no time for other people to give it a try - marking something as accepted so is basically saying 'The challenge is over' - while most of the world has probably not even had time to look at it! \$\endgroup\$
    – Sanchises
    May 25, 2015 at 14:42
  • 3
    \$\begingroup\$ @Edi Please stop posting random challenges you find on the web. Plagiarism is frowned on by our community. Challenges from ongoing programming competitions have no business here at all, since they may help someone winning this competition. And are challenges, which are discussed in a blog post, like this chess challenge (original source), will not be well-received here. One reason is, that the original source may have some sort of copyright. \$\endgroup\$
    – Jakube
    May 26, 2015 at 8:22
  • 2
    \$\begingroup\$ @Edi For instance the source of this challenge allows copying and redistributing, but only if you give appropriate credit. \$\endgroup\$
    – Jakube
    May 26, 2015 at 8:23

7 Answers 7

10
\$\begingroup\$

Pyth, 38 bytes

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

Try it online: Demonstration

Explanation:

                                        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
\$\endgroup\$
5
  • \$\begingroup\$ Seems to me that if we're going to create super-concise languages for the sole purpose of golfing, we might as well implement the required algorithm as a primitive. \$\endgroup\$
    – mc0e
    May 26, 2015 at 6:50
  • 3
    \$\begingroup\$ @mc0e No, that would be a standard forbidden loophole. See here. \$\endgroup\$
    – Jakube
    May 26, 2015 at 6:56
  • \$\begingroup\$ can we get the non-golfed code pls ? \$\endgroup\$ Nov 9, 2017 at 6:38
  • 1
    \$\begingroup\$ @YaShChaudhary Do you mean the version with 39 bytes, or the version with 40 bytes. :-P I'm afraid there never existed a truly non-golfed version. I wrote this code directly in Pyth, and Pyth programs are always short. \$\endgroup\$
    – Jakube
    Nov 9, 2017 at 11:30
  • \$\begingroup\$ @Jakube ohk np :) \$\endgroup\$ Nov 9, 2017 at 13:04
8
\$\begingroup\$

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

Try it online: http://ideone.com/ZIjOmP

The equivalent non-golfed code:

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
\$\endgroup\$
5
\$\begingroup\$

Haskell - 235

Implements a function f with parameters l 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)
\$\endgroup\$
5
\$\begingroup\$

Matlab, 124 119

Exactly implements the described algorithm.

I was able to shorten it by 5 bytes with some help of @sanchises, thanks!

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

Expanded:

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

Old 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(:));
\$\endgroup\$
3
  • \$\begingroup\$ One hint: s is initialized by MATLAB, so you can just do s(l,l)=0; Too bad MATLAB does not have fibonnaci as a built-in function, that would be a great optimization for m. \$\endgroup\$
    – Sanchises
    May 25, 2015 at 15:33
  • \$\begingroup\$ That is a super awesome trick, thanks! I am still tryting to find a shorter way of creating m by a matrix decomposition... \$\endgroup\$
    – flawr
    May 25, 2015 at 15:44
  • \$\begingroup\$ Yeah, I was looking at it for a while too. Perhaps some smart logical indexing, but I can't think of anything. m+m'+fliplr(m+m') seems to be an increase in bytecount, and so are all my other options. \$\endgroup\$
    – Sanchises
    May 25, 2015 at 20:29
5
\$\begingroup\$

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

Usage:

g[5,5,1,2]

Output:

9/64
\$\endgroup\$
2
\$\begingroup\$

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)

Improves on @flawr's solution by being more MATLAB-y.

Expanded:

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)
\$\endgroup\$
1
\$\begingroup\$

><> - 620 (not counting whitespace)

Initial stack should be 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;

Test it out

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.