объяснение

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 (или любой другой вариант) для написания кода.

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]

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)

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 к этому значению.

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и попробуйте снова.

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после печати результата (в конце концов).

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 в порядке.

Pyth - 35 байт

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

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

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

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 ( /), потому что я не вижу, как это будет необходимо.