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
\$\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

| improve this answer | |
\$\endgroup\$
  • 2
    \$\begingroup\$ I think you can replace max m n with m+n \$\endgroup\$ – Christian Sievers Apr 13 at 8:45
  • \$\begingroup\$ @ChristianSievers seems like it, and with that the m*n>0 check was also unnecessary, ty! \$\endgroup\$ – clapp Apr 13 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!

| improve this answer | |
\$\endgroup\$
  • \$\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 Apr 13 at 3:59
  • \$\begingroup\$ Yes, you're definitely right. It probably just takes longer for larger inputs. \$\endgroup\$ – dingledooper Apr 13 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 Apr 13 at 21:36
  • \$\begingroup\$ @xnor Clever idea; thanks for the improvement! \$\endgroup\$ – dingledooper Apr 13 at 21:48
4
\$\begingroup\$

K (ngn/k), 33 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

| improve this answer | |
\$\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!

| improve this answer | |
\$\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.

| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

J, 60 50 bytes

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

Try it online!

| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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