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


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.

  • 1
    \$\begingroup\$ You can use any regex flavour which existed before this challenge this rule doesn't reflect current consensus, which says that languages (and therefore regex flavors) created or updated after the challenge has been posted can still compete. \$\endgroup\$ Commented Dec 13, 2017 at 20:40
  • 1
    \$\begingroup\$ Related. (I suspect answers to this will look somewhat similar to jimmy's .NET answer there.) \$\endgroup\$ Commented Dec 13, 2017 at 21:08
  • 1
    \$\begingroup\$ @EriktheOutgolfer really there is consensus that languages created after the challenge can COMPETE? That's totally nonsense \$\endgroup\$
    – edc65
    Commented Dec 14, 2017 at 11:56
  • 3
    \$\begingroup\$ @edc65 As of half a year ago. \$\endgroup\$ Commented Dec 14, 2017 at 12:14
  • \$\begingroup\$ Perl 5's /e modifier only applies to substitutions, and is not the only way to run external code. Also this disqualifies Perl 6 entirely as a regex is just a method with additional syntax. (The reason is it makes regexes easier to read and write) As a result all of the features needed in archaic regexes aren't needed (or included) as you just put in Perl 6 code. (meaning it probably isn't possible to do this challenge if you just limit to regex specific code) /^(\d+)**3%' '$ <?{$0[2]==[+] $0[0,1]}>/ or /^(\d+)' '(\d+)' '(\d+)$ <?{$2==$0+$1}>/ or /^(\d+)' '(\d+){}" {$0+$1}"$/ \$\endgroup\$ Commented Dec 15, 2017 at 17:38

3 Answers 3


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

  • 4
    \$\begingroup\$ Definitely interested in some explanations ! \$\endgroup\$
    – etene
    Commented Sep 5, 2018 at 15:25
  • 2
    \$\begingroup\$ @etene I edited the post with a link to a thorough write-up :D \$\endgroup\$
    – jaytea
    Commented Sep 6, 2018 at 19:10
  • 1
    \$\begingroup\$ Thank you, that will be an interesting read ! \$\endgroup\$
    – etene
    Commented Sep 6, 2018 at 19:15

.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!

  • 3
    \$\begingroup\$ "I'll explain this later" How much later? \$\endgroup\$
    – Οurous
    Commented Sep 6, 2018 at 11:56
  • 3
    \$\begingroup\$ @Οurous much later as it turns out. \$\endgroup\$ Commented Sep 6, 2018 at 12:25

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.