I recently stumbled upon a problem from Stanford Local ACM Programming Contest (SLPC) 2011.
(original page)
(try the problem yourself here)
So the problem is, in short, given algebraic expressions of trigonometry like $$$x(sin^2x + cos^2x) − x$$$, you have to determine whether each expression equates to zero.
The intended solution, I am assuming, is to
1) convert the input string into a function of $$$x$$$ that returns the value, under the same process the expression is described,
2) input multiple values of $$$x$$$ into that function, and
3) confirm the identity if the function always returns zero — within the bounds of float precision error.
Unaware of this idea, I initially tried to solve this problem by building a recursive reduction algorithm. Using the F# language, I made a custom algebraic data type, with a set of rules, such as $$$sin^2x + cos^2x = 1$$$, so that the algebraic expressions can be reduced according to the actual formulas of basic operations and trigonometry.
...Which turned out to be very difficult. Every time I found a case where the expressions could not be reduced under the current set of rules, I had to add new rules to cater that case, and that went on and on, often causing runtime errors.
After I realized that I didn't actually have to reduce the expressions and just substitute some float values for $$$x$$$, the rest was very easy compared to the tedious process I had underwent.
Being angry at myself for consuming energy on things that did not come to fruition, I came up with some questions, including:
1) If this problem was intended to be solved the way I attempted (not by substituting arbitrary values for $$$x$$$ and reducing all the expressions), how would the conditions of the inputs have been different? Would this problem even be suitable for a programming contest?
2) The problem guarantees that recursion of function arguments containing functions is no deeper than $$$sin(sinx)$$$. How much more difficult would it be to reduce these expressions if there were no constraints on this recursion?
3) I guess somebody smart would have already made an algorithm, or a software that can do this algebraic reduction that I attempted. I think WolframAlpha can do it given enough computation time, but are there any "lightweight" tools out there that can perform tasks like this?
I am not a math/CS/engineering major so I have little knowledge that is needed to build such an algorithm myself.
After conducting a not-too-profound research I found there is something called "computer algebra system (CAS)" which seemed to be capable of performing tasks like I had, but to a much greater extent.
But I don't need all of the functionalities these software can provide, I am just curious what knowledge I should be familiar with in order to write a program that conducts handling simple algebraic expressions.
Several months ago I attempted writing a program that does this on polynomials. It is unfinished ever since, but it actually worked on some problems like this one.
So... my question to the Codeforces community is,
