Monday, July 5, 2010

Split into powers of 2 using regex

There are so many levels of abuse here it's not even funny.
for (String s :
   new String(new char[(1 << 8) - 1])
   .split("(?=(.*))(?<=(?<=(^.*))\\G.*)(?<=(?=\\2\\2.\\1)^.*)")
) {
   System.out.printf("%s ", s.length());
} // "1 2 4 8 16 32 64 128 "
I think there's still room for "improvement", though...
"Improvements", as Java string literals:
"(?=(.*))(?<=(?<=(^.*))\\G.*)(?<=(?=\\2\\2.\\1)^.*)"
"(?=(.*))(?<=(?<=(^.*))\\G.*)(?<=(?=\\2.\\1)\\G.*)"

2 comments:

  1. Can you explain the regex a bit.

    ReplyDelete
  2. The regex uses lookarounds, nested lookarounds, nesting a lookahead inside a lookbehind, capturing inside lookarounds, continuing previous match with \G, exploiting Java's regex engine bug by anchoring an infinite length lookbehind, etc.

    Properties of sum of powers of two is also used for the arithmetic part.

    ReplyDelete