Automating reduction on algebraic expressions

Revision en4, by Wanderkind, 2024-10-05 11:35:29

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 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.

the F# code I wrote for the ADT

...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 a float value of $$$0$$$ for $$$x$$$, the rest was very easy compared to the tedious process I had underwent.

Being angry at myself for wasting energy on things that did not come to fruition, I came up with some questions:

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en11 English Wanderkind 2024-10-05 12:50:42 12 Tiny change: 'fields of algebra precisely' -> 'fields of math/CS precisely' (published)
en10 English Wanderkind 2024-10-05 12:48:30 27 Tiny change: 'o cater that case' -> 'o cater the generalized pattern of that case'
en9 English Wanderkind 2024-10-05 12:46:26 5 Tiny change: 'algorithm.\nUsing th' -> 'algorithm. <br>\nUsing th'
en8 English Wanderkind 2024-10-05 12:43:24 3 Tiny change: 'ite such algorithm' -> 'ite such an algorithm'
en7 English Wanderkind 2024-10-05 12:42:38 98 Tiny change: '<br>\n\n[(original page)](https:/' -> '<br>\n\n[(contest info)](https:/'
en6 English Wanderkind 2024-10-05 12:21:35 593
en5 English Wanderkind 2024-10-05 12:10:45 1739 Tiny change: ' the value the same way the expre' -> ' the value, under the same process the expre'
en4 English Wanderkind 2024-10-05 11:35:29 410
en3 English Wanderkind 2024-10-05 11:21:16 669
en2 English Wanderkind 2024-10-05 11:02:24 739 Tiny change: ' to <br>\n1) conve' -> ' to <br>\n\n1) conve'
en1 English Wanderkind 2024-10-05 10:42:36 296 Initial revision (saved to drafts)