13
\$\begingroup\$

Task

Given two positive integers \$m,n\$, imagine a chessboard of size \$m \times n\$. A chess queen is on the upper-left corner. In how many ways can it reach the lower-right corner, by moving only right, down, or diagonally right-down (possibly moving many steps at once, because it's a queen)?

The resulting 2D sequence is A132439.

Standard rules apply. The shortest code in bytes wins.

Test cases

m n result
1 1      1
1 2      1
1 3      2
1 4      4
1 5      8
2 2      3
2 3      7
2 4     17
2 5     40
3 3     22
3 4     60
3 5    158
4 4    188
4 5    543
5 5   1712
\$\endgroup\$

6 Answers 6

6
\$\begingroup\$

Haskell, 94 91 64 54 bytes

1!1=1;m!n=sum[m!(n-x)+(m-x)!n+(m-x)!(n-x)|x<-[1..m+n]]

Try it online!

Initially a boring port of the comment on OEIS

-27 from some tricks off dingledooper's answer

-10 from Christian Sievers

\$\endgroup\$
2
  • 3
    \$\begingroup\$ I think you can replace max m n with m+n \$\endgroup\$ Commented Apr 13, 2020 at 8:45
  • \$\begingroup\$ @ChristianSievers seems like it, and with that the m*n>0 check was also unnecessary, ty! \$\endgroup\$
    – clapp
    Commented Apr 13, 2020 at 9:02
6
\$\begingroup\$

Python 2, 75 bytes

@xnor's idea which is 2 bytes smaller than the one below. Returns True for 1 1.

f=lambda m,n:sum(f(m-i,n)+f(m,n-i)+f(m-i,n-i)for i in range(1,n|m))or m>0<n

Try it online!


Python 2, 79 77 bytes

f=lambda m,n:(m==n==1)+sum(f(m-i,n)+f(m,n-i)+f(m-i,n-i)for i in range(1,n+m))

Try it online!

\$\endgroup\$
4
  • \$\begingroup\$ I think the 77-byter is surely correct. The correctness is clear and it will end in finite time because n+m is decreasing. \$\endgroup\$
    – newbie
    Commented Apr 13, 2020 at 3:59
  • \$\begingroup\$ Yes, you're definitely right. It probably just takes longer for larger inputs. \$\endgroup\$ Commented Apr 13, 2020 at 17:52
  • \$\begingroup\$ Here's a way to shave two bytes off the base case for the first one, with True for 1: Try it online! \$\endgroup\$
    – xnor
    Commented Apr 13, 2020 at 21:36
  • \$\begingroup\$ @xnor Clever idea; thanks for the improvement! \$\endgroup\$ Commented Apr 13, 2020 at 21:48
5
\$\begingroup\$

K (ngn/k), 36 bytes

{(x~1 1)+/o'x-/:{|/'~x,'-/'x}#1_+!x}

Try it online!

!x odometer

+ transpose

1_ drop the first

{ }# filter

|/'~x,'-/'x either element or their difference is 0

x-/: subtract each right

o' recur each

+/ sum

(x~1 1) does x match 1 1? use as initial value for the sum

\$\endgroup\$
3
\$\begingroup\$

Erlang (escript), 92 bytes

Boring port of the Haskell answer.

f(1,1)->1;f(M,N)->lists:sum([f(M,N-X)+f(M-X,N)+f(M-X,N-X)||X<-lists:seq(1,max(M,N)),M*N>0]).

Try it online!

\$\endgroup\$
1
\$\begingroup\$

Charcoal, 40 bytes

NθFNFθ⊞υ∨¬υΣΦυ∨∨⁼ι÷μθ⁼κ﹪μθ⁼⁻ικ⁻÷μθ﹪μθI⊟υ

Try it online! Link is to verbose version of code. Explanation:

Nθ

Input the number of columns.

FN

Loop over the rows.

Fθ

Loop over each column.

⊞υ∨¬υ

The first result is always 1...

ΣΦυ∨∨⁼ι÷μθ⁼κ﹪μθ⁼⁻ικ⁻÷μθ﹪μθ

... otherwise find the existing results that are a Queen's move away, take the total, and push that to the list of results. The list therefore simulates a matrix, requiring its index to be divided or taken modulo the number of columns as appropriate to compare with the loop variables.

I⊟υ

Output the last result calculated.

\$\endgroup\$
1
\$\begingroup\$

J, 60 50 bytes

_2{(],1#.]#~(#:#)(0=*/*-/)@:-"1(#:i.@#))^:(*/@[)&1

Try it online!

\$\endgroup\$
0

Your Answer

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

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