A regex to match three consecutive integers iff the third integer is the sum of the first two

Question

Write a regular expression which matches a given string consisting of three non-negative, space-separated integers if and only if the last integer is the sum of the previous two. Answers may be for integers of any numeral system with radix between 2 and 10.

Test cases

These should fail:

0 1 2
10 20 1000

These should match:

10 20 30
28657 46368 75025
0 0 0

Rules

Your answer should consist of a single regex, without any additional code (except, optionally, a list of regex modifiers required to make your solution work). You must not use features of your language's regex flavour that allow you to invoke code in the hosting language (e.g. Perl's e modifier).

Please specify your regex flavour in your answer.

This is regex golf, so the shortest regex in bytes wins. If your language requires delimiters (usually /.../) to denote regular expressions, don't count the delimiters themselves. If your solution requires modifiers, add one byte per modifier.

_{Credits to Martin Ender and jaytea for the regex-golfing rules.}

---

I have reason to believe it's possible based on the solution of Martin Ender for finding and incrementing integers with regex.

Answer 1

Perl/PCRE: 2,685 bytes

^(?!(?!0*+(?=(\d*?)((?:(?=\d+ 0*+(\d*?)(\d(?(4)\4)) 0*(\d*?)(\d\6?+)$)\d)+) )(?=(?(?!\1(?:(?=\d+ 0*\3((\7?+)\d))(?=\d(\d* 0*\3\8))(?=0\9[9]|1\9[8]|2\9[7]|3\9[6]|4\9[5]|5\9[4]|6\9[3]|7\9[2]|8\9[1]|9\9[0])\d)*+(?=\d(\d* 0*\3\8?+))(?=[5-9]\10[5-9]|1\10[9]|2\10[89]|3\10[7-9]|4\10[6-9]|6\10[4]|7\10[34]|8\10[2-4]|9\10[1-4]))(?=\d+ \d+ 0*\1\3\6$)|(?(?!.*+\3)\d+ )(?=\d*(\2|\4)( .*?0*+)\d+$)(?(?=9*\11 )(?:9(?=\d*\12[1](\13?+0)))*?(?=\11 )\11\12[1]\13?+\6$|(?:(\d)(?=\d*\12(\15?+\14)))*(?=\d(\d*\12\15?+))(?=0\16[1]|1\16[2]|2\16[3]|3\16[4]|4\16[5]|5\16[6]|6\16[7]|7\16[8]|8\16[9])\d(?:9(?=\d*\12\15?+\d(\17?+0)))*?\11\12\15?+\d\17?+\6$)))\1(?:(?=(\d)\d* 0*+\3((\19?+)\d)\d* 0*+\5((\21?+)\d))(?=\d(\d* 0*+\3\20)\d(\d* 0*+\5\22))(?(?!\18(?:(?=\d+ 0*+\3\19((\25?+)\d))(?=\d(\d* 0*+\3\19\26))(?=0\27[9]|1\27[8]|2\27[7]|3\27[6]|4\27[5]|5\27[4]|6\27[3]|7\27[2]|8\27[1]|9\27[0])\d)*+(?=\d(\d* 0*+\3\19\26?+))(?=[5-9]\28[5-9]|1\28[9]|2\28[89]|3\28[7-9]|4\28[6-9]|6\28[4]|7\28[34]|8\28[2-4]|9\28[1-4]))(?=1\23(?:1\24[2]|2\24[3]|3\24[4]|4\24[5]|5\24[6]|6\24[7]|7\24[8]|8\24[9]|9\24[0])|2\23(?:1\24[3]|2\24[4]|3\24[5]|4\24[6]|5\24[7]|6\24[8]|7\24[9]|8\24[0]|9\24[1])|3\23(?:1\24[4]|2\24[5]|3\24[6]|4\24[7]|5\24[8]|6\24[9]|7\24[0]|8\24[1]|9\24[2])|4\23(?:1\24[5]|2\24[6]|3\24[7]|4\24[8]|5\24[9]|6\24[0]|7\24[1]|8\24[2]|9\24[3])|5\23(?:1\24[6]|2\24[7]|3\24[8]|4\24[9]|5\24[0]|6\24[1]|7\24[2]|8\24[3]|9\24[4])|6\23(?:1\24[7]|2\24[8]|3\24[9]|4\24[0]|5\24[1]|6\24[2]|7\24[3]|8\24[4]|9\24[5])|7\23(?:1\24[8]|2\24[9]|3\24[0]|4\24[1]|5\24[2]|6\24[3]|7\24[4]|8\24[5]|9\24[6])|8\23(?:1\24[9]|2\24[0]|3\24[1]|4\24[2]|5\24[3]|6\24[4]|7\24[5]|8\24[6]|9\24[7])|9\23(?:1\24[0]|2\24[1]|3\24[2]|4\24[3]|5\24[4]|6\24[5]|7\24[6]|8\24[7]|9\24[8])|0\23(\d)\24\29|(\d)\23[0]\24\30)|(?=1\23(?:0\24[2]|1\24[3]|2\24[4]|3\24[5]|4\24[6]|5\24[7]|6\24[8]|7\24[9]|8\24[0]|9\24[1])|2\23(?:0\24[3]|1\24[4]|2\24[5]|3\24[6]|4\24[7]|5\24[8]|6\24[9]|7\24[0]|8\24[1]|9\24[2])|3\23(?:0\24[4]|1\24[5]|2\24[6]|3\24[7]|4\24[8]|5\24[9]|6\24[0]|7\24[1]|8\24[2]|9\24[3])|4\23(?:0\24[5]|1\24[6]|2\24[7]|3\24[8]|4\24[9]|5\24[0]|6\24[1]|7\24[2]|8\24[3]|9\24[4])|5\23(?:0\24[6]|1\24[7]|2\24[8]|3\24[9]|4\24[0]|5\24[1]|6\24[2]|7\24[3]|8\24[4]|9\24[5])|6\23(?:0\24[7]|1\24[8]|2\24[9]|3\24[0]|4\24[1]|5\24[2]|6\24[3]|7\24[4]|8\24[5]|9\24[6])|7\23(?:0\24[8]|1\24[9]|2\24[0]|3\24[1]|4\24[2]|5\24[3]|6\24[4]|7\24[5]|8\24[6]|9\24[7])|8\23(?:0\24[9]|1\24[0]|2\24[1]|3\24[2]|4\24[3]|5\24[4]|6\24[5]|7\24[6]|8\24[7]|9\24[8])|9\23(?:0\24[0]|1\24[1]|2\24[2]|3\24[3]|4\24[4]|5\24[5]|6\24[6]|7\24[7]|8\24[8]|9\24[9])|0\23(?:0\24[1]|1\24[2]|2\24[3]|3\24[4]|4\24[5]|5\24[6]|6\24[7]|7\24[8]|8\24[9]|9\24[0])))\d)+\ |^0+\ 0*(\d+)\ 0*\g{-1}$|^0*(\d+)\ 0+\ 0*\g{-1}$)).+

Try it online!

I've been on the prowl for difficult challenges after a hiatus from regex, and just happened to stumble across this doozy. Verifying addition (with Perl/PCRE) is something I've thought about before, but promptly dismissed as either impossible or beyond my ability. However, I took another crack at it now and I'm quite thrilled to say that I've actually done it!

I didn't really golf this other than considering short algorithms and overall matching technique when I wrote it. I'm just really happy I got it done :D

If people are interested, I could add comments and explain how it works.

Edit: I made a detailed post on my blog about this, with explanations and comments :) enjoy: http://www.drregex.com/2018/09/a-regex-i-submitted-to-reddit-climbed.html

Answer 2

.NET flavour, 139 111 106 + 1 = 107 bytes

Needs the RightToLeft modifier r. Input in binary.

(?(2)!)^\5 \7 ((?(2)()(?(2)!)(?<-2>){2})(0|(?<-2>1))(?<=(((0|(?<2>1)|\b)(?=.*(?<=(\5).*))?\7?) \d*){2}))+$

Try it online! (Using Retina.)

Yay for balancing groups. I'll explain this later...

Decimal version, 340 243 + 1 = 244 bytes

(?(2)!)^\5 \7 ((?(2)()(?(2)!)(?<-2>){10})(0|(?<-2>1|(?<-2>2|(?<-2>3|(?<-2>4|(?<-2>5|(?<-2>6|(?<-2>7|(?<-2>8|(?<-2>9))))))))))(?<=(((0|(?<2>1|(?<2>2|(?<2>3|(?<2>4|(?<2>5|(?<2>6|(?<2>7|(?<2>8|(?<2>9)))))))))|\b)(?=.*(?<=(\5).*))?\7?) \d*){2}))+$

Try it online!

Answer 3

.NET, 96 bytes

^\4 \6((?(2)()(?(2)^)(?<-2>){2}| ?)(0|(?<-2>1))(?<=((0|(?<2>1)|)\4?) .*((0|(?<2>1)|)\6?) .*))+$

Flag: r

Try it online!

Decimal version, 238 bytes

^\5 \6(?<-6>)((?(2)()(?(2)^)(?<-2>){10}| ?)((?<-2>[1469]|(?<-2>[27]))|[0358])(?([5-9])(?<-2>){5})(?([3489])(?<-2>){3})(?<=(((((?=[5-9](?<2>){5}|)(?=[3489](?<2>){3}|)((?<2>[1469]|(?<2>[27]))|.))?(?( .*)\6?(?<-6>)?|\5?(?<-5>)))) .*){2}))+$

Flag: r

Try it online!

Similar to Martin's answer.