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, regardless of the value of $$$x$$$.
The intended solution, I am assuming, is to
1) convert the input string into a function of $$$x$$$ that returns the value the same way 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.
[collapse=the OCaml/F# code I wrote for the ADT] type trig = | Zero | X | One | Sin of trig | Cos of trig | Tan of trig | Add of trig * trig | Sub of trig * trig | Mul of trig * trig // hopefully you get the idea. [/collapse]
...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.
So