Explicação

O Befunge é um programa bidimensional que utiliza pilhas .

Isso significa que, para fazer 5 + 6, você escreve 56+, significando:

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)

No entanto, como os inteligentes de vocês observaram, não podemos colocar o número 56diretamente na pilha.

Para isso, devemos escrever 78*em vez disso, que se multiplica 7e 8e empurra o produto para a pilha.

Detalhes

A entrada pode ser obtida em qualquer formato, o que significa que pode ser STDIN ou não, a critério do programador.

A entrada será um número inteiro positivo (nenhum bônus para 0números inteiros ou negativos).

A saída será uma string composta apenas por esses caracteres: 0123456789+-*/(eu não usaria o %módulo.)

O objetivo é encontrar a string mais curta que possa representar a entrada, usando o formato descrito acima.

Por exemplo, se a entrada for 123, a saída seria 67*99*+. A saída deve ser avaliada da esquerda para a direita.

Se houver mais de uma saída aceitável (por exemplo, 99*67*+também é aceitável), qualquer uma poderá ser impressa (sem bônus por imprimir todas elas).

Explicação adicional

Se você ainda não entende como 67*99*+avalia 123, aqui está uma explicação detalhada.

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

O programa precisa encontrar a string mais curta que possa representar a entrada (número), usando o formato especificado acima.

Notas

Este é um desafio de código-golfe , portanto o código mais curto em bytes vence.

Desambiguação

O -pode ser x-you y-x, a critério do programador. No entanto, a escolha deve ser consistente dentro da solução. Da mesma forma para o /.

Programa de exemplo

Lua, 1862 bytes ( experimente online )

Como sou o autor, não jogarei nada.

Explicação:

This uses the depth-first search method.

Mais sobre a pesquisa em profundidade: aqui .

O programa:

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

Bônus

Um bolo para você, se você usar o Befunge (ou qualquer outra variante) para escrever o código.

Python 2, 278 bytes

Minha melhor solução, que sempre dá a menor resposta. (mas muito lento)

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 bytes

Esta solução é mais longa, mas muito rápida (não força bruta). E tenho certeza de que sempre retorna o menor resultado possível.

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 bytes

Inclui +5 para -Xlp(2 extras porque o código contém ')

Execute com o número de destino em 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{$_}}{

Ele não tem limites artificiais e é conceitualmente um tanto eficiente, mas possui tempos de execução terríveis, apesar de eu ter sacrificado alguns bytes para acelerar. A geração de uma solução 11 (por exemplo, número de destino 6551) leva cerca de 5 horas no meu sistema.

Sacrificar mais 7 bytes torna a velocidade um pouco mais suportável.

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

17 minutos para uma solução de comprimento 11, cerca de 5 horas para uma solução de comprimento 13. O primeiro número que precisa do comprimento 15 é 16622, o que leva cerca de 2 dias. O primeiro número que precisa do comprimento 17 é 73319.

Observe que ele assume que a divisão retorna um número inteiro truncando para 0 (conforme a especificação 93 do befunge)

C, 550 545 bytes

#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 bytes após a exclusão das novas linhas desnecessárias (todas, exceto as três novas linhas após as diretivas de pré-processamento).

@Kenny Lau - Ele pode receber como entrada um número inteiro entre 1 e 9998, mas acho que o intervalo de entrada para o qual uma solução ideal é calculada é menor que 9998. Por outro lado, os dois intervalos podem ser estendidos, se a memória permite.

O programa não pode enviar para a pilha nenhum número superior a 9998. (9998 pode ser modificado.) Executei o programa em uma versão diferente, repetindo o loop externo (aquele com k) enquanto houver melhoria para qualquer número entre 1 e 9998 (como no algoritmo de Dijkstra). Após três iterações, não há melhorias. Então, para economizar bytes, codifiquei k = 3.

Para estender o intervalo, são necessárias duas coisas - modificar as constantes 9999 e 9998, executando-o com um número variável de iterações no loop externo pelo tempo que houver melhorias, para ver quanto tempo leva até que nenhuma melhoria ocorra. modifique a constante k = 3 para esse valor.

Python 2, 284 bytes

Isenção de responsabilidade: Demora uma eternidade para alguns valores ... mas deve- se garantir que sempre retorne a string mais curta e não tenha limite de intervalo artificialmente imposto ... até funciona com valores negativos. :)

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

Algoritmo:

• Começar com i = 0
• Pegue a sequência que representa o valor hexadecimal de ie substitua abcdpor +-*/respectivamente e remova qualqueref
• Tentativa de processar a string como notação postfix (RPN)
• Se for bem-sucedido, e o resultado corresponder ao valor de entrada, retorne a sequência usada.
• Caso contrário, aumente ie tente novamente.

Python 2, 182 bytes

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

Tão obscenamente lento, deixei-o funcionando por uma hora na entrada 221e ele ainda não terminou. Uma grande parte da lentidão é porque eu estou usando uma lista como uma fila para uma pesquisa em largura, e .pop(0)éO(n) para listas.

L é apenas uma fila contendo (stack, code to reach stack) pares. A cada etapa, os dígitos são sempre adicionados e os operadores são executados se a pilha tiver pelo menos dois elementos. A divisão só é executada se o último elemento não for 0, embora eu tenha uma forte suspeita de que a divisão nunca seja necessária (embora eu não tenha como provar isso, mas verifiquei que esse é o caso até 500).

O programa termina através de um NameErrorapós a impressão do resultado (eventualmente).

CJam, 79

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

Experimente online

Isso é terrivelmente ineficiente, mas, com tempo e memória suficientes, ele finalmente funciona. 123 fica sem memória com 16 GB, mas 120 e 125 estão ok.

Pitão - 35 bytes

Força bruta. Uma coisa estranha é que a nova entrada implícita realmente prejudica minha pontuação, porque parece estar funcionando .vtambém para pyth_eval.

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

Experimente online aqui .

Python 3, 183 bytes

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])

A velocidade não é totalmente irracional (123, 221, 1237, 6551 terminam na ordem de segundos ou minutos). Alterar a ifinstrução para if j<=i and <k<2*nacelerar mais, ao custo de mais 9 bytes. Eu deixei de fora a divisão ( /), porque não consigo ver como seria necessário.