Flagrant Badassery

A JavaScript and regular expression centric blog

Solving Algebraic Equations Using Regular Expressions

Regexes suck at math. To a regex engine, the characters 0 through 9 are no more special than any others.

I should mention that there are a couple exceptions. Perl and PCRE allow dynamic code to be run at any point during the matching process, which presents a great deal of extra potential. Perl does this with code embedded in the regex; PCRE with callouts to external functions. But those regex flavors are the exceptions, and even with them the extended capabilities only take you so far. Generally, math-related problems such as matching numeric ranges (useful for tasks like matching a set of years within longer text) are a pain in the a** to deal with, when they're possible at all.

However, the power and expressiveness of even basic regular expression syntax can lead to some nifty tricks. Things like matching only non-prime-length strings! The primality regex is somewhat famous now, but another hack that might surprise you is using regexes to solve a simple class of linear equations. I stumbled on the idea for this pattern while messing around with RegexBuddy's awesome debugger. The implementation itself is dead simple and should work pretty much universally, with the exception of strict POSIX ERE implementations or other esoteric flavors which don't allow backreferences. Here's the template:

^(.*)\1{A−1}(.*)\2{B−1}$

That lets us solve for x and y with an equation like 17x + 12y = 51. A and B are placeholders for constants that in this case are 17 and 12. So, the regex becomes ^(.*)\1{16}(.*)\2{11}$. We subtract one from values A and B because we're repeating backreferences to subpatterns that have already matched once before. If you run that regex against a 51-character string, the length of $1 (backreference one) will be 3 (which tells us that x = 3), and the length of $2 (backreference two) will be 0 (meaning that y = 0). Indeed, 17×3 + 12×0 = 51. If the problem is unsolvable, the regex will not match the string. If there are multiple possible solutions, the one with the highest value of x will be returned since x is handled earlier in the regex.

Try it out. You can use as many variables as you'd like as long as the equation follows the same form. E.g., 11x + 2y + 5z = 115 can be solved with ^(.*)\1{10}(.*)\2{1}(.*)\3{4}$ and a 115-character subject string (the result: 11×10 + 2×0 + 5×1 = 115). Run ^(.*)\1{12}$ against a 247-character string and you'll get back a 19-character value for backreference one, demonstrating that 13×19 = 247. Keep in mind that as the integers and string lengths get higher and the number of variables increase, the amount of backtracking by the regex engine will also increase. At some threshold this pattern will slow to the point that it's unusable. But I don't really care; it's still cool. wink

There Are 21 Responses So Far. »

  1. Cool. Just to be anal: you have *one* solution of many for the 17x + 12y = 51; 😀

    You need x number of equations for y number of variables. I’d go into the details, but it’s 3AM and I have a deadline at 3pm! oo noes.

    Great article.

  2. Cool. I wrote a python function to do this based on your method:

    http://xix.org/misc/solve.py

  3. To match all solutions in Perl:

    local our @solutions;
    /
    …regex from article…
    (?{ push @solutions, [$1,$2,$3] })
    (?!) # Force backtracking.
    /x

  4. Have hammer. Seems like a nail. *Swing*

  5. This seems similar (but more complex): Diophantine Equation Solver. I’m not very familiar with Perl though (aside from its regex flavor), and haven’t delved into the code.

  6. […] Solving Algebraic Equations Using Regular Expressions. This is just absolutely the geekiest coding thing I’ve seen in a while. Couldn’t not mention it. […]

  7. […] Using RegEx’s to solve algebraic equations is a novel idea — I don’t know if I’d use this, but I’d never seen this before. […]

  8. This is a good idea.Thank you.

  9. Cool. But really slow.

  10. […] ?????17x + 12y = 51 ???????????????^(.*)1{16}(.*)2{11}$ ?????11x + 2y + 5z = 115 ???????????????^(.*)1{10}(.*)2{1}(.*)3{4}$ ????????????????????????????????????????????????????????????? […]

  11. Hi… I was looking for something like it *-* for a schoolar work

    I,ll test it =)
    Ty

  12. […] ????????????????????????????????????????????????????????????? […]

  13. […] ????????????????????????????????????????????????????????????? […]

  14. […] can find a nice introduction about solving algebra equations using regex in this blog post by author of regex […]

  15. […] ????? Solving Algebraic Equations Using Regular Expressions […]

  16. […] ??????????????????????????????????????????????? ?????17x + 12y = 51 ???????????????^(.*)1{16}(.*)2{11}$ ?????11x + 2y + 5z = 115 ???????????????^(.*)1{10}(.*)2{1}(.*)3{4}$ ????????????????????????????????????????????????????????????? […]

  17. […] ????????????????????????????????????????????????????????????? […]

  18. matrix???
    exactly , almost i gust use Algebraic Equations or matrix to get RegExp when coding

  19. Male, I absolutely treasured looking over this article. You may have certain myself to join in your blog site, although just where may i uncover the particular Feed?
    coque iphone X https://www.paulsurtel.fr/coque-iphone-6.html

  20. Thanks a whole lot intended for spreading this particular using folks you will understand what occur to be speaking approximately! Bookmarked. Generously also discuss having my very own web site =). We could actually use a net alternative written agreement among us hello there!, I enjoy your own writing quite definitely! percentage we all keep up a correspondence much more your publish about AMERICA ONLINE? We would like a professional about this area in order to resolve the difficulty. Perhaps that is definitely anyone! Looking forward to fellow anyone.
    coque iphone xr https://www.neoval.fr/coque-iphone-8.html

  21. What type of serious software work are you hoping to do over a gadget that you just can’t carry out at this time? I highly recommend you remember that whenever Steve Job opportunities launched the actual apple ipad, it had been presented like a finally platform option (along having desktop pcs and laptops). Wanting a tablet to accomplish SolidWorks design and style do the job is not precisely what its intended for. For the reason that same abnormal vein, the things you may well think about to become non-serious job might be contrary the other point is customer (think salespeople). Really facts concerning workflow as well as discovering what works most effective for you.
    coque iphone xr https://www.blizzcorp.fr/

Post a Response

If you are about to post code, please escape your HTML entities (&, >, <).