A regex I submitted to Reddit recently climbed to the top of /r/programming and made quite a few heads explode in the process. As delightful as this was, I couldn't help but feel a little guilty for subjecting tens of thousands of people to this disgraceful pile of electronic fecal matter. Absolutely zero effort was put into making it something that even remotely resembled a useful, constructive demonstration. Instead, I lured you all into my own private lemon party and left you shocked, bewildered, and fearing for your lives. And for this I apologize.
At the risk of taking myself too seriously, I went ahead and added comments to the regex as well as tidied it up, re-wrote a couple of parts for greater clarity, and corrected a few glaring oversights. Some of you have levels of curiosity that far outweigh your better judgement, and so I invite you to read on.
First, it may be worth outlining the general method of handling addition when you're restricted to matching from left to right:
At the risk of taking myself too seriously, I went ahead and added comments to the regex as well as tidied it up, re-wrote a couple of parts for greater clarity, and corrected a few glaring oversights. Some of you have levels of curiosity that far outweigh your better judgement, and so I invite you to read on.
First, it may be worth outlining the general method of handling addition when you're restricted to matching from left to right:
- First, compare the excess part of A or B with the excess part of C. They will either be equal, or C's will be greater by 1.
- Next, iterate through digits in A and match corresponding digits in B with their sums in C. Again, there may be differences of 1 depending upon the rest of the digits in A and B.
These potential differences of 1 ("carrying") are determined by moving through pairs of digits that sum to 9 until a pair is found whose sum exceeds 9.
# I wrapped the entire expression in (?!(?! )) just to do away with all
# captured substrings and cleanly match a verified line.
(?!(?!
^0*+
# Here we essentially right-align A, B, and C, ignoring leading zeros,
# and populate backreferences with components that will be useful later.
#
# \1 \2 \3 \4 \5 \6
(?=(\d*?)((?:(?=\d+\ 0*+(\d*?)(\d(?(4)\4))\ 0*+(\d*?)(\d(?(6)\6))$)\d)++)\ )
#
# Taking "12345 678 13023" as an example:
#
# \1 = "12", ie. the extra digits in A if A is longer than B. Empty otherwise.
# \2 = "345", ie. the rest of the digits in A that match up with those in B and C.
# \3 = "", ie. the extra digits in B if B is longer than A. Empty otherwise.
# \4 = "678", ie. the rest of the digits in B that match up with those in A.
# \5 = "13", ie. the extra digits in C that match up with the longer of A and B.
# \6 = "023", ie. the rest of the digits in C.
# This next part checks the extra digit portions to make sure everything is in order.
#
# There are two main paths to take:
# Easy: Adding \2 to \4 results in no "carrying"; the length stays the same.
# \5 should then exactly equal either \1 or \3, whichever was longer.
# An example of this is when matching "5123 456 5579", since 123+456=579.
# Then \5 = \1 = "5".
# OR
# Hard: Adding \2 to \4 results in "carrying"; the length increases by 1. In this case,
# \5 should equal 1 more than either \1 or \3 (which is non-empty).
# This is the case we need to handle for our example of "12345 678 13023".
# Here, \5 = "13" and \1 = "12", and so we need to verify \5 = \1 + 1.
(?=(?(?!
# First thing to check is whether \2 + \4 results in carrying.
# To do this, we must inspect \2 and \4 from the left and match
# optional pairs of digits that sum to 9 until we find a pair that
# sum to > 9.
#
# In our example, "345" and "678", we find that '3' and '6' sum to 9,
# then '4' and '7' sum to > 9. Therefore we have carrying.
# Consume the extra digits in A; they're not important here.
\1
# Move through all pairs of digits that sum to 9.
(?:
# Collect the next digit of interest in B.
(?=\d+\ 0*+\3((\g{-2}?+)\d))
# This lookahead is used to set up a backreference that goes from one digit
# of interest to the next, in the interests of simplifying the long check ahead.
(?=\d(\d*\ 0*+\3\g{-2}))
# Now to use that backreference to match pairs of digits that sum to 9.
(?=0\g{-1}9|1\g{-1}8|2\g{-1}7|3\g{-1}6|4\g{-1}5
|5\g{-1}4|6\g{-1}3|7\g{-1}2|8\g{-1}1|9\g{-1}0)
# Consume a digit so we can move forward.
\d
)*+
# Now that we've gone through all pairs that sum to 9, let's try to match one
# that sums to > 9.
# First set up our backreference of convenience.
(?=\d(\d*\ 0*+\3\g{-3}?+))
# Now find a pair that sums to > 9.
(?=[5-9]\g{-1}[5-9]|1\g{-1}9|2\g{-1}[89]|3\g{-1}[7-9]
|4\g{-1}[6-9]|6\g{-1}4|7\g{-1}[34]|8\g{-1}[2-4]|9\g{-1}[1-4])
)
# The above was a negative lookahead, so if it matched successfully then there is no
# carrying and it's smooth sailing ahead.
# Since either \1 or \3 (or both) is empty, the concatenation of the two will produce
# what we need to match at the front of C. Then, \6 is the rest of C.
(?=\d+\ \d+\ 0*+\1\3\6$)
|
# Carrying. This is where it gets complicated.
# First let's move forward to the extra digits of interest.
# ".*+" matches up to the end of the line with no backtracking. The only way
# \3 can be found at that position is if \3 = "".
# So if the negative lookahead succeeds, \3 isn't empty and B contains the
# extra digits of interest, so we consume A and a space in that case.
(?(?!.*+\3)\d+\ )
# More declarations for convenience.
# \11 \12
(?=\d*?(\2|\4)(\ .*?0*+)\d+$)
# \11 = the rest of the digits in A or B, \2 or \4, depending on where we're at.
# This anchor is important so we know where to stop matching the extra digits.
# \12 = The part between the end of A/B and the beginning of C.
# Another decision tree. Are the extra digits of interest composed solely of '9's,
# such as in the example "999123 878 1000001"?
# If so, the strategy is somewhat simplified.
# This also handles zero '9's, when A and B are of equal length.
(?(?=9*\11\ )
# If the extra digits of interest are composed solely of '9's, all we need
# to do is pair '9's in A/B with '0's in C, and match a '1' at the start of C.
# So, start pairing '9's and '0's.
(?:9(?=\d*?\12[1](\g{-1}?+0)))*?
# Stop when we exhaust the extra digits of interest.
(?=\11\ )
# Now verify C actually starts with a '1', then match the '0's we've collected,
# and also make sure all that follows is \6 (the rest of C).
\11\12[1]\g{-1}?+\6$
|
# Now the trickier path. We need to add 1 to extra digits in A/B and match it to C.
# Because we know these extra digits are not composed solely of '9's, we know the
# extra digits in C will be the same length.
#
# How do you check if a number is 1 more than another given they're equal length?
# First, iterate through the digits and match pairs of equivalent digits.
# When you reach a position where they differ, it must be the case that C's
# digit is 1 greater than A/B's. After this point, you need to pair '9's in A/B
# with '0's in C until you exhaust the extra digits of interest.
#
# To see why this last part is necessary, consider the example "4129990 10 4130000".
# When we compare "41299" to "41300", we first match '4' in A to '4' in C, then '1'
# in A to '1' in C. Then we find the point where the next digit in C is 1 greater
# than the next one in A, and pair '2' in A with '3' in C. There can only be exactly
# one such point like this. Afterwards, the only thing that could possibly follow is
# a series of '9's in A and '0's in C until we exhaust the extra digits of interest.
# The first part, consume all equivalent digits.
(?:(\d)(?=\d*\12(\g{-1}?+\g{-2})))*+
# Now we prepare for the next check by setting up a backreference that contains
# everything in between the two digits of interest, for simplicity.
(?=\d(\d*\12\g{-2}?+))
# Match pairs that differ by 1 in favour of C.
(?=0\g{-1}1|1\g{-1}2|2\g{-1}3|3\g{-1}4|4\g{-1}5|5\g{-1}6|6\g{-1}7|7\g{-1}8|8\g{-1}9)\d
# Now consume any and all additional '9's, pairing them with '0's in C.
(?:9(?=\d*\12\g{-2}?+\d(\g{-1}?+0)))*?
# Stop when we exhaust the extra digits of interest.
(?=\11\ )
# Now verify C by checking it contains all extra digits shared with A/B, followed by
# the lone digit that was found to be 1 greater than the corresponding one in A/B,
# then any '0's that followed, and finally \6, the rest of its digits.
\11\12\g{-3}?+\d\g{-1}?+\6$
)
))
# At this point, we've managed to successfully verify the extra digits in A, B, and C.
# We have examined the "12" and "13" in our example of "12345 678 13023" and found them
# to be sound. We would have rejected examples such as "11 1 22" and "92 8 110" by now,
# since their extra digits don't compute.
#
# The rest of the logic examines the equi-length portions of A and B (saved as \2 and \4
# respectively). This is actually simpler since we don't have to fuss around with things
# being different lengths; we took care of all that earlier.
#
# At this point, we can simply match pairs of digits in A and B to their sum in C.
# There is, however, still some considerations to be made as to carrying. We're iterating
# through digits from left to right, after all, and the sum of every pair of digits we
# sum in A and B may be found in C as either A+B(mod 10) or 1+A+B(mod 10) depending on
# whether carrying occurs to the right.
# Consume any extra digits in A; they're no longer important.
\1
# Iterate through A, B, and C one digit at a time, from the left.
(?:
# Here we set up backreferences to useful portions of the subject, ignoring any
# leading '0's, and also ignoring those extra digits from before, \3 and \5.
#
# 18 19 20 21 22
(?=(\d)\d*\ 0*+\3((\g{-2}?+)\d)\d*\ 0*+\5((\g{-2}?+)\d))
#
# These values update as we iterate through A, but on the first run,
# using our example of "12345 678 13023":
#
# \18 = "3", ie. the next digit to inspect in A.
# \19 = "6", ie. what we've examined in B including the next digit.
# \20 = "", ie. what we've examined in B excluding the next digit.
# \21 = "0", ie. what we've examined in C including the next digit.
# \22 = "", ie. what we've examined in C excluding the next digit.
# Like before, we must proceed in one of two directions based on whether or not we
# encounter carrying.
#
# Similar to the first part, in order to determine this, we need to look at the parts
# of A and B that follow our current digits of interest. And, as before, we sift through
# any pairs of digits that total 9 until we find a pair whose sum is > 9.
(?(?!
# Consume the current digit of interest in A.
\18
# Then start matching pairs of digits in A and B whose sum is 9.
(?:
# Use nested references to remember how far into B we are.
(?=\d+\ 0*+\3\19((\g{-2}?+)\d))
# Set up a backreference for our simple pair matching.
(?=\d(\d*\ 0*+\3\19\g{-2}))
# Match pairs of digits that sum to 9.
(?=0\g{-1}9|1\g{-1}8|2\g{-1}7|3\g{-1}6|4\g{-1}5
|5\g{-1}4|6\g{-1}3|7\g{-1}2|8\g{-1}1|9\g{-1}0)
# Consume a digit to move forward.
\d
)*+
# All that's left is to check if the next pair of digits in A and B has
# a sum exceeding 9. Set up our convenient back reference and check.
(?=\d(\d*\ 0*+\3\19\g{-3}?+))
# Now test for a combination of digits whose sum is > 9.
(?=[5-9]\g{-1}[5-9]|1\g{-1}9|2\g{-1}[89]|3\g{-1}[7-9]|4\g{-1}[6-9]
|6\g{-1}4|7\g{-1}[34]|8\g{-1}[2-4]|9\g{-1}[1-4])
)
# The above negative lookahead succeeded, so fortunately we don't have to contend
# with carrying in the first branch. We need to match pairs of digits in A and B
# and their sum in C. I don't think there's a more clever way to do this in PCRE
# than tabulating all the combinations.
# First set up convenient backreferences.
(?=\d(\d*\ 0*+\3\20)\d(\d*\ 0*+\5\22))
# Now the ugly part.
(?=
1\g{-2}(?:1\g{-1}2|2\g{-1}3|3\g{-1}4|4\g{-1}5|5\g{-1}6|6\g{-1}7|7\g{-1}8|8\g{-1}9|9\g{-1}0)
|2\g{-2}(?:1\g{-1}3|2\g{-1}4|3\g{-1}5|4\g{-1}6|5\g{-1}7|6\g{-1}8|7\g{-1}9|8\g{-1}0|9\g{-1}1)
|3\g{-2}(?:1\g{-1}4|2\g{-1}5|3\g{-1}6|4\g{-1}7|5\g{-1}8|6\g{-1}9|7\g{-1}0|8\g{-1}1|9\g{-1}2)
|4\g{-2}(?:1\g{-1}5|2\g{-1}6|3\g{-1}7|4\g{-1}8|5\g{-1}9|6\g{-1}0|7\g{-1}1|8\g{-1}2|9\g{-1}3)
|5\g{-2}(?:1\g{-1}6|2\g{-1}7|3\g{-1}8|4\g{-1}9|5\g{-1}0|6\g{-1}1|7\g{-1}2|8\g{-1}3|9\g{-1}4)
|6\g{-2}(?:1\g{-1}7|2\g{-1}8|3\g{-1}9|4\g{-1}0|5\g{-1}1|6\g{-1}2|7\g{-1}3|8\g{-1}4|9\g{-1}5)
|7\g{-2}(?:1\g{-1}8|2\g{-1}9|3\g{-1}0|4\g{-1}1|5\g{-1}2|6\g{-1}3|7\g{-1}4|8\g{-1}5|9\g{-1}6)
|8\g{-2}(?:1\g{-1}9|2\g{-1}0|3\g{-1}1|4\g{-1}2|5\g{-1}3|6\g{-1}4|7\g{-1}5|8\g{-1}6|9\g{-1}7)
|9\g{-2}(?:1\g{-1}0|2\g{-1}1|3\g{-1}2|4\g{-1}3|5\g{-1}4|6\g{-1}5|7\g{-1}6|8\g{-1}7|9\g{-1}8)
|0\g{-2}(\d)\g{-2}\g{-1} # At least we can handle zeros
|(\d)\g{-4}0\g{-3}\g{-1} # with a bit of intelligence.
)
|
# And in the else branch, we have to deal with carrying. So we'll match pairs of
# digits like up there, but this time we'll match pairs of digits in A and B with
# their sum + 1 (mod 10) in C.
# Convenient backreferences.
(?=\d(\d*\ 0*+\3\20)\d(\d*\ 0*+\5\22))
# Almost done, let's just get through this last bit of ugliness.
(?=
1\g{-2}(?:0\g{-1}2|1\g{-1}3|2\g{-1}4|3\g{-1}5|4\g{-1}6|5\g{-1}7|6\g{-1}8|7\g{-1}9|8\g{-1}0|9\g{-1}1)
|2\g{-2}(?:0\g{-1}3|1\g{-1}4|2\g{-1}5|3\g{-1}6|4\g{-1}7|5\g{-1}8|6\g{-1}9|7\g{-1}0|8\g{-1}1|9\g{-1}2)
|3\g{-2}(?:0\g{-1}4|1\g{-1}5|2\g{-1}6|3\g{-1}7|4\g{-1}8|5\g{-1}9|6\g{-1}0|7\g{-1}1|8\g{-1}2|9\g{-1}3)
|4\g{-2}(?:0\g{-1}5|1\g{-1}6|2\g{-1}7|3\g{-1}8|4\g{-1}9|5\g{-1}0|6\g{-1}1|7\g{-1}2|8\g{-1}3|9\g{-1}4)
|5\g{-2}(?:0\g{-1}6|1\g{-1}7|2\g{-1}8|3\g{-1}9|4\g{-1}0|5\g{-1}1|6\g{-1}2|7\g{-1}3|8\g{-1}4|9\g{-1}5)
|6\g{-2}(?:0\g{-1}7|1\g{-1}8|2\g{-1}9|3\g{-1}0|4\g{-1}1|5\g{-1}2|6\g{-1}3|7\g{-1}4|8\g{-1}5|9\g{-1}6)
|7\g{-2}(?:0\g{-1}8|1\g{-1}9|2\g{-1}0|3\g{-1}1|4\g{-1}2|5\g{-1}3|6\g{-1}4|7\g{-1}5|8\g{-1}6|9\g{-1}7)
|8\g{-2}(?:0\g{-1}9|1\g{-1}0|2\g{-1}1|3\g{-1}2|4\g{-1}3|5\g{-1}4|6\g{-1}5|7\g{-1}6|8\g{-1}7|9\g{-1}8)
|9\g{-2}(?:0\g{-1}0|1\g{-1}1|2\g{-1}2|3\g{-1}3|4\g{-1}4|5\g{-1}5|6\g{-1}6|7\g{-1}7|8\g{-1}8|9\g{-1}9)
|0\g{-2}(?:0\g{-1}1|1\g{-1}2|2\g{-1}3|3\g{-1}4|4\g{-1}5|5\g{-1}6|6\g{-1}7|7\g{-1}8|8\g{-1}9|9\g{-1}0)
)
)
# Whew. It's over. Consume a digit so we can move forward and restart the fun.
\d
)+
# At the end of all this, if we can match a space then we have succeeded in matching all
# of A, and hence all of B and C.
\s
|
# I tripped up on these edge cases involving zeros the first time I made this.
^0+\ 0*(\d+)\ 0*\g{-1}$
|
# I'm not going to make that mistake again!
^0*(\d+)\ 0+\ 0*\g{-1}$
)).+
Demo on regex101 (comments removed)
See, it's not so scary after all!
In case anyone is still wondering in earnest why I did this, the simple answer is: it was fun! Once I saw this challenge on StackOverflow's codegolf section and realized it may be possible, I just couldn't stop thinking about it until I had a working solution.
If anyone out there shares my zany passion for things of this nature, I invite you to subscribe to this blog and/or follow me on Twitter. I do have plenty more madness lined up to share with the world.
Also, please know that I do actually spend time creating and helping others create regular expressions that are useful and serve a practical purpose. You are welcome to fire up your favourite IRC client and pop by Freenode's #regex if you ever need any advice or just want to shoot the shit. We've got a great team there who are always happy to help you conquer your regex woes.
Thanks for reading.
