Automating reduction on algebraic expressions

Revision en2, by Wanderkind, 2024-10-05 11:02:24

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(sin2x + cos2x) − 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 set of custom algebraic data types

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)