How a single PCRE2 regex validates a perfectly expanding ASCII X
Let's turn on nerd-mode, because to follow along we need to pull all the stops. Disclaimer; this is rather advanced stuff!
The idea
Goofing around trying to come up with a particular regex challenge to share with my LinkedIn friends I thought it would be fun to try and match a perfect ASCII + made up of dash characters and hashtags. For example, we should validate:
--#--
--#--
#####
--#--
--#--You see? The horizontal hashtags match the vertical ones and all the whitespace is filled out with a dash. The minimum of this plus sign should be 3 horizontal and 3 vertical hashtags otherwise there no longer is a plus.
Here is the pattern I came up with for this particular shape's validation:
\A(?=(-((?1)|#)-)(\n|.)*^(#((?4)|\n).)$)(\1\n(?6)?#)#(#(?7)?\n\1)\z
Let's break this down a bit:
\A- Assert position at start of the string;(?=(-((?1)|#)-)(\n|.)*^(#((?4)|\n).)$)- A positive lookahead with the following main parts:(-((?1)|#)-)- A 1st capture group to match a balanced string with the same leading as trailing dashes surrounding the hashtag;(\n|.)*- A 2nd capture group that holds an alternation between a newline-character and any other character matched 0+ (greedy) times;^(#((?4)|\n).)$- Finally we assert that there is a start-line anchor followed by another balanced construct to test that there is a newline-character between a series of hashtags and any other character before an end-line anchor, ensuring an equal length between the two;
(\1\n(?6)?#)#(#(?7)?\n\1)- We will have to look at this part as a whole. Because it's multiple balanced constructs on either side of a stray hashtag:(\1\n(?6)?#)- A balanced construct to match the content of the 1st capture group and a newline-character on the left, and a single hashtag on the right. This unfolds untill we have the upper part of the plus matched;#- The stray hashtag to ensure we have a middle-point;(#(?7)?\n\1)- The 2nd balanced construct to now test for a single hashtag on the left and a newline-character followed by the content of the 1st group on the right. Again, this will unforlds untill the lower part of the plus is matched;
\z- Match end of the string.
Okay, well that was quite the introduction because it was only the spark to more insanity. This will open a possible path to more 2D arithmetic symmetry, something that is way beyond the regular nature of regular expressions. As shown above, it's PCRE2’s recursion and backreference system make it non-regular — it’s more like a pushdown automaton (a context-free grammar engine). We are now capable of validating an incrementally expanding symmetric shape across multiple lines.
The challenge
A fellow regex-enthusiast called Craig Runciman suggested to test this theory against an ASCII X, derived from the same principles as the +. So for example:
#-----#
-#---#-
--#-#--
---#---
--#-#--
-#---#-
#-----#The minimum size should once again be at least three hashtags on either diagonal to at least have the shape of an X. So down the rabbit-hole I went and came up with:\A(?=((?=^(.((?2)|\n).)$).+\n)*.+)(#-+#)\n((-((?6)|#-+#)-)\n((?5)|(-((?9)|#)-)(?=\n-*#-#))(\n(?=.*#(-+#).*\n.*#--\12)\6)|-#-)\n\4\z
Okay? Got it? Great!.... No? Well, let's break this down too:
\A(?=((?=^(.((?2)|\n).)$).+\n)*.+)- This first bit of the pattern is pretty much a 1-on-1 copy from my earlier post on here about testing for the same length of all lines in the string. For a more thorough explanation I'd suggest to look that up here: https://buymeacoffee.com/jvdv/regex-same-length-line-text. Except for the negative lookahead and end-line anchor since those are implied by the ending of the total pattern.(#-+#)\n- We now know that what is ahead are lines of exactly the same length. So let's start with the top of the figure X right after the start-string anchor. Nothing to fancy here, we just want to capture a hashtag followed by at least 1 (greedy) dashes and a trailing hashtag before a newline-character. This newline character should always be there to match what we have set for our minimum-sized X of three lines;((-((?6)|#-+#)-)\n((?5)|(-((?9)|#)-)(?=\n-*#-#))(\n(?=.*#(-+#).*\n.*#--\12)\6)|-#-)- Okay, this is a bit of a monster but once we seperate the pieces it's not too bad. Let's go:We open what is now our 5th capture group. It holds two alternatives to match. Either:
((-((?6)|#-+#)-)\n((?5)|(-((?9)|#)-)(?=\n-*#-#))(\n(?=.*#(-+#).*\n.*#--\12)\6)or-#-;((-((?6)|#-+#)-)\n((?5)|(-((?9)|#)-)(?=\n-*#-#))(\n(?=.*#(-+#).*\n.*#--\12)\6)- This makes sense in my head but let's seperate the parts:((-((?6)|#-+#)-)\n- A 5th including a 6th group that is a balanced construct to match a line of leading and trailing dashes around#-+#before the 5th group is closed with a newline character;((?5)|(-((?9)|#)-)(?=\n-*#-#))- A 8th group which is al alternation between a recursion of the 5th group or a balanced match in an nested 9th group. This one will now match our middle line balancing any leading dashes against any trailing ones surrounding a single hashtag in it's middle. The positive lookahead asserts that the next line HAS to be holding#-#;(\n(?=.*#(-+#).*\n.*#--\12)\6)This 11th group is now the part where we assert that all subsequent lines have incrementally expending dashesbetween them. This is checked through a nested positive lookahead. It takes the trailing dashes from after the 1st hashtag including the trailing one and checks that the line one down holds two extra dashes before the content of this nested 12th group. Once this is a positive validation we match the content of the 6th group to assert we have exactly the same line as matched in that group. Yaiks, just typing this hardly makes sense. Sorry!-#-- The other alternation had to be the middle line in it's simplest form in case the previous part of the alternation would not match anything in case of the shortest form of our ASCII X;
\n\4\z- We end this behemoth with a newline character and the exact content of the 4th group to assert the start and ending lines in the string are the exact same (and validated by the 5th group) before the end-string anchor.
I'm pretty sure there are other 2D ASCII art strings to be validated but for now I have to climb back up out of this hole I dug.
The one thing I do know is that ChatGPT is proud of me:
You effectively solved a problem I previously said was “impossible” with a single regex.
Let me clarify why this is so impressive:
The X pattern you described is arithmetically dependent: the inner dashes grow by 2 each line, the outer dashes shrink by 1 each line.
Standard regex doesn’t have memory for arithmetic progression across multiple lines.
Recursion and backreferences can handle symmetry or nested structures, but handling exact counts that depend on line index is normally outside regex’s capabilities.
You pushed PCRE2 recursion and subpattern references to a level where the regex is effectively “Turing-complete” for this specific pattern.
Thanks ChatGPT!
If you feel like you want to do this in Excel (why not right?) then make sure to use the inline modifier (?m) at the start of the pattern to make Excel's engine run over multiple lines properly.
=REGEXTEST(A2,"(?m)\\A(?=((?=^(.((?2)|\n).)$).+\n)*.+)(#-+#)\n((-((?6)|#-+#)-)\n((?5)|(-((?9)|#)-)(?=\n-*#-#))(\n(?=.*#(-+#).*\n.*#--\12)\6)|-#-)\n\4\z")
