39
\$\begingroup\$

I want to try a new type of regex golf challenge, which asks you to solve nontrivial computational tasks with nothing but regex substitution. To make this more possible and less of a chore, you will be allowed to apply several substitutions, one after the other.

The Challenge

We'll start simple: given a string containing two positive integers, as decimal numbers separated by a ,, produce a string containing their sum, also as as a decimal number. So, very simply

47,987

should turn into

1034

Your answer should work for arbitrary positive integers.

The Format

Every answer should be a sequence of substitution steps, each step consisting of a regex and a replacement string. Optionally, for each of those steps in the sequence, you may choose to repeat the substitution until the string stops changing. Here is an example submission (which does not solve the above problem):

Regex    Modifiers   Replacement   Repeat?
\b(\d)   g           |$1           No
|\d      <none>      1|            Yes
\D       g           <empty>       No

Given the input 123,456, this submission would process the input as follows: the first substitution is applied once and yields:

|123,|456

Now the second substitution is applied in a loop until the string stops changing:

1|23,|456
11|3,|456
111|,|456
111|,1|56
111|,11|6
111|,111|

And lastly, the third substitution is applied once:

111111

Note that the termination criterion for loops is whether the string changes, not whether the regex found a match. (That is, it might also terminate if you find a match but the replacement is identical to the match.)

Scoring

Your primary score will be the number of substitution steps in your submission. Every repeated substitution will count for 10 steps. So the above example would score 1 + 10 + 1 = 12.

In the (not too unlikely) case of a tie, the secondary score is the sum of the sizes of all steps. For each step add the regex (without delimiters), the modifiers and the substitution string. For the above example this would be (6 + 1 + 3) + (3 + 0 + 2) + (2 + 1 + 0) = 18.

Miscellaneous Rules

You may use any regex flavour (which you should indicate), but all steps must use the same flavour. Furthermore, you must not use any features of the flavour's host language, like replacement callbacks or Perl's e modifier, which evaluates Perl code. All manipulation must happen exclusively through regex substitution.

Note that it depends on your flavour and modifiers whether each single replacement replaces all occurrences or only a single one. E.g. if you choose the ECMAScript flavour, a single step will by default only replace one occurrence, unless you use the g modifier. On the other hand, if you're using the .NET flavour, each step will always replace all occurrences.

For languages which have different substitution methods for single and global replacement (e.g. Ruby's sub vs. gsub), assume that single replacement is the default and treat global replacement like a g modifier.

Testing

If your chosen flavour is either .NET or ECMAScript, you can use Retina to test your submission (I'm being told, it works on Mono, too). For other flavours, you will probably have to write a small program in the host language which applies the substitutions in order. If you do, please include this test program in your answer.

\$\endgroup\$
  • \$\begingroup\$ If anyone has a good idea what to call this type of challenge, leave a comment! :) (Just in case I'm doing more of these in the future.) \$\endgroup\$ – Martin Ender Mar 9 '15 at 10:48
  • \$\begingroup\$ Those who like this might also enjoy Add without addition and Multiply without numbers \$\endgroup\$ – Toby Speight Jun 5 '15 at 8:07
  • \$\begingroup\$ Is Retina's regex "flavour" a valid submission? :P (I'm fairly proud of myself for managing to add two numbers at all, let alone golf it.) \$\endgroup\$ – totallyhuman Sep 13 '17 at 15:33
  • \$\begingroup\$ @icrieverytim Retina's flavour is just the .NET flavour. \$\endgroup\$ – Martin Ender Sep 13 '17 at 15:53
  • \$\begingroup\$ But Retina has features .NET doesn't have, no? \$\endgroup\$ – totallyhuman Sep 13 '17 at 15:55
32
\$\begingroup\$

.NET flavor, score:2

Regex        Modifiers  Replacement  Repeat?
<empty>      <none>     9876543210   No
<see below>  x          <empty>      No

I'm not bothered to golf it yet, and x is just for ignoring whitespaces.

It firstly insert 9876543210 at each position, then delete the original characters and the characters those are not the current digit of the sum.

The big regex (1346 bytes without whitespaces and comments):

# If the length of the left number <= right number, delete every digit on the left.
.(?=.*,(?<=^(?<len>.)*,)(?<-len>.)*(?(len)(?!)))|

# Do the opposite if it is not the case.
.(?<=(?(len)(?!))(?<-len>.)*(?=(?<len>.)*$),.*)|

# Remove leading zeros.
(?<=(^|,).{9})0|

# Delete everything that is not the current digit of the sum.
.(?!
    # For digits in the left part:
    (?<cur>.){0,9}               # cur = the matched digit
    (?=(.{11})*,)                # and find the position before the next digit.
    (?<first>)                   # first = true
    (                            # Loop on the less significant digits:
        (?<cur>){10}             # cur += 10
        (?<=                     # cur -= the current digit in this number.
            (
                0|^|
                1(?<-cur>)|
                2(?<-cur>){2}|
                3(?<-cur>){3}|
                4(?<-cur>){4}|
                5(?<-cur>){5}|
                6(?<-cur>){6}|
                7(?<-cur>){7}|
                8(?<-cur>){8}|
                9(?<-cur>){9}
            )
            .{10}
        )
        (?=
            (?<pos>.{11})*,      # pos = which digit it is.
            .*$(?<=              # cur -= the current digit in the other number.
                (
                    0|,|
                    1(?<-cur>)|
                    2(?<-cur>){2}|
                    3(?<-cur>){3}|
                    4(?<-cur>){4}|
                    5(?<-cur>){5}|
                    6(?<-cur>){6}|
                    7(?<-cur>){7}|
                    8(?<-cur>){8}|
                    9(?<-cur>){9}
                )
                .{10}
                (?(pos)(?!))     # Assert pos = 0.
                                 # Skip pos input digits from the end.
                                 # But stop and set pos = 0 if the comma is encountered.
                ((?<-pos>\d{11})|(?<=(?>(?<-pos>.)*),.{10}))*
            )
        )
        (?(first)                # If first:
            (?>((?<-cur>){10})?) #  cur -= 10 in case there is no carry.
                                 #  Assert cur = 0 or 1, and if cur = 1, set cur = 10 as carry.
            (?(cur)(?<-cur>)(?(cur)(?!))(?<cur>){10})
            (?<-first>)          #  first = false
        |                        # Else:
                                 #  cur is 10 or 20 at the beginning of an iteration.
                                 #  It must be 1 to 11 to make the equation satisfiable.
            (?<-cur>)            #  cur -= 1
            (?(cur)              #  If cur > 0:
                                 #   cur -= max(cur, 9)
                (?(cur)(?<-cur>)){9}
                (?(cur)          #   If cur > 0:
                                 #    Assert cur = 1 (was 11) and set cur = 10.
                    (?<-cur>)(?(cur)(?!))(?<cur>){10}
                |                #   Else:
                    .*(?=,)      #    cur was 2 to 10, break from the loop.
                )
            )                    #  Else cur is 0 (was 1) and do nothing.
        )
        (.{11}|,)                # Jump to the next digit.
    )*(?<=,)(?(cur)(?!))         # End the loop if it is the last digit, and assert cur = 0.
|
    # Do the same to the right part. So the sum will be calculated two times.
    # Both are truncated to the original length of the number on that side + 1.
    # Only the sum on the longer side will be preserved in the result.
    (?<cur>\d){0,9}
    (?=(\d{11})*$)
    (?<first>)
    (
        (?<cur>){10}
        (?<=
            (
                0|,|
                1(?<-cur>)|
                2(?<-cur>){2}|
                3(?<-cur>){3}|
                4(?<-cur>){4}|
                5(?<-cur>){5}|
                6(?<-cur>){6}|
                7(?<-cur>){7}|
                8(?<-cur>){8}|
                9(?<-cur>){9}
            )
            .{10}
        )
        (?=
            (?<pos>.{11})*$
            (?<=
                (
                    0|^|
                    1(?<-cur>)|
                    2(?<-cur>){2}|
                    3(?<-cur>){3}|
                    4(?<-cur>){4}|
                    5(?<-cur>){5}|
                    6(?<-cur>){6}|
                    7(?<-cur>){7}|
                    8(?<-cur>){8}|
                    9(?<-cur>){9}
                )
                .{10}
                (?(pos)(?!))
                ((?<-pos>\d{11})|(?<=^.{10})(?=(?>(?<-pos>.)*)))*
                ,.*
            )
        )
        (?(first)
            (?>((?<-cur>){10})?)
            (?(cur)(?<-cur>)(?(cur)(?!))(?<cur>){10})
            (?<-first>)
        |
            (?<-cur>)
            (?(cur)
                (?(cur)(?<-cur>)){9}
                (?(cur)
                    (?<-cur>)(?(cur)(?!))(?<cur>){10}
                |
                    .*$(?<end>)
                )
            )
        )
        (.{11}|$(?<end>))
    )*(?<-end>)(?(cur)(?!))
)

This made me think of the final level of Manufactoria... But I think .NET regex, which is obviously no longer "regular", can solve any problems in PH. And this is just an algorithm in L.

\$\endgroup\$
  • 4
    \$\begingroup\$ All hail .NET balancing groups. \$\endgroup\$ – Sp3000 Mar 9 '15 at 14:01
  • \$\begingroup\$ First I thought my five-step process was pretty good. Then I saw someone claim a solution with half the length. Then... this. Does this even count as a regex? \$\endgroup\$ – John Dvorak Mar 10 '15 at 9:20
  • 1
    \$\begingroup\$ @JanDvorak For the theoretical "regular expression", no. For "regex", yes, everybody call this a regex, and almost every regex flavor has something like this. Microsoft still call them "regular expressions" officially. \$\endgroup\$ – jimmy23013 Mar 10 '15 at 9:34
  • \$\begingroup\$ Wow, this is amazing work! \$\endgroup\$ – user230910 Jan 11 at 3:53
6
\$\begingroup\$

Score: 24

I think this works...

Regex                                                                                                                       Modifiers   Replacement             Repeat?
(?|(\d*)(\d)(,\d*)(\d)|(^,?\d*)(\d)|, |^,)                                                                                  <none>      $1$3 $2$4               Yes
$                                                                                                                           <none>      ;111111111234567890     No
0|(?|(;.*)|9(?=.*(1{9}))|8(?=.*(1{8}))|7(?=.*(1{7}))|6(?=.*(1{6}))|5(?=.*(1{5}))|4(?=.*(1{4}))|3(?=.*(111))|2(?=.*(11)))    g           $1                      No
 1{10}                                                                                                                      <none>      1                       Yes
 (?|1{9}(?=.*(9))|1{8}(?=.*(8))|1{7}(?=.*(7))|1{6}(?=.*(6))|1{5}(?=.*(5))|1{4}(?=.*(4))|1{3}(?=.*(3))|1{2}(?=.*(2))|)       g            $1                     No
 (?!\d)(?=.*(0))| |;.*                                                                                                      g           $1                      No

I haven't spent much time golfing the individual regular expressions yet. I will try to post an explanation soon, but it's getting late now. In the meantime, here's the result between each step:

'47,987'
' 9 48 77'
' 9 48 77;111111111234567890'
' 111111111 111111111111 11111111111111;111111111234567890'
'1  111 1111;111111111234567890'
'1  3 4;111111111234567890'
'1034'

Full perl program:

$_ = <>;
chomp;

do {
    $old = $_;
    s/(?|(\d*)(\d)(,\d*)(\d)|(^,?\d*)(\d)|, |^,)/$1$3 $2$4/;
} while ($old ne $_);

s/$/;111111111234567890/;

s/0|(?|(;.*)|9(?=.*(1{9}))|8(?=.*(1{8}))|7(?=.*(1{7}))|6(?=.*(1{6}))|5(?=.*(1{5}))|4(?=.*(1{4}))|3(?=.*(111))|2(?=.*(11)))/$1/g;

do {
    $old = $_;
    s/ 1{10}/1 /;
} while ($old ne $_);

s/ (?|1{9}(?=.*(9))|1{8}(?=.*(8))|1{7}(?=.*(7))|1{6}(?=.*(6))|1{5}(?=.*(5))|1{4}(?=.*(4))|1{3}(?=.*(3))|1{2}(?=.*(2))|)/ $1/g;

s/ (?!\d)(?=.*(0))| |;.*/$1/g;

print "$_\n";
\$\endgroup\$
  • \$\begingroup\$ This looks a lot like my own proof of concept. :) I had 7 non-loop substitutions though, but I didn't try particularly hard to keep them down. \$\endgroup\$ – Martin Ender Mar 9 '15 at 13:08
  • \$\begingroup\$ @MartinBüttner haha nice! I'm pretty sure my last two subs could be merged as well, but I've had enough for one day... \$\endgroup\$ – grc Mar 9 '15 at 13:10
  • \$\begingroup\$ All leading spaces intentional ? \$\endgroup\$ – Optimizer Mar 9 '15 at 13:12
  • \$\begingroup\$ @Optimizer yes. I should have chosen a better character sorry. \$\endgroup\$ – grc Mar 9 '15 at 13:13
5
\$\begingroup\$

Any regex flavor, 41

    s/0/d/g
    ...
    s/9/dxxxxxxxxx/g
rep s/xd/dxxxxxxxxxxx/g
    s/[d,]//g
rep s/(^|d)xxxxxxxxxx/xd/g
    s/(^|d)xxxxxxxxx/9/g
    ...
    s/(^|d)x/1/g
    s/d/0/g

Let's try unary. d serves for a digit order separator, x stores the value. First we unarise each digit, then we squeeze the x10 multipliers to the left, then drop all separators, then back-insert the multipliers, then convert each order back to digits.

\$\endgroup\$
5
\$\begingroup\$

.NET Regex, 14

Not as good as user23013's solution, but it was fun. None of the replacements have modifiers.

The reason for the .NET regex isn't because of balancing groups for once — I just tested with Retina, which uses .NET, and I also found that the variable length lookbehinds helped a lot.

Replacement 1 (repeat = no)

Regex:

\d(?=\d+$)|\d(?=\d+,)|\d(?=,(\d+)$)|(?<=(\d+),\d*)\d$

Replacement

0$1$2

Swap the two numbers, padding to have the same number of leading zeroes.

Replacement 2 (repeat = no)

Regex:

(\d+)

Replacement:

 $1

Add a space before each number

Replacement 3 (repeat = no)

$

Replacement:

&0 ~00000 ~00101 ~00202 ~00303 ~00404 ~00505 ~00606 ~00707 ~00808 ~00909 ~01001 ~01102 ~01203 ~01304 ~01405 ~01506 ~01607 ~01708 ~01809 ~01910 ~02002 ~02103 ~02204 ~02305 ~02406 ~02507 ~02608 ~02709 ~02810 ~02911 ~03003 ~03104 ~03205 ~03306 ~03407 ~03508 ~03609 ~03710 ~03811 ~03912 ~04004 ~04105 ~04206 ~04307 ~04408 ~04509 ~04610 ~04711 ~04812 ~04913 ~05005 ~05106 ~05207 ~05308 ~05409 ~05510 ~05611 ~05712 ~05813 ~05914 ~06006 ~06107 ~06208 ~06309 ~06410 ~06511 ~06612 ~06713 ~06814 ~06915 ~07007 ~07108 ~07209 ~07310 ~07411 ~07512 ~07613 ~07714 ~07815 ~07916 ~08008 ~08109 ~08210 ~08311 ~08412 ~08513 ~08614 ~08715 ~08816 ~08917 ~09009 ~09110 ~09211 ~09312 ~09413 ~09514 ~09615 ~09716 ~09817 ~09918 ~10001 ~10102 ~10203 ~10304 ~10405 ~10506 ~10607 ~10708 ~10809 ~10910 ~11002 ~11103 ~11204 ~11305 ~11406 ~11507 ~11608 ~11709 ~11810 ~11911 ~12003 ~12104 ~12205 ~12306 ~12407 ~12508 ~12609 ~12710 ~12811 ~12912 ~13004 ~13105 ~13206 ~13307 ~13408 ~13509 ~13610 ~13711 ~13812 ~13913 ~14005 ~14106 ~14207 ~14308 ~14409 ~14510 ~14611 ~14712 ~14813 ~14914 ~15006 ~15107 ~15208 ~15309 ~15410 ~15511 ~15612 ~15713 ~15814 ~15915 ~16007 ~16108 ~16209 ~16310 ~16411 ~16512 ~16613 ~16714 ~16815 ~16916 ~17008 ~17109 ~17210 ~17311 ~17412 ~17513 ~17614 ~17715 ~17816 ~17917 ~18009 ~18110 ~18211 ~18312 ~18413 ~18514 ~18615 ~18716 ~18817 ~18918 ~19010 ~19111 ~19212 ~19313 ~19414 ~19515 ~19616 ~19717 ~19818 ~19919

Add a carry bit (the &0) as well as the giant lookup table of <c> <a> <b> <carry of a+b+c> <last digit of a+b+c>.

Replacement 4 (repeat = yes)

Regex:

(?<=(\d),.*(\d)&)(\d)(?=.*~\3\1\2(.))|(\d)(?=,.*\d&)|(?<=\d,.*)(\d)(?=&)|^(?=.* .*(\d),.*(\d)&(\d).*~\9\7\8.(.))

Replacement:

$4$10

Keep taking the last digits of each number, and find their (sum, carry). Put the sum at the start of the string and replace the carry.

Replacement 5 (repeat = no)

Regex:

^0*| .*

Replacement:

<empty>

Clean up.

Example run

Repl no.        String
(input)         1428,57
1               000057,001428
2                000057, 001428
3                000057, 001428&0 <lookup table>
4               5 00005, 00142&1 <lookup table>
4               85 0000, 0014&0 <lookup table>
4               485 000, 001&0 <lookup table>
4               1485 00, 00&0 <lookup table>
4               01485 0, 0&0 <lookup table>
4               001485 , &0 <lookup table>
5               1485

(By combining a few of the steps I can get 12, but since it gets pretty messy and won't win anyway I think I'll keep this more elegant version up instead.)

\$\endgroup\$
4
\$\begingroup\$

Score: 50 40 31 21

Thanks for this excellent challenge. This solution isn't very elegant, but, given the restrictions, I couldn't see any way to handle a digit generically in the output.

This solution features capture groups that sometimes don't match and relies on them being empty when that occurs. This works in Perl, though it normally produces a warning.

Regex 1:     (((((((((9)|8)|7)|6)|5)|4)|3)|2)|1)|0                                            
Modifiers:   g
Replacement: <$1$2$3$4$5$6$7$8$9>             
Repeat:      no

Regex 2:     (.*)<(\d*)>(,.*)<(\d*)>|(.*)<(\d*)>(.*)|(?:(^[^<]*)b(\d*)c)?(b)\d{9}(\d)(\d*)(c)
Modifiers:   none 
Replacement: \8\1\5\3b$9$11\2\6\4c\7$10$12$13 
Repeat:      yes

Regexes 3-12: ,?baaaaaaaaac
Modifiers:    g
Replacement:  9 etc. (one for each digit)

Full Perl code sample, with explanation and printing of intermediate results:

no warnings;
use 5.16.0;

$_ = '47,987';

#Convert numbers to beans
s/(((((((((9)|8)|7)|6)|5)|4)|3)|2)|1)|0/<$1$2$3$4$5$6$7$8$9>/g;

say;
my $last;

#Combine pairs of digits, starting with least significant.
do {
    $last=$_;
    s/(.*)<(\d*)>(,.*)<(\d*)>|(.*)<(\d*)>(.*)|(?:(^[^<]*)b(\d*)c)?(b)\d{9}(\d)(\d*)(c)/\8\1\5\3b$9$11\2\6\4c\7$10$12$13/;
    say;
}
while ($last ne $_);

#Convert beans back to numbers.
s/,?b\d{9}c/9/g;
s/,?b\d{8}c/8/g;
s/,?b\d{7}c/7/g;
s/,?b\d{6}c/6/g;
s/,?b\d{5}c/5/g;
s/,?b\d{4}c/4/g;
s/,?b\d{3}c/3/g;
s/,?b\d{2}c/2/g;
s/,?b\d{1}c/1/g;
s/,?bc/0/g;

say;

Update: I was able to combine two of the looping regexes together, saving 10.

Update 2: I managed to crack the input digit conversion with a single regex.

Update 3: I reduced to a single looping regex.

\$\endgroup\$
  • \$\begingroup\$ Interesting solution. :) What do the braces do in the replacement strings? Is ${1} different from $1? Also, you might want to include the byte count in case of ties. \$\endgroup\$ – Martin Ender Mar 9 '15 at 12:45
  • \$\begingroup\$ @MartinBüttner, the braces simply separate the variable name from other characters that could be in a variable. \$\endgroup\$ – user7486 Mar 9 '15 at 12:55
  • \$\begingroup\$ Ah, that makes sense. Thanks. \$\endgroup\$ – Martin Ender Mar 9 '15 at 12:56
  • \$\begingroup\$ @MartinBüttner, I changed it to use \1, etc., instead, saving a few characters. \$\endgroup\$ – user7486 Mar 9 '15 at 12:59

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.