Thursday, 1 November 2018

How to match "A B C" where A+B=C: The Beast Reborn

A while ago, I created a regex to verify addition of two non-negative integers, and unleashed the unholy mess onto reddit. Reactions were fierce, heads exploded, etc. and so I immediately took to demystifying it by introducing line breaks, comments, and structured formatting. This follow-up was so effective that many commenters were lulled to a state of boredom by the result, underwhelmed by its simplicity. The loudest voices expressed dissatisfaction with the robustness of the solution, complaining about the lack of negative number support and, worse yet, the stark absence of decimal support.

Slowly, I came to realize that these people were right. These features needed to be implemented; the regex simply wasn’t long and complicated enough. So I returned to the drawing board, puked on it several times, and ended up with the following:

# A slow start
^
# Immediately step on the gas
# Parse expression as before, but with some extra pizzazz
(?=[-+]?(?:0\B)*+(\d*?)((?:(?=\d+(?:\.\d+)?\ [-+]?(?:0\B)*+(\d*?)(\d(?(4)\4))(?:\.\d+)?\ [-+]?(?:0\B)*+(\d*?)(\d(?(6)\6))(?:\.\d+)?$)\d)++)\b)

(?:

 # 0th case: handle 0 + 0 = 0 with any sign orientation
 ^(?:[-+]?0+(?:\.0+)?(?:\ |$)){3}\b$
 
|
 
 # 1st case: handle "A B C" and "-A -B -C", ie. check A+B=C
 (?=-\S*\ -\S*\ -|(?!.*-))

 [-+]?(?:0\B)*+

 # Check leading excess digits
 (?=
  (?(?!\1\.?(?!(?!(?&a))))

   # No carrying, match one excess part to the other
   (?=\S+\ \S+\ [-+]?0*\1\3\6(?:\.\d+)?$)
  |
   
   # Carrying, match one excess part to 1 + the other
   (?(?!.*+\3)\S+\ [-+]?(?:0\B)*)
   (?=\d*?(\2|\4)\b(.*?\ [-+]?(?:0\B)*)\S+$)
   
   # Check for carrying with all 9s
   (?(?=9*\7\b)
    # If so, match '9's to '0's and check for a leading '1'
    (?:9(?=\d*?\8[1](\g{-1}?+0)))*?
    \7\8[1]\g{-1}?+\6\b
   |
    # Otherwise, match equivalent pairs of digits until they differ by 1
    # Then pair any extra '0's with '9's
    (?:(\d)(?=\d*\8(\g{-1}?+\g{-2})))*+
    (?=\d(\d*\8\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)
    \d
    (?:9(?=\d*\8\g{-2}?+\d(\g{-1}?+0)))*?
    \7\8\g{-3}?+\d\g{-1}?+\6\b
   )
  )
 )

 \1

 # Check rest of digits
 (?:
  # Identify next group of digits to examine
  (?=\.?(\d)\S*\ [-+]?(?:0\B)*+\3((\g{-2}?+\.?)\d)\S*\ [-+]?(?:0\B)*+\5((\g{-2}?+\.?)\d))
  \.?(*SKIP)
  
  # Check for carrying and match digits accordingly
  (?(?=(?!
    \14\.?
    (?<a>
     # Match pairs of digits that total 9
     (?:
      (?=\d\.?\d(?<b>\S*?\ [-+]?(?:0\B)*\3\15?+)((\g{-2}?+\.?)\d))
      (?=\d(\S*?\g{-4}\g{-2}))
      (?=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)
      \d\.?(?=\S*?(\g{-5}\g{-4}))
     )*+
     # Match a pair of digits that totals > 9
     (?=\d(\g{-2}\.?|(?&b)\.?))
     (?=[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])
    ){0}
    
    # Backreferences were erroneously being set that carried over to subsequent iterations,
    # necessitating this subroutine call
    # PCRE really wanted me to fail, apparently
    (?&a)
   ))
  
   # No carrying, match pairs of digits and their sums
   # My goodness it's beautiful
   (?=\d(\S*\ [-+]?(?:0\B)*\3\16)\d(\S*\ [-+]?(?:0\B)*\5\18))
   (?=
     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}
    |(\d)\g{-4}0\g{-3}\g{-1}
   )
  |
  
   # Carrying, match pairs of digits and their sums + 1
   (?=\d((?-5))\d((?-5)))
   (?= 
     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)
   )

  )
  \d
 )++

 # Paths to success
 (?:
  # A, B and C contain no more significant digits
  (?:\.0+)?0*\ [-+]?0*\3\15(?:\.0+)?0*\ [-+]?0*\5\17(?:\.0+)?0*$
 |
  # A contains no more significant digits, match B's excess to C's
  \ [-+]?0*\3\15(\.?\d*?)0*\ [-+]?0*\5\17\g{-1}(?:\.0+)?0*$
 |
  # B contains no more significant digits, match A's excess to C's
  (\.?\d*?)0*\ [-+]?0*\3\15\ [-+]?0*\5\17\g{-1}(?:\.0+)?0*$
 |
  # C contains no more significant digits but A and B both do
  # Match pairs of digits that total 9 until one that totals 10 is found
  \.?
  (?:
   (?=\d\d((?&b))((\g{-2}?+\.?)\d))
   (?=\d(\S*?\g{-4}\g{-2}))
   (?=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)
   \d
   (?=\S*?(\g{-5}(\g{-5})))
  )*+
  # Match a pair that totals 10 then validate
  (?=\d(\g{-3}|(?&b)\.?))
  (?=1\g{-1}9|2\g{-1}8|3\g{-1}7|4\g{-1}6|5\g{-1}5|6\g{-1}4|7\g{-1}3|8\g{-1}2|9\g{-1}1)
  \d0*\ [-+]?0*\3\15\g{-2}?+\.?\d0*\ [-+]?0*\5\17\.?0*$
 )

|

 # Case 2: handle "-A B C" and "A -B -C", ie. check A+C=B
 (?=-(?!.*-)|[^-]\S*\ -\S*\ -)

 [-+]?(?:0\B)*+

 # Check leading excess digits
 (?=
  (?(?!\1\.?(?!(?!(?&c))))
  
   # No carrying, match one excess part to the other
   (?=\S+\ [-+]?0*\1\5\4\b)
   
  |
   
   # Carrying, match one excess part to 1 + the other
   # There are two paths here depending on whether |A| < |C| or |C| <= |A|
   (?|
   
    # |A| < |C|
    (?!.++\5)
    \S+\ [-+]?(?:0\B)*+(?=\S*(\ [-+]?(?:0\B)*+)())
    
    # Check for carrying with all '9's
    (?(?=\S*\41[9]*\6\b)
     # If so, match '9's to '0's and check for a leading '1'
     1(?:0(?=\S*\41(\g{-1}?+9)))*?
     \4\b\S*\41\g{-1}?+\6\b
    |
     # Otherwise, match equivalent pairs of digits until they differ by 1
     # Then pair any extra '0's with '9's
     (?:(\d)(?=\S*\41(\g{-1}?+\g{-2})))*+
     (?=\d(\S*\41\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)
     \d
     (?:0(?=\S*\41\g{-2}?+\d(\g{-1}?+9)))*?
     \4\b\S*\41\g{-3}?+\d\g{-1}?+\6\b
    )
   |
    # |C| <= |A|, basically the same comments as above
    (?=.*+\5)
    (?=\d*?(\2)\b(\S*\ [-+]?(?:0\B)*+))
    
    (?(?=9*\41\b)
     (?:9(?=\d*?\42[1](\g{-1}?+0)))*?
     \41\42[1]\g{-1}?+\4\b
    |
     (?:(\d)(?=\d*\42(\g{-1}?+\g{-2})))*+
     (?=\d(\d*\42\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)
     \d
     (?:9(?=\S*\42\g{-2}?+\d(\g{-1}?+0)))*?
     \41\42\g{-3}?+\d\g{-1}?+\4\b
    )
   )
  )
 )

 \1

 # Check rest of digits
 (?:
  # Identify next group of digits to examine
  (?=\.?(\d)\S*\ [-+]?(?:0\B)*+\3((\g{-2}?+\.?)\d)\S*\ [-+]?(?:0\B)*+\5((\g{-2}?+\.?)\d))
  \.?(*SKIP)
  
  # Check for carrying and match digits accordingly
  (?(?=(?!
    \48\.?
    (?<c>
     # Match pairs of digits that total 9
     (?:
      (?=\d\.?\d(?<d>\S*?\ \S+\ [-+]?(?:0\B)*\5\51?+)((\g{-2}?+\.?)\d))
      (?=\d(\S*?\g{-4}\g{-2}))
      (?=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)
      \d\.?(?=\S*?(\g{-5}\g{-4}))
     )*+
     # Match a pair of digits that totals > 9
     (?=\d(\g{-2}\.?|(?&d)\.?))
     (?=[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])
    ){0}
    
    # Backreferences were erroneously being set that carried over to subsequent iterations,
    # necessitating this silly subroutine call 
    (?&c)
   ))
   
   # No carrying, match pairs of digits and their sums
   (?=\d(\S*\ [-+]?(?:0\B)*\3\50)\d(\S*\ [-+]?(?:0\B)*\5\52))
   (?=
    1\g{-2}(?: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{-1}9)
    |2\g{-2}(?: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|0\g{-1}8|1\g{-1}9)
    |3\g{-2}(?:4\g{-1}1|5\g{-1}2|6\g{-1}3|7\g{-1}4|8\g{-1}5|9\g{-1}6|0\g{-1}7|1\g{-1}8|2\g{-1}9)
    |4\g{-2}(?:5\g{-1}1|6\g{-1}2|7\g{-1}3|8\g{-1}4|9\g{-1}5|0\g{-1}6|1\g{-1}7|2\g{-1}8|3\g{-1}9)
    |5\g{-2}(?:6\g{-1}1|7\g{-1}2|8\g{-1}3|9\g{-1}4|0\g{-1}5|1\g{-1}6|2\g{-1}7|3\g{-1}8|4\g{-1}9)
    |6\g{-2}(?:7\g{-1}1|8\g{-1}2|9\g{-1}3|0\g{-1}4|1\g{-1}5|2\g{-1}6|3\g{-1}7|4\g{-1}8|5\g{-1}9)
    |7\g{-2}(?:8\g{-1}1|9\g{-1}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)
    |8\g{-2}(?:9\g{-1}1|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)
    |9\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)
    |0\g{-2}(\d)\g{-2}\g{-1}
    |(\d)\g{-4}\g{-1}\g{-3}0
   )
   
  |
   # Carrying, match pairs of digits and their sums + 1
   (?=\d((?-5))\d((?-5)))
   (?= 
    1\g{-2}(?: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|0\g{-1}8|1\g{-1}9)
    |2\g{-2}(?: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|0\g{-1}7|1\g{-1}8|2\g{-1}9)
    |3\g{-2}(?:4\g{-1}0|5\g{-1}1|6\g{-1}2|7\g{-1}3|8\g{-1}4|9\g{-1}5|0\g{-1}6|1\g{-1}7|2\g{-1}8|3\g{-1}9)
    |4\g{-2}(?:5\g{-1}0|6\g{-1}1|7\g{-1}2|8\g{-1}3|9\g{-1}4|0\g{-1}5|1\g{-1}6|2\g{-1}7|3\g{-1}8|4\g{-1}9)
    |5\g{-2}(?:6\g{-1}0|7\g{-1}1|8\g{-1}2|9\g{-1}3|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{-2}(?:7\g{-1}0|8\g{-1}1|9\g{-1}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{-2}(?:8\g{-1}0|9\g{-1}1|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{-2}(?:9\g{-1}0|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{-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}(?: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{-1}9)
   )   
  )
 \d
 )++

 # Paths to success
 (?:

  # A, B, and C contain no more significant digits
  (?:\.0+)?0*\ [-+]?0*\3\49(?:\.0+)?0*\ [-+]?0*\5\51(?:\.0+)?0*$

 |

  # A contains no more significant digits, match B's excess to C's
  \ [-+]?0*\3\49(\.?\d*?)0*\ [-+]?0*\5\51\g{-1}(?:\.0+)?0*$

 |
  # C contains no more significant digits, match A's excess to B's
  (\.?\d*?)0*\ [-+]?0*\3\49\g{-1}(?:\.0+)?0*\ [-+]?0*\5\51$
  
 |
  
  # B contains no more significant digits but A and B both do
  # Match pairs of digits that total 9 until one that totals 10 is found
  \.?
  (?:
   (?=\d\d((?&d))((\g{-2}?+\.?)\d))
   (?=\d(\S*?\g{-4}\g{-2}))
   (?=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)
   \d
   (?=\S*?(\g{-5}(\g{-5})))
  )*+
  # Match a pair that totals 10 then validate
  (?=\d(\g{-3}|(?&d)\.?))
  (?=1\g{-1}9|2\g{-1}8|3\g{-1}7|4\g{-1}6|5\g{-1}5|6\g{-1}4|7\g{-1}3|8\g{-1}2|9\g{-1}1)
  \d0*\ [-+]?0*\3\49\.?0*\ [-+]?0*\5\51\g{-2}?+\.?\d0*$
 )

|

 # And finally, handle "A -B C" and "-A B -C", ie. check B+C=A
 (?=[^-]\S*\ -\S*\ [^-]\S*|-\S*\ [^-]\S*\ -)

 [-+]?(?:0\B)*+

 # Check leading excess digits
 (?=
  (?(?!\S+\ [-+]?(?:0\B)*+\3\.?(?!(?!(?&e))))
   
   # No carrying, match one excess part to the other
   (?=\3\5\2\b)
  |
   
   # Carrying, match one excess part to 1 + the other
   (?=\d*(\S*\ (?(?=.*+\3)\S+\ )[-+]?(?:0\B)*+)\d*?(\4|\6)\b)
   
   # Check for carrying with a leading '1' and all '0's
   (?(?=10*\2\b)
    # If so, match '0's to '9's
    1(?:0(?=\d*\75(\g{-1}?+9)))*?
    \2\b\75\g{-1}?+\76\b
   |
    # Otherwise, match equivalent pairs of digits until they differ by 1
    # Then pair any extra '0's with '9's
    (?:(\d)(?=\d*\75(\g{-1}?+\g{-2})))*+
    (?=\d(\d*\75\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)
    \d
    (?:0(?=\d*\75\g{-2}?+\d(\g{-1}?+9)))*?
    \2\b\75\g{-3}?+\d\g{-1}?+\76\b
   )
  )
 )

 \1

 # Check rest of digits
 (?:
  # Identify next group of digits to examine
  (?=\.?(\d)\S*\ [-+]?(?:0\B)*+\3((\g{-2}?+\.?)\d)\S*\ [-+]?(?:0\B)*+\5((\g{-2}?+\.?)\d))
  \.?(*SKIP)
  
  # Check for carrying and match digits accordingly
  (?(?=(?!
    \S*\ [-+]?(?:0\B)*+\3\83\.?
    (?<e>
     # Match pairs of digits that total 9
     (?:
      (?=\d\.?\d(?<f>\S*?\ [-+]?(?:0\B)*\5\85?+)((\g{-2}?+\.?)\d))
      (?=\d(\S*?\g{-4}\g{-2}))
      (?=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)
      \d\.?
      (?=\S*?(\g{-5}\g{-4}))
     )*+
     # Match a pair of digits that totals > 9
     (?=\d(\g{-2}\.?|(?&f)\.?))
     (?=[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])
    ){0}
    
    # Backreferences were erroneously being set that carried over to subsequent iterations,
    # necessitating this preposterous subroutine call 
    (?&e)
   ))
   
   # No carrying, match pairs of digits and their sums  
   (?=\d(\S*\ [-+]?(?:0\B)*\3\84)\d(\S*\ [-+]?(?:0\B)*\5\86))
   (?=
     (?:2\g{-2}1|3\g{-2}2|4\g{-2}3|5\g{-2}4|6\g{-2}5|7\g{-2}6|8\g{-2}7|9\g{-2}8|0\g{-2}9)\g{-1}1
    |(?:3\g{-2}1|4\g{-2}2|5\g{-2}3|6\g{-2}4|7\g{-2}5|8\g{-2}6|9\g{-2}7|0\g{-2}8|1\g{-2}9)\g{-1}2
    |(?:4\g{-2}1|5\g{-2}2|6\g{-2}3|7\g{-2}4|8\g{-2}5|9\g{-2}6|0\g{-2}7|1\g{-2}8|2\g{-2}9)\g{-1}3
    |(?:5\g{-2}1|6\g{-2}2|7\g{-2}3|8\g{-2}4|9\g{-2}5|0\g{-2}6|1\g{-2}7|2\g{-2}8|3\g{-2}9)\g{-1}4
    |(?:6\g{-2}1|7\g{-2}2|8\g{-2}3|9\g{-2}4|0\g{-2}5|1\g{-2}6|2\g{-2}7|3\g{-2}8|4\g{-2}9)\g{-1}5
    |(?:7\g{-2}1|8\g{-2}2|9\g{-2}3|0\g{-2}4|1\g{-2}5|2\g{-2}6|3\g{-2}7|4\g{-2}8|5\g{-2}9)\g{-1}6
    |(?:8\g{-2}1|9\g{-2}2|0\g{-2}3|1\g{-2}4|2\g{-2}5|3\g{-2}6|4\g{-2}7|5\g{-2}8|6\g{-2}9)\g{-1}7
    |(?:9\g{-2}1|0\g{-2}2|1\g{-2}3|2\g{-2}4|3\g{-2}5|4\g{-2}6|5\g{-2}7|6\g{-2}8|7\g{-2}9)\g{-1}8
    |(?:0\g{-2}1|1\g{-2}2|2\g{-2}3|3\g{-2}4|4\g{-2}5|5\g{-2}6|6\g{-2}7|7\g{-2}8|8\g{-2}9)\g{-1}9
    |(\d)\g{-3}0\g{-2}\g{-1}
    |(\d)\g{-4}\g{-1}\g{-3}0
   )
  |
   # Carrying, match pairs of digits and their sums + 1
   (?=\d((?-5))\d((?-5)))
   (?= 
     (?:2\g{-2}0|3\g{-2}1|4\g{-2}2|5\g{-2}3|6\g{-2}4|7\g{-2}5|8\g{-2}6|9\g{-2}7|0\g{-2}8|1\g{-2}9)\g{-1}1
    |(?:3\g{-2}0|4\g{-2}1|5\g{-2}2|6\g{-2}3|7\g{-2}4|8\g{-2}5|9\g{-2}6|0\g{-2}7|1\g{-2}8|2\g{-2}9)\g{-1}2
    |(?:4\g{-2}0|5\g{-2}1|6\g{-2}2|7\g{-2}3|8\g{-2}4|9\g{-2}5|0\g{-2}6|1\g{-2}7|2\g{-2}8|3\g{-2}9)\g{-1}3
    |(?:5\g{-2}0|6\g{-2}1|7\g{-2}2|8\g{-2}3|9\g{-2}4|0\g{-2}5|1\g{-2}6|2\g{-2}7|3\g{-2}8|4\g{-2}9)\g{-1}4
    |(?:6\g{-2}0|7\g{-2}1|8\g{-2}2|9\g{-2}3|0\g{-2}4|1\g{-2}5|2\g{-2}6|3\g{-2}7|4\g{-2}8|5\g{-2}9)\g{-1}5
    |(?:7\g{-2}0|8\g{-2}1|9\g{-2}2|0\g{-2}3|1\g{-2}4|2\g{-2}5|3\g{-2}6|4\g{-2}7|5\g{-2}8|6\g{-2}9)\g{-1}6 
    |(?:8\g{-2}0|9\g{-2}1|0\g{-2}2|1\g{-2}3|2\g{-2}4|3\g{-2}5|4\g{-2}6|5\g{-2}7|6\g{-2}8|7\g{-2}9)\g{-1}7
    |(?:9\g{-2}0|0\g{-2}1|1\g{-2}2|2\g{-2}3|3\g{-2}4|4\g{-2}5|5\g{-2}6|6\g{-2}7|7\g{-2}8|8\g{-2}9)\g{-1}8
    |(?:0\g{-2}0|1\g{-2}1|2\g{-2}2|3\g{-2}3|4\g{-2}4|5\g{-2}5|6\g{-2}6|7\g{-2}7|8\g{-2}8|9\g{-2}9)\g{-1}9
    |(?:1\g{-2}0|2\g{-2}1|3\g{-2}2|4\g{-2}3|5\g{-2}4|6\g{-2}5|7\g{-2}6|8\g{-2}7|9\g{-2}8|0\g{-2}9)\g{-1}0
   )
  )
  \d
 )++

 # Paths to success
 (?:
  # A, B, and C contain no more significant digits
  (?:\.0+)?0*\ [-+]?0*\3\83(?:\.0+)?0*\ [-+]?0*\5\85(?:\.0+)?0*$
 |
  # C contains no more significant digits, match A's excess to B's
  (\.?\d*?)0*\ [-+]?0*\3\83\g{-1}(?:\.0+)?0*\ [-+]?0*\5\85$
 |
  # B contains no more significant digits, match A's excess to C's
  (\.?\d*?)0*\ [-+]?0*\3\83\ [-+]?0*\5\85\g{-1}(?:\.0+)?0*$
 |
  # A contains no more significant digits but B and C both do
  # Match pairs of digits that total 9 until one that totals 10 is found
  \.?0*\ [-+]?(?:0\B)*+\3\83\.?
  (?:
   (?=\d\d((?&f))((\g{-2}?+\.?)\d))
   (?=\d(\S*?\g{-4}\g{-2}))
   (?=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)
   \d
   (?=\S*?(\g{-5}(\g{-5})))
  )*+
  # Match a pair that totals 10 then validate
  (?=\d(\g{-3}|(?&f)\.?))
  (?=1\g{-1}9|2\g{-1}8|3\g{-1}7|4\g{-1}6|5\g{-1}5|6\g{-1}4|7\g{-1}3|8\g{-1}2|9\g{-1}1)
  \d0*\ [-+]?0*\5\85\g{-2}?+\.?\d0*$
 ) 
)

Demo on regex101 (comments removed)

This was a fantastic personal challenge that really pushed me to consider how every conceivable arrangement of digits would be matched by each piece of the regex. When, say, test case #2,490,511 erroneously failed to match and the only hint given consists solely of the three numbers that caused the failure, it’s a little tricky to know where to begin debugging. This happened over and over, prompting revision after revision, until - finally - it stopped. When I could safely conclude that the regex was fully functional, that was a very satisfying “Eureka” moment indeed.

The general method is similar to the simple, positive-integer regex that I commented exhaustively last time, and so I didn't feel the need to add as many comments this time. The individual algorithms are almost the same, but the general method has of course been expanded:



Step 1: Examine the signs of A, B, and C to determine the order of matching. There are eight possible combinations of signs: two complementary arrangements for when each of A, B, and C appear as the highest value (ie. the sum of the addition), and two invalid arrangements (“-A –B C” and “A B –C”).

In the above example, an arrangement of “A –B C” calls for verifying that B + C = A, ie. 12345.67 = 656.4321 + 11689.2379.

Step 2: Compare the excess part of the total with the excess part of the longer of the two operands, similar to last time. They will either be equal or differ by exactly 1. Note that this comparison cannot spill over into the decimal portion.

In our example, we find the excess part of A, “12”, should be compared to the excess part of C, “11”. After pairing ‘3’ and ‘6’, which total 9, we find ‘4’ and ‘8’, which yield a sum greater than 9. And so we can rightly match “12” against “11” since they differ by 1.

Step 3: Compare the equal-length portions of A, B, and C. Like before, this is done by matching pairs of digits in the two operands to their sums in the total. However, unlike before, this matching may continue into the decimal portions of the 3 numbers.

In the example, ‘3’ matches with ‘6’ and ‘6’ because of carrying (6+6=12, then + 1 = 3), and then ‘4’ matches with ‘5’ and ‘8’, and so on until A runs out of digits.

Step 4: At this stage, if the addition is correct then the only digits that could possibly remain are decimals. In fact, these residual decimal digits would exist in exactly two of A, B, or C, and there would be the same number of digits left in both. If one of these two is the total, then our final check is basic: make sure the two residual parts are equivalent (for example, 1.2 + 1.2345 = 2.4345). Otherwise, we need to match pairs of digits that total 9 until the last pair, which should total 10.

So in our example, we are left with “21” in B and “79” in C. ‘2’ and ‘7’ total 9, and then ‘9’ and ‘1’ give us 10 as needed.


Thursday, 6 September 2018

How to Match "A B C" where A+B=C: The Beast Tamed

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:

  1. 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.
  2. 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.