Добавление чисел с помощью регулярных выражений

39

Я хочу попробовать новый тип задач по регулярному выражению в гольф, в котором вас просят решать нетривиальные вычислительные задачи с помощью только замены регулярных выражений. Чтобы сделать это более возможным и менее трудоемким, вам будет разрешено применить несколько замен, одну за другой.

Соревнование

Мы начнем с простого: учитывая строку, содержащую два натуральных числа в виде десятичных чисел, разделенных ,символом a , получим строку, содержащую их сумму, также в виде десятичного числа. Итак, очень просто

47,987

должен превратиться в

1034

Ваш ответ должен работать для произвольных натуральных чисел.

Формат

Каждый ответ должен быть последовательностью шагов замещения, каждый шаг состоит из регулярного выражения и строки замены. При желании для каждого из этих шагов в последовательности вы можете выбрать повторение замены до тех пор, пока строка не перестанет изменяться. Вот пример представления (который не решает вышеуказанную проблему):

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

Учитывая входные данные 123,456, эта отправка будет обрабатывать входные данные следующим образом: первая замена применяется один раз и дает:

|123,|456

Теперь вторая подстановка применяется в цикле, пока строка не перестанет меняться:

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

И, наконец, третья замена применяется один раз:

111111

Обратите внимание, что критерием завершения для циклов является то, изменяется ли строка, а не находило ли регулярное выражение совпадение. (То есть, оно также может прекратиться, если вы найдете совпадение, но замена идентична совпадению.)

счет

Ваша основная оценка будет количеством шагов замещения в вашей заявке. Каждая повторная замена будет учитываться в течение 10 шагов. Таким образом, приведенный выше пример будет оценен 1 + 10 + 1 = 12.

В (не слишком маловероятном) случае ничьи вторичная оценка представляет собой сумму размеров всех шагов. Для каждого шага добавьте регулярное выражение ( без разделителей), модификаторы и строку подстановки. Для приведенного выше примера это будет (6 + 1 + 3) + (3 + 0 + 2) + (2 + 1 + 0) = 18.

Разные правила

Вы можете использовать любой аромат regex (который вы должны указать), но все шаги должны использовать один и тот же аромат. Кроме того, вы не должны использовать какие-либо функции основного языка флейвора, такие как замена обратных вызовов или eмодификатор Perl , который оценивает код Perl. Все манипуляции должны происходить исключительно посредством замены регулярных выражений.

Обратите внимание, что от вашего вкуса и модификаторов зависит, заменяет ли каждая отдельная замена все вхождения или только один. Например, если вы выберете вариант ECMAScript, один шаг по умолчанию заменит только одно вхождение, если вы не используете gмодификатор. С другой стороны, если вы используете разновидность .NET, каждый шаг всегда заменяет все вхождения.

Для языков, которые имеют разные методы замещения для одиночной и глобальной замены (например, Ruby's subvs. gsub), предположим, что единичная замена используется по умолчанию, и обрабатывайте глобальную замену как gмодификатор.

тестирование

Если выбранный вами вариант - .NET или ECMAScript, вы можете использовать Retina для проверки вашего предложения (мне говорят, это работает и на Mono). Для других вариантов вам, вероятно, придется написать небольшую программу на языке хоста, которая применяет замены по порядку. Если да, включите эту тестовую программу в свой ответ.

Мартин Эндер
источник
Если у кого-то есть хорошая идея, как назвать этот тип вызова, оставьте комментарий! :) (на всякий случай, если я сделаю больше таких вещей в будущем.)
Мартин Эндер,
Те, кому это нравится, могут также наслаждаться добавлением без добавления и умножением без номеров
Тоби Спейт
Является ли регулярное выражение Retina «вкусом» верным представлением? : P (Я очень горжусь собой за то, что сумел добавить два числа вообще, не говоря уже
об
@icrieverytim Retina - это просто вкус .NET.
Мартин Эндер
Но Retina имеет функции .NET не имеет, нет?
полностью человек

Ответы:

32

.NET аромат, оценка: 2

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

Я еще не удосужился поиграть в гольф, и xпросто для игнорирования пробелов.

Сначала вставьте 9876543210в каждую позицию, затем удалите оригинальные символы и символы, которые не являются текущей цифрой суммы.

Большое регулярное выражение (1346 байт без пробелов и комментариев):

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

Это заставило меня задуматься о конечном уровне Мануфактуры ... Но я думаю, что регулярное выражение .NET, которое, очевидно, больше не является "регулярным", может решить любые проблемы в PH. И это всего лишь алгоритм в L.

jimmy23013
источник
4
Все приветствуют .NET балансировки групп.
Sp3000
Сначала я подумал, что мой пятиступенчатый процесс был довольно хорош. Потом я увидел, что кто-то претендует на решение с половиной длины. Тогда ... это. Это даже считается регулярным выражением?
Джон Дворжак
1
@JanDvorak Для теоретического "регулярного выражения", нет. Для "регулярного выражения", да, все называют это регулярным выражением, и почти у каждого вида регулярного выражения есть что-то подобное. Microsoft до сих пор официально называет их « регулярными выражениями ».
jimmy23013
Вау, это потрясающая работа!
user230910
6

Оценка: 24

Я думаю, что это работает ...

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

Я еще не проводил много времени в гольфе на отдельных регулярных выражениях. Я постараюсь опубликовать объяснение в ближайшее время, но сейчас уже поздно. А пока вот результат между каждым шагом:

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

Полная программа Perl:

$_ = <>;
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";
GRC
источник
Это очень похоже на мое собственное доказательство концепции. :) У меня было 7 замен без петель, но я не особенно старался их сдерживать.
Мартин Эндер
@ MartinBüttner, ха-ха, приятно! Я почти уверен, что мои последние два саба также могут быть объединены, но мне хватило одного дня ...
grc
Все ведущие пространства намеренно?
Оптимизатор
@ Оптимизатор да. Я должен был выбрать лучшего персонажа извините.
grc
5

Любое регулярное выражение, 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

Давайте попробуем унарный. dслужит для разделителя порядкового номера, xсохраняет значение. Сначала мы сжимаем каждую цифру, затем сжимаем множители x10 влево, затем отбрасываем все разделители, затем вставляем обратно множители, а затем преобразуем каждый ордер обратно в цифры.

Джон дворак
источник
5

.NET Regex, 14

Не так хорошо, как решение пользователя 23013, но это было весело. Ни одна из замен не имеет модификаторов.

Причина .NET регулярных выражений не в том, что на этот раз балансировка групп - я только что протестировал Retina , которая использует .NET, и обнаружил, что lookbehinds переменной длины очень помогли.

Замена 1 (повтор = нет)

Regex:

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

замена

0$1$2

Поменяйте местами два числа, добавив одинаковое количество ведущих нулей.

Замена 2 (повтор = нет)

Regex:

(\d+)

Замена:

 $1

Добавьте пробел перед каждым номером

Замена 3 (повтор = нет)

$

Замена:

&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

Добавьте бит для переноса ( &0) и гигантский справочный стол <c> <a> <b> <carry of a+b+c> <last digit of a+b+c>.

Замена 4 (повтор = да)

Regex:

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

Замена:

$4$10

Продолжайте брать последние цифры каждого номера и найдите их (сумма, перенос). Поместите сумму в начале строки и замените перенос.

Замена 5 (повтор = нет)

Regex:

^0*| .*

Замена:

<empty>

Убирайся

Пример запуска

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

(Комбинируя несколько шагов, я могу получить 12, но, поскольку это становится довольно грязным и не выиграет в любом случае, я думаю, что я оставлю эту более элегантную версию вместо этого.)

Sp3000
источник
4

Оценка: 50 40 31 21

Спасибо за этот отличный вызов. Это решение не очень изящно, но, учитывая ограничения, я не мог найти никакого способа для обработки общей цифры в выводе.

Это решение имеет группы захвата, которые иногда не совпадают, и полагается, что они будут пустыми, когда это происходит. Это работает в Perl, хотя обычно выдает предупреждение.

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)

Полный пример кода Perl с объяснением и печатью промежуточных результатов:

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;

Обновление: я смог объединить два регулярных выражения, сохранив 10.

Обновление 2: мне удалось взломать преобразование входных цифр с помощью одного регулярного выражения.

Обновление 3: я сократил до регулярного регулярного выражения.


источник
Интересное решение. :) Что делать брекеты в заменяющих струнах? Отличается ${1}от $1? Кроме того, вы можете включить количество байтов в случае связей.
Мартин Эндер
@ MartinBüttner, фигурные скобки просто отделяют имя переменной от других символов, которые могут быть в переменной.
Ах, это имеет смысл. Спасибо.
Мартин Эндер
@ MartinBüttner, я изменил его, чтобы использовать \1, и т. Д., Вместо того, чтобы сохранить несколько символов.