2
\$\begingroup\$

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ How is input/output handled (stdin, file, etc)? Any test cases? \$\endgroup\$ – Kyle Kanos Jul 23 '14 at 2:02
  • 1
    \$\begingroup\$ 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"? \$\endgroup\$ – Jerry Jeremiah Jul 23 '14 at 3:07
3
\$\begingroup\$

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]
\$\endgroup\$
  • 1
    \$\begingroup\$ I have edited the question, so you cannot use built-in libraries to do matrix operations, you need to implement your own... \$\endgroup\$ – mmk Jul 23 '14 at 10:54
1
\$\begingroup\$

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

Matlab (157) (155)(151)

I am not sure which parts of the program count for the score? (Currently only counting the algorithm, just 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
\$\endgroup\$
  • \$\begingroup\$ I have edited the question, so you cannot use built-in libraries to do matrix operations, you need to implement your own... \$\endgroup\$ – mmk Jul 23 '14 at 10:53
  • \$\begingroup\$ Yes, only the size of the algorithm needs to be counted \$\endgroup\$ – mmk Jul 23 '14 at 10:53
  • \$\begingroup\$ Well that was a significant change added somewhat late, but I changed it now=) \$\endgroup\$ – flawr Jul 23 '14 at 11:53

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.