Perl Regexes and Math

Just a few weeks ago, I started solving some of the problems on projecteuler.net. The third problem asks you to find the largest prime factor of 317584931803, which I did by modifying the sieve method that I picked up from the second chapter of the Perl Cookbook (2nd Ed.). I've been reading a few pages from the Perl Cookbook (2nd Ed.) for the past couple months, and so I was glad that I was actually able to use some of it for fun. Tonight, I just read recipe 6.16, which discusses detecting doubled words. I had almost skipped chapter six entirely because I'm already half way through reading Mastering Regular Expressions (2nd Ed.), but I'm glad I didn't. I found these two little gems (not very practical, but interesting) in recipe 6.16:

for ($N = ('o' x shift); $N =~ /^(oo+?)\1+$/; $N =~ s/$1/o/g) { print length($1), " "; } which calculates prime factors when given a number as an argument, and # this solves the equation 12x + 15y + 16z = 281 if (($X, $Y, $Z) = (('o' x 281) =~ /^(o*)\1{11}(o*)\2{14}(o*)\5{15}$/)) { ($x, $y, $z) = (length($X), length($Y), length($Z)); print "One solution is x=$x; y=$y; z=$z.\n"; } else { print "No solution found.\n"; } # One solution is: x=17; y=3; z=2. which solves for Diophantine equations of order one. The regex can be modified to give different solutions: ('o' x 281) =~ /^(o*?)\1{11}(o*)\2{14}(o*)\5{15}$/ # One solution is: x=0; y=7; z=11. ('o' x 281) =~ /^(o+?)\1{11}(o*)\2{14}(o*)\5{15}$/ # One solution is: x=1; y=3; z=14. Now I'm not sure which shocked me more: that others experimented with regexes like this or that I actually understood how and why each worked. Either way, like I said, I'm glad I didn't skip over this chapter. :-)

[all posts in /tech/]  [permanent link]