Is it possible to increment numbers using regex substitution?

Is it possible to increment numbers using regex substitution? Not using evaluated/function-based substitution, of course.

This question was inspired by another one, where the asker wanted to increment numbers in a text editor. There are probably more text editors that support regex substitution than ones that support full-on scripting, so a regex might be convenient to float around, if one exists.

Also, often I've learned neat things from clever solutions to practically useless problems, so I'm curious.

Assume we're only talking about non-negative decimal integers, i.e. \d+.

• Is it possible in a single substitution? Or, a finite number of substitutions?

• If not, is it at least possible given an upper bound, e.g. numbers up to 9999?

Of course it's doable given a while-loop (substituting while matched), but we're going for a loopless solution here.

This question's topic amused me for one particular implementation I did earlier. My solution happens to be two substitutions so I'll post it.

My implementation environment is solaris, full example:

echo "0 1 2 3 7 8 9 10 19 99 109 199 909 999 1099 1909" |
perl -pe 's/\b([0-9]+)\b/0$1~01234567890/g' |
perl -pe 's/\b0(?!9*~)|([0-9])(?=9*~[0-9]*?\1([0-9]))|~[0-9]*/$2/g'

1 2 3 4 8 9 10 11 20 100 110 200 910 1000 1100 1910

Pulling it apart for explanation:

s/\b([0-9]+)\b/0$1~01234567890/g

For each number (#) replace it with 0#~01234567890. The first 0 is in case rounding 9 to 10 is needed. The 01234567890 block is for incrementing. The example text for "9 10" is:

09~01234567890 010~01234567890

The individual pieces of the next regex can be described seperately, they are joined via pipes to reduce substitution count:

s/\b0(?!9*~)/$2/g

Select the "0" digit in front of all numbers that do not need rounding and discard it.

s/([0-9])(?=9*~[0-9]*?\1([0-9]))/$2/g

(?=) is positive lookahead, \1 is match group #1. So this means match all digits that are followed by 9s until the '~' mark then go to the lookup table and find the digit following this number. Replace with the next digit in the lookup table. Thus "09~" becomes "19~" then "10~" as the regex engine parses the number.

s/~[0-9]*/$2/g

This regex deletes the ~ lookup table.

Wow, turns out it is possible (albeit ugly)!

In case you do not have the time or cannot be bothered to read through the whole explanation, here is the code that does it:

$str = '0 1 2 3 4 5 6 7 8 9 10 11 12 13 19 20 29 99 100 139';
$str = preg_replace("/\d+/", "$0~", $str);
$str = preg_replace("/$/", "#123456789~0", $str);
do
{
$str = preg_replace(
    "/(?|0~(.*#.*(1))|1~(.*#.*(2))|2~(.*#.*(3))|3~(.*#.*(4))|4~(.*#.*(5))|5~(.*#.*(6))|6~(.*#.*(7))|7~(.*#.*(8))|8~(.*#.*(9))|9~(.*#.*(~0))|~(.*#.*(1)))/s",
    "$2$1",
    $str, -1, $count);
} while($count);
$str = preg_replace("/#123456789~0$/", "", $str);
echo $str;

Now let's get started.

So first of all, as the others mentioned, it is not possible in a single replacement, even if you loop it (because how would you insert the corresponding increment to a single digit). But if you prepare the string first, there is a single replacement that can be looped. Here is my demo implementation using PHP.

I used this test string:

$str = '0 1 2 3 4 5 6 7 8 9 10 11 12 13 19 20 29 99 100 139';

First of all, let's mark all digits we want to increment by appending a marker character (I use ~, but you should probably use some crazy Unicode character or ASCII character sequence that definitely will not occur in your target string.

$str = preg_replace("/\d+/", "$0~", $str);

Since we will be replacing one digit per number at a time (from right to left), we will just add that marking character after every full number.

Now here comes the main hack. We add a little 'lookup' to the end of our string (also delimited with a unique character that does not occur in your string; for simplicity I used #).

$str = preg_replace("/$/", "#123456789~0", $str);

We will use this to replace digits by their corresponding successors.

Now comes the loop:

do
{
$str = preg_replace(
    "/(?|0~(.*#.*(1))|1~(.*#.*(2))|2~(.*#.*(3))|3~(.*#.*(4))|4~(.*#.*(5))|5~(.*#.*(6))|6~(.*#.*(7))|7~(.*#.*(8))|8~(.*#.*(9))|9~(.*#.*(~0))|(?<!\d)~(.*#.*(1)))/s",
    "$2$1",
    $str, -1, $count);
} while($count);

Okay, what is going on? The matching pattern has one alternative for every possible digit. This maps digits to successors. Take the first alternative for example:

0~(.*#.*(1))

This will match any 0 followed by our increment marker ~, then it matches everything up to our cheat-delimiter and the corresponding successor (that is why we put every digit there). If you glance at the replacement, this will get replaced by $2$1 (which will then be 1 and then everything we matched after the ~ to put it back in place). Note that we drop the ~ in the process. Incrementing a digit from 0 to 1 is enough. The number was successfully incremented, there is no carry-over.

The next 8 alternatives are exactly the same for the digits 1to 8. Then we take care of two special cases.

9~(.*#.*(~0))

When we replace the 9, we do not drop the increment marker, but place it to the left of our the resulting 0 instead. This (combined with the surrounding loop) is enough to implement carry-over propagation. Now there is one special case left. For all numbers consisting solely of 9s we will end up with the ~ in front of the number. That is what the last alternative is for:

(?<!\d)~(.*#.*(1))

If we encounter a ~ that is not preceded by a digit (therefore the negative lookbehind), it must have been carried all the way through a number, and thus we simply replace it with a 1. I think we do not even need the negative lookbehind (because this is the last alternative that is checked), but it feels safer this way.

A short note on the (?|...) around the whole pattern. This makes sure that we always find the two matches of an alternative in the same references $1 and $2 (instead of ever larger numbers down the string).

Lastly, we add the DOTALL modifier (s), to make this work with strings that contain line breaks (otherwise, only numbers in the last line will be incremented).

That makes for a fairly simple replacement string. We simply first write $2 (in which we captured the successor, and possibly the carry-over marker), and then we put everything else we matched back in place with $1.

That's it! We just need to remove our hack from the end of the string, and we're done:

$str = preg_replace("/#123456789~0$/", "", $str);
echo $str;
> 1 2 3 4 5 6 7 8 9 10 11 12 13 14 20 21 30 100 101 140

So we can do this entirely in regular expressions. And the only loop we have always uses the same regex. I believe this is as close as we can get without using preg_replace_callback().

Of course, this will do horrible things if we have numbers with decimal points in our string. But that could probably be taken care of by the very first preparation-replacement.

Update: I just realised, that this approach immediately extends to arbitrary increments (not just +1). Simply change the first replacement. The number of ~ you append equals the increment you apply to all numbers. So

$str = preg_replace("/\d+/", "$0~~~", $str);

would increment every integer in the string by 3.

I managed to get it working in 3 substitutions (no loops).

tl;dr

s/$/ ~0123456789/

s/(?=\d)(?:([0-8])(?=.*\1(\d)\d*$)|(?=.*(1)))(?:(9+)(?=.*(~))|)(?!\d)/$2$3$4$5/g

s/9(?=9*~)(?=.*(0))|~| ~0123456789$/$1/g

Explanation

Let ~ be a special character not expected to appear anywhere in the text.

1. If a character is nowhere to be found in the text, then there's no way to make it appear magically. So first we insert the characters we care about at the very end.

   s/$/ ~0123456789/
   

   For example,

   0 1 2 3 7 8 9 10 19 99 109 199 909 999 1099 1909
   

   becomes:

   0 1 2 3 7 8 9 10 19 99 109 199 909 999 1099 1909 ~0123456789
   

2. Next, for each number, we (1) increment the last non-9 (or prepend a 1 if all are 9s), and (2) "mark" each trailing group of 9s.

   s/(?=\d)(?:([0-8])(?=.*\1(\d)\d*$)|(?=.*(1)))(?:(9+)(?=.*(~))|)(?!\d)/$2$3$4$5/g
   

   For example, our example becomes:

   1 2 3 4 8 9 19~ 11 29~ 199~ 119~ 299~ 919~ 1999~ 1199~ 1919~ ~0123456789
   

3. Finally, we (1) replace each "marked" group of 9s with 0s, (2) remove the ~s, and (3) remove the character set at the end.

   s/9(?=9*~)(?=.*(0))|~| ~0123456789$/$1/g
   

   For example, our example becomes:

   1 2 3 4 8 9 10 11 20 100 110 200 910 1000 1100 1910
   

PHP Example

$str = '0 1 2 3 7 8 9 10 19 99 109 199 909 999 1099 1909';
echo $str . '<br/>';
$str = preg_replace('/$/', ' ~0123456789', $str);
echo $str . '<br/>';
$str = preg_replace('/(?=\d)(?:([0-8])(?=.*\1(\d)\d*$)|(?=.*(1)))(?:(9+)(?=.*(~))|)(?!\d)/', '$2$3$4$5', $str);
echo $str . '<br/>';
$str = preg_replace('/9(?=9*~)(?=.*(0))|~| ~0123456789$/', '$1', $str);
echo $str . '<br/>';

Output:

0 1 2 3 7 8 9 10 19 99 109 199 909 999 1099 1909
0 1 2 3 7 8 9 10 19 99 109 199 909 999 1099 1909 ~0123456789
1 2 3 4 8 9 19~ 11 29~ 199~ 119~ 299~ 919~ 1999~ 1199~ 1919~ ~0123456789
1 2 3 4 8 9 10 11 20 100 110 200 910 1000 1100 1910