Учитывая строку символов, +=-где есть хотя бы один =, вставьте положительные целые числа между всеми символами и в начале и в конце так, чтобы выполнялись математические уравнения.

Например, учитывая вход

+-=-=

вам нужно вставить положительные целые числа от A до F, как это

A+B-C=D-E=F

так что все уравнения выполняются, т. е. A + B - Cи D - Eи Fвсе имеют одинаковое число.

Есть много возможных способов сделать это, так как, пока уравнения работают, любой набор положительных целых чисел может использоваться. Каждая строка здесь является возможным допустимым выводом для ввода +-=-=:

2+3-4=6-5=1
1+1-1=2-1=1
4+2-4=4-2=2
100+1-10=182-91=91
89+231-77=1024-781=243

Обратите внимание, что значение выражений не обязательно должно быть положительным целым числом, как в случае вставленных чисел. Например, при заданном входе -=-выходы 1-10=8-17(значение до -9) и 10-1=17-8(значение до 9) одинаково действительны. Конечно, для некоторых входных данных, например =, нельзя использовать отрицательное выражение, поскольку 5=5можно вставлять только положительные числа, подобные .

Обратите внимание, что ноль не является положительным целым числом.

Самый короткий код в байтах побеждает.

Вы можете выводить числа в виде списка, а не вставлять их непосредственно в строку. Если вы выводите строку, могут быть пробелы, разделяющие символы и цифры. Итак, для ввода +-=-=, вывода

2, 3, 4, 6, 5, 1

или

2 + 3 - 4 = 6 - 5 = 1

эквивалентно выводу

2+3-4=6-5=1

Тестовые случаи

Input | One Possible Output
= | 1=1
== | 2=2=2
+= | 1+3=4
=+ | 2=1+1
-= | 30-10=20
=- | 1=2-1
=-= | 3=7-4=3
=+= | 2=1+1=2
=== | 100=100=100=100
+=- | 3+2=7-2
-=+ | 7-2=3+2
+=+ | 3+3=3+3
-=- | 1-10=8-17
--= | 60-1-1=58
++= | 60+1+1=62
-+= | 60-9+1=52
+-= | 60+9-1=68
+-=-= | 2+3-4=6-5=1
--=-- | 2-1-1=2-1-1
==-== | 47=47=50-3=47=47
=++=+-=-+=--= | 3=1+1+1=3+1-1=1-1+3=5-1-1=3
+--++-=-+-+- | 35+10-16-29+20+107-1000=5-4+3-2+1-876
====== | 8=8=8=8=8=8=8

Сетчатка , 58 байт

[-+]
$&1
\B((\+1)|(-1))*
$._$*1$#3$*1$#2$*_$&
+`1_

1+
$.&

Попробуйте онлайн!

Альтернативное решение с тем же количеством байтов:

((\+)|(-))*
$._$*1$#3$*1$#2$*_$&
+`1_

([+-])1*
$+1
1+
$.&

Попробуйте онлайн!

объяснение

Основная идея состоит в том, чтобы превратить все +s и -s в простые +1и -1операции, а затем добавить достаточно большое число, которое заставляет работать все уравнения. Чтобы привести уравнения в соответствие, мы можем просто добавить одно и то же число к каждому из них, а затем уменьшить его на единицу для каждого +1и увеличить на единицу для каждого -1после него. Поскольку мы будем работать с унарными числами, единственный улов заключается в том, что первое число должно быть достаточно большим, чтобы мы могли уменьшить его в 1 раз.

[-+]
$&1

Мы начинаем с вставки 1после каждого -или +.

\B((\+1)|(-1))*
$._$*1$#3$*1$#2$*_$&

В \Bгарантирует , что эти матчи либо в начале ввода, или между =и +или -, то есть все позиции , где мы хотим вставить ведущее число выражения. Затем ((\+1)|(-1))*часть просто считает количество +1s и -1s в группах 2и 3соответственно. Теперь давайте разберем строку подстановки:

$._$*1   # For each character in the current string, insert a 1. This is
         # an offset which is the same for each expression and is guaranteed
         # to be large enough that all subsequent +1s can be cancelled.
$#3$*1   # For each -1, insert a 1.
$#2$*_   # For each +1, insert a _.
$&       # Re-insert the string of +1s and -1s.

+`1_

Неоднократно удаляйте 1_из строки, применяя необходимые отмены из +1s.

1+
$.&

Наконец, замените все строки 1s их длинами, чтобы преобразовать их из унарной в десятичную.

Python 2 , 76 байт

lambda e:sum([[len(e+s)-2*s.count('+')]+[1]*len(s)for s in e.split('=')],[])

Попробуйте онлайн!

Python 2, 199 179 178 172 162 158 156 152 151 байт

Слишком долго, но решение было легко создать.

from itertools import*
i=input()
k='%s'
s=k+k.join(i)+k
for p in product(*[range(1,65537)]*-~len(i)):
    if eval((s%p).replace('=','==')):print s%p;break

Попробуйте онлайн

Это попробует каждую возможность, пока не найдет решение. Программа очень медленная. Он также выполняет замену строки на каждой итерации. Редактирование «172» сделало его значительно медленнее, поскольку вместо того, чтобы начинать с небольшого диапазона, оно начинается с максимума. Например, входы -=или =+нужно попробовать 2 ** 32 попытки до достижения решения.

Чтобы ускорить программу, используйте версию с 178 байтами из истории редактирования.

JavaScript (ES6), 92 82 байта

Гольф 8 байтов с трюком от @xnor

let f =
x=>x.split`=`.map(q=>(x+q).length-2*~-q.split`+`.length+[...q,''].join(1)).join`=`

<input oninput="if(/^[+=-]+$/.test(value))O.innerHTML=f(value)" value="="><br>
<pre id=O>1=1</pre>

Хитрость заключается в том, чтобы вставить 1после каждого +или -, а затем добавить к каждому выражению число, которое делает выражение равным длине ввода. Таким образом, мы можем гарантировать, что число всегда положительно; поскольку =в строке всегда есть хотя бы 1 , число +s никогда не может достигать длины строки, поэтому остаток всегда равен по крайней мере 1. Вы можете убедиться в этом, введя произвольное число +s в приведенном выше фрагменте.

Python 2 , 120 119 байт

^{-1 байт благодаря mbomb007}

a=['1'+(n and('1'.join(n)+'1'))for n in input().split('=')]
print'='.join(`max(map(eval,a))-eval(c)+1`+c[1:]for c in a)

Попробуйте онлайн! или проверить все контрольные примеры

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

GNU Prolog, 156 байт

x(L,R,V)-->{E#>0},({L=[E|R],E=V};x(L,[E|R],X),("+",{V#=X+E};"-",{V#=X-E})).
q(L,R,V)-->x(L,T,V),({T=R};"=",q(T,R,V)).
s(Q,L):-q(L,[],_,Q,[]),fd_labeling(L).

объяснение

Нам нужно решить несколько уравнений, так почему бы не использовать реальный решатель уравнений?

xв основном является оценщиком уравнений для уравнений вида +-+; в дополнение к самому уравнению у него есть два дополнительных аргумента (список разностей, L,Rкоторый содержит значения уравнения и значение V, к которому уравнение оценивает). Как обычно в Прологе, его можно использовать любым способом (например, вы можете указать Vи получить L,R, указать L,Rи получить V, указать и то, и другое, и убедиться, что значение верное, или не указывать ни то, ни другое, в этом случае соответствующие ограничения будут наложены на оба Vи L,R). «Текущий элемент» из L,Rназван E, и мы также включаем утверждение, чтоEбольше 0 (потому что вопрос требует использования положительных чисел). Эта функция немного более многословна, чем мне бы хотелось, например, мне пришлось написать [E|R]шаблон сопоставления / несоответствия дважды из-за того факта, что списки ассоциированы справа, но сложение и вычитание ассоциированы слева. К сожалению, для работы нам нужно использовать фактический список, а не придумывать свой собственный левоассоциативный тип списка из cons-ячеек fd_labeling.

qпохоже x, но также включает в себя =. Это в основном просто звонки x, а само по себе рекурсивно. Кстати, это очень наглядная демонстрация того , как разница списки работы, показывая , что вы можете объединить два разностных списки L,Tи T,Rв единый список разницы L,R. Основная идея заключается в том, что список различий является частичной функцией, которая принимает аргумент Rи возвращает значение, к Lкоторому Rдобавлен сам список. Таким образом, идентифицируя аргумент одного списка различий и возвращаемое значение другого, мы можем составлять функции и, таким образом, объединять списки.

Наконец, sфункция, которая фактически решает задачу в вопросе, является функцией-оболочкой, вызываемой qс аргументами. Мы преобразуем список различий в обычный список, предоставляя []его в качестве аргумента, и используем его, fd_labelingчтобы найти решение уравнения, которое мы создали. (По умолчанию, похоже, что значение 1 установлено, если нет причин устанавливать их на что-то другое. Однако его можно настроить; оно value_method(random)дает более «интересные» решения, чем, например, повсеместное размещение 1 с, и все еще очень быстро. )

Образец вывода

С программой как написано:

| ?- s("=++=+-=-+=--=", V).

V = [3,1,1,1,3,1,1,3,1,1,5,1,1,3] ?

Если я добавлю программу немного дольше value_method(random), результат будет разным, но выглядит примерно так:

| ?- s("=++=+-=-+=--=", V).

V = [68,6,12,50,85,114,131,45,3,26,71,1,2,68] ? 

В обоих случаях, ?в конце вывода означает, что может быть более одного решения. (Конечно, в этом случае мы знаем, что существует гораздо больше, чем одно решение!)

Mathematica, 116 байт

Join@@(Prepend[#^2,1-Min[Tr/@c]+Tr@#]&/@(c=Characters@StringSplit["0"<>#<>"0","="]/."+"->-1/."-"->1/."0"->Nothing))&

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

c=Characters@StringSplit[#,"="]/."+"->-1/."-"->1разделит входную строку на каждый знак равенства, а затем заменит каждый +на -1и каждый -на 1. Однако, если в начале или конце есть знак равенства, он будет проигнорирован. Поэтому мы искусственно добавляем новый символ в каждый конец ( "0"<>#<>"0") и убираем его после завершения разбиения строки ( /."0"->Nothing).

Сумма каждого подсписка теперь равна целому числу, которое мы можем поставить перед +s и -s, чтобы сделать каждое выражение равным. 1-Min[Tr/@c]это наименьшее целое число, которое мы можем добавить к каждому итогу, чтобы сделать их все положительными. Таким образом, Prepend[#^2,1-Min[Tr/@c]+Tr@#]&берет каждый подсписок ( ^2поворачивает все их записи 1) и добавляет его общее смещение на это наименьшее компенсирующее целое число. Полученные списки Joinредактируются вместе, чтобы произвести вывод.

Руби, 76

->s{(?1+s.gsub(/./){|a|a+?1}).split(?=).map{|e|e[0]="#{5**8-eval(e)}";e}*?=}

Целевое значение для выражений установлено в 5**8минус 1 по причинам, связанным с игрой в гольф! Первоначально я использовал s.size+1минус 1.

Неуправляемый в тестовой программе

f=->s{(?1+s.gsub(/./){|a|a+?1}).           #add a 1 at the beginning and after every symbol
       split(?=).                          #split into an array of expressions at = signs
       map{|e|                             #for each expression string
         e[0]="#{5**8-eval(e)}";e          #change the first number to 5**8-eval(e)
       }*?=                                #and rejoin the strings
}


puts f["="] 
puts f["=="] 
puts f["+="] 
puts f["=+"]
puts f["-="]
puts f["=-"]
puts f["=-="]
puts f["=+="]
puts f["==="]
puts f["+=-"]
puts f["-=+"]
puts f["+=+"]
puts f["-=-"]
puts f["--="]
puts f["++="]
puts f["-+="]
puts f["+-="]
puts f["+-=-="]
puts f["--=--"]
puts f["==-=="]
puts f["=++=+-=-+=--="]
puts f["+--++-=-+-+-"]
puts f["======"]

Выход

390624=390624
390624=390624=390624
390623+1=390624
390624=390623+1
390625-1=390624
390624=390625-1
390624=390625-1=390624
390624=390623+1=390624
390624=390624=390624=390624
390623+1=390625-1
390625-1=390623+1
390623+1=390623+1
390625-1=390625-1
390626-1-1=390624
390622+1+1=390624
390624-1+1=390624
390624+1-1=390624
390624+1-1=390625-1=390624
390626-1-1=390626-1-1
390624=390624=390625-1=390624=390624
390624=390622+1+1=390624+1-1=390624-1+1=390626-1-1=390624
390624+1-1-1+1+1-1=390625-1+1-1+1-1
390624=390624=390624=390624=390624=390624=390624

PHP, 207 204 197 114 байтов

прямой подход: намного короче и быстрее

foreach(explode("=",$argn)as$t)echo"="[!$c],strlen($argn)+($c=count_chars($t))[45]-$c[43],@chunk_split($t,!!$t,1);

Запустите echo '<input>' | php -nR '<code>'или протестируйте его онлайн .

сломать

foreach(explode("=",$argn)as$t) // loop through terms
    echo                            // print ...
        "="[!$c],                       // 1. "=" if not first term
        strlen($argn)                   // 2. maximum number
            +($c=count_chars($t))[45]   //    + number of "-"
            -$c[43],                    //    - number of "+"
        @chunk_split($t,!!$t,1);        // 3. each operator followed by "1"

• !$cверно в первой итерации, приведенной к 1для индексации строки; "="[1]пустой.
  После этого $cустанавливается и !$cложь, приводится к 0и "="[0]является первым символом.
• Максимальное значение для любого термина не должно превышать количество плюсов +1;
  таким образом, мы определенно в безопасности с длиной ввода. Все условия оценят к этому.
• chunk_split($s,$n,$i)вставляет $iпосле каждого $nсимвола $s- и в конце.
  Чтобы предотвратить обращение пустых терминов к 1, принудительно устанавливается ошибка, устанавливающая длину куска 0.

Röda , 112 110 109 байт

f x{[(`:$x:`/"=")()|{|p|p~=":",""a=p;a~=`\+`,""b=p;b~="-","";["=",#x-#b+#a];{(p/"")|{|o|[o,"1"*#o]}_}}_][1:]}

Попробуйте онлайн!

Функция разделения не работала так, как я предполагал с этой программой. Например, split("", sep="")возвращает одну пустую строку вместо ничего. Как это логично? Благодаря этому программа почти на 20 байтов больше, чем могла бы быть, если бы семантика разбиения была идеальной.

Идея этого ответа состоит в том, что мы знаем, что длина входной строки должна быть больше или равна значению уравнения, поэтому мы определяем значение уравнения как длину строки. Для каждой части уравнения мы думаем, что каждый оператор является +1или -1и вычитаем и добавляем их к значению уравнения.

Ungolfed:

function f(x) {
    /* Adds ":"s around the string to prevent "=" being split wrong. */
    [split(`:$x:`, sep="=") | for p do
        p ~= ":", ""          /* Removes colons. */
        a := p; b := p        /* Initializes a and b to be p. */
        a ~= "\\+", ""        /* The lengths of a and are now equal to the */
        b ~= "-", ""          /* numbers of "-" and "+" characters in x. */
        push("=", #x-#b+#a)   /* Prints "=" and the value of the equation */
                              /* minus number of "+"s plus number of "-"s. */
        split(p, sep="") | for o do /* For each operator: */
            push(o)                 /* Prints the operator. */
            push(1) if [o != ""]    /* Prints 1 unless the operator is "". */
        done
    done][1:] /* Removes the first character of the output ("="). */
}