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\$ – Erik the Outgolfer Dec 13 '17 at 20:40
  • 1
    \$\begingroup\$ Related. (I suspect answers to this will look somewhat similar to jimmy's .NET answer there.) \$\endgroup\$ – Martin Ender Dec 13 '17 at 21:08
  • \$\begingroup\$ @EriktheOutgolfer really there is consensus that languages created after the challenge can COMPETE? That's totally nonsense \$\endgroup\$ – edc65 Dec 14 '17 at 11:56
  • 3
    \$\begingroup\$ @edc65 As of half a year ago. \$\endgroup\$ – Martin Ender Dec 14 '17 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\$ – Brad Gilbert b2gills Dec 15 '17 at 17:38

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 Sep 5 '18 at 15:25
  • 2
    \$\begingroup\$ @etene I edited the post with a link to a thorough write-up :D \$\endgroup\$ – jaytea Sep 6 '18 at 19:10
  • 1
    \$\begingroup\$ Thank you, that will be an interesting read ! \$\endgroup\$ – etene Sep 6 '18 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 Sep 6 '18 at 11:56
  • 3
    \$\begingroup\$ @Οurous much later as it turns out. \$\endgroup\$ – Martin Ender Sep 6 '18 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, privacy policy and cookie policy

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