Выразите число только с 0-9 и четырьмя операциями

14

объяснение

Befunge - это двумерная программа, использующая стеки .

Это означает, что для выполнения 5 + 6 вы пишете 56+, что означает:

56+
5    push 5 into stack
 6   push 6 into stack
  +  pop the first two items in the stack and add them up, and push the result into stack

(to those of you who do not know stacks, "push" just means add and "pop" just means take off)

Однако, как заметил ваш ум, мы не можем поместить число 56прямо в стек.

Чтобы сделать это, мы должны написать 78*вместо этого, который умножает 7и 8и помещает продукт в стек.

Детали

Ввод может быть сделан в любом формате, то есть может быть STDIN или нет, по усмотрению программиста.

На входе будет положительное целое число (без бонуса за включение 0или отрицательное целое число ).

На выходе будет строка, состоящая только из этих символов: 0123456789+-*/(я бы не использовал% по модулю.)

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

Например, если вход есть 123, то выход будет 67*99*+. Результат должен оцениваться слева направо.

Если имеется более одного приемлемого вывода (например 99*67*+, также приемлемо), любой может быть напечатан (без бонуса за печать всех из них).

Дальнейшее объяснение

Если вы все еще не понимаете, как 67*99*+оценивать 123, вот подробное объяснение.

stack    |operation|explanation
          67*99*+
[6]       6         push 6 to stack
[6,7]      7        push 7 to stack
[42]        *       pop two from stack and multiply, then put result to stack
[42,9]       9      push 9 to stack
[42,9,9]      9     push 9 to stack
[42,81]        *    pop two from stack and multiply, then put result to stack
[123]           +   pop two from stack and add, then put result to stack

TL; DR

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

Примечания

Это задача , поэтому выигрывает самый короткий код в байтах.

Disambiguation

-Может быть либо x-yили y-x, по усмотрению программиста. Тем не менее, выбор должен быть последовательным в рамках решения. Аналогично для /.

Пример программы

Lua, 1862 байта ( попробуйте онлайн )

Поскольку я автор, я не буду играть в гольф вообще.

Объяснение:

This uses the depth-first search method.

Подробнее о поиске в глубину: здесь .

Программа:

local input = (...) or 81

local function div(a,b)
    if b == 0 then
        return "error"
    end
    local result = a/b
    if result > 0 then
        return math.floor(result)
    else
        return math.ceil(result)
    end
end

local function eval(expr)
    local stack = {}
    for i=1,#expr do
        local c = expr:sub(i,i)
        if c:match('[0-9]') then
            table.insert(stack, tonumber(c))
        else
            local a = table.remove(stack)
            local b = table.remove(stack)
            if a and b then
                if c == '+' then
                    table.insert(stack, a+b)
                elseif c == '-' then
                    table.insert(stack, b-a)
                elseif c == '*' then
                    table.insert(stack, a*b)
                elseif c == '/' then
                    local test = div(b,a)
                    if test == "error" then
                        return -1
                    else
                        table.insert(stack, a+b)
                    end
                end
            else
                return -1
            end
        end
    end
    return table.remove(stack) or -1
end

local samples, temp = {""}, {}

while true do
    temp = {}
    for i=1,#samples do
        local s = samples[i]
        table.insert(temp, s..'0')
        table.insert(temp, s..'1')
        table.insert(temp, s..'2')
        table.insert(temp, s..'3')
        table.insert(temp, s..'4')
        table.insert(temp, s..'5')
        table.insert(temp, s..'6')
        table.insert(temp, s..'7')
        table.insert(temp, s..'8')
        table.insert(temp, s..'9')
        table.insert(temp, s..'+')
        table.insert(temp, s..'-')
        table.insert(temp, s..'*')
        table.insert(temp, s..'/')
    end
    for i=1,#temp do
        if input == eval(temp[i]) then
            print(temp[i])
            return
        end
    end
    samples = temp
end

бонус

Торт для вас, если вы используете Befunge (или любой другой вариант) для написания кода.

Дрянная Монахиня
источник
3
Может быть трудно решить, учитывая ответ, всегда ли он генерирует самую худшую строку. Одна идея состоит в том, чтобы создать большой набор, скажем, 30-50 чисел и оценить по сумме всей длины выходной строки. Тем не менее, я не уверен, как объединить этот счет с длиной кода
Луис Мендо
4
Подмножество этого .
Аддисон Крамп
2
Копирование моих мыслей из чата : «Я думал об этом, но я бы сказал, что подмножество делает вещи намного проще, потому что 1) нет гекса, 2) нет поплавков, 3) нет дублирования и 4) только позитив»
Sp3000
1
@CoolestVeto этот достаточно отличается, чтобы лишить законной силы старые ответы.
Rɪᴋᴇʀ
1
@CoolestVeto Я думаю, что другой вызов должен быть закрыт как дубликат этого.
mbomb007

Ответы:

4

Python 2, 278 байт

Мое лучшее решение, которое всегда дает кратчайший ответ. (но очень медленно)

def e(c):
 s=[];x,y=s.append,s.pop
 while c:
  d,c=c[0],c[1:]
  if"/"<d<":":x(d)
  else:a,b=y(),y();x(str(eval(b+d+a)))
 return int(y())
def g(v):
 s="0123456789+-*";t=list(s)
 while 1:
  for x in t:
   try:
    if e(x)==v:return x
   except:0
  t=[x+y for x in t for y in s]

Python 2, 437 байт

Это решение длиннее, но очень быстро (не грубой силой). И я совершенно уверен, что он всегда даст кратчайший результат.

r=range;l=len;a=input()
def f(n):
 if n<=9:return str(n)
 for d in r(9,1,-1):
  if n%d==0:return f(n/d)+"%d*"%d
 h=sum(map(int,list(str(n))))%9
 return f(n-h)+"%d+"%h
m={x:f(x) for x in r(a*9)}
for b in m:
 if a-b in m and l(m[b])+l(m[a-b])+1<l(m[a]):m[a]=m[a-b]+m[b]+"+"
 if a+b in m and l(m[b])+l(m[a+b])+1<l(m[a]):m[a]=m[a+b]+m[b]+"-"
 if b!=0 and a%b==0 and a/b in m and l(m[b])+l(m[a/b])+1<l(m[a]):m[a]=m[a/b]+m[b]+"*"
print m[a]
pbochniak
источник
2
Добро пожаловать в PPCG ! Надеюсь, вы отлично проведете время здесь.
Утренняя монахиня
1
@pbochinak Я думаю, я мог бы найти правильный. f(6551)возвращает 25*8*9*7+9*8+(13 символов), а 9999***52*-(11 символов) лучше. Проверено с моей собственной evalфункцией выше (в вопросе).
Дрянная Монахиня
4
@pbochniak Как отмечается в предыдущем комментарии, этот ответ недействителен в своем текущем состоянии. Рекомендуется временно удалить его, пока вы работаете над исправлением (если ничего другого, чтобы предотвратить привлечение отрицательных голосов).
Деннис
1
Ваше время может быть простоwhile c:
Ven
Вы можете использовать ;для разделения назначений переменных (которые сохраняют байты в блоки с отступами), подсказку ven, избавиться от пробела между символом и чем-то еще, и tможете идти.
CalculatorFeline
4

Perl, 134 133 132 128 байт

Включает +5 для -Xlp(2 дополнительных, потому что код содержит' )

Запустите с целевым номером на STDIN:

perl -Xlp befour.pl <<< 123

befour.pl:

@1{1..9}=1..9;$.+=2,map{for$a(%1){"+-*/"=~s%.%"\$1{\$-=$a$&$_/'$1{$a}$1{$_}$&'=~/^.{$.}\$/}||=\$&"%eegr}}%1until$\=$1{$_}}{

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

Принесение в жертву еще 7 байтов делает скорость несколько более терпимой.

@1{1..9}=1..9;$.+=2,map{for$a(@a){"+-*/"=~s%.%"\$1{\$-=$a$&$_/'$1{$a}$1{$_}$&'=~/^.{$.}\$/}||=\$&"%eegr}}@a=keys%1until$\=$1{$_}}{

17 минут для раствора длиной 11, около 5 часов для раствора длиной 13. Первое число, которому нужна длина 15, это 16622, что занимает около 2 дней. Первое число, которому нужна длина 17, - 73319.

Обратите внимание, что предполагается, что деление возвращает целое число путем усечения до 0 (согласно спецификации befunge 93)

Тон Хоспел
источник
Что делают знаки доллара? (Я вообще не говорю на Perl)
Дрянная Монахиня
1
@KennyLau $обращается к скалярному значению. Где бы на большинстве языков вы ни писали a=4, Perl будет использовать $a=4. Но также используется для скалярного доступа к более сложным переменным. Например, $a{$b}извлекает из хэша (карта, словарь) %aскалярное значение, указанное на $b
клавиатуре
2

C 550 545 байт

#define L strlen
#define y strcpy
#define t strcat
char c[9999][99];i=1,k=3;main(j){for(;i<10;i++)*c[i]=i+'0';for(;k--;){
for(i=1;i<9999;i++)for(j=1;j<=i;j++)*c[i]&&*c[j]&&(i+j>9998||*c[i+j]&&
L(c[i+j])<L(c[i])+L(c[j])+2||t(t(y(c[i+j],c[i]),c[j]),"+"),
i*j>9998||*c[i*j]&&L(c[i*j])<L(c[i])+L(c[j])+2||t(t(y(c[i*j],c[i]),c[j]),"*"));
for(i=9999;--i;)for(j=i;--j;)*c[i]&&*c[j]&&(*c[i/j]&&
L(c[i/j])<L(c[i])+L(c[j])+2||t(t(y(c[i/j],c[i]),c[j]),"/"),
*c[i-j]&&L(c[i-j])<L(c[i])+L(c[j])+2||t(t(y(c[i-j],c[i]),c[j]),"-"));}
scanf("%d",&i);printf("%s",c[i]);}

550 545 байт после удаления ненужных строк новой строки (все, кроме трех строк новой строки после директив предварительной обработки).

@Kenny Lau - Он может принимать в качестве входных данных целое число от 1 до 9998, но я думаю, что диапазон ввода, для которого вычисляется оптимальное решение, меньше, чем 9998. С другой стороны, оба диапазона могут быть расширены, если память позволяет это.

Программа не может вытолкнуть в стек любое число, большее 9998. (9998 можно изменить.) Я запускал программу в другой версии, повторяя итерацию по внешнему циклу (та, что с k), пока есть улучшения для любого числа между 1 и 9998 (как в алгоритме Дейкстры). После трех итераций улучшения не происходит. Таким образом, чтобы сохранить байты, я жестко закодировал k = 3.

Чтобы расширить диапазон, необходимы две вещи - изменение констант 9999 и 9998, запуск его с переменным числом итераций по внешнему циклу до тех пор, пока есть улучшение, чтобы увидеть, сколько времени потребуется, пока улучшение не произойдет, затем изменить константу к = 3 к этому значению.

mIllIbyte
источник
Добро пожаловать в PPCG ! Надеюсь, вы отлично проведете время здесь.
Утренняя монахиня
Это проходит мой 6551 тест отлично. Каков эффективный диапазон этой программы?
Утренняя монахиня
Я считаю, что это 9999. Можете ли вы добавить эту информацию к вашему решению?
Утренняя монахиня
Он должен быть 9998. Кроме того , вы можете съесть некоторые байты инициализации i, jи kдо того main().
Утренняя монахиня
1
@ Кенни Лау - Спасибо за редактирование. Что касается расширения диапазона, я заметил, что на самом деле требуется немного больше, чтобы расширить диапазон. Я включил эту информацию в ответ.
Миллибайт
2

Python 2, 284 байта

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

def f(v):
 i,z=0,'+-*/'
 while 1:
  s=('%x'%i).translate(__import__('string').maketrans('abcd',z),'ef');t=s;q=[];a,p=q.append,q.pop;i+=1
  try:
   while t:
    o,t=t[0],t[1:]
    if o in z:n,m=p(),p();a(eval(`m`+o+`n`))
    else:a(int(o))
   if p()==v and not q:return s
  except:pass

Алгоритм:

  • Начать с i = 0
  • Возьмите строку, представляющую шестнадцатеричное значение i, и замените abcdна+-*/ соответственно, и удалитеef
  • Попытка обработать строку как постфиксную нотацию (RPN)
  • Если результат успешен и результат соответствует входному значению, верните используемую строку.
  • В противном случае увеличьте значение iи попробуйте снова.
Кен "Джои" Мошер
источник
«[t] akes [...] навсегда для некоторых значений» Вы проверяли это? Какие ценности?
Утренняя монахиня
@KennyLau я просто написал тест , который расчетливый f(i)из 0 <= i <= 6551(захватить 6551значение , которое используется для аннулированию @pbochniak «s первоначального представления). Прямо сейчас он работает всего несколько минут, и вот последний результат теста: 91 : 49+7* 3.020 s (total 108.174 s, worst 89: 5.827 s) Обновление - он только что закончил со значением 92: 92 : 149+7*+ 258.761 s (total 366.935 s, worst 92: 258.761 s)
Кен «Джои» Мошер,
@KennyLau: тест выполнялся более часа, и только до 113полной стоимости ... смотрите полный тестовый вывод здесь (pastebin), если вам интересно ...
Кен 'Джои' Мошер,
2

Python 2, 182 байта

n=input()
L=[[[],""]]
while 1:
 s,c=L.pop(0);L+=[[s+[i],c+`i`]for i in range(10)]+(s[1:]and[[s[:-2]+[eval(`s[-2]`+o+`s[-1]`)],c+o]for o in"/+-*"[s[-1]==0:]])
 if[n]==s[-1:]:print c;E

Так непристойно медленно я оставил его включенным в течение часа при вводе, 221и он все еще не завершился. Большое медлительности, потому что я использую список в виде очереди за поиск в ширину, и .pop(0)это O(n)для списков.

Lэто просто очередь, содержащая (stack, code to reach stack)пары. На каждом шаге всегда добавляются цифры, и операторы выполняются, если в стеке есть хотя бы два элемента. Деление выполняется только в том случае, если последний элемент не равен 0, хотя у меня есть сильное подозрение, что деление никогда не требуется (хотя у меня нет способа доказать это, но я проверил, что это случай до 500).

Программа завершается через NameErrorпосле печати результата (в конце концов).

Sp3000
источник
Что ;Eделает в конце?
Утренняя монахиня
@KennyLau Это NameErrorдля завершения, так Eкак больше нигде не определено
Sp3000
Вау, такой ум.
Утренняя монахиня
1

CJam, 79

ri:M;A,:s:L;{L2m*{s,Y=},{~:A+AS*~!"/+-*">\f{\+}~}%Y2+:Y;_L@+:L;{S*~M=},:R!}gR0=

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

Это ужасно неэффективно, но, учитывая достаточно памяти и времени, в конечном итоге это работает. 123 не хватает памяти с 16 ГБ, но 120 и 125 в порядке.

уйти, потому что SE это зло
источник
1

Pyth - 35 байт

Грубая сила. Странная вещь в том, что новый неявный ввод на самом деле вредит моему счету, потому что он, кажется, работает и для .vpyth_eval.

.V1IKfqQ.x.v+jd_T\;N^s+"+-*/"UTbhKB

Попробуйте это онлайн здесь .

Maltysen
источник
0

Python 3, 183 байта

e,n=enumerate,input()
v=list('0123456789')+[' '*n]*n*2
for i,s in e(v):
 for j,t in e(v):
  for o,k in zip('+*-',(i+j,i*j,i-j)):
   if 9<k<2*n:v[k]=min(v[k],s+t+o,key=len)
print(v[n])

Скорость не является абсолютно необоснованной (123, 221, 1237, 6551 финишируют с точностью до секунд или минут). Изменение ifоператора на if j<=i and <k<2*nускоряет его еще больше, за счет еще 9 байтов. Я пропустил Division ( /), потому что я не вижу, как это будет необходимо.

RootTwo
источник
Подсказка: деление необходимо.
Утренняя монахиня