Erläuterung

Befunge ist ein zweidimensionales Programm, das Stapel verwendet .

Das heißt, um 5 + 6 zu tun, schreiben Sie 56+, was bedeutet:

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)

Wie die Intelligenten von Ihnen bemerkt haben, können wir die Zahl jedoch nicht 56direkt in den Stapel schieben .

Dazu müssen wir 78*stattdessen schreiben , was das Produkt multipliziert 7und 8in den Stapel schiebt.

Einzelheiten

Die Eingabe kann in einem beliebigen Format erfolgen, dh nach Ermessen des Programmierers kann dies STDIN sein oder nicht.

Die Eingabe ist eine positive Ganzzahl (kein Bonus für Einschluss- 0oder negative Ganzzahlen).

Der Ausgang wird eine Reihe von nur diese Zeichen aus: 0123456789+-*/(ich würde nicht verwenden %. Modulo)

Das Ziel besteht darin, die kürzeste Zeichenfolge zu finden, die die Eingabe darstellen kann, indem das oben beschriebene Format verwendet wird.

Wenn zum Beispiel die Eingabe ist 123, dann wäre die Ausgabe 67*99*+. Die Ausgabe sollte von links nach rechts ausgewertet werden.

Wenn es mehr als eine akzeptable Ausgabe gibt (z. B. 99*67*+auch akzeptabel), kann eine beliebige gedruckt werden (kein Bonus für das Drucken aller).

Weitere Erklärung

Wenn Sie immer noch nicht verstehen, wie Sie 67*99*+auswerten sollen 123, finden Sie hier eine ausführliche Erklärung.

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

Das Programm muss die kürzeste Zeichenfolge finden, die die Eingabe (Zahl) darstellen kann, wobei das oben angegebene Format verwendet wird.

Anmerkungen

Dies ist eine Code-Golf- Herausforderung, daher gewinnt der kürzeste Code in Bytes.

Begriffsklärung

Das -kann entweder x-yoder y-xnach Ermessen des Programmierers sein. Die Auswahl muss jedoch innerhalb der Lösung konsistent sein. Ebenso für die /.

Beispielprogramm

Lua, 1862 Bytes ( online testen )

Da ich der Autor bin, werde ich überhaupt nicht Golf spielen.

Erläuterung:

This uses the depth-first search method.

Mehr zur Tiefensuche: hier .

Das Programm:

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

Bonus

Ein Kuchen für Sie, wenn Sie Befunge (oder eine andere Variante davon) verwenden, um den Code zu schreiben.

Python 2, 278 Bytes

Meine beste Lösung, die jedes Mal die kürzeste Antwort gibt. (aber sehr langsam)

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

Diese Lösung ist länger, aber sehr schnell (keine rohe Kraft). Und ich bin mir ziemlich sicher, dass es immer das kürzestmögliche Ergebnis liefert.

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

Beinhaltet +5 für -Xlp(2 extra, weil der Code enthält ')

Führen Sie mit der Zielnummer auf STDIN aus:

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{$_}}{

Es hat keine künstlichen Grenzen und ist konzeptionell einigermaßen effizient, hat aber dennoch schreckliche Laufzeiten, obwohl ich ein paar Bytes geopfert habe, um es zu beschleunigen. Das Generieren einer Lösung der Länge 11 (z. B. Zielnummer 6551) dauert auf meinem System ungefähr 5 Stunden.

Das Aufopfern von 7 weiteren Bytes macht die Geschwindigkeit etwas erträglicher.

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

17 Minuten für eine Lösung der Länge 11, ungefähr 5 Stunden für eine Lösung der Länge 13. Die erste Nummer, die eine Länge von 15 benötigt, ist 16622, was ungefähr 2 Tage dauert. Die erste Nummer, die die Länge 17 benötigt, ist 73319.

Beachten Sie, dass davon ausgegangen wird, dass die Division eine Ganzzahl zurückgibt, indem sie gegen 0 abschneidet (gemäß der Vorgabe von 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 nach dem Löschen der unnötigen Zeilenumbrüche (alle Zeilen mit Ausnahme der drei Zeilenumbrüche nach den Vorverarbeitungsrichtlinien).

@Kenny Lau - Es kann als Eingabe eine Ganzzahl zwischen 1 und 9998 empfangen, aber ich denke, dass der Eingabebereich, für den eine optimale Lösung berechnet wird, kleiner als 9998 ist. Andererseits können beide Bereiche erweitert werden, wenn der Speicher erweitert wird erlaubt es.

Das Programm kann keine höhere Zahl als 9998 auf den Stapel schreiben. (9998 kann geändert werden.) Ich habe das Programm in einer anderen Version ausgeführt und die äußere Schleife (die mit k) durchlaufen, solange es Verbesserungen für eine beliebige Zahl gibt zwischen 1 und 9998 (wie im Dijkstra-Algorithmus). Nach drei Iterationen gibt es keine Verbesserung. Um Bytes zu sparen, habe ich k = 3 fest codiert.

Um den Bereich zu erweitern, sind zwei Dinge erforderlich: Ändern Sie die Konstanten 9999 und 9998, und führen Sie sie mit einer variablen Anzahl von Iterationen über die Outter-Schleife aus, solange eine Verbesserung vorliegt modifiziere die Konstante k = 3 auf diesen Wert.

Python 2, 284 Bytes

Haftungsausschluss: Dauert bei einigen Werten ewig ... es sollte jedoch garantiert werden, dass immer die kürzeste Zeichenfolge zurückgegeben wird, und es gibt keine künstlich auferlegte Bereichsgrenze ... sogar bei negativen Werten. :)

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

Algorithmus:

• Beginnen mit i = 0
• Nehmen Sie die Zeichenfolge, die den Hexadezimalwert von darstellt i, und ersetzen Sie sie abcddurch +-*/jeweils. Entfernen Sie alle Zeichenfolgenef
• Versuch, String als Postfix-Notation (RPN) zu verarbeiten
• Wenn erfolgreich und das Ergebnis mit dem Eingabewert übereinstimmt, geben Sie die verwendete Zeichenfolge zurück.
• Andernfalls erhöhen iund erneut versuchen.

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

So unglaublich langsam, dass ich es bei der Eingabe eine Stunde lang laufen lassen habe 221und es immer noch nicht beendet ist. Ein großer Teil der Langsamkeit ist , weil ich eine Liste als eine Warteschlange für eine Breitensuche verwenden und .pop(0)ist O(n)für Listen.

List nur eine Warteschlange mit (stack, code to reach stack)Paaren. Bei jedem Schritt werden immer Ziffern hinzugefügt und Operatoren ausgeführt, wenn der Stapel mindestens zwei Elemente enthält. Eine Division wird nur durchgeführt, wenn das letzte Element nicht 0 ist, obwohl ich den starken Verdacht habe, dass eine Division niemals notwendig ist (obwohl ich keine Möglichkeit habe, dies zu beweisen, aber ich habe dies bis zu 500 geprüft).

Das Programm bricht NameErrornach dem Ausdruck des Ergebnisses (evtl.) über a ab.

CJam, 79

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

Probieren Sie es online aus

Dies ist schrecklich ineffizient, aber wenn genügend Speicher und Zeit zur Verfügung stehen, funktioniert es schließlich. 123 hat nicht genügend Speicher mit 16 GB, aber 120 und 125 sind in Ordnung.

Pyth - 35 Bytes

Rohe Gewalt. Eine seltsame Sache ist, dass die neue implizite Eingabe tatsächlich meine Punktzahl verletzt , da sie auch für .vpyth_eval zu funktionieren scheint.

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

Probieren Sie es hier online aus .

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

Geschwindigkeit ist nicht völlig unvernünftig (123, 221, 1237, 6551 werden in der Größenordnung von Sekunden oder Minuten beendet). Wenn Sie die ifAnweisung if j<=i and <k<2*nändern, um sie zu beschleunigen, werden 9 weitere Bytes benötigt. Ich habe division ( /) weggelassen, weil ich nicht sehen kann, wie es gebraucht wird.