Tuesday, September 14, 2010

Computing the root of squares using regex

final Pattern SQUARE = Pattern.compile(
   "(?x) (?: (\\2|^) (\\1 .) )+"
);
for (int n = 0; n < 1000; n++) {
   Matcher m = SQUARE.matcher(new String(new char[n]));
   if (m.matches()) {
      System.out.printf("%3s = %2s^2%n", n, m.group(2).length());
   }
}
//   1 =  1^2
//   4 =  2^2
//   9 =  3^2
//  16 =  4^2
//     :
// 961 = 31^2
(see also on ideone.com)

Group 1 contains a forward reference to group 2, and group 2 contains a back reference to group 1.

Alternatively you can have just a single self-referencing group, but this is way more fun.

No comments:

Post a Comment