|
Re: List all different equations for a given one
by kennethk (Abbot) 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.
| [reply]
[d/l]
[select] |
|
|
| [reply] |
|
|
| [reply] |
|
|
Re: List all different equations for a given one
by LanX (Saint) 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 5x³y² + 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 | [reply]
[d/l]
[select] |
Re: List all different equations for a given one
by BrowserUk (Patriarch) 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.
| [reply] |
|
|
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.
| [reply] |
|
|
| [reply] |
|
|
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)
| [reply]
[d/l]
[select] |
|
|
$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.
| [reply]
[d/l] |
Re: List all different equations for a given one
by kcott (Archbishop) 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.
| [reply]
[d/l]
[select] |
|
|
| [reply] |
Re: List all different equations for a given one
by hdb (Monsignor) 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
| [reply]
[d/l]
[select] |
|
|
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
^
^
^
?
| [reply]
[d/l]
[select] |
Re: List all different equations for a given one
by MidLifeXis (Monsignor) on Sep 24, 2013 at 16:55 UTC
|
Can you show what you have tried, or are you stuck close to the beginning?
| [reply] |
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? | [reply]
[d/l] |
|
|
| [reply] |
