# Fibonacci-style matrix expansion

For each row and then column of a matrix, we can add an extra entry with the sum of the last two entries in that row or column. For example with the following input matrix:

``````[ 1 1 1 ]
[ 2 3 4 ]
``````

The resulting matrix would be:

``````[ 1 1 1 2 ]
[ 2 3 4 7 ]
[ 3 4 5 9 ]
``````

Given an input of an integer N and an [X,Y] matrix of size at least 2x2, perform the above expansion N times and output the result. The resulting matrix will always be of size [X+N,Y+N].

### Examples:

``````Input:                     Output:

2, [ 0 0 ]                 [ 0 0 0 0 ]
[ 0 0 ]                 [ 0 0 0 0 ]
[ 0 0 0 0 ]
[ 0 0 0 0 ]

3, [ 1 1 1 ]               [ 1  1  1  2  3  5 ]
[ 2 3 4 ]               [ 2  3  4  7 11 18 ]
[ 3  4  5  9 14 23 ]
[ 5  7  9 16 25 41 ]
[ 8 11 14 25 39 64 ]
``````
-

# MATL, 13 1415162021 bytes

``````2*:"!tP2:Y)sv
``````

Thanks @Zgarb for removing 1 byte!

Try it online!

``````2*         % implicitly input number N and multiply by 2
:          % create vector [1,2,...,2*N]
"          % for loop: do this 2*N times
!        %   transpose. Implicitly input matrix in the first iteration
tP       %   duplicate and flip vertically
2:       %   vector [1,2]
Y)       %   pick submatrix formed by the first two rows
s        %   sum of each column
v        %   append as a new row
% end for
% implicit display
``````
-
I don't know MATL, but wouldn't it be shorter to loop `2N` times than to loop twice `N` times? – Zgarb Feb 5 at 0:25
@Zgarb Of course! How did I miss that? Thanks!! – Luis Mendo Feb 5 at 0:42
Does MATL have a built-in for doubling a number? – Zgarb Feb 5 at 0:46
@Zgarb No. You need `2*` (postfix notation). Maybe it should have a one-character built-in, it's used often. Also `2^` (square). But I'm running out of code space :-) – Luis Mendo Feb 5 at 0:49

## J, 19 bytes

``````(v"1@v=.,[+&{:}:)^:
``````

This defines an adverb, which takes the number on its left, and produces a verb taking the matrix on its right. For the second example, it gives

``````  3 ((v"1@v=.,[+&{:}:)^:) 2 3 \$ 1 1 1 2 3 4
1  1  1  2  3  5
2  3  4  7 11 18
3  4  5  9 14 23
5  7  9 16 25 41
8 11 14 25 39 64
``````

## Explanation

``````(v"1@v=.,[+&{:}:)^:  Left argument x, right argument y
(               )^:  Repeat x times:
v=.               Bind the following verb to v, and apply to y:
[    }:         y and y-without-last-item
+&{:           Sum of their last items
,                Append that to y
v"1@                  then apply v to columns
``````
-

# Jelly, 1513 12 bytes

-1 byte by @Dennis

``````ṫ-S;@"Z
ÇḤ}¡
``````

Like @LuisMendo's MATL answer, this transposes the array before doing the transformation along one axis. Therefore, we need to call the function 2*n times.

``````ṫ-S;@"Z       Helper link. Input: x (2D array)
-              Numeric literal: -1
ṫ               Get x[-1:], i.e. last two rows in x
S             Sum
;@"          Append each to x. " is 'zipWith'; @ switches argument order.
Z         Transpose the array.
ÇḤ}¡          Main link. Input: a, n
Ç               Call the last link on a
Ḥ}             2n
¡            times.
``````

Try it here.

-

# K, 23 bytes

``````{x(2({x,+/-2#x}'+)/)/y}
``````

In action:

``````  {x(2({x,+/-2#x}'+)/)/y}[3;(1 1 1;2 3 4)]
(1 1 1 2 3 5
2 3 4 7 11 18
3 4 5 9 14 23
5 7 9 16 25 41
8 11 14 25 39 64)
``````

Try it here.

-

## ES6, 134 bytes

``````(n,a)=>[...a.map(b=>[...b,...Array(n)].map(c=>(c<1/0?0:c=a+d,d=a,a=c))),...Array(n)].map(b=>(b?0:b=[...a].map((c,j)=>c+d[j]),d=a,a=b))
``````

Explanation:

``````(n,a)=> // arguments n is number to expand, a is original array
[...
a.map(b=> // for each row in a
[...b,...Array(n)] // append n elements to the row
.map(c=>(c<1/0?0:c=a+d,d=a,a=c))) // scan the elements and fill the new ones by summing the previous two
,...Array(n)] // append n rows
.map(b=>(b?0:b=[...a].map((c,j)=>c+d[j]),d=a,a=b)) // scan the rows and fill the new rows by summing the previous two rows
``````
-

``````o%m=m++[o(+)(last m)\$last\$init m]
(!!).iterate(map(id%).(zipWith%))
``````

Usage example:

``````*Main> ( (!!).iterate(map(id%).(zipWith%)) ) [[1,1,1],[2,3,4]] 3
[[1,1,1,2,3,5],[2,3,4,7,11,18],[3,4,5,9,14,23],[5,7,9,16,25,41],[8,11,14,25,39,64]]
``````

How it works:

``````(!!).iterate(    ...         )  -- repeatedly apply ... to the first agrument and
-- pick the iteration defined by the second arg
(zipWith%)   -- for one iteration add a new row and
map(id%)              -- then a new element at the end of each each row

o%m                             -- add row or element at the end of a row resp.
-- argument o is a "modify function"
--          m the whole matrix or a row
m++[    (last m)(last\$init m)] -- take m and append the result of combining the
-- last and 2nd last element of m
o(+)                       -- with a modified version of (+)
-- modification is none (aka. id) when adding an
-- element to the end of a row and
-- zipping elementwise (zipWith) when adding a row
``````
-
I'm a haskell novice. I've got as far as `sudo apt-get install haskell-platform` and am running the `ghci` REPL which gives me a `Prelude> ` prompt. When I paste in `o%m=m++[o(+)(last m)\$last\$init m]` I get `<interactive>:2:4: parse error on input '='`. Can you give me a little primer either running this from a source file or in the REPL? – Digital Trauma Feb 5 at 16:59
@DigitalTrauma: either put the `o%m=...` line (and only this line) in a file called, let's say `fib-matrix.hs`. Then you can use the `:l fib-matrix.hs` command in `ghci` to load the definitions and call the main function just as described in my usage example. -- Or use `let o%m=... in ( (!!). ... ) [[1,1,1]...] 3`. – nimi Feb 5 at 17:16
@DigitalTrauma: oh, there's a 3rd way: give the main function a name, e.g. add a `f=` in front of the second line: `f=(!!).iterate...`, save both lines in a file and load it via `l: <filename.hs>`. Then you can call `f [[1,1,1],[2,3,4]] 3`, etc. – nimi Feb 5 at 17:20
I'm not sure I would accept this as valid haskell, the top line is a function definition and needs modification for use in the REPL, but the 2nd line can be can only be used in the REPL. – Daniel Hill Feb 7 at 3:25
@DanielHill: there's a topic on meta which allows unnamed functions that depend on global helper functions. – nimi Feb 7 at 8:59

## CJam, 17 16 bytes

``````q~2*{~_2\$.+]z}*p
``````

Input format is the matrix first (as a CJam-style 2D array) and the number of iterations afterwards.

Test it here.

### Explanation

Turns out this is the same solution as everyone else's:

``````q~      e# Read and evaluate input.
2*      e# Double the iteration count.
{       e# Run this block that many times...
~     e#   Dump all rows on the stack.
_     e#   Copy the last row.
2\$    e#   Copy the penultimate row.
]     e#   Wrap all rows in a new array.
z     e#   Transpose such that the next iteration processes the other dimension.
}*
p       e#   Pretty-print.
``````
-

## Seriously, 20 bytes

``````,,τ"┬`;d@d@X+@q`M"£n
``````

Takes input the matrix (as a 2D list), then `N`. Outputs a 2D list.

This version doesn't work on the online interpreter for some reason, but does work with this pre-challenge commit.

A version that works online, for 23 bytes:

``````,τ",┬`;d@d@X+@q`M"nkΣ£ƒ
``````

Takes input in the opposite order (`N`, then matrix).

Try it online!

I will add an explanation after I sleep for a little while. Working around interpreter bugs is never fun.

-

# Pyth, 13 12 bytes

``````u+Rs>2dCGyEQ
``````

Uses the same algorithm to most answers. Takes as input the matrix as a 2D array on the first line and `n` on the second line.

### Explanation

``````u        yEQ     do 2*N times, starting with input matrix:
CG          transpose
+R                append to each row:
s                 sum of
>2d              last 2 elements of row
``````
-

# Matlab, 60 bytes

I was first messing about with Matlab's fancy indexing methods (i.e., `A(end+1,:)=sum...`) before I figured that in this rare case, simple concatenation is actually cheaper in Matlab. Too bad I had to convert this into an actual function. Should work with Octave as well.

``````function A=f(A,n)
for i=1:2*n
A=[A;sum(A(end-1:end,:))]';end
``````

I suppose this is a prime example of how not to make algorithms. For A=2x2, n=1000 this algorithm already takes 5 seconds on my laptop, n=2000 it's almost 50 seconds! (or approximately 30s if A is a `gpuArray` thanks to my trusty Quadro 1000M)

-
I don't have a copy of Matlab. Can I run this under GNU octave? If so can you give instructions? – Digital Trauma Feb 5 at 17:06
Yes I called it Matlab because it doesn't use any Octave specific functions. Simply put it in a file called f.m and run as e.g. `f([0,1;2,3],1000)` – sanchises Feb 5 at 17:26
I see. 1) save as `f.m`. 2) Start `octave`. 3) Paste `load f.m; f([1,1,1;2,3,4],3)` into the REPL prompt - works for me. – Digital Trauma Feb 5 at 17:39
If you say so! I only use the octave online website so no idea how it should work otherwise. I'll see if I can permalink from there – sanchises Feb 5 at 18:19

# Java, 2179 bytes

Just Worked it out:- This code is on Java Language.

``````import java.util.Scanner;

public class FebonnaciMatrix {
static Scanner scan=new Scanner(System.in);

public static void main(String[] args) {

int x,y;
System.out.println("For the Array to Work Upon:- ");

System.out.println("Enter the Row:- ");
int row=scan.nextInt();
System.out.println("Enter the Column:- ");
int col=scan.nextInt();

int inpArr[][]=new int[row][col];

System.out.println("Enter the values");
inpArr=inpValues(row,col);

System.out.println("The Input Array is:- ");
display(inpArr,row,col);

System.out.println("Input the Array size of Febonacci Array ");

System.out.println("Enter the Row");
int frow=scan.nextInt();
System.out.println("Enter the Column");
int fcol=scan.nextInt();

int febArr[][]=new int[frow][fcol];
febArr=copyValue(inpArr,febArr,row,col);

for(x=0;x<row;x++)
{
for(y=col;y<fcol;y++)
febArr[x][y]=febArr[x][y-2]+febArr[x][y-1];
}

for(x=row;x<frow;x++)
{
for(y=0;y<fcol;y++)
febArr[x][y]=febArr[x-2][y]+febArr[x-1][y];
}

System.out.println();
System.out.println("The Febonacci Array:-");
display(febArr,frow,fcol);
}

static void display(int[][] arr,int row,int col)
{
int x,y;
for(x=0;x<row;x++)
{
for(y=0;y<col;y++)
System.out.print(arr[x][y]+"\t");
System.out.println();
}
}

static int[][] inpValues(int row,int col)
{
int arr[][]=new int[row][col];
int x,y;
for(x=0;x<row;x++)
{
for(y=0;y<col;y++)
{
System.out.print("Enter the value:- ");
arr[x][y]=scan.nextInt();
}
}
return arr;
}

static int[][] copyValue(int[][] old, int[][] ne, int row,int col)
{
int x,y;
for(x=0;x<row;x++)
{
for(y=0;y<col;y++)
ne[x][y]=old[x][y];

}
return ne;
}

}
``````
-
Welcome to Programming Puzzles and Code Golf! The question is tagged code-golf which means that answers are competing to be written in the shortest amount of code possible (in bytes). Your answer may well solve the problem, but I see little attempt to "golf" the code (i.e. make it as short as possible). There are plenty of trivial opportunities to do this with your code, e.g. variables with 1-char names, and removal of unnecessary whitespace. Beyond that you can read these tips, specifically for java – Digital Trauma Feb 5 at 21:11
... Have a look at the tag-wiki for code-golf, especially the How should I answer a code golf? Any hints? section. Also note that java is notoriously hard to golf down to short code, in comparison with many other languages. This shouldn't dissuade you though - if you have a well-golfed java answer, it is likely to be quite popular, even if it is longer than all the other answers. Don't be put off by all the mind-bendingly short esolang answers - this community tends to be good at taking language handicaps into account. – Digital Trauma Feb 5 at 21:18
@DigitalTrauma- Thanks... for helping me out as a newbee to this... I'll surely go through the links and come up with a new code... – Dhruv Govila Feb 5 at 21:21
Since you're a new user, I took the liberty of editing your answer for better formatting. In particular a) a clear title stating language and number of bytes, b) code formatting of your code. On all stackexchange sites, code formatting is easy - simply prefix all your code lines with 4 spaces. In fact even easier - in the edit box, select your code, then click the `{}` at the top of the edit box - this will automatically do this prefixing. – Digital Trauma Feb 5 at 21:22
Okay... I will just check it out... – Dhruv Govila Feb 5 at 21:27

# Python, 103 105 bytes

``````f=lambda n,L:f(n-1,[l+[sum(l[-2:])]for l in L])if n else L
lambda n,L:zip(*f(n,map(list,zip(*f(n,L)))))
``````

Anonymous function takes list of list and passes to recursive function `f`. Output is transposed and then passed to `f` again, then the output of the second go is re-transposed. Output is a list of tuples

Saved two bytes thanks to bakuriu

-
`n>0` could simply be `n`, since you start with a positive `n` and when you reach `0` its value is false. – Bakuriu Feb 5 at 21:44

# Perl 6,  87 73  71 bytes

``````->\c,\m{for ^c {.[+*]=[+] .[*X-1,2]for m;m.push: [map {[+] m[*X-1,2;\$_]},m[0].keys]};m}
->\c,\m{for ^c {.[+*]=[+] .[*X-1,2]for m;m[+*]=[m[*-2;*] »+«m[*-1]]};m}
->\c,\m{for ^c {.[+*]=[+] .[*X-1,2]for m;m[+*]=[m[*-2;*]Z+m[*-1;*]]};m}
``````
``````-> \c, \m {
for ^c { # 0 ..^ c

# each row
.[+*]                            # new column at the end of row (\$_)
= [+] .[ * X- 1,2 ]        # add up the last two entries in row (\$_)
for m; # for every row

# too bad this was longer than the above code
# m[*;+*]=map *+*,m[*;*-2,*-1]

# each column
m[ +* ]                 # add new row
= [             # make it an Array rather than a List
m[ *-2; * ] # the second to last row
m[ *-1 ]    # the last row
]
};

m # return the result
}
``````

### Usage:

``````use v6.c;
# give it a lexical name
my &code = ->\c,\m{ … }

my @return = code 3,[[1,1,1],[2,3,4]];

put '[ ', \$_».fmt('%2d'), ' ]' for @return;

put '';

put @return.perl ~~ {S:g/' '//};
``````
``````[  1  1  1  2  3  5 ]
[  2  3  4  7 11 18 ]
[  3  4  5  9 14 23 ]
[  5  7  9 16 25 41 ]
[  8 11 14 25 39 64 ]

[[1,1,1,2,3,5],[2,3,4,7,11,18],[3,4,5,9,14,23],[5,7,9,16,25,41],[8,11,14,25,39,64]]
``````
-
Pasting this into `perl6` gives me some errors. I'm a perl novice - what am I doing wrong? – Digital Trauma Feb 5 at 17:04
@DigitalTrauma I'm sorry I should have written the usage as `my &code = ->\c,\m{ … }` to make it clear that the `->\c,\m{ … }` needs to be replaced with the code above. I usually use an implicit `\$_` or `@_` or explicit placeholder parameters `\$^a` because they tend to be shorter. I just didn't think about it. Also make sure that you are using a new enough version ( `\$*PERL.compiler.version !before 2015.12` ) – Brad Gilbert b2gills Feb 5 at 22:00
@DigitalTrauma You can also go on the #perl6 channel on freenode.net and use camelia (like this) to run the code (precede lines with `m: ` and a space) You can also msg camelia directly – Brad Gilbert b2gills Feb 5 at 22:44