10
\$\begingroup\$

Write a program to solve a series of linear equations as short as possible. It must solve arbitrary number of equations problems. They can inputted however you like, coefficients of augmented matrix is probably the easiest. The program doesn't have to handle non-integer coefficients or solutions. No degenerate or invalid cases will be tested. The program must output the value of each variable or reduced row echelon form.

No equation solving libraries, matrix functions, or any way to automatically solve is allowed. You can simulate matrices with arrays or lists.

Example input (or equivalent):

m={{2,1,-1,8},{-3,-1,2,-11},{-2,1,2,-3}}

This represents 2x+y-z=8, -3x-y+2z=-11, -2x+y+2z=-3

Example output (or equivalent):

{2,3,-1}

This represents x=2, y=3, z=-1

\$\endgroup\$
  • 2
    \$\begingroup\$ Can the coefficients of the variables and the constant terms be separated into two arrays in the input? \$\endgroup\$ – ace Mar 1 '14 at 21:58
  • \$\begingroup\$ @ace yes, that's fine \$\endgroup\$ – qwr Mar 1 '14 at 22:08
  • 1
    \$\begingroup\$ What exactly are you saying by degenerated cases? I guess that you are refering to all of those cases: 1) Malformed input; 2) Things like 0x=0 or 0x=5; 4) Cases where the number of equations is different than the number of variables; 5) Contradictory cases like x+5y=7, x+5y=8; 6) Cases without linear independency, like x+3y=6, 2x+6y=12. Am I right? \$\endgroup\$ – Victor Stafusa Mar 1 '14 at 22:40
  • \$\begingroup\$ @Victor Yes, any input that has any ambiguity at all or isn't solvable. \$\endgroup\$ – qwr Mar 1 '14 at 22:53
  • \$\begingroup\$ What about cases which aren't degenerate but are ill-conditioned? (Or, in other words, what kind of pivoting is required?) \$\endgroup\$ – Peter Taylor Mar 1 '14 at 23:43
3
\$\begingroup\$

Python 169 166

Implementation

def s(a):
 if a:b=a[0];r=s([[x-1.*y*b[0]/r[0]for x,y in zip(b[1:],r[1:])]for r in a[1:]]);return[round((b[-1]-sum(x*y for x,y in zip(b[1:-1],r)))/b[0])]+r
 return[]

Demo

>>> arr=[[2, 1, -1, 8], [-3, -1, 2, -11], [-2, 1, 2, -3]]
>>> s(arr)
[2.0, 3.0, -1.0]

Note

If you are OK with the float approximation, then you can remove the round function call and further golf to 159 characters

\$\endgroup\$
7
\$\begingroup\$

APL, 1 char

I know it doesn't fit the (revised) requirements, but it's too good not to post:

Symbol "domino" (division ÷ inside a rectangle) performs matrix division, therefore it can solve any system of linear equations. You just have to put it between the constant term vector and the matrix with the other terms:

      8 ¯11 ¯3 ⌹ ⊃(2 1 ¯1)(¯3 ¯1 2)(¯2 1 2)
2 3 ¯1

(if you want to try it on TryApl, is )

\$\endgroup\$
4
\$\begingroup\$

Javascript (284 181) - Gauss Elimination method

function f(A){l=A.length;d=1;for(i=0;i+1;i+=d){v=A[i][i];for(k=0;k<l+1;k++)A[i][k]/=v;for(j=i+d;A[j];j+=d)for(k=0,w=A[j][i];k<l+1;k++)A[j][k]-=w*A[i][k];if(i==l-d)d=-1,i=l}return A}

Test

f([[2,1,-1,8],[-3,-1,2,-11],[-2,1,2,-3]]);

=> [[1,0,0,2],[0,1,0,3],[-0,-0,1,-1]]

The returned array combine the identity matrix and the solution.

\$\endgroup\$
  • \$\begingroup\$ You can save couple more characters. \$\endgroup\$ – MarcinJuraszek Mar 2 '14 at 1:16
  • \$\begingroup\$ Instead of l=A.length;for(i=0;i<l;i++) use for(i=0;i<l=A.length;i++). \$\endgroup\$ – Victor Stafusa Mar 2 '14 at 1:22
  • \$\begingroup\$ Instead of for(i=l-1;i>=0;i--) use for(i=l;--i;). \$\endgroup\$ – Victor Stafusa Mar 2 '14 at 1:25
  • \$\begingroup\$ You can also move w=A[j][i] into for() and skip {} around. \$\endgroup\$ – MarcinJuraszek Mar 2 '14 at 5:24
  • \$\begingroup\$ Thanks everyone, I managed to merge forward and backward steps in one single step, saving a hundred chars and some of your tips are not valid anymore. (except @MarcinJuraszek tip) \$\endgroup\$ – Michael M. Mar 2 '14 at 9:07
3
\$\begingroup\$

This answer no longer fits the question after the rule change as it uses a matrix function.*

Sage, 32

~matrix(input())*vector(input())

Sample input:

[[2, 1, -1], [-3, -1, 2], [-2, 1, 2]]
[8, -11, -3]

Sample output:

(2, 3, -1)

*Arguably, matrix() is a typecast, not a function (running import types; isinstance(matrix, types.FunctionType) gives False). Also, the ~ and * are operators, not functions.

\$\endgroup\$
  • \$\begingroup\$ I've updated the rules. The code must handle different number of equations and you now can't use matrix functions. \$\endgroup\$ – qwr Mar 1 '14 at 22:01
3
\$\begingroup\$

Java - 522 434 228 213 chars

Solves by systematically checking all possible integer n-tuples by direct multiplication until one is found that works.

Function takes augmented matrix, A, trial solution vector, x, and dimension, n, as input - outputs solution vector, x. Note that the vector x is actually one larger than the dimension to help step through possible solutions. (If I declared variables A,x,n,j,k,s as instance variables, the function would be 31 chars shorter - for a total of 182, but that feels like bending the rules too far.)

int[]Z(int[][]A,int[]x,int n){int j,k,s;for(;;){for(j=0;j<n;j++){for(k=s=0;k<n;s+=A[j][k]*x[k++]);if(s!=A[j][n])j+=n;}if(j==n)return x;for(j=0;j<=n;j++)if(x[j]!=x[n]||j==n){x[j]++;for(k=0;k<j;x[k++]=-x[n]);j=n;}}}

Program for testing (somewhat ungolfed):

import java.util.*;
class MatrixSolver{
    public MatrixSolver() {
        Scanner p=new Scanner(System.in); //initialize everything from stdin
        int j,k,n=p.nextInt(),A[][]=new int[n][n+1],x[]=new int[n+1];
        for(j=0;j<n;j++)for(k=0;k<=n;A[j][k++]=p.nextInt());
        x=Z(A,x,n); //call the magic function
        for(j=0;j<n;j++) System.out.print(x[j]+" "); //print the output
    }
    public static void main(String[]args){
        new MatrixSolver();
    } 

    int[]Z(int[][]A,int[]x,int n){
        int j,k,s;
        for(;;){
            for(j=0;j<n;j++){ //multiply each row of matrix by trial solution and check to see if it is correct
                for(k=s=0;k<n;s+=A[j][k]*x[k++]);
                if(s!=A[j][n])j+=n;
            }
            if(j==n)return x; //if it is correct return the trial solution
            for(j=0;j<=n;j++)if(x[j]!=x[n]||j==n){//calculate the next trial solution
                x[j]++;
                for(k=0;k<j;x[k++]=-x[n]);
                j=n;
            }
        }
    }
}

Program takes input from stdin as space separated integers as follows: first, the dimension of the problem, second, the entries of the augmented matrix by row.

Sample run:

$java -jar MatrixSolver.jar
3 2 1 -1 8 -3 -1 2 -11 -2 1 2 -3
2 3 -1 

I shaved several characters by following Victor's advice about loops and "public", storing the RHS in the augmented matrix instead of separately, and adding an extra entry to my trial solution to simplify the generation of each new trial solution. The OP also said that a function is enough - no need to count the entire program.

\$\endgroup\$
  • \$\begingroup\$ while(true){f=0;for(j=0;j<n;j++) can be replaced by while(true){for(f=j=0;j<n;j++). Further your class don't need to be public. For-loops with only one instruction in the body don't need the curly-braces. \$\endgroup\$ – Victor Stafusa Mar 2 '14 at 6:03
  • \$\begingroup\$ I think that for(j=0;j<n;j++){for(k=0;k<n;k++){A[j][k]=p.nextInt();}b[j]=p.nextInt();} can be replaced by for(j=0;j<n;b[j++]=p.nextInt())for(k=0;k<n;)A[j][k++]=p.nextInt(); \$\endgroup\$ – Victor Stafusa Mar 2 '14 at 6:06
  • \$\begingroup\$ @Victor Thanks, I made those, and other, changes. \$\endgroup\$ – Wally Mar 2 '14 at 7:37
  • \$\begingroup\$ while(true) can be changed to for(;;) \$\endgroup\$ – ace Mar 2 '14 at 9:05
  • \$\begingroup\$ @ace thanks - changed that and a couple other things and shaved 15 chars. \$\endgroup\$ – Wally Mar 2 '14 at 23:39

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.