26
\$\begingroup\$

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

14 Answers 14

8
\$\begingroup\$

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
\$\endgroup\$
4
  • 1
    \$\begingroup\$ I don't know MATL, but wouldn't it be shorter to loop 2N times than to loop twice N times? \$\endgroup\$
    – Zgarb
    Feb 5, 2016 at 0:25
  • \$\begingroup\$ @Zgarb Of course! How did I miss that? Thanks!! \$\endgroup\$
    – Luis Mendo
    Feb 5, 2016 at 0:42
  • \$\begingroup\$ Does MATL have a built-in for doubling a number? \$\endgroup\$
    – Zgarb
    Feb 5, 2016 at 0:46
  • \$\begingroup\$ @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 :-) \$\endgroup\$
    – Luis Mendo
    Feb 5, 2016 at 0:49
6
\$\begingroup\$

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
\$\endgroup\$
0
3
\$\begingroup\$

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.

\$\endgroup\$
1
  • \$\begingroup\$ it still works if you remove the leading {x and trailing y} \$\endgroup\$
    – ngn
    Feb 6, 2018 at 1:50
3
\$\begingroup\$

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.

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

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
\$\endgroup\$
2
\$\begingroup\$

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
\$\endgroup\$
5
  • \$\begingroup\$ 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? \$\endgroup\$ Feb 5, 2016 at 16:59
  • \$\begingroup\$ @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. \$\endgroup\$
    – nimi
    Feb 5, 2016 at 17:16
  • 1
    \$\begingroup\$ @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. \$\endgroup\$
    – nimi
    Feb 5, 2016 at 17:20
  • \$\begingroup\$ 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. \$\endgroup\$ Feb 7, 2016 at 3:25
  • \$\begingroup\$ @DanielHill: there's a topic on meta which allows unnamed functions that depend on global helper functions. \$\endgroup\$
    – nimi
    Feb 7, 2016 at 8:59
2
\$\begingroup\$

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.
\$\endgroup\$
1
\$\begingroup\$

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.

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

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
\$\endgroup\$
1
\$\begingroup\$

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)

\$\endgroup\$
4
  • \$\begingroup\$ I don't have a copy of Matlab. Can I run this under GNU octave? If so can you give instructions? \$\endgroup\$ Feb 5, 2016 at 17:06
  • 1
    \$\begingroup\$ 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) \$\endgroup\$
    – Sanchises
    Feb 5, 2016 at 17:26
  • \$\begingroup\$ 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. \$\endgroup\$ Feb 5, 2016 at 17:39
  • \$\begingroup\$ 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 \$\endgroup\$
    – Sanchises
    Feb 5, 2016 at 18:19
1
\$\begingroup\$

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;
    }

}
\$\endgroup\$
5
  • 1
    \$\begingroup\$ 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 \$\endgroup\$ Feb 5, 2016 at 21:11
  • \$\begingroup\$ ... 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. \$\endgroup\$ Feb 5, 2016 at 21:18
  • \$\begingroup\$ @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... \$\endgroup\$ Feb 5, 2016 at 21:21
  • \$\begingroup\$ 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. \$\endgroup\$ Feb 5, 2016 at 21:22
  • \$\begingroup\$ Okay... I will just check it out... \$\endgroup\$ Feb 5, 2016 at 21:27
1
\$\begingroup\$

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

\$\endgroup\$
1
  • 1
    \$\begingroup\$ n>0 could simply be n, since you start with a positive n and when you reach 0 its value is false. \$\endgroup\$
    – Bakuriu
    Feb 5, 2016 at 21:44
1
\$\begingroup\$

APL (Dyalog Classic), 17 bytes

{⍉⍵,⊢/2+/⍵}⍣2⍣⎕⊢⎕

Try it online!

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

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]]
\$\endgroup\$
3
  • \$\begingroup\$ Pasting this into perl6 gives me some errors. I'm a perl novice - what am I doing wrong? \$\endgroup\$ Feb 5, 2016 at 17:04
  • \$\begingroup\$ @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 ) \$\endgroup\$ Feb 5, 2016 at 22:00
  • \$\begingroup\$ @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 \$\endgroup\$ Feb 5, 2016 at 22:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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