6
\$\begingroup\$
class LinearEquationSolver
{
    List<LinearEquation> rows = new List<LinearEquation>();
    decimal[] solution;

    public void AddLinearEquation(decimal result, params decimal[] coefficients)
    {
        rows.Add(new LinearEquation(result, coefficients));
    }

    public IList<decimal> Solve()       //Returns a list of coefficients for the variables in the same order they were entered
    {
        solution = new decimal[rows[0].Coefficients.Count()];

        for (int pivotM = 0; pivotM < rows.Count() - 1; pivotM++)
        {
            int pivotN = rows[pivotM].IndexOfFirstNonZero;

            for (int i = pivotN + 1; i < rows.Count(); i++)
            {
                LinearEquation rowToReduce = rows[i];
                decimal pivotFactor = rowToReduce[pivotN] / -rows[pivotM][pivotN];
                rowToReduce.AddCoefficients(rows[pivotM], pivotFactor);
            }
        }

        while (rows.Any(r => r.Result != 0))
        {
            LinearEquation row = rows.FirstOrDefault(r => r.NonZeroCount == 1);
            if (row == null)
            {
                break;
            }

            int solvedIndex = row.IndexOfFirstNonZero;
            decimal newSolution = row.Result / row[solvedIndex];

            AddToSolution(solvedIndex, newSolution);
        }

        return solution;
    }

    private void AddToSolution(int index, decimal value)
    {
        foreach (LinearEquation row in rows)
        {
            decimal coefficient = row[index];
            row[index] -= coefficient;
            row.Result -= coefficient * value;
        }

        solution[index] = value;
    }

    private class LinearEquation
    {
        public decimal[] Coefficients;
        public decimal Result;

        public LinearEquation(decimal result, params decimal[] coefficients)
        {
            this.Coefficients = coefficients;
            this.Result = result;
        }

        public decimal this[int i]
        {
            get { return Coefficients[i]; }
            set { Coefficients[i] = value; }
        }

        public void AddCoefficients(LinearEquation pivotEquation, decimal factor)
        {
            for (int i = 0; i < this.Coefficients.Count(); i++)
            {
                this[i] += pivotEquation[i] * factor;
                if (Math.Abs(this[i]) < 0.000000001M)    //Because sometimes rounding errors mean it's not quite zero, and it needs to be
                {
                    this[i] = 0;
                }
            }

            this.Result += pivotEquation.Result * factor;
        }

        public int IndexOfFirstNonZero
        {
            get
            {
                for (int i = 0; i < Coefficients.Count(); i++)
                {
                    if (this[i] != 0) return i;
                }
                return -1;
            }
        }

        public int NonZeroCount
        {
            get
            {
                int count = 0;
                for (int i = 0; i < Coefficients.Count(); i++)
                {
                    if (this[i] != 0) count++;
                }
                return count;
            }
        }
    }
}

Are there any edge-cases I've missed? Is there a better way to handle potential rounding errors than just checking if a value is close to zero and zeroing it if it is? Is it overkill to use Decimals like this?

Here's a test program:

class Program
{
    static void Main(string[] args)
    {
        LinearEquationSolver test = new LinearEquationSolver();

        test.AddLinearEquation(5, 1, 2, 1, -1);
        test.AddLinearEquation(16, 3, 2, 4, 4);
        test.AddLinearEquation(22, 4, 4, 3, 4);
        test.AddLinearEquation(15, 2, 0, 1, 5);
        var result = test.Solve();

        foreach (var asdf in result)
        {
            Console.Write(asdf);
        }

        Console.ReadKey();
    }
}
\$\endgroup\$
1
  • 4
    \$\begingroup\$ In my opinion even when testing you should give variables meaningful names, otherwise you will develop a bad habit which might be hard to overcome. \$\endgroup\$ Jul 8, 2016 at 7:42

1 Answer 1

3
\$\begingroup\$

Enumerable.Count() vs count access

One problem that slows your program's performance is that you call

Coefficients.Count()

In a few places while you are using array instead of an IEnumerable<T> where this is the only way to count the elements and as you can see this is a method rather than being a property. Instead you should simply call Coefficients.Length.

Edit

As @t3chb0t pointed in the comments and discussed here C# will simply return the Count property of the collection even when you call the method .Count() which means Coefficients.Count() & Coefficients.Length are almost equivalent in performance since the method has to do a type checking.

Nevertheless when possible, you should always prefer using your collection's specific functions and properties, rather than the generic ones. In your case Coefficients.Length.

Properties vs fields

Ideally you should always use properties instead of fields

public decimal[] Coefficients;
public decimal Result;

Can become

public decimal[] Coefficients { get; }
public decimal Result { get; set; }

You properties should be as restrictive as possible the less your class exposes the better.

Indexer with public backing collection ?

This doesn't makes much sense. Usually when a class has a indexer it's used internally with a private backing collection, but you have an iterator + a public collection.

In your case I don't see any reason why would you use an indexer here the public array Coefficients is more than enough and it's a lot more readable, so you should remove that indexer and just access the array like this :

public void AddCoefficients(LinearEquation pivotEquation, decimal factor)
{
    for (int i = 0; i < this.Coefficients.Length; i++)
    {
        Coefficients[i] += pivotEquation.Coefficients[i]*factor;
        if (Math.Abs(Coefficients[i]) < 0.000000001M)
            //Because sometimes rounding errors mean it's not quite zero, and it needs to be
        {
            Coefficients[i] = 0;
        }
    }
    this.Result += pivotEquation.Result*factor;
}

Redundant this qualifier

While I do agree that this is up to a personal preference I don't like it. You don't need a single this qualifier in your code it would be better to remove it it's just extra text to read..

Expression bodied properties + LINQ

public int IndexOfFirstNonZero
{
    get
    {
        for (int i = 0; i < Coefficients.Length; i++)
        {
            if (Coefficients[i] != 0)
            {
                return i;
            }
        }
        return -1;
    }
}


public int NonZeroCount
{
    get
    {
        int count = 0;
        for (int i = 0; i < Coefficients.Length; i++)
        {
            if (Coefficients[i] != 0) count++;
        }
        return count;
    }
}

You can really shorten those get only properties using LINQ :

public int IndexOfFirstNonZero
{
    get
    {
        int value = (int) Coefficients.FirstOrDefault(x => x != 0);
        return value == default(int) ? -1 : value;
    }
}

public int NonZeroCount => Coefficients.Count(t => t != 0);
\$\endgroup\$
3
  • \$\begingroup\$ One correction. The Count extension is smart enough to not enumerate a collection if it implements the ICollection interface, see Enumerable.Count<TSource> Method If the type of source implements ICollection<T>, that implementation is used to obtain the count of elements. Otherwise, this method determines the count. \$\endgroup\$
    – t3chb0t
    Dec 25, 2016 at 12:50
  • \$\begingroup\$ And a tip: I suggest qouting the OP's code in the answer. This way it's easier to distinquish it from the review ;-) \$\endgroup\$
    – t3chb0t
    Dec 25, 2016 at 12:52
  • \$\begingroup\$ Thanks for the edit @t3chb0t I will make sure to apply that to my future answer, I will update the answer with the correction you mentioned. \$\endgroup\$
    – Denis
    Dec 25, 2016 at 12:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.