Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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 ]
share|improve this question

13 Answers 13

MATL, 13 14 15 16 20 21 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
share|improve this answer
1  
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 automatically threads to rows)
 v"1@                  then apply v to columns
share|improve this answer

Jelly, 15 13 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.

share|improve this answer

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.

share|improve this answer

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
share|improve this answer

Haskell, 67 bytes

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
share|improve this answer
    
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
1  
@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#   Vectorised addition.
  ]     e#   Wrap all rows in a new array.
  z     e#   Transpose such that the next iteration processes the other dimension.
}*
p       e#   Pretty-print.
share|improve this answer

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.

share|improve this answer

Pyth, 13 12 bytes

u+Rs>2dCGyEQ

Try it online. Test suite.

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
share|improve this answer

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)

share|improve this answer
    
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
1  
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;
    }

}
share|improve this answer
1  
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

share|improve this answer
1  
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
                »+«         # added columnwise with
                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]]
share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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