24
\$\begingroup\$

What do you get when you cross Pascal's Triangle and the Fibonacci sequence? Well, that's what you have to find out!

Task

Create a triangle that looks like this:

          1
        1   1
       2  2  2
    3   5  5   3
  5  10  14  10  5
8  20  32  32  20  8

Basically, instead of each cell being the sum of the cells above it on the left and right, you also need to add the cell on the left above the cell on the left and the cell on the right above the cell on the right.

This is A036355.

You may choose to do one of the following:

  • Output the \$n\$th row (indexed as you wish)
  • Output the first \$n\$ rows
  • Output all rows infinitely

Rules

  • Each row may be represented as a string separated by some character that is not a digit or an ordered collection of numbers. You do not need to align the triangle like I did in the example.
  • If you choose to output multiple rows, you need either an ordered list of rows, or a string that uses a different separator than the one you use within rows.
  • Please specify which task you chose in your answer, along with the input (if applicable) and output format.
  • You can receive input and output through any of the standard IO methods.
  • This is , so shortest code in bytes wins!

Bounty

As Scala is the language of the month, I will be giving a 50 rep bounty for any Scala answers to this question (not just if you're a first-time user). If multiple Scala answers are posted, I will be happy to put a bounty on a different Scala answer of yours instead.

\$\endgroup\$
2
  • \$\begingroup\$ Can rows be padded with 0s? \$\endgroup\$ – att Jan 4 at 21:22
  • \$\begingroup\$ @att Hmm, that's probably all right, as long as you center the actual triangle and padding all the rows to be as long as the nth row. \$\endgroup\$ – user Jan 4 at 21:42

18 Answers 18

13
\$\begingroup\$

Python 2, 73 72 69 bytes

-1 byte thanks to dingledooper!
-3 bytes thanks to Sisyphus!

Prints the rows indefinitely.

c=a=[0]
b=[1]
while 1:print b;a,b=b,map(sum,zip(c*2+a,a+c*2,c+b,b+c))

Try it online!

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

Haskell, 82 75 69 66 62 bytes

u%v=v:v%foldl1(zipWith(+))[0:0:u,u++[0,0],0:v,v++[0]]
f=[]%[1]

Try it online!

-10 thanks to @user

-4 thanks to @ovs

Fairly new to Haskell, and never golfed in it before. Happy to be beaten!

\$\endgroup\$
3
  • \$\begingroup\$ You can save a few bytes if you start with g[][1] and don't prepend anything to the result of that \$\endgroup\$ – user Jan 1 at 19:47
  • \$\begingroup\$ 66 bytes by making g % \$\endgroup\$ – user Jan 1 at 20:20
  • \$\begingroup\$ 62 bytes by using foldl1 to remove some parentheses. \$\endgroup\$ – ovs Jan 1 at 21:27
6
\$\begingroup\$

J, 30 bytes

Returns the n'th row.

0{((+|.)@(+/)@,.,:{~)&0&(1,:0)

Try it online!

How it works

  • f&0&(1,:0) (1,:0) f 0 will be executed n times
  • (last two rows) g@,. (0) append a 0 to each row and execute g, f.e. g (2 2 2 0,: 1 1 0 0)
  • (+|.)@(+/) sum the two rows 3 3 2 0 and add it to its reverse: 3 5 5 3
  • ,:{~ append the previous row 3 5 5 3,:2 2 2 0
  • 0{ after n iteration get the last row 3 5 5 3
\$\endgroup\$
5
+50
\$\begingroup\$

Scala, 156..133 120 bytes

-23 bytes thanks to user!
-13 bytes thanks to Command Master!

()=>{var(a,b)=Seq(1,1)->Seq(1)
while(1>0){println(b)
val t=a
a=Seq(0+:0+:b,b:+0:+0,a:+0,0+:a).transpose.map(_.sum)
b=t}}

Try it online!

Output is infinite.

Explanation:

object M extends App {
  var (a, b) = Seq(1, 1) -> Seq(1)                                          // init (a, b) := ([1, 1], [1]])
  while (1 > 0) {                                                           // while true
    println(b)                                                              // print b
    val t = a                                                               // cache a in a local variable t
    a = Seq(0 +: 0 +: b, b :+ 0 :+ 0, a :+ 0, 0 +: a).transpose.map(_.sum)  // calculate the new triangle row with 
                                                                            // the help of the shifted lists a and b like in the example below
    b = t                                                                   // set b the cached previous value of a
  }
}

Example for n = 4:

   0  0  2  2  2
+  2  2  2  0  0
+  3  5  5  3  0
+  0  3  5  5  3
-----------------
=  5 10 14 10  5
\$\endgroup\$
5
  • 1
    \$\begingroup\$ Nice answer! You can save a couple bytes by using -> and using infix syntax for mkString. I think it's also valid if you make a (parameterless) lambda instead of making a full program, so that'll save some more bytes. \$\endgroup\$ – user Jan 2 at 16:41
  • 1
    \$\begingroup\$ And 149 bytes by eliminating zipped altogether using transpose! (Also, I replaced t with a and b, and used -> to initialise them). By the way, you might want to add your answer to the list of Scala answers posted in January, so I'll remember to put a bounty on this. \$\endgroup\$ – user Jan 2 at 17:00
  • 1
    \$\begingroup\$ @user That is impressive! I have so much to learn. Thank you very much for your help. I really appreciate it. \$\endgroup\$ – Michael Chatiskatzi Jan 2 at 17:28
  • 1
    \$\begingroup\$ You're welcome :) Just one thing: you'll have to wrap your code in a ()=>{...} lambda. I don't think plain code snippets are allowed. \$\endgroup\$ – user Jan 2 at 18:19
  • 2
    \$\begingroup\$ According to the rules: Each row may be represented as a string separated by some character that is not a digit or an ordered collection of numbers. You do not need to align the triangle like I did in the example. Which I think means you are allowed to print the rows in Scala's list format, removing ` mkString " "` \$\endgroup\$ – Command Master Jan 5 at 5:17
5
\$\begingroup\$

05AB1E, 25 24 19 18 13 12 bytes

-6 bytes thanks to @ovs

-4 bytes thanks to @Neil, which allowed for additional -1

-2 bytes thanks to @Kevin Cruijssen

1‚ηλ₂0š+0šÂ+

Try it online!

A port of the python answer, basically. Outputs the rows infinitly

Explaination:

1 push 1
‚ pair. Since there is no input, it pairs 1 with 1, to get [1, 1]
η prefixes, get [[1], [1, 1]]
λ recursive environment
₂ push a(n-2)
0š prepend 0 to a(n-2)
+ sum with implicit a(n-1)
0š prepend a zero
 Bifurcate - push a and reversed(a)
+ sum
\$\endgroup\$
5
  • 2
    \$\begingroup\$ I didn't know you could pass multiple base cases to λ like this, that's neat! 18 bytes using ζ to append 0's and shorten the sum, slightly shorter initialization and the fact that recursive enviroment automatically pushes a(n-1) if needed. \$\endgroup\$ – ovs Jan 1 at 19:25
  • \$\begingroup\$ any idea on why it now takes a lot more time? \$\endgroup\$ – Command Master Jan 1 at 19:40
  • \$\begingroup\$ I'm not sure why exactly, but transposing nested lists can be really slow. Sometimes it helps to disable lazy evaluation with --no-lazy, but apparently not in this case. \$\endgroup\$ – ovs Jan 1 at 21:35
  • 2
    \$\begingroup\$ You can use symmetry to knock 4 bytes off: 2LÅ1λ₂0š+0šDR+. Sadly + won't fill with 0 so the ₂0š is necessary. \$\endgroup\$ – Neil Jan 5 at 0:54
  • \$\begingroup\$ 2LÅ1 can be 1‚η for -1 byte. If a 05AB1E doesn't have an input, it will use the last used value again when it needs more than one. So the 1‚ will create a pair [1,1] (and then prefixes builtin η will transform it into [[1],[1,1]]). This only works because there is no input. :) \$\endgroup\$ – Kevin Cruijssen Jan 7 at 9:53
4
\$\begingroup\$

Haskell, 81 bytes

q=zipWith(+)
z=[0,0]
f=[]:[1]:[q(a++z)$q(z++a)$q(b++[0])$0:b|(a,b)<-zip f$tail f]

Try it online!

Returns an infinite list of all rows, 1-indexed (hence the tail in TIO to dispose of element 0).

\$\endgroup\$
4
\$\begingroup\$

Perl 5, 86 bytes

$,=$";@b=@c,@c=@,while say@,=map$,[$_]+($_>0)*$,[$_-1]+($_>1)*$b[$_-2]+$b[$_]||1,0..@,

Try it online!

Output is infinite.

\$\endgroup\$
4
\$\begingroup\$

Charcoal, 54 39 bytes

≔⟦¹⟧ηFN«⊞υ⁰≔Eυ⁺κ§ηλι≔ηυ⊞ι⁰≔E⮌ι⁺κ§ιλη»Iη

Try it online! Link is to verbose version of code. Outputs the 0-indexed nᵗʰ row. Explanation: Relies on the symmetry of the triangle.

≔⟦¹⟧η

Start with the 0ᵗʰ row with just a 1 in it (using the predefined empty list for the "-1ᵗʰ" row).

FN«

Repeat n times.

⊞υ⁰

Append a 0 to the previous row.

≔Eυ⁺κ§ηλι

Sum the previous and current row to a temporary variable.

≔ηυ

Copy the current row to the previous row.

⊞ι⁰

Append a 0 to the new row.

≔E⮌ι⁺κ§ιλη

Add the new row to its reverse and save that as the current row.

»Iη

Print the final row.

Previous 54-byte version worked by creating the matrix formed by rotating the triangle anticlockwise by 45°:

Nθ⊞υEθ⁼ι¹⊞υ⟦⁰⟧Fθ«≔⟦⁰⟧ηF⁻θι⊞ηΣ⁺…⮌η²E…⮌υ²§λ⊕κ⊞υη»I✂Eυ⊟ι²

Try it online! Link is to verbose version of code. Outputs the 1-indexed nᵗʰ row. Explanation:

Nθ

Input n.

⊞υEθ⁼ι¹

Create a fictitious "-1ᵗʰ" row with a single 1 in the first column. This seeds the first row later.

⊞υ⟦⁰⟧

Create a "0ᵗʰ" row of zeros. (Because Charcoal uses cyclic indexing, I only need one zero.)

Fθ«

Loop over the desired output rows.

≔⟦⁰⟧η

Start with a "0ᵗʰ" column of just a zero.

F⁻θι

Loop over the additional numbers needed to complete this row of the rotated triangle.

⊞ηΣ⁺…⮌η²E…⮌υ²§λ⊕κ

Get the latest two numbers for this row plus the two numbers in the columns above and push the sum to the current row.

⊞υη

Push the completed row to the triangle.

»I✂Eυ⊟ι²

Print the last number in each row, excluding the two initial dummy rows.

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

AWK, 117 111 bytes

Prints the first n rows of the triangle, unformatted.

Edit: Let l and c be two integers. l c concatenates their values as a string. For example: in the first element, 0 0 evaluates "00" (str). 00 would evaluate 0 (int).

{print a[0 0]=1;for(;++l<$1;)for(c=0;c<=l;c++)printf a[l c]=a[l-1 c-1]+a[l-1 c]+a[l-2 c-2]+a[l-2 c](c~l?RS:FS)}

Step by step:

{
print a[0 0]=1;                  # sets the top of the triangle
for(;++l<$1;)                    # looping for the lines
  for(c=0;c<=l;c++)              # looping for the columns
    printf a[l c]=               # prints the ["l c"]th element of the array,
           a[l-1 c-1]+a[l-1 c]+  # which is the sum of these elements of the l-1 line
           a[l-2 c-2]+a[l-2 c]   # and these elements of the l-2 line.
           (c~l?RS:FS)           # if it's the last column, adds a line feed,
                                 # otherwise, a space.
}

Try it online!

\$\endgroup\$
2
  • 1
    \$\begingroup\$ Nice! You can shave off a few more characters by using array indexes like a[l-1 c-1] in place of a[l-1][c-1] since AWK will just concatenate the numbers together. \$\endgroup\$ – cnamejj Jan 2 at 8:38
  • \$\begingroup\$ @cnamejj very keen of you! Thanks! \$\endgroup\$ – Pedro Maimere Jan 4 at 15:15
3
+100
\$\begingroup\$

Husk, 17 15 bytes

:;1mSż+oΘ↔Ẋż+Θ₀

Try it online!

Answering Razetime's challenge from the Husk chat

Explanation

:;1mSż+oΘ↔Ẋż+Θ₀
:;1                Begin with [1]
              ₀    Define the sequence recursively
          Ẋż+Θ     Pairwise sums of rows (e.g. [1,1]+[2,2,2]=[3,3,2])
   m               For each of these sums
    Sż+             Sum it to
       oΘ↔          itself reversed with an extra leading 0
                    (e.g. [3,3,2]+[0,2,3,3]=[3,5,5,3])

All the sums between lines are performed with ż+, which sums elements at the same indices and keeps elements from the longer line unchanged.


Previous solution, 17 bytes

∂ƒ(:İftS‡+T0Ẋż+ΘΘ

Try it online!

Here's my previous solution using an original approach.

Explanation

If we rotate the triangle 45° counterclockwise, we'll find out it is actually an infinite 2D matrix:

1  1  2  3  5 ...
1  2  5 10 20 ...
2  5 14 32 71 ...
3 10 32 84 ...
5 20 71 ...
...

This answer builds that matrix and then returns its antidiagonals, which will be the rows of the original triangle.

∂ƒ(:İftS‡+T0Ẋż+ΘΘ
∂                    Antidiagonals of
 ƒ(                  Fixpoint of the following function (defines the matrix recursively)
   :İft              Set the Fibonacci sequence as the first row
               ΘΘ    Add two empty rows before the matrix
            Ẋż+      and get the pairwise row sums
       S‡+T0         then sum this to itself transposed

The recursive definition computes the sums of each row with the previous one, and adds it to the sums of each column with the previous one; since the matrix is symmetric along the main diagonal, column sums are computed by transposing the row sums. Two empty rows need to be added to deal with the numbers near the sides of the triangle, where there are less than two rows/columns to sum.

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

JavaScript (V8), 82 bytes

f=(a=0,b=[1])=>print(b)+f(b,[...b,0].map((x,i)=>x+(a[i]|0)+(b[i-1]|0)+(a[i-2]|0)))

Try it online!

  • Missing a JavaScript answer, hoping @Arnauld is fine
\$\endgroup\$
1
  • \$\begingroup\$ Mm.. Agreed, it's used inside the body \$\endgroup\$ – AZTECCO Jan 3 at 14:36
2
\$\begingroup\$

Jelly, 14 13 12 bytes

1WɓŻ+Ż++µ³¡0

Try it online!

Returns the nth row, indexed from 0.

Makes use of the fact that Jelly's “repeat n times” quick ¡, when given a dyad, behaves in a Fibonacci-ish way.

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

Husk, 29 28 23 19 bytes

  • Saved 1 byte thanks to caird coinheringaahing
  • Saved 5 bytes thanks to Razetime!
  • Saved 4 bytes thanks to Leo!
¡öFz+S+m↔z+ḣ´e0↔;;1

Try it online!

Outputs an infinite list, explanation coming soon. This is really long, so it looks like I'm not going to get the bounty anyway.

¡öFz+S+m↔z+ḣ´e0↔;;1
¡                     Create infinite list by repeatedly applying function
                      that list of previous result to create new result
                ;;1   Initial list of results - [[1]]
  Fz+S+m↔z+ḣ`e0↔      Function to get next row from previous rows
               ↔      Reverse previous rows (so last 2 rows are at start)
            `e0       [0, 0]
           ḣ          Prefixes ([[0], [0,0]])
         z+           Zip by concatenating ([0, 1, 1], [0, 0, 1])
     S+               Then add those lists
       m↔             To their reverse ([1, 2, 1], [1, 0, 1])
  F                   Fold over that 2-element list of lists
   z+                 By adding them together to get the new row
\$\endgroup\$
4
  • 1
    \$\begingroup\$ You can remove the o in the helper \$\endgroup\$ – caird coinheringaahing Apr 27 at 14:31
  • 1
    \$\begingroup\$ Moving everything inside the lambda, removing parens: 23 \$\endgroup\$ – Razetime Apr 27 at 15:10
  • 1
    \$\begingroup\$ 1) The helper function is not actually saving any bytes, it can be inlined. 2) The lambda here is superfluous, by replacing it with normal brackets we don't need the anymore. With this plus some other small golfs you can get down to 19 bytes \$\endgroup\$ – Leo Apr 29 at 2:12
  • 1
    \$\begingroup\$ @Leo Thanks, that’s amazing! I’m on mobile now but I’ll add it tomorrow when I’m on my laptop \$\endgroup\$ – user Apr 29 at 2:25
2
\$\begingroup\$

Haskell, 59 bytes

x!y=zipWith(+)x$y++[0,0]
x#y=x:(0:0:y)!y!(0:x)!x#x
t=[1]#[]

Try it online!

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

Julia 1.0, 53 bytes

f(i=1,j=[])=@show(i),f([i;0]+[0;i]+[j;0;0]+[0;0;j],i)

Try it online!

call f() for infinite output

Only correct up to 64-bit signed integer limit, replace i=1 with i=big(1) to make it work for any number

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

PHP, 124 115 112 bytes

echo 1;for($q=[1];print"
";$p=$q,$q=$r)for($i=-1;++$i<=count($q);)echo$r[$i]=$q[$i-1]+$q[$i]+$p[$i-2]+$p[$i].~_;

Try it online!

Did the world want this answer? Probably not. Did it deserve it? Definetly.

straightforward PHP soup that outputs all rows forever (at least until scientific notation -quickly- makes things unreadable)

EDIT: saved 9 bytes by not initializing $p and $r. There wasn't enough warnings for my taste.

EDIT2: saved another 3 bytes with another strategy for the newline output, thanks to print returning a truthy value (note that I'm aware that a byte could be saved with a "assumed constant" line separator like print A, but I preferred a readable output)

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

Pip -s, 22 bytes

Y^1LaS(l+:Py)+:RVlPE0y

Outputs the first n rows. Try it online!

Explanation

Each row of the triangle, represented as a list, can be obtained by a two-step process: first add the two previous rows; then take that result, reverse it, prepend 0, and add it to itself.

 [2 2 2]
+[3 5 5 3]
----------
 [5 7 7 3]
+[0 3 7 7 5]
------------
 [5 10 14 10 5]

Let's start with a less-golfed version of the code:

Y[1]La{Pyl+:yl+:RVlPE0Sly}
                            a is command-line argument; l is empty list (implicit)
Y[1]                        Yank the first row into y
    La{                  }  Loop a times:
       Py                    Print y, the current row
         l+:y                Add the two rows together, saving the result in l
                RVl          Reverse that list,
                   PE0       prepend 0,
             l+:             and add it back to l (the new row)
                      Sly    Swap l and y; y is now the new row and l the row above it

To get to 22 bytes:

  • Using this tip, [1]^1.
  • We can print y while adding it to l: l+:Py.
  • An assignment expression evaluates to an lvalue, so we can use it in the swap command: S(l+:RVlPE0)y (parentheses not necessary, added for clarity).
  • But then we can take the same idea one step further and replace the l in that assignment with the first l assignment. We'll need parentheses because assignment operators are right-associative; but since the body of the loop is now one statement, we can drop the curly braces for a net 1-byte savings: S(l+:Py)+:RVlPE0y.
\$\endgroup\$
1
\$\begingroup\$

Wolfram Language (Mathematica), 60 47 bytes

#3&@@@(#3&@@(1/(1-x(1+y+x+y^2x))+O@x^#)+O@y^#)&

Try it online!

1-indexed. Returns the first \$n\$ rows by truncating the generating function \$\frac1{1-x(1+x+y+xy^2)}\$.


older, 66 bytes

Sum[Multinomial[#-n-2i,n-2j,i,j],{i,0,#-n},{j,0,n}]~Table~{n,0,#}&

Try it online!

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