Using Regex to solve Diophantine equations – Perl
January 27, 2012
Posted by on
I stumbled upon this cool concept of solving algebraic equations especially the tougher Diophantine equation using regex.
I decided to aggregate the information i found into this article and its worth to know this super cool concept.
You can find a nice introduction about solving algebra equations using regex in this blog post by author of regex cookbook.
Diophantine equation is an indeterminate polynomial equation that allows the variables to be integers only. Diophantine problems have fewer equations than unknown variables and involve finding integers that work correctly for all equations – Wikipedia.
The Oldest plays piano puzzle ends up being a Diophantine equation. In the perl monks you can see how the author uses regex to derive the different possible solutions to x*y*z = 72 equation and hence find a solution to the puzzle.
However this could only work for positive integers and a positive constant as described in this forum.
But if you know before hand that your variables and constant need to be positive for example the piano puzzle( the ages cant be negative) its worthwhile to use a regex to get those values.
# 3x + 2y + 5z = 40
$_ = 'o' x 40;
$a = 'o' x 3;
$b = 'o' x 2;
$c = 'o' x 5;
$_ =~ /^((?:$a)+)((?:$b)+)((?:$c)+)$/;
print "x = ", length($1)/length($a), "\n";
print "y = ", length($2)/length($b), "\n";
print "z = ", length($3)/length($c), "\n";
> perl darkmoon.pl
x = 11
y = 1
z = 1