Наименьшее количество операций до 100

15

обзор

Учитывая список цифр, найдите наименьшее количество операций, чтобы сделать 100

вход

Строка цифр, которая может быть или не быть в числовом порядке. Порядок цифр не может быть изменен, однако операторы плюс (+) или минус (-) могут быть добавлены между каждым, так что общая сумма равна 100.

Выход

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

Примеры

действительный

Вход: 123456789
Выход:3 123–45–67+89

Неверный
ввод: 123456789
вывод:
6 1+2+34-5+67-8+9
(Есть способы решения этой проблемы с меньшим количеством операций)

CyberJacob
источник
Должны ли мы использовать все цифры? Можем ли мы использовать только +и -? Можем ли мы предположить, что мы всегда сможем сделать 100из входа?
TheLethalCoder
6
Хотелось бы еще несколько тестов.
Арно
2
Можете ли вы подтвердить, что знаки не могут быть добавлены к первой цифре? То есть, учитывая данные 299399, будет -299+399действительным?
Луис Мендо
1
«0» - это цифра? Например, '10808' является действительным входом? Является ли '1 108-08' действительным ответом?
Час Браун

Ответы:

10

JavaScript (ES6), 153 176 байт

РЕДАКТИРОВАНИЕ: В нестрогом режиме JS интерпретирует числовые выражения с префиксом 0 как восьмеричные (например 017, анализируется как 15 в десятичном виде). Это фиксированная версия, которая поддерживает ведущие нули.

let f =

s=>[...Array(3**(l=s.length,l-1))].map((_,n)=>m=eval((x=s.replace(/./g,(c,i)=>c+['','+','-'][o=(n/3**i|0)%3,j-=!o,o],j=l)).replace(/\b0+/g,' '))-100|j>m?m:(S=x,j),m=l)&&m+' '+S

console.log(f("123456789"))
console.log(f("20172117"))

Arnauld
источник
Хорошо, как насчет 20172117 в качестве ввода?
17
@ LuisMendo На самом деле, я думаю, что ожидаемый ответ 2-017-2+117. Но 017это восьмеричное обозначение в JS, которое дает 15 в десятичном виде. Так что мой текущий код только находит 2-0-17-2+117. Я постараюсь решить эту проблему позже сегодня.
Арно
@Arnauld Ах, я не видел другого решения. Удаление моего комментария
Луис Мендо
@mdahmoune Спасибо, что подняли это. Сейчас исправлено.
Арно
3**(l=s.length,l-1)=>3**~-(l=s.length)
l4m2
5

MATL , 37 36 байт

n'+-'OhZ^!t2\s&SZ)"G@!vXzU100=?@z3M.

Тестовый пример занимает около 6 секунд в TIO.

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

Как это устроено

n        % Implicitly input a string. Number of elements, say k
'+-'     % Push this string
Oh       % Append char 0. This is treated like ' ' (space)
Z^       % Cartesian power of the three-char string '+- ' raised to k.
         % Gives a matrix where each row is a Cartesian k-tuple
!        % Transpose
t        % Duplicate
2\       % Modulo 2. This turns '+' and '-' into 1, and ' ' into 0
s        % Sum of each column: number of '+' and '-' symbols
&S       % Sort and push the indices of the sorting
Z)       % Apply as column indices. This sorts the columns (k-tuples)
         % by the number of '+' and '-' they contain
"        % For each column, i.e. each k-tuple formed by '+', '-' and ' '
  G      %   Push input string again
  @!     %   Push k-tuple as row vector (string)
  v      %   Concatenate vertically into a 2×k char array
  Xz     %   Remove space (and char 0). Gives a string as result. In this
         %   process, the 2×k array is linearized in column major order 
         %   (down, then across). So the '+' and '-' signs are between 
         %   digits of the input, or at the end
  U      %   Convert to number. This performs the operation determined by
         %   by the '+' and '-' signs and returns the result. A trailing
         %   '+' or '-' sign makes the input invalid, which causes an
         %   empty result
  100=   %   Is it equal to 100?
  ?      %   If so
    @    %     Push current k-tuple
    z    %     Number of nonzeros, i.e. of '+' and '-' signs
    3M   %     Push linearized string without spaces again
    .    %     Break for loop
         %   Implicit end
         % Implicit end
         % Implicitly dispplay stack
Луис Мендо
источник
Отлично, а как насчет 299399 на входе?
17
1
@mdahmoune 299399не имеет решения и, следовательно, не является допустимым вводом (операторы были указаны для перехода «между» цифрами, для этого ввода потребуется, -299+399чтобы -между цифрами не было).
Джонатан Аллан
@mdahmoune Если знаки могут быть вставлены только между цифрами (как говорится в тексте запроса), я думаю, что нет никакого решения. Если они также могут быть добавлены к первой цифре, решение будет -299+399, и в этом случае мне нужно небольшое изменение в моем коде . Я попросил у ОП уточнения
Луис Мендо
Также следует отметить, что если это должно быть как до, так и между ними, то в примере 123456789должно быть число операторов 4not 3.
Джонатан Аллан
@mdahmoune ОП подтвердил, что знаки могут быть только между цифрами. Так что мой код верен и 299399является недопустимым входом, потому что, как выяснил ОП, каждый вход должен иметь хотя бы одно решение
Луис Мендо
3

[Python 2], 164 158 байт

from itertools import*
f=lambda N:min((len(s)-len(N),s)for s in(''.join(sum(zip(N,p+('',)),()))for p in product(('+','-',''),repeat=len(N)-1))if eval(s)==100)

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

Возьмите N как строку цифр; возвращает кортеж (numOps, expressionString).

В основном такой же подход, как и другие; использует itertools.product для построения отдельных «падежей», например, для N == «1322», «падеж» будет иметь ('-','','+')значение 1-32 + 2.

Выдает ValueError, если ввод неверен (но я думаю, что OP гарантированно не допустил ввод).

Час Браун
источник
3

PHP, 166 171 байт

for(;$n<3**$e=strlen($x=$argn);eval("return $s;")-100?:$r[]=sprintf("%2d $s",strlen($s)-$e))for($i=0,$s="",$k=$n++;a&$c=$x[$i];$k/=3)$s.="+-"[$i++?$k%3:2].$c;echo min($r);

Запустите как трубу с -nRили проверьте это онлайн .

использует форматированные числа для сортировки результатов ->
может печатать начальные пробелы (и может не сработать при вводе более 99 цифр; увеличьте число при %2dисправлении).

не более 10 цифр, 161 байт

for(;$n<3**$e=strlen($x=$argn);eval("return $s;")-100?:$r[]=(strlen($s)-$e)." $s")for($i=0,$s="",$k=$n++;a&$c=$x[$i];$k/=3)$s.="+-"[$i++?$k%3:2].$c;echo min($r);

сломать

for(;$n<3**$e=strlen($x=$argn); # loop $n up
    eval("return $s;")-100?:        # 2. evaluate term, if 100 then
                                    # prepend number of operations, add to results
        $r[]=sprintf("%2d $s",strlen($s)-$e)
)
                                # 1. create term
    for($i=0,$s="",$k=$n++;         # init variables, increment $n
        a&$c=$x[$i];$k/=3)          # loop through digits/operator index
        $s.="+-"[$i++?$k%3:2].$c;   # prepend operator for base-3 digit (nothing for 2)
echo min($r);                   # print lowest result
Titus
источник
3

Желе , 32 байта

L’⁾+_ṗż@€
ŒṖÇ€ẎµFV=ȷ2µÐfLÞḢFṄḟ³L

Полная программа, которая отображает с использованием операторов Jelly ( _вместо -).

Замечания: для отображения -в выходных данных вместо _(не обязательно) добавьте ⁾_-yмежду Fи ( ⁾_-является литералом пары символов ['_','-']и yявляется диадическим атомом "перевода").

Как?

L’⁾+_ṗż@€ - Link 1, form all sums from a partition: list of lists of characters
                                     e.g. ["12","345","67"]
L         - length                        3
 ’        - decremented                   2
  ⁾+_     - literal ['+','_']
     ṗ    - Cartesian power               ["++","+_","_+","__"]
      ż@€ - zip for €ach (swap @rguments) ["12+345+67","12+345_67","12_345+67","12_345_67"]

ŒṖÇ€ẎµFV=ȷ2µÐfLÞḢFṄḟ³L - Main link: list of characters
ŒṖ                     - all partitions
  Ç€                   - call the last link (1) as a monad for €ach
    Ẏ                  - tighten (flatten by 1 level)
     µ     µÐf         - filter keep if:
      F                -   flatten
       V               -   evaluate as Jelly code (perform the sum)
         ȷ2            -   literal 100
        =              -   equal?
               Þ       - sort by:
              L        -  length
                Ḣ      - head
                 F     - flatten
                  Ṅ    - print that and a newline
                   ḟ³  - filter out the characters from the input
                     L - length (number of operators)
                       - implicit print

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

Джонатан Аллан
источник
2

Математика, 136 146 149 156 165 166 байтов

#&@@Sort[{StringLength@#-e+9!(ToExpression@#-100)^2,#}&/@StringJoin/@(Riffle[b,#]&)/@Tuples[{"","+","-"},(e=Length[b=Characters@#])-1]]&

Возвращает {3, 123-45-67+89}к примеру.

Тестовый пример занимает около 0,09 секунды.

Кейу Ган
источник
2

Python 2 , 256 230 208 205 172 171 170 165 байтов, итерационный метод

  • 33 благодаря Часу Брауну
  • Один сохраненный байт при замене len(a)наw
  • Один сохраненный байт при замене z-=1;d=zнаd=z=z-1
q=[];a=input()
w=len(a);z=n=3**w
while z-n/3:
 d=z=z-1;j=0;b=''
 while d:r=d%3;d/=3;b+=a[j]+chr(r+43)*(d>0!=r-1);j+=1
 if eval(b)==100:q+=[(len(b)-w,b)]
print min(q)

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

Небольшое объяснение Используя представление в базе 3, код чередует цифры с операторами {'+', '-', конкатенация} в соответствии со всеми возможными комбинациями.

Python 2 , 167 байт, рекурсивный метод

def f(s):
 if len(s)==1:return[s]
 b=s[0];q=[]
 for z in f(s[1:]):q+=[b+'+'+z,b+'-'+z,b+z]
 return q
a=input()
print min((len(x)-len(a),x)for x in f(a)if eval(x)==100)

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

Некоторые выводы

"399299"    --> (1, '399-299')
"987654321" --> (4, '98-76+54+3+21')
"1111111"   --> (3, '1+111-1-11')
mdahmoune
источник
1
Мне нравится использование divmod! Я вижу несколько гольфов: замените list(input())на just input(), поскольку строка уже повторяется, чтобы сохранить 6 байт; заменить b.count('+')+b.count('-')на, len(b)-len(a)чтобы сохранить 12 байтов; и заменить chr(r+43)на, chr(r+43)*(d>0!=r-1)а затем вы можете удалить строку, b=b[:-1].replace(',','')чтобы сохранить чистые 15 байтов ( (d>0!=r-1)эквивалентно (d>0 and 0!=r-1)).
Час Браун
2

Брахилог , 36 байт

~cịᵐ{|ṅ}ᵐ{+100&{ℕṫ,"+"↻|ṫ}ᵐcbE&kl;E}

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

Более половины этого - чтобы получить правильный формат вывода. Фактическая логика ядра:

15 байт

~cịᵐ{|ṅ}ᵐ.+100∧

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

Это возвращает список как [123, –45, –67,89]. Выражение является суммой элементов, а количество операторов на 1 меньше длины списка.

~cLhℕ∧100~+Lпочти работает для 12 байтов ( попробуйте онлайн! ) - но он слишком медленный, чтобы обрабатывать полные 9-значные вводы на TIO, и, что более важно, он не работает для таких входов, как 10808- Brachylog слишком умен, чтобы разбивать числа, чтобы иметь лидирующие нули, так что см. раздел [108, -08].

sundar - Восстановить Монику
источник
1

Haskell , 180 178 байт

m#[a]=[[a]]
m#(b:r)|s<-m#r=m(b:)=<<[s,m('+':)s,m('-':)s]
o '-'=(-)
o _=(+)
(p:r)?a|[(b,s)]<-lex r=s?o p a(read b)
_?a=a
g s=minimum[(sum[1|c<-t,c<'0'],t)|t<-map#s,('+':t)?0==100]

Попробуйте онлайн! Использование: g "123456789"урожайность (3,"123-45-67+89").

#создает список всех возможных терминов, ?оценивает термин и gфильтрует те термины, которые оцениваются как 100, и возвращает один с минимальным количеством операндов.

Laikoni
источник
0

Желе , 27 байт

L’““+“_”ṗ⁸żF¥ⱮV⁼ȷ2ƊƇLÞḢṄḟ⁸L

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

Не могу сказать, что я не взял несколько подсказок из более старого ответа Джонатана Аллана. ;-)

По сравнению с его ответом, этот на два байта короче (30), а не на пять, если мы сделаем сравнение справедливым из-за языковых обновлений:

L’““+“_”ṗ⁸żF¥Ð€V⁼ȷ2$$ÐfLÞḢṄḟ⁸L

Если мы сравним другой способ (более новая версия вместо старой), разница будет той же (его становится 29 байтов, как показано ниже):

ŒṖżⱮL’⁾+_ṗƲ$€ẎFV=ȷ2ƲƇLÞḢFṄḟ³L
Эрик Outgolfer
источник