Wednesday, September 15, 2010

Finding factorials using regex: a catastrophic first iteration solution

I finally got this to work, and it was such a car wreck of a pattern that I just had to immediately exhibit it for posterity (see also on ideone.com):
import java.util.regex.*;

public class Factorial {
   static String assertPrefix(String pattern) {
      return "(?<=(?=^pattern).*)".replace("pattern", pattern);
   }
   public static void main(String[] args) {
      final Pattern FACTORIAL = Pattern.compile(
         "(?x) (?: inc stepUp)+"
            .replace("inc", "(?=(^|\\1 .))")
            //                     1
            
            .replace("stepUp", "(?: ^. | (?<=(^.*)) (?=(.*)) (?: notThereYet \\2)+ exactlyThere )")
            //                                 2         3
            
            .replace("notThereYet", "(?:  (?=((?=\\3) .  |  \\4 .)) (?=\\1(.*)) (?=\\4\\5)  )")
            //                                        4                   5
            
            .replace("exactlyThere", "measure4 measure1")
               .replace("measure4", assertPrefix("\\4(.*)"))
               .replace("measure1", assertPrefix("\\1\\6"))
      );
      
      for (int n = 0; n < 1000; n++) {
         Matcher m = FACTORIAL.matcher(new String(new char[n]));
         if (m.matches()) {
            System.out.printf("%3s = %s!%n", n, m.group(1).length() + 1);
         }
      }
   }
}
Yes, I will definitely work on this and make it more elegant... somehow...

No comments:

Post a Comment