17
\$\begingroup\$

The determinant of a 2 by 2 matrix

a b
c d

is given by ad - bc.

Given a matrix of digits with dimensions 2n by 2n, n ≥ 1, output the result obtained by recursively computing the determinant of each 2 by 2 sub-block until we reach a single number.

For example, given the input

3 1 4 1
5 9 2 6
5 3 5 8
9 7 9 3

After one step, we obtain:

(3*9 - 1*5)    (4*6 - 1*2)    =    22  22
(5*7 - 3*9)    (5*3 - 8*9)         8  -57

And iterating once more, we get:

(22*-57 - 22*8) = -1430

Hence, the output should be -1430.

Rules

  • The elements of the matrix will always be single digit integers, i.e. 0 to 9.
  • You may take input in any convenient list or string format, as long as no preprocessing of data is done. Since the matrix is always square, you may take input as a single 1D list instead of a 2D list if you wish.
  • Input can be via function input, STDIN, command-line argument or closest alternative.
  • Output should be a single integer to function output, STDOUT or closest alternative. You may not output the single integer in a list or matrix.
  • You may use builtin determinant and matrix manipulation methods if your language happens to support them.
  • Your algorithm must work in theory for any valid input.
  • Standard rules apply.

Test cases

The following test cases are given as Python-style lists:

[[1,0],[0,1]] -> 1
[[1,9],[8,4]] -> -68
[[0,1,2,3],[4,5,6,7],[8,9,0,1],[2,3,4,5]] -> 40
[[3,1,4,1],[5,9,2,6],[5,3,5,8],[9,7,9,3]] -> -1430
[[9,0,0,9],[0,9,9,0],[9,0,9,0],[0,9,0,9]] -> 13122
[[1,0,0,0,0,0,0,0],[2,1,0,0,0,0,0,0],[3,2,1,0,0,0,0,0],[4,3,2,1,0,0,0,0],[5,4,3,2,1,0,0,0],[6,5,4,3,2,1,0,0],[7,6,5,4,3,2,1,0],[8,7,6,5,4,3,2,1]] -> 1
[[7,1,0,5,8,0,1,5],[9,9,6,6,1,2,4,8],[4,8,7,3,8,7,4,7],[4,6,1,9,7,0,1,7],[7,6,7,1,9,4,1,6],[8,0,0,8,5,5,9,9],[4,6,4,8,9,4,8,6],[9,0,8,7,6,2,1,5]] -> 2937504
[[1,2,3,4,5,6,7,8],[2,3,4,5,6,7,8,1],[3,4,5,6,7,8,1,2],[4,5,6,7,8,1,2,3],[5,6,7,8,1,2,3,4],[6,7,8,1,2,3,4,5],[7,8,1,2,3,4,5,6],[8,1,2,3,4,5,6,7]] -> -10549504
[[1,1,1,0,1,1,1,1,1,1,1,1,1,1,1,0],[0,1,1,1,1,0,0,1,0,1,1,1,1,1,1,0],[1,1,0,1,1,0,1,1,1,1,1,1,1,1,1,0],[0,1,1,1,1,0,0,0,0,1,1,1,1,1,0,1],[1,0,1,0,1,1,1,0,0,1,1,1,1,0,1,0],[0,0,1,1,1,0,1,1,1,1,1,1,1,0,0,0],[1,1,1,1,1,0,1,0,1,1,1,1,1,1,1,1],[1,1,0,1,1,1,1,1,1,1,1,1,0,1,0,1],[1,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1],[0,1,1,1,1,1,1,1,1,0,0,1,0,1,0,1],[1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1],[1,1,0,1,1,0,1,1,1,1,1,0,0,1,1,0],[1,1,1,1,1,1,1,1,0,1,1,1,1,1,1,0],[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1],[1,0,1,0,0,1,0,1,0,1,1,1,1,1,0,1],[1,1,1,1,1,1,1,1,1,0,0,1,1,1,0,1]] -> -8

(Thanks to @MartinBüttner for help with this challenge)

\$\endgroup\$
  • 3
    \$\begingroup\$ Fun fact: I ran some experiments on this and there is a surprisingly large number of binary matrices with non-zero recursive determinant. For sizes 2x2, 4x4, 8x8, 16x16, we get 6, 16488, 2229617029168687104, 3349795881591711813037585032680117995553655026185547430764970842694019448832 matrices with non-zero determinant which corresponds to 37.5%, 25.1587%, 12.0868%, 2.89294%, respectively. \$\endgroup\$ – Martin Ender Feb 9 '16 at 14:20
  • \$\begingroup\$ @MartinBüttner: I get 6, 22560, 10160459763342013440, ... which matches A055165. \$\endgroup\$ – Charles Feb 9 '16 at 18:36
  • \$\begingroup\$ @Charles odd, I'll check my code \$\endgroup\$ – Martin Ender Feb 9 '16 at 18:43
  • \$\begingroup\$ @MartinBüttner: Possibly we're just computing two different things? \$\endgroup\$ – Charles Feb 9 '16 at 18:49
  • \$\begingroup\$ @Charles Consider the matrix [1,0,1,0;1,1,1,1;1,1,1,1;0,0,0,1]. The full determinant of it is zero since it has two identical rows. This one is therefore a singular (meaning non-invertible) 4×4 matrix, so it is not counted by A055165. However, the "recursive" determinant discussed here is 1*1-1*0==1. In the opposite direction, the matrix [0,0,0,1;1,0,0,0;0,1,0,0;0,0,1,0] has "recursive" determinant 0*0-0*0==0. However, its full determinant must be non-zero because its rows is just the rows of the identity matrix in another order; and it is counted by A055165. \$\endgroup\$ – Jeppe Stig Nielsen Oct 10 '17 at 22:05

11 Answers 11

8
\$\begingroup\$

J, 21 25 bytes

0{0{(_2(_2-/ .*\|:)\])^:_

Usage:

   ]input=.(3,1,4,1),(5,9,2,6),(5,3,5,8),:(9,7,9,3)
3 1 4 1
5 9 2 6
5 3 5 8
9 7 9 3
   (0{0{(_2(_2-/ .*\|:)\])^:_) input
_1430

At every step we cut up the matrix to 2-by-2's and compute each ones determinant resulting in the next step's input matrix. We repeat this process until the result doesn't change (the final element is the determinant itself). We convert the final result to a scalar with 0{0{.

Try it online here.

\$\endgroup\$
  • \$\begingroup\$ Tried using Cut's tiling function to do this, but wasn't able to golf it as far as your version. 29 bytes: (2 2$2)&(-/ .*;._3^:(2^.#@])) Try it online! \$\endgroup\$ – Jonah Oct 13 '17 at 4:19
4
\$\begingroup\$

Mathematica, 52 40 bytes

Thanks to Martin Büttner for saving 12 bytes.

Tr[#//.l:{_,__}:>BlockMap[Det,l,{2,2}]]&

Explanation

BlockMap[f,expr,n] split expr into sublists of size n and map f on every sublists. BlockMap[Det,#,{2,2}]& split the input array into 2*2 blocks and calculate their determinants.


Test case

%[{{3,1,4,1},{5,9,2,6},{5,3,5,8},{9,7,9,3}}]
(* -1430 *)
\$\endgroup\$
  • 1
    \$\begingroup\$ I wrote a reference implementation in Mathematica while discussing the challenge idea with Sp3000 and it's 40 bytes. It's pretty similar to yours though, so I'll give you some time to find it yourself if you like. :) \$\endgroup\$ – Martin Ender Feb 9 '16 at 12:38
  • \$\begingroup\$ @MartinBüttner I failed. :( \$\endgroup\$ – njpipeorgan Feb 9 '16 at 12:55
  • 1
    \$\begingroup\$ You can avoid the [[1,1]] with Tr and the Nest with //.: Tr[#//.l:{_,__}:>BlockMap[Det,l,{2,2}]]& \$\endgroup\$ – Martin Ender Feb 9 '16 at 21:15
  • \$\begingroup\$ @MartinBüttner Actually, I came up with //. idea when reading the answer in J, but stuck in finding a good way to match the array. :P \$\endgroup\$ – njpipeorgan Feb 9 '16 at 23:08
  • \$\begingroup\$ feel free to use my solution to update your answer \$\endgroup\$ – Martin Ender Feb 9 '16 at 23:09
3
\$\begingroup\$

Jelly, 20 17 bytes

s€2s2U×¥/€ḅ-µL¡SS

Try it online! or verify all test cases at once.

How it works

s€2s2U×¥/€ḅ-µL¡SS  Main link. Input: M (matrix)

s€2                Split each row of M into pairs.
   s2              Split the result into pairs of rows.
        /€         Reduce each pair...
       ¥             by applying the following, dyadic chain:
     U                 Reverse each pair of the left argument (1st row).
      ×                Multiply element-wise with the right argument (2nd row).
          ḅ-       Convert each resulting pair from base -1 to integer.
                   This maps [a, b] -> b - a.
            µ      Turn the previous links into a monadic chain. Begin a new one.
             L     Yield the length of the input.
              ¡    Execute the previous chain L times.
                   log2(L) times would do, but who's counting?
               SS  Sum twice to turn the resulting 1x1 matrix into a scalar.
\$\endgroup\$
2
\$\begingroup\$

Haskell, 93 86 bytes

EDIT: Thanks to @Laikoni for shortening this a whole 7 bytes!

f[[a,b],[c,d]]=a*d-b*c
f m|let l=[take,drop]<*>[div(length m)2]=f[f.($b<$>m)<$>l|b<-l]

I didn't know you could put a let statement before the = and I've never gotten used to those monad operators. Thanks again @Laikoni

Old version:

f[[a,b],[c,d]]=a*d-b*c
f m=f[[f$a$map b m|a<-l]|b<-l]where h=length m`div`2;l=[take h,drop h]

Try it online!

This is a function that recurs on itself in two different ways. First the pattern matching catches the the base case: a 2x2 matrix and it does the calculation. I use this to do the calculation in the recursive case by calling the function with a 2x2 matrix I generate that has the recursive solutions in it. That matrix is generated by iterating twice over an array of functions that each chop a list in half. I apply it to rows with a simple call and apply it to columns using map.

\$\endgroup\$
  • \$\begingroup\$ Instead of where h=length m`div`2;l=[take h,drop h], you can use f m|let l=[take,drop]<*>[length m`div`2]=. map b m can be b<$>m, and [f$a$b<$>m|a<-l] can be further shortened to f.($b<$>m)<$>l. Altogether 86 bytes: [tio.run/… Try it online!] \$\endgroup\$ – Laikoni Oct 11 '17 at 12:35
1
\$\begingroup\$

Python, 166 bytes

def f(m):l=len(m)/2;g=lambda x,y:[(s[:l],s[l:])[x]for s in(m[:l],m[l:])[y]];return f(g(0,0))*f(g(1,1))-f(g(0,1))*f(g(1,0)) if l>1 else m[0][0]*m[1][1]-m[1][0]*m[0][1]

This passes all the test cases provided. m has to be a 2D array (like in the test cases), g selects the sub matrix.

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

Pyth, 26

M-F*VG_HhhumgMCcR2dcG2llQQ

Test Suite

This has two parts: M-F*VG_H redefines the function g to calculate the determinant of a two by two matrix. This saves bytes even though we only use it once because it unpacks the two rows.

The other part is a large reduce statement that we call log_2( len( input() ) ) times. Unfortunately, performing a step in the reduction on a 1 by 1 matrix causes the result to be wrapped in a list, so we don't get a fixed point. The reduce is mostly just splitting up the matrix to get 2 by 2 matrices and then applying g.

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

MATL, 26 30 bytes

`tnX^teHHhZC2Ih2#Y)pwp-tnq

Input is a 2D array with rows separated by ;, that is,

[3 1 4 1; 5 9 2 6; 5 3 5 8; 9 7 9 3]

Try it online!

`             % do...while loop
  tnX^te      %   reshape into square matrix. Implicitly asks for input the first time
  HHhZC       %   transform each 2x2 block into a column
  2Ih2#Y)     %   push matrix with rows 2,3, and also matrix with remaining rows (1,4)
  pwp-        %   multiplications and subtraction to compute the 2x2 determinants
  tnq         %   condition of do...while loop: is number of elements greater than 1?
              % implicitly end loop
              % implicitly display
\$\endgroup\$
1
\$\begingroup\$

Perl 5, 120 + 1 (-a) = 121 bytes

while($#F){@r=();for$i(@o=0..($l=sqrt@F)/2-1){push@r,$F[$k=$i*$l*2+2*$_]*$F[$k+$l+1]-$F[$k+$l]*$F[$k+1]for@o}@F=@r}say@F

Try it online!

Takes the input as a list of space separated numbers.

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

ES6, 91 bytes

(a,x=0,y=0,w=a.length)=>(w>>=1)?f(a,x,y,w)*f(a,x+w,y+w,w)-f(a,x,y+w,w)*f(a,x+w,y,w):a[x][y]

Straightforward recursive solution.

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

R, 111 bytes

f=function(m)"if"((n=nrow(m))-2,f(matrix(c(f(m[x<-1:(n/2),x]),f(m[y<-x+n/2,x]),f(m[x,y]),f(m[y,y])),2)),det(m))

Try it online!

Takes input as an R matrix (which is converted by the function in the header).

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

Groovy, 221 189 bytes (At this point, could've used Java)

f={x->b=x.size();c=b/2-1;a=(0..c).collect{i->(0..c).collect{j->z=x.toList().subList(i*2,i*2+2).collect{it.toList().subList(j*2,j*2+2)};z[0][0]*z[1][1]-z[0][1]*z[1][0];}};a.size()==1?a:f(a)}

Old crappy version, which might as well be Java (221 bytes):

f={x->b=x.size();a=new int[b/2][b/2];for(i=0;i<b-1;i+=2){for(j=0;j<b-1;j+=2){z=x.toList().subList(i,i+2).collect{it.toList().subList(j,j+2)};a[(int)(i/2)][(int)(j/2)]=z[0][0]*z[1][1]-z[0][1]*z[1][0];}};a.size()==1?a:f(a)}

Ungolfed code:

f=
{x->
  b=x.size();
  int[][]a=new int[b/2][b/2];
  for(i=0;i<b-1;i+=2) {
    for(j=0;j<b-1;j+=2) {
      z=x.toList().subList(i,i+2).collect{
        it.toList().subList(j,j+2)
      };
      a[(int)(i/2)][(int)(j/2)]=z[0][0]*z[1][1]-z[0][1]*z[1][0];
    }
  }
  a.size()==1
    ?
      a:f(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.