Chcę wypróbować nowy rodzaj golfowego wyrażenia regularnego, który prosi o rozwiązanie nietrywialnych zadań obliczeniowych bez podstawiania wyrażeń regularnych. Aby uczynić to bardziej możliwym i mniej uciążliwym, będziesz mógł zastosować kilka zmian, jedna po drugiej.

Wyzwanie

Zaczniemy od prostego: biorąc pod uwagę ciąg znaków zawierający dwie dodatnie liczby całkowite, jako liczby dziesiętne oddzielone a ,, wygeneruj ciąg zawierający ich sumę, również jako liczbę dziesiętną. Więc bardzo prosto

47,987

powinien zamienić się w

1034

Twoja odpowiedź powinna działać dla dowolnych liczb całkowitych dodatnich.

Format

Każda odpowiedź powinna być sekwencją kroków podstawienia, każdy krok składa się z wyrażenia regularnego i łańcucha zastępczego. Opcjonalnie, dla każdego z tych kroków w sekwencji, możesz powtarzać podstawienie, aż łańcuch przestanie się zmieniać. Oto przykładowe przesłanie (które nie rozwiązuje powyższego problemu):

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

Biorąc pod uwagę dane wejściowe 123,456, przedłożenie to przetworzyłoby dane wejściowe w następujący sposób: pierwsze podstawienie jest stosowane raz i daje:

|123,|456

Teraz drugie podstawienie jest stosowane w pętli, aż łańcuch przestanie się zmieniać:

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

Wreszcie trzecia zamiana jest stosowana raz:

111111

Zauważ, że kryterium zakończenia pętli jest to, czy łańcuch się zmienia, a nie czy wyrażenie regularne znalazło dopasowanie. (Oznacza to, że może również zakończyć się, jeśli znajdziesz dopasowanie, ale zamiennik jest identyczny z dopasowaniem).

Punktacja

Twój wynik główny będzie liczbą kroków podmiany w twoim zgłoszeniu. Każda powtórzona zamiana będzie się liczyła przez 10 kroków. Tak więc powyższy przykład uzyskałby wynik 1 + 10 + 1 = 12.

W (niezbyt mało prawdopodobnym) przypadku remisu wynik dodatkowy jest sumą rozmiarów wszystkich kroków. Do każdego kroku dodaj regex ( bez ograniczników), modyfikatory i łańcuch podstawienia. W powyższym przykładzie byłoby to (6 + 1 + 3) + (3 + 0 + 2) + (2 + 1 + 0) = 18.

Różne zasady

Możesz użyć dowolnego smaku wyrażenia regularnego (który powinieneś wskazać), ale wszystkie kroki muszą używać tego samego smaku. Ponadto, należy nie używać żadnych cech języka gospodarza smaku, podobnie jak callbacków zamiennych lub Perl emodyfikatora, który ocenia kod Perl. Wszelkie manipulacje muszą odbywać się wyłącznie poprzez podstawienie wyrażenia regularnego.

Pamiętaj, że to od Twojego smaku i modyfikatorów zależy, czy każda pojedyncza zamiana zastępuje wszystkie wystąpienia, czy tylko jedno. Np. Jeśli wybierzesz smak ECMAScript, pojedynczy krok domyślnie zastąpi tylko jedno wystąpienie, chyba że użyjesz gmodyfikatora. Z drugiej strony, jeśli używasz smaku .NET, każdy krok zawsze zastępuje wszystkie wystąpienia.

W przypadku języków, które mają różne metody zastępowania pojedynczej i globalnej zamiany (np. Ruby's subvs. gsub), załóż, że pojedyncza zamiana jest domyślna i traktuj globalną zamianę jak gmodyfikator.

Testowanie

Jeśli wybranym przez Ciebie smakiem jest .NET lub ECMAScript, możesz użyć Retiny do przetestowania swojego przesłania (powiedziano mi, że działa również na Mono). W przypadku innych smaków prawdopodobnie będziesz musiał napisać mały program w języku hosta, który zastosuje podstawienia w kolejności. Jeśli tak, proszę dołączyć ten program testowy do swojej odpowiedzi.

Smak .NET, wynik: 2

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

Nie interesuje mnie jeszcze gra w golfa, a xto po prostu ignorowanie białych znaków.

Najpierw wstawia 9876543210w każdej pozycji, a następnie usuwa oryginalne znaki i znaki, które nie są bieżącą cyfrą sumy.

Duże wyrażenie regularne (1346 bajtów bez białych znaków i komentarzy):

# 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)(?!))
)

To sprawiło, że pomyślałem o ostatecznym poziomie Manufaktury ... Ale myślę, że regex .NET, który oczywiście nie jest już „regularny”, może rozwiązać wszelkie problemy w PH. A to tylko algorytm w L.

Wynik: 24

Myślę, że to działa ...

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

Nie spędziłem jeszcze dużo czasu na grze w poszczególne wyrażenia regularne. Postaram się wkrótce opublikować wyjaśnienie, ale robi się już późno. Tymczasem oto wynik między każdym krokiem:

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

Pełny program perla:

$_ = <>;
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";

Dowolny smak wyrażenia regularnego, 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

Spróbujmy jedni. dsłuży do separatora cyfr, xprzechowuje wartość. Najpierw rozpakowujemy każdą cyfrę, następnie ściskamy mnożniki x10 w lewo, a następnie upuszczamy wszystkie separatory, a następnie wstawiamy mnożniki z powrotem, a następnie przekształcamy każde zamówienie z powrotem na cyfry.

.NET Regex, 14

Nie tak dobre jak rozwiązanie user23013, ale było fajnie. Żadna z zamienników nie ma modyfikatorów.

Powodem wystąpienia wyrażenia regularnego .NET nie jest chociażby bilansowanie grup - po prostu przetestowałem z Retiną , która korzysta z .NET, i odkryłem również, że różne długości lookhinds bardzo pomogły.

Zamiennik 1 (powtórzenie = nie)

Regex:

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

Zastąpienie

0$1$2

Zamień dwie liczby, wypełnianie, aby mieć taką samą liczbę zer wiodących.

Zamiennik 2 (powtórzenie = nie)

Regex:

(\d+)

Zastąpienie:

 $1

Dodaj spację przed każdą liczbą

Zamiennik 3 (powtórzenie = nie)

$

Zastąpienie:

&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

Dodaj bit przeniesienia ( &0) oraz gigantyczną tablicę odnośników <c> <a> <b> <carry of a+b+c> <last digit of a+b+c>.

Zamiennik 4 (powtórz = tak)

Regex:

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

Zastąpienie:

$4$10

Nadal bierz ostatnie cyfry każdego numeru i znajdź ich (suma, przeniesienie). Umieść sumę na początku łańcucha i zastąp carry.

Zamiennik 5 (powtórzenie = nie)

Regex:

^0*| .*

Zastąpienie:

<empty>

Sprzątać.

Przykładowy przebieg

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

^{(Łącząc kilka kroków, mogę uzyskać 12, ale ponieważ robi się dość bałagan i i tak nie wygrywa, myślę, że zamiast tego utrzymam tę bardziej elegancką wersję.)}

Wynik: 50 40 31 21

Dzięki za to wspaniałe wyzwanie. To rozwiązanie nie jest zbyt eleganckie, ale biorąc pod uwagę ograniczenia, nie widziałem żadnego sposobu, aby ogólnie potraktować cyfrę na wyjściu.

To rozwiązanie oferuje przechwytywanie grup, które czasami nie pasują, i polega na tym, że są one puste, gdy to nastąpi. Działa to w Perlu, chociaż zwykle generuje ostrzeżenie.

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)

Pełna próbka kodu Perla z wyjaśnieniem i wydrukowaniem wyników pośrednich:

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;

Aktualizacja: Byłem w stanie połączyć dwa zapętlone wyrażenia regularne, oszczędzając 10.

Aktualizacja 2: Udało mi się złamać konwersję cyfr wejściowych za pomocą jednego wyrażenia regularnego.

Aktualizacja 3: Zmniejszono do jednego wyrażenia regularnego z zapętleniem.