Explicación

Befunge es un programa bidimensional que utiliza pilas .

Eso significa que, para hacer 5 + 6, escribes 56+, lo que significa:

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)

Sin embargo, como han observado los inteligentes, no podemos insertar el número 56directamente en la pila.

Para ello, debemos escribir 78*en su lugar, lo que multiplica 7y 8y empuja el producto en la pila.

Detalles

La entrada puede tomarse en cualquier formato, lo que significa que puede ser STDIN o no, a discreción del programador.

La entrada será un entero positivo (sin bonificación por incluir 0o enteros negativos).

La salida será una cadena formada únicamente por los caracteres: 0123456789+-*/(yo no uso %. Módulo)

El objetivo es encontrar la cadena más corta que pueda representar la entrada, utilizando el formato descrito anteriormente.

Por ejemplo, si la entrada es 123, entonces la salida sería 67*99*+. La salida debe evaluarse de izquierda a derecha.

Si hay más de una salida aceptable (por ejemplo, 99*67*+también es aceptable), se puede imprimir cualquiera (no hay bonificación por imprimirlas todas).

Explicación adicional

Si aún no comprende cómo se 67*99*+evalúa 123, aquí hay una explicación detallada.

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

El programa necesita encontrar la cadena más corta que pueda representar la entrada (número), utilizando el formato especificado anteriormente.

Notas

Este es un desafío de código de golf , por lo que gana el código más corto en bytes.

Desambiguación

El -puede ser x-yo y-x, a discreción del programador. Sin embargo, la elección debe ser coherente dentro de la solución. Asimismo para el /.

Programa de muestra

Lua, 1862 bytes ( pruébelo en línea )

Como soy el autor, no jugaré golf en absoluto.

Explicación:

This uses the depth-first search method.

Más sobre la búsqueda en profundidad: aquí .

El 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

Prima

Un pastel para ti si usas Befunge (o cualquier variante) para escribir el código.

Python 2, 278 bytes

Mi mejor solución, que cada vez da la respuesta más corta. (pero muy 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 solución es más larga, pero muy rápida (no fuerza bruta). Y estoy bastante seguro, que siempre devuelve el resultado más corto posible.

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

Incluye +5 para -Xlp (2 extra porque el código contiene ')

Ejecutar con el número objetivo en 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{$_}}{

No tiene límites artificiales y es conceptualmente algo eficiente, pero tiene tiempos de ejecución terribles, aunque sacrifiqué algunos bytes para acelerarlo. Generar una solución de longitud 11 (por ejemplo, el número de destino 6551) toma alrededor de 5 horas en mi sistema.

Sacrificar 7 bytes más hace que la velocidad sea algo más soportable.

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

17 minutos para una solución de longitud 11, aproximadamente 5 horas para una solución de longitud 13. El primer número que necesita longitud 15 es 16622, que demora aproximadamente 2 días. El primer número que necesita longitud 17 es 73319.

Tenga en cuenta que supone que la división devuelve un entero truncando hacia 0 (según la especificación de befunge 93)

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 después de eliminar las nuevas líneas innecesarias (todas menos las tres nuevas líneas después de las directivas de preprocesamiento).

@Kenny Lau: puede recibir como entrada un número entero entre 1 y 9998, pero creo que el rango de entrada para el que se calcula una solución óptima es menor que 9998. Por otro lado, ambos rangos se pueden extender, si la memoria lo permite

El programa no puede empujar a la pila ningún número superior a 9998. (9998 se puede modificar). Ejecuté el programa en una versión diferente, iterando sobre el bucle externo (el que tiene k) mientras haya una mejora para cualquier número entre 1 y 9998 (como en el algoritmo de Dijkstra). Después de tres iteraciones no hay mejora. Entonces, para guardar bytes, codifiqué k = 3.

Para extender el rango, son necesarias dos cosas: modificar las constantes 9999 y 9998, ejecutarlo con un número variable de iteraciones sobre el bucle externo durante el tiempo que haya una mejora, para ver cuánto tiempo lleva hasta que no ocurra ninguna mejora, luego modifique la constante k = 3 a ese valor.

Python 2, 284 bytes

Descargo de responsabilidad: se vuelve loco para siempre para algunos valores ... pero se debe garantizar que siempre devuelva la cadena más corta y no tiene un límite de rango impuesto artificialmente ... incluso funciona en 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:

• Empezar con i = 0
• Tome la cadena que representa el valor hexadecimal de iy reemplácela abcdcon +-*/respectivamente, y elimine cualquieref
• Intente procesar una cadena como notación postfix (RPN)
• Si tiene éxito y el resultado coincide con el valor de entrada, devuelva la cadena utilizada.
• De lo contrario, incremente ie intente nuevamente.

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

Tan obscenamente lento, lo dejé funcionando durante una hora en la entrada 221y todavía no ha terminado. Gran parte de la lentitud se debe a que estoy usando una lista como cola para una búsqueda de amplitud, y .pop(0)es O(n)para listas.

L es solo una cola que contiene (stack, code to reach stack) pares. En cada paso, siempre se agregan dígitos y se realizan operadores si la pila tiene al menos dos elementos. La división solo se realiza si el último elemento no es 0, aunque tengo una fuerte sospecha de que la división nunca es necesaria (aunque no tengo forma de demostrarlo, pero he comprobado que este es el caso hasta 500).

El programa finaliza mediante un NameErrordespués de imprimir el resultado (eventualmente).

CJam, 79

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

Pruébalo en línea

Esto es terriblemente ineficiente, pero dado suficiente memoria y tiempo, eventualmente funciona. 123 se queda sin memoria con 16 GB, pero 120 y 125 están bien.

Pyth - 35 bytes

Fuerza bruta. Una cosa extraña es que la nueva entrada implícita realmente daña mi puntaje porque parece estar funcionando .vtambién para pyth_eval.

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

Pruébelo en línea aquí .

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

La velocidad no es totalmente irrazonable (123, 221, 1237, 6551 terminan en el orden de segundos o minutos). Cambiar el ifenunciado para if j<=i and <k<2*nacelerarlo más, a costa de 9 bytes más. Dejé fuera la división ( /), porque no puedo ver cómo se necesitaría.