Creating an Algorithm

This is a simple guide for creating a solving algorithm for Solve4x. You don't have to know much about how the solver works to work on the algorithms that power it. They're quite separate, and it is the solver's job to decide when to use an algorithm (of course, the individual algorithms give it a little info in order to make that decision). It's not as difficult as it sounds; we're not working on Blender's soft body physics engine!

---

How an Algorithm Works

We're going to look at how an algorithm works in this section. The basics are quite simple, while advanced ones can be quite complex. First of all, every algorithm extends com.github.nateowami.solve4x.solver.Algorithm, and should be in package com.github.nateowami.solve4x.algorithm. Algorithm has two abstract methods: smarts(Algebra) and execute(Algebra). The method smarts(Algebra) needs to return an int in the range of 0 to 9. This simply tells the solver how "smart" it would be to use that algorithm in the present situation (the situation can be determined by working with the Algebra instance that is passed as an argument). Don't fret over what value to return. Some algorithms simply return 0 if the algorithm shouldn't be used, and 7 if it should. If the solver decides to use the algorithm, it will call execute(Algebra), which will create and return a new Step (com.github.nateowami.solver.Step). A Step simply represents one step in the solving of an equation. Don't worry if you don't understand all that. We can summarize with the following:

• public int smarts(Algebra) Determines if it's a good idea to use the algorithm in this situation.
• public Step execute(Algebra) Actually uses the algorithm to solve one step in the solving process.

Now you may be wondering what that Algebra type is all about. Basically, it's the ancestor of AlgebraicParticle and Equation. Now, supposing your algorithm is only interested in working with fractions, this would be rather inconvenient, as you'd have to determine the type and possibly walk the tree and find fractions to work on. Instead, you can simply write a constructor that calls super(Fraction.class). While Java's type system doesn't quite understand this, it declares what type the algorithm works on, and the solver promises to only feed it that type. You'll then have to cast it to the desired type within your execute() and smarts() methods. Enough talk; this will be much easier to understand in a simple example:

package com.github.nateowami.solve4x.algorithm;
import com.github.nateowami.solve4x.*;

public class AlgorithmName extends Algorithm{
    
    public AlgorithmName() {
        super(SomeClass.class); // Use the class that you'll work on, e.g. Fraction.class
}
    
	@Override
	public Step execute(Algebra algebra) {
        // Cast to the class we specified in the constructor
	    SomeClass someClass = (SomeClass) algebra;
        // Now do stuff...
	}

	@Override
	public int smarts(Algebra algebra) {
        // Again, cast to the class we specified in the constructor
	    SomeClass someClass = (SomeClass) algebra;
        // Now do stuff...
	}

	//Other "helper" methods can go here
}

If you want to learn a bit about the types that may be passed in you'll want to read the algebra syntax definition. You should also take a look at the documentation for AlgebraicParticle, Expression, and Term (looking at Number, Fraction, MixedNumber, Variable, and Root would be good as well!). Documentation is posted online at http://nateowami.github.io/Solve4x/doc/, but it's usually outdated, so it's better to just clone the repo and read the docs in the source. For easy reference, all the above mentioned classes are in package com.github.nateowami.solve4x.solver.

A Basic Algorithm

We've looked at the structure of an algorithm, we've looked at the types it works on, but we haven't looked at the basic processing an algorithm needs to do. One of the most important algorithms would combine like terms. Given the equation 2x-x=5, it should notice that 2x and x are like terms. Combining them it would give just plain x. The final equation then would be x=5. Note that it's just incidental that the algorithm completely solved the problem. Generally this will not be the case. When smarts() is called, it would find all like terms in the expression it's given. smarts() should return something in the range of 0-9 for the smarts, telling the solver if it's good idea to combine terms in this case. When execute() is called, the algorithm again finds like terms and simplifies the expression.

Once all like terms are added we construct a Step. The constructor is Step(Algebra). Then we explain how to solve like this: step.explain("So now I guess maybe we should consider combining like terms, huh? Start with the expression ").explain(originalExpression).explain(" and then combine all the like terms...");

Of course the explanation needs to be more detailed, but you get the idea.

Making the Solver Use Your Algorithm

While writing an algorithm it's a good idea have it working so you can test it. To do this, write unit tests, write unit tests, write unit tests, write unit tests, write unit tests, write unit tests, write unit tests. Or I guess you could just write unit tests instead. In the example of combining like terms, it could work both when simplifying or solving. Some Algorithms, however, would only be applicable when solving an equation (e.g. subtracting something from both sides of the equation). You need to decide which of these categories your Algorithm falls under. Go to Solver.getAlgorithms(). There is a switch statement there. Make sure your algorithm is added to the ArrayList in that method only if your algorithm is applicable for the argument passed.

Resources & Feedback

• It may be a good idea to open a GitHub issue for your algorithm so it can be discussed and you can get help if necessary. You can use the algorithm tag.
• Feel free to look at current algorithms.
• Finally, feel free to edit this article and/or ask questions if it's not clear. The sole purpose of this wiki is to make things understandable, and if it fails to do that, speak up!