Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. Join them; it only takes a minute:

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

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)

share|improve this question
2  
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. – Martin Ender Feb 9 at 14:20
    
@MartinBüttner: I get 6, 22560, 10160459763342013440, ... which matches A055165. – Charles Feb 9 at 18:36
    
@Charles odd, I'll check my code – Martin Ender Feb 9 at 18:43
    
@MartinBüttner: Possibly we're just computing two different things? – Charles Feb 9 at 18:49

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.

share|improve this answer

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

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 *)
share|improve this answer
    
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. :) – Martin Ender Feb 9 at 12:38
    
@MartinBüttner I failed. :( – njpipeorgan Feb 9 at 12:55
1  
You can avoid the [[1,1]] with Tr and the Nest with //.: Tr[#//.l:{_,__}:>BlockMap[Det,l,{2,2}]]& – Martin Ender Feb 9 at 21:15
    
@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 – njpipeorgan Feb 9 at 23:08
    
feel free to use my solution to update your answer – Martin Ender Feb 9 at 23:09

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.

share|improve this answer

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.

share|improve this answer

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

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.

share|improve this answer

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.