Beefy Boxes and Bandwidth Generously Provided by pair Networks
XP is just a number
 
PerlMonks  

List all different equations for a given one

by jess195 (Novice)
on Sep 24, 2013 at 16:36 UTC ( #1055515=perlquestion: print w/ replies, xml ) Need Help??
jess195 has asked for the wisdom of the Perl Monks concerning the following question:

Hi all

I'm trying to build a calculator that would accept mathematical expressions from different users. I'm stuck in one part and would like to know good ways of solving the following problem:

I need to check what user enters against my answer. Say I have x + 1 as a correct answer, but user entered 1 + x. How can I build something that would check for all associativity and commutativity in a given equation? Of course that's one example but the problem gets more complicated when you have more than 4 variables. (with one unknown variable things are easy just easy)

I have used shunting yard algorithm to find the operators-precedence but it complicated things and I failed to do the task. Any idea how would I solve such a problem?

Comment on List all different equations for a given one
Re: List all different equations for a given one
by kennethk (Monsignor) on Sep 24, 2013 at 16:50 UTC
    If you are trying to solve a permutation problem (which is what it sounds like to me), I think you are applying yourself incorrectly. Rather than figuring out how to map your answer to their answer, your parser should generate a canonical read that will necessarily map to yours. For your simple case, it might look like:
    my $eq = {op => '+', terms => [1, 'x', ], };
    where a canonical sorting algorithm is used to order terms. Note that, if you want to accept complex expressions, the sort is non-trivial since you'll need to rank complex references, so cmp won't be enough. This type of format also supports nested operations:
    my $eq = {op => '+', terms => [{ op => '*', terms => [3, 'z', ], }, 'x', ], };
    You can then do a recursive descent in order to check equivalence. Of course, this isn't going to help you with distributivity.

    #11929 First ask yourself `How would I do this without a computer?' Then have the computer do it the same way.

      Distributivity is something to think about... Thanks for bringing it up. And yes, I'm trying to solve a permutation problem taking commutativity and associativity properties into account. Looks to me this way is best that what I have been trying so far.... Thanks!

        If you haven't seen this yet, likely worth a read: Stack Overflow


        #11929 First ask yourself `How would I do this without a computer?' Then have the computer do it the same way.

Re: List all different equations for a given one
by MidLifeXis (Prior) on Sep 24, 2013 at 16:55 UTC

    Can you show what you have tried, or are you stuck close to the beginning?

    --MidLifeXis

Re: List all different equations for a given one
by LanX (Canon) on Sep 24, 2013 at 17:28 UTC
    Long ago we did something similar in University studies (second year maybe) ... IIRC it was called minimal word (or term) problem.

    In short you are transforming the term into a representation which allows a weighting function defining a maximum. The permutation (associativity, commutativity, ...) leading to the maximum is your normal form.

    To terms leading to the same normal form are identical.

    Sounds abstract but shouldn't be to difficult to achieve, e.g. normal forms of polynomials are easy, if you have different variables like in 5xy + 2xy *, give certain variables a (e.g. lexicographic) precedence (i.e. x>y) and order them by exponent.

    If your terms are not transformable to polynomials it gets a bit more difficult...

    Cheers Rolf

    ( addicted to the Perl Programming Language)

    * ) which is a normal form of xy * (5x+2) * y

Re: List all different equations for a given one
by BrowserUk (Pope) on Sep 24, 2013 at 17:59 UTC
    Any idea how would I solve such a problem?

    Substitute a semi-random range of numerical values for each variable into both equations and evaluate them. If the both result in the same answer, for a well-chosen set of inputs, they're probably the same equation.

    Of course, that kind of just moves the goal posts a little to one of coming up with a good set of values; but given the performance of modern processors, unless these are quite complicated formulae, you can probably afford to throw a little (or even quite a lot) of everything at them and still get a statistically, highly probable answer in a few seconds.


    With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday'
    Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
    "Science is about questioning the status quo. Questioning authority".
    In the absence of evidence, opinion is indistinguishable from prejudice.

      actually I was using shunting yard algorithm to do me one thing: break down the equation into parts so I can swtich tings around. For example if I have a * b + c, then the algorithm should return: a b * c +, and then from here I would list different things, like add b a * c +, or c b a * + to the list of accepted equations, yet there are a lot to consider. But that's really difficult to do, as you will end up brute forcing everything. I believe the same goes to your way of solving it. I'm sure there is a smarter way to solve and take into consideration performance.

        If the only operations allowed are + - / * and ** plus parens then read my answer again for a "smart" solution.

        update

        or specify which operations are allowed... e.g. polynom devisions might a challenge for you.

        Cheers Rolf

        ( addicted to the Perl Programming Language)

      How many random numbers do you need to proof that abs($x**10000001) and abs($x**10000000) are identical? :)

      Please if you consider replying that you limit the range as soon that one function returns inf think about functions with multiple separated intervals not being inf.

      I'd rather avoid numerical approaches as long as possible. (IIRC for instance some differential equations can only be solved numerically)

      Cheers Rolf

      ( addicted to the Perl Programming Language)

        How many random numbers do you need {drivel} {drone}

        Not many. My first guess:

        $x = 1.000000001; say abs($x**1e8);; 1.10517092716461 $x = 1.000000001; say abs($x**(1e8+1));; 1.10517092826979

        You seem to have missed: "semi-random range" & "well-chosen set of inputs". Inspecting a string for exponentiation by big constants is trivial.

        if you consider replying that you limit the range as soon that one function returns inf think about functions with multiple separated intervals ...

        Vary them one at a time...

        I'd rather avoid ...

        You are quite welcome to do things the hard way; it seems to suite.

        The OP asked for ideas.


        With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday'
        Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
        "Science is about questioning the status quo. Questioning authority".
        In the absence of evidence, opinion is indistinguishable from prejudice.
Re: List all different equations for a given one
by kcott (Abbot) on Sep 24, 2013 at 20:33 UTC

    G'day jess195,

    Welcome to the monastery.

    "I need to check what user enters against my answer. Say I have x + 1 as a correct answer, but user entered 1 + x. How can I build something that would check for all associativity and commutativity in a given equation?"

    My thoughts on this was to substitute the variables with real values and then compare the results. However, looking at some of your subsequent replies in this thread, I'm wondering if you really do want to compare two answers or generate a list of all possible answers: assuming the former, here's some code I've been playing around with that you can possibly adapt to your needs.

    #!/usr/bin/env perl use strict; use warnings; use constant DEBUG => 0; use constant FUZZINESS => 1e-15; use Scalar::Util 'looks_like_number'; my %vals = map { $_ => rand } 'a' .. 'z'; my @equations = ( 'x + y', 'x - y', 'x * y', 'x / y', 'x % y', 'x ^ y', 'x * (y + z)', 'x / (y + z)', '(x + y) * (x + y)', '(x + y) * (x - y)', ); EQUATION: for my $equation (@equations) { TRY: while (1) { print '-' x 40, "\n"; print "Base equation: $equation\n"; print 'Try/Skip/Quit (t/s/q) [t]: '; my $choice = <>; next EQUATION if $choice =~ /^s/i; last EQUATION if $choice =~ /^q/i; print 'Equivalent equation: '; my $try = <>; chomp $try; if (equivalent($equation, $try)) { print "'$equation' and '$try' are equivalent.\n"; print 'Try again (y/n) [n]: '; my $choice = <>; next TRY if $choice =~ /^y/i; last TRY; } else { print "'$equation' and '$try' are not equivalent.\n"; next TRY; } } } sub equivalent { my ($equation, $try) = @_; my $eqn_val = get_value($equation); return 0 unless defined $eqn_val; my $try_val = get_value($try); return 0 unless defined $try_val; return abs($eqn_val - $try_val) < FUZZINESS ? 1 : 0; } sub get_value { my $in_equation = shift; print "get_value($in_equation)\n" if DEBUG; (my $equation = $in_equation) =~ s/([a-z])/$vals{$1}/g; $equation =~ s/\^/**/g; print "SUBS: $equation\n" if DEBUG; my $value = eval { eval $equation; }; if ($@) { warn $@; return undef; } if (not defined $value && length $value && looks_like_number $valu +e) { warn "!!! BAD EQUATION: '$in_equation'\n"; return undef; } print "VALUE: $value\n" if DEBUG; return $value; }

    Here's some example output:

    'x + y' and 'y + x' are equivalent. ... 'x - y' and 'y - x' are not equivalent. ... 'x - y' and 'x-y' are equivalent. ... 'x * (y + z)' and 'x*y + x*z' are equivalent. ... 'x * (y + z)' and 'z * x + y * x' are equivalent. ... 'x / (y + z)' and 'x/y + x/z' are not equivalent. ... '(x + y) * (x + y)' and 'x^2 + 2*x*y + y^2' are equivalent. ... '(x + y) * (x - y)' and 'x^2 + y^2' are not equivalent. ... '(x + y) * (x - y)' and 'x^2 - y^2' are equivalent.

    -- Ken

      Thanks for bringing this to my attention! I'll test against ranges of numbers instead, which looks to be the most reasonable solution!

Re: List all different equations for a given one
by zork42 (Monk) on Sep 25, 2013 at 15:47 UTC
    What operations are allowed?

    + - * / ** ()

    or more?

      for now, I'm trying to make those operations work perfectly. But for the future, I'll need to add more. I'm in the right path with all those above ideas

Re: List all different equations for a given one
by hdb (Prior) on Sep 25, 2013 at 17:38 UTC

    As I had some fun with drawing binary trees recently, I thought, parsing equations into such a tree would be interesting as well. I was also able to simplify the tree for operations on numbers (in contrast to variables) and expand based on distributivity. But now I am stuck. I was thinking that some re-ordering would lead to a definite form for each equation but I have no idea how to go about it. In any case, the code produces the following output which might be of interest (or at least entertaining). (Numbers are written vertically, and I have used ^ instead of **.)

    Equation: 1+x^2*((1+y)*3)+5*(4+(4+3)) + / \__________________ 1 + __________/ \ * 5 __/ \__ 5 ^ + / \ / \__ x 2 3 * / \ y 3 Equation: ((4+c)*y)^(4+2)/5-s^200 - __/ \__ / ^ __/ \ / \ ^ 5 s 2 ______/ \ 0 + 6 0 __/ \__ * * / \ / \ 4 y c y Equation: 2+2 4
      Very nice!

      One minor point, the "/" in the 2nd equation "((4+c)*y)^(4+2)  /  5-s^200" gets a bit confused with the tree structure as you also use "/" to print the tree:
      - __/ \__ / ^ __/ \ / \ ^ 5 s 2 ^ ^ ^
      Maybe you could use "'/'" (that's a bit hard to read, here it is again with 4 spaces added: " ' / ' ") or similar to make it stand out a bit more:
      - __/ \__ '/' ^ __/ \ / \ ^ 5 s 2 ^ ^ ^
      ?

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: perlquestion [id://1055515]
Approved by hippo
Front-paged by toolic
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others exploiting the Monastery: (8)
As of 2014-12-27 12:57 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    Is guessing a good strategy for surviving in the IT business?





    Results (177 votes), past polls