Take the 2-minute tour ×
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.

Create an algorithm that uses Cramer's Rule (with determinants of matrices) to solve for the solutions of a system of linear equations. The code should work for an "n" number of variables.

You may use whatever data structure you want to hold the matrix and return the result

Note: Also, consider that a possible system can have no solutions and may have infinitely many solutions :), so, your solution should take account of this...

If this is the case, just print out or return "none" or "infinitely many".

Since this is code golf, smallest code wins...

EDIT: To make this more challenging, you cannot use a language's built-in matrix operations libraries.

Also, your algorithm DOES NOT have to deal how to get the input, just how to process the input and return the correct output. As said before, you can store this input in whatever structure.

share|improve this question
1  
How is input/output handled (stdin, file, etc)? Any test cases? –  Kyle Kanos Jul 23 at 2:02
1  
This would be easy in array based languages like APL, J and K. And if we are allowed libraries probably easy to do in any language. Maybe you should say "no built in or library based matrix operations"? –  Jerry Jeremiah Jul 23 at 3:07

3 Answers 3

Mathematica 40

Setting up the problem in your reference link:

Mathematica graphics

s = {{2, 1, 1}, {1, -1, -1}, {1, 1, 1}};
r = {3, 0, 0};

The algorithm (spaces not needed):

i = 1; (a = s; a[[All, i++]] = r; Det@a/Det@s) & /@ r

result:

{1, -2, 3}

If the system has infinite solutions it returns Indeterminate or ComplexInfinite

Please note that Mathematica can solve linear systems natively. Among other possible ways you could use:

s~LinearSolve~r

or

Solve[s.{x,y,z}==r]
share|improve this answer
    
I have edited the question, so you cannot use built-in libraries to do matrix operations, you need to implement your own... –  mmk Jul 23 at 10:54

Python3 - 310

def det(m,n):
 if n==1: return m[0][0]
 z=0
 for r in range(n):
  k=m[:]
  del k[r]
  z+=m[r][0]*(-1)**r*det([p[1:]for p in k],n-1)
 return z
w=len(t)
d=det(h,w)
if d==0:r=[]
else:r=[det([r[0:i]+[s]+r[i+1:]for r,s in zip(h,t)],w)/d for i in range(w)]
print(r)

The determinant is calculated using Laplace's formula, nothing fancy :)

Supply the matrix and the known terms respectively in an array named h and t, like this

h = [[2, 1, 1],[1, -1, -1],[1, 2, 1]]
l = [3, 0, 0]

Which gives

[1.0, -2.0, 3.0]
share|improve this answer

Matlab (157) (155)(151)

I am not sure which parts of the program count for the score? (Currently only counting the algorithm as @belisarius did.)

%input
a = [1,2,3;4,5,6;7,4,2]
b = [1;3;4]

%algo
%%functiondefinition
function e = d(a)
z=length(a)
if z==1
    e=a
else
    e=0
    w=2:z
    for i=1:z
        e=e-(-1)^i*a(1,i)*d([a(w,1:i-1),a(w,i+1:end)])
    end
end
%%main
for i=1:numel(b)
    c=a
    c(:,i)=b
    x(i)=d(c)/d(a)
end

%output
if any(isinf(d))
    'no solutions'
elseif ~d(a)
    'infinite solutions'
end
x

Matlab can of course solve linear systems natively:

a\b
share|improve this answer
    
I have edited the question, so you cannot use built-in libraries to do matrix operations, you need to implement your own... –  mmk Jul 23 at 10:53
    
Yes, only the size of the algorithm needs to be counted –  mmk Jul 23 at 10:53
    
Well that was a significant change added somewhat late, but I changed it now=) –  flawr Jul 23 at 11:53

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.