Explication

Befunge est un programme en deux dimensions qui utilise des piles .

Cela signifie que pour faire 5 + 6, vous écrivez 56+, ce qui signifie:

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)

Cependant, comme vous l'avez remarqué, vous ne pouvez pas pousser le nombre 56directement dans la pile.

Pour ce faire, il faut écrire à la 78*place, qui se multiplie 7et 8et pousse le produit dans la pile.

Détails

L'entrée peut être prise dans n'importe quel format, ce qui signifie qu'elle peut être STDIN ou non, à la discrétion du programmeur.

L'entrée sera un entier positif (pas de bonus pour 0les entiers inclus ou négatifs).

La sortie sera une chaîne composée de seulement ces caractères: 0123456789+-*/(je ne l' utiliser %. Modulo)

Le but est de trouver la chaîne la plus courte pouvant représenter l'entrée, en utilisant le format décrit ci-dessus.

Par exemple, si l'entrée est 123, alors la sortie le serait 67*99*+. La sortie doit être évaluée de gauche à droite.

S'il y a plus d'une sortie acceptable (par exemple, elle 99*67*+est également acceptable), n'importe laquelle peut être imprimée (pas de bonus pour toutes les imprimer).

Plus d'explications

Si vous ne comprenez toujours pas comment est 67*99*+évalué 123, voici une explication détaillée.

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

Le programme doit trouver la chaîne la plus courte pouvant représenter l'entrée (nombre), en utilisant le format spécifié ci-dessus.

Remarques

C'est un défi de code-golf , donc le code le plus court en octets gagne.

Désambiguïsation

Le -peut être x-ysoit y-x, soit à la discrétion du programmeur. Cependant, le choix doit être cohérent au sein de la solution. De même pour le /.

Exemple de programme

Lua, 1862 octets ( essayez-le en ligne )

Puisque je suis l'auteur, je ne jouerai pas au golf du tout.

Explication:

This uses the depth-first search method.

En savoir plus sur la recherche en profondeur: ici .

Le programme:

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

Prime

Un gâteau pour vous si vous utilisez Befunge (ou toute variante de celui-ci) pour écrire le code.

Python 2, 278 octets

Ma meilleure solution, qui à chaque fois donne la réponse la plus courte. (mais très lent)

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 octets

Cette solution est plus longue, mais très rapide (pas de force brute). Et je suis tout à fait sûr, qu'il retourne toujours le résultat le plus court possible.

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 128 octets

Comprend +5 pour -Xlp(2 supplémentaires car le code contient ')

Exécutez avec le numéro cible sur 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{$_}}{

Il n'a pas de limites artificielles et est conceptuellement quelque peu efficace mais a néanmoins des temps d'exécution terribles même si j'ai sacrifié quelques octets pour l'accélérer. La génération d'une solution de longueur 11 (par exemple, le numéro cible 6551) prend environ 5 heures sur mon système.

Sacrifier 7 octets supplémentaires rend la vitesse un peu plus supportable.

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

17 minutes pour une solution de longueur 11, environ 5 heures pour une solution de longueur 13. Le premier numéro qui a besoin d'une longueur de 15 est 16622, ce qui prend environ 2 jours. Le premier nombre qui a besoin de la longueur 17 est 73319.

Notez qu'il suppose que la division retourne un entier en tronquant vers 0 (selon la spécification befunge 93)

C, 550 545 octets

#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 octets après suppression des sauts de ligne inutiles (tous sauf les trois sauts de ligne après les directives de prétraitement).

@Kenny Lau - Il peut recevoir en entrée un entier compris entre 1 et 9998, mais je pense que la plage d'entrée pour laquelle une solution optimale est calculée est plus petite que 9998. Par contre, les deux plages peuvent être étendues, si la mémoire le permet.

Le programme ne peut pas pousser sur la pile un nombre supérieur à 9998. (9998 peut être modifié.) J'ai exécuté le programme dans une version différente, en itérant sur la boucle externe (celle avec k) tant qu'il y a une amélioration pour n'importe quel nombre entre 1 et 9998 (comme dans l'algorithme de Dijkstra). Après trois itérations, il n'y a pas d'amélioration. Donc, pour économiser des octets, j'ai codé en dur k = 3.

Pour étendre la plage, deux choses sont nécessaires - modifier les constantes 9999 et 9998, l'exécuter avec un nombre variable d'itérations sur la boucle externe pendant qu'il y a une amélioration, pour voir combien de temps il faut jusqu'à ce qu'aucune amélioration n'ait lieu, puis modifier la constante k = 3 à cette valeur.

Python 2, 284 octets

Avis de non-responsabilité: prend une éternité pour certaines valeurs ... mais doit toujours être garanti pour renvoyer la chaîne la plus courte, et n'a pas de limite de plage imposée artificiellement ... fonctionne même sur des valeurs négatives. :)

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

Algorithme:

• Commencer avec i = 0
• Prenez la chaîne représentant la valeur hexadécimale de i, et remplacez abcdpar +-*/respectivement, et supprimez toutef
• Tentative de traitement de la chaîne en notation postfixée (RPN)
• En cas de succès et si le résultat correspond à la valeur d'entrée, renvoyez la chaîne utilisée.
• Sinon, incrémentez iet réessayez.

Python 2, 182 octets

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

Si incroyablement lent, je l'ai laissé fonctionner pendant une heure en entrée 221et il n'est toujours pas terminé. Une grande partie de la lenteur est due au fait que j'utilise une liste comme file d'attente pour une recherche en largeur d'abord, et .pop(0)est O(n)pour les listes.

L est juste une file d'attente contenant (stack, code to reach stack) paires. À chaque étape, des chiffres sont toujours ajoutés et des opérateurs sont exécutés si la pile comporte au moins deux éléments. La division n'est effectuée que si le dernier élément n'est pas 0, bien que je soupçonne fortement que la division n'est jamais nécessaire (même si je n'ai aucun moyen de le prouver, mais j'ai vérifié que c'est le cas jusqu'à 500).

Le programme se termine via un NameErroraprès l'impression du résultat (éventuellement).

CJam, 79

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

Essayez-le en ligne

C'est horriblement inefficace, mais avec suffisamment de mémoire et de temps, cela fonctionne finalement. 123 manque de mémoire avec 16 Go, mais 120 et 125 sont corrects.

Pyth - 35 octets

Force brute. Une chose étrange est que la nouvelle entrée implicite nuit réellement à mon score car elle semble également fonctionner pour .vpyth_eval.

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

Essayez-le en ligne ici .

Python 3, 183 octets

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 vitesse n'est pas totalement déraisonnable (123, 221, 1237, 6551 terminent de l'ordre des secondes ou des minutes). Changer la ifdéclaration pour l' if j<=i and <k<2*naccélérer davantage, au prix de 9 octets supplémentaires. J'ai omis division ( /), car je ne vois pas comment cela serait nécessaire.