20
\$\begingroup\$

Pascal's Rhombus (which is actually a triangle) is obtained by adding in the pattern:

  *
 ***
  x

instead of

* *
 x

This means that each cell is the sum of the three cells on the row directly above it and one cell on the row 2 above it. Just like Pascal's triangle the zeroth row has a single 1 on it that generates the triangle.

Here are the first couple of rows of Pascal's Rhombus

      1
    1 1 1
  1 2 4 2 1
1 3 8 9 8 3 1

Task

Given a row number (starting from the top) and an column number (starting from the first non-zero item on that row) output the value at that particular cell. Both inputs may be either 1 or 0 indexed (you may mix and match if you desire).

This is so you should aim to make the file size of your source code as a small as possible.

OEIS A059317

\$\endgroup\$

14 Answers 14

12
\$\begingroup\$

Haskell, 59 55 bytes

Pascal's Rhombus? More like Haskell's Rhombus! amiright?

4 bytes saved thanks to Ørjan Johansen

I thought I'd have a go at my own problem and practice my Haskell. Hopefully this will inspire more people to answer this.

1!1=1
n!k=sum[(n-2)!(k-2)+sum(map((n-1)!)[k-2..k])|n>1]

Try it online!

Explanation

This is a bit out of date with the latest golf

Instead of calculating

  *
 ***
  x

We calculate

*
***
  x

This slants our entire triangle to become

1
1 1 1
1 2 4 2 1
1 3 8 9 8 3 1

This lines up all of our rows making it easier to index the nth item of any column. We then define our base cases.

The zeroth row is all zeros so

0!_=0

There is a single 1 at position 1,1 so we define that

1!1=1

And we define the rest of the first row to be zeros as well

1!_=0

Then we define the general case recursively using the pattern described above:

n!k=(n-2)!(k-2)+(sum$map((n-1)!)[k-2..k])
\$\endgroup\$
  • \$\begingroup\$ Beat me to it! This is also a lot cleaner than mine. \$\endgroup\$ – Julian Wolf Jul 5 '17 at 23:16
  • \$\begingroup\$ @JulianWolf Sorry about that, when I posted this it looked like no one other than Jorg was doing the problem. I'd still like to see your solution. \$\endgroup\$ – Sriotchilism O'Zaic Jul 5 '17 at 23:20
  • 1
    \$\begingroup\$ You can save four bytes with n!k=sum[(n-2)!(k-2)+sum(map((n-1)!)[k-2..k])|n>1]. \$\endgroup\$ – Ørjan Johansen Jul 5 '17 at 23:50
10
\$\begingroup\$

Pascal, 122 bytes

Well, it's Pascal's rhombus.

37 bytes saved thanks to @manatwork

function f(n,k:integer):integer;begin f:=1-Ord((k<0)or(k>n*2));if n>0then f:=f(n-1,k-2)+f(n-1,k-1)+f(n-1,k)+f(n-2,k-2)end;

Try it online!

\$\endgroup\$
  • \$\begingroup\$ Parenthesis around the entire if condition are pointless. (On 1st if you save 2 characters, on the 2nd if 1 character by leaving no space between then keyword and the preceding digit.) Oh, and variable r is completely unnecessary. \$\endgroup\$ – manatwork Jul 6 '17 at 8:51
  • \$\begingroup\$ Weird animal that Pascal on Ideone. Never seen double quotes delimited strings in any Pascal variant before. One more thing you can remove: the ; before the function's end. \$\endgroup\$ – manatwork Jul 6 '17 at 9:24
  • \$\begingroup\$ @manatwork yea, now when you mentioned it, all of the other online editors complained about it \$\endgroup\$ – Uriel Jul 6 '17 at 9:28
  • \$\begingroup\$ @manatwork I'm not sure I understood. wouldnt that just lengthen the code with the >= <=? I still need to preserve the if n=0 \$\endgroup\$ – Uriel Jul 6 '17 at 9:44
  • \$\begingroup\$ Sorry @Uriel, I don't have that version anymore. Currently I'm at function f(n,k:integer):integer;begin f:=1-Ord((k<0)or(k>n*2));if n>0then f:=f(n-1,k-2)+f(n-1,k-1)+f(n-1,k)+f(n-2,k-2)end; \$\endgroup\$ – manatwork Jul 6 '17 at 9:55
7
\$\begingroup\$

PHP, 86 bytes

recursive way only the function row and column 0-Indexed

function f($r,$c){return$r|$c?$r<0?0:f($r-=1,$c)+f($r,$c-1)+f($r,$c-=2)+f($r-1,$c):1;}

Try it online!

PHP, 114 bytes

recursive way full program row and column 0-Indexed

<?=f(...$_GET);function f($r,$c){return$r|$c?$r<0|$c<0|$c>2*$r?0:f($r-=1,$c)+f($r,$c-1)+f($r,$c-=2)+f($r-1,$c):1;}

Try it online!

PHP, 129 bytes

row and column 0-Indexed

for(;$r<=$argv[1];$l=$t[+$r++])for($c=~0;$c++<$r*2;)$t[+$r][$c]=$r|$c?$t[$r-2][$c-2]+$l[$c]+$l[$c-1]+$l[$c-2]:1;echo$l[$argv[2]];

Try it online!

\$\endgroup\$
  • \$\begingroup\$ and +1 for actually improving it :) \$\endgroup\$ – Uriel Jul 6 '17 at 11:59
4
\$\begingroup\$

Jelly, 22 20 19 bytes

3ḶṚp@Ḣḣ4
Ḟ_ЀÇ߀ȯ¬S

Takes a 0-based index pair as command-line argument.

Try it online!

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

MATL, 22 20 19 bytes

Ti:"2Y6Y+FT_Y)]!i_)

Both inputs are 0-based.

Try it online!

Explanation

Let r and c denote the two inputs, specifying 0-based row and column respectively.

Each new row in Pascal's rhombus can be built from the matrix containing the previous two rows by convolving with the kernel [1 1 1; 0 1 0] and keeping the last two rows of the result swapped. This is done r times, starting from matrix 1.

It turns out to be shorter to use the kernel [0 1 0; 1 1 1; 0 1 0], which is a predefined literal. This produces an extra row, which will be discarded.

Consider for example r = 3, so there are 3 iterations.

  1. Starting from

    1
    

    convolution with [0 1 0; 1 1 1; 0 1 0] gives

    0 1 0
    1 1 1
    0 1 0
    

    Keeping the last two rows (the whole matrix, in this case) and swapping them gives

    0 1 0
    1 1 1
    
  2. Convolution of the above with [0 1 0; 1 1 1; 0 1 0] gives

    0 0 1 0 0
    0 1 1 1 0
    1 2 4 2 1
    0 1 1 1 0
    

    The matrix formed by the last two rows swapped is

    0 1 1 1 0
    1 2 4 2 1
    

    This contains the new row at the bottom, and the preceding one extended with zeros.

  3. Convolving again yields

    0 0 1 1 1 0 0
    0 1 2 3 2 1 0
    1 3 8 9 8 3 1
    0 1 2 4 2 1 0
    

    Taking the last two rows swapped gives

    0 1 2 4 2 1 0
    1 3 8 9 8 3 1
    

After the r iterations have been done, the output is contained in the last row of the final matrix. For example, for c = 2 (0-based) the result would be 8. Instead of indexing the last row and the desired column, a trick can be used which exploits the symmetry of each row: the final matrix is transposed

0 1
1 3
2 8
4 9
2 8
1 3
0 1

and its -c-th element is taken. This uses linear indexing, that is, the matrix is indexed by a single index in column-major order. Since indexing is modular, the 0-entry is the lower-right corner (value 1) and the -2-th entry is two steps above (value 8).

T       % Push true
i       % Input row number
:"      % Do the following that many times
  2Y6   %   Push predefined literal [0 1 0; 1 1 1; 0 1 0]
  Y+    %   2D convolution, increasing size
  FT_   %   Push [0 -1]
  Y)    %   Matrix with rows 0 (last) and -1 (second-last), in that order
]       % End
!       % Transpose
i       % Input: colun number
_       % Negate
)       % Entry with that index. Implicitly display
\$\endgroup\$
3
\$\begingroup\$

Pari/GP, 60 bytes

i->j->polcoeff(Vec(1/(1-x*(1+y+y^2+x*y^2))+O(x^i++))[i],j,y)

Try it online!

\$\endgroup\$
2
\$\begingroup\$

Haskell, 74 bytes

0#0=1
n#m|m<=2*n&&m>=0=sum[(n-a)#(m-b)|(a,b)<-zip[2,1,1,1]$2:[0..2]]
n#m=0

Try it online!

Call with n # m, where n is the row and m is the column.

\$\endgroup\$
  • \$\begingroup\$ m<=2*n&&m>=0 can be just n>0. \$\endgroup\$ – Ørjan Johansen Jul 6 '17 at 0:06
2
\$\begingroup\$

Mathematica, 56 bytes

If[#<1,Boole[##==0],Sum[#0[#-i,#2-j],{i,2},{j,2i-2,2}]]&

Pure function taking two integer arguments (row first, column second) and returning an integer. Works for negative integer arguments as well, returning 0. A pretty straightforward recursive structure: If[#<1,Boole[##==0],...] defines the base-case behavior for the 0th row (and above), while Sum[#0[#-i,#2-j],{i,2},{j,2i-2,2}] implements the recursive definition.

\$\endgroup\$
2
\$\begingroup\$

Python 2, 70 66 65 bytes

f=lambda n,k:(k==0)|sum(f(n+~j/3,k-j+j/3)for j in range(4)[:3*n])

Try it online!

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

JavaScript (ES6), 68 bytes

f=(y,x)=>x<0|x>y+y?0:x>0&x<y+y?f(--y,x)+f(y,--x)+f(y,--x)+f(--y,x):1
\$\endgroup\$
1
\$\begingroup\$

Mathematica, 53 bytes

D[1/(1-x(1+y+y^2(1+x))),{x,#},{y,#2}]/#!/#2!/.x|y->0&

Using the generating function.

\$\endgroup\$
0
\$\begingroup\$

Python 3, 82 84 bytes

This is a recursive implementation with 1-indexed rows and columns. (Technically needs an f= in front, someone let me know if I should change it to 84 bytes. Still new and not 100% sure of the rules.)

This uses the recursive formula found on the OEIS page, but with the k's shifted one to the left to line up properly. Coincidently, sum(f(n-1,k-i)for i in(0,1,2)) is the same size as f(n-1,k)+f(n-1,k-1)+f(n-1,k-2). The whole function is the Python and or trick, where the first condition checks if k is inside the triangle and not on the boundary, in which case the recursive formula is used. If is isn't, the part after the or is returned, which checks if k is in (1, 2*n-1), i.e. on the boundary, returning True and False. k+1in(2,2*n) is one byte shorter than k in(1,2*n-1). Wrapping that in parentheses and putting a + in front converts to integer, which is what is needed.

f=lambda n,k:2*n-1>k>1and sum(f(n-1,k-i)for i in(0,1,2))+f(n-2,k-2)or+(k+1in(2,2*n))

Try it online!

\$\endgroup\$
  • \$\begingroup\$ Recursive functions need the f=. \$\endgroup\$ – Sriotchilism O'Zaic Jul 6 '17 at 0:11
  • \$\begingroup\$ While I personally disagree with it according to this somewhat buried meta consensus, you may output True instead of 1 because it behaves like 1 to python. This allows you to remove the +(...) at the end. I understand if you don't want to do this, because it will make the output look a little strange, it is an option. \$\endgroup\$ – Sriotchilism O'Zaic Jul 6 '17 at 3:55
  • \$\begingroup\$ @WheatWizard Wow that's very interesting. Thanks for the tip. \$\endgroup\$ – C McAvoy Jul 6 '17 at 13:42
0
\$\begingroup\$

Java (OpenJDK 8), 87 bytes

int f(int r,int c){return c<0|2*r<c?0:0<c&c<2*r?f(--r,c)+f(r,--c)+f(r,--c)+f(--r,c):1;}

Try it online!

At first, I was happy with my 160 bytes iterative method... Hmmm... let's just forget about it, OK?

\$\endgroup\$
0
\$\begingroup\$

Python 3, 75 Bytes

This is a recursive lambda that takes column and row as 0-indexed integers.

p=lambda r,c:(r<0 or((c==0)|p(r-1,c-2)+p(r-1,c)+p(r-1,c-1)+p(r-2,c-2))+1)-1

Here's a (slightly) more readable version with a printing function:

p = lambda r,c:(r<0 or ((c==0) | p(r-1,c-2)+p(r-1,c)+p(r-1,c-1)+p(r-2,c-2))+1)-1

def pp(r):
    ml = len(str(p(r,r)))+1
    for i in range(0, r):
            a=" "*ml*(r-i)
            for j in range(0,i*2 + 1):
                    a+=str(p(i,j))+(" "*(ml-len(str(p(i,j)))))
            print(a)
\$\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.