Regexercise: factorials

Question

_{This is an experimental new feature for StackOverlow: using your regular expression muscles to solve various classic problems. There is no right answer, and in fact, we must collect as many correct answers as possible if they offer educational value. All tastes are accepted, but please document them. In practice, provide test / snippets to demonstrate that the pattern "works."}

How can we find if x is a factorial using a regular expression?

Bonus: if a template can determine that x = n !, can it also find n?

Answer 1

Java with an infinite lookbehind length and nested links ( see also at ideone.com ):

import java.util.regex.*; 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); } } } } 

Answer 2

With .NET balancing groups in C # ( see also at ideone.com ):

 var r = new Regex(@"(?xn) ^( ( ( ^. | (?= (?<temp-n> .)+ ) (?<= (?<fact> .+) ) (?<n-temp> \k<fact> )+? (?(temp) (?!)) ) (?<n>) )+ )$ "); for (int x = 0; x < 6000; x++) { Match m = r.Match("".PadLeft(x)); if (m.Success) { Console.WriteLine("{0,4} = {1}! ", x, m.Groups["n"].Captures.Count); } } 

Note:

The .NET version used by ideone.com seems to have an error in balancing groups that did a reluctant repeat of +? necessary in the above snippet. In newer versions, a simple greedy + enough. See Also: Rollback of balancing group in greedy repetition can cause imbalance?