Monday, March 30, 2009

Magic of perl!

Here is a small script my friend gave me to debug...
Amazing piece of perl regular expression mastery..

perl -e '$i=$ARGV[0];$i++while("."x$i)=~/^(..+?)\1+$/;print"$i\n" _input number_

The output will be the next possible prime number inclusive of the number itself.

for example:
$ perl -e '$i=$ARGV[0];$i++while("."x$i)=~/^(..+?)\1+$/;print"$i\n"' 8

$ perl -e '$i=$ARGV[0];$i++while("."x$i)=~/^(..+?)\1+$/;print"$i\n"' 7

Each time a number is input the number. A string of "."'s with length equal to the input number is generated.

$ perl -e 'print "."x$ARGV[0]\n;'
To understand what "."x$i does.

$ perl -e 'print "."x$ARGV[0];' 4

now here is the master piece...
(..+?) matches the smallest possible string of dots (>=2) in the generated string (remember "."x$i) which can be repeated to match the generated string. The ? makes sure that the search is not greedy.

Repetition is achieved by \1+
which says repeat the last matched pattern (\1) at least once (+).
Now smallest possible factoring number is achieved only for non-primes.
Any prime number will not have any string of dots which can be repeated atleast 2 times. Hence the match ("."x$i=~/^(..+?)\1+$/) will fail and while will not increment $i.

So the output will be the next prime number >= the input number.

Who said perl was not powerful? And regular expressions are arcane and cryptic?

Happy scripting!!