Drücken Sie eine Zahl mit nur 0-9 und den vier Operationen aus

14

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 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.

Undichte Nonne
quelle
3
Bei einer gegebenen Antwort kann es schwierig sein, zu entscheiden, ob immer die sorteste Zeichenfolge erzeugt wird. Eine Idee wäre, eine große Menge von 30 bis 50 Zahlen zu generieren und durch die Summe der Länge aller ausgegebenen Zeichenfolgen zu bewerten. Ich bin mir jedoch nicht sicher, wie ich diese Punktzahl mit der Codelänge kombinieren soll
Luis Mendo
4
Teilmenge davon .
Addison Crump
2
Kopieren meiner Gedanken aus dem Chat : "Ich habe darüber nachgedacht, aber ich würde argumentieren, dass die Teilmenge die Dinge viel einfacher macht, weil 1) kein Hex, 2) kein Floaten, 3) keine Vervielfältigung und 4) nur positiv"
Sp3000
1
@CoolestVeto dieses ist unterschiedlich genug, um die alten Antworten ungültig zu machen.
31.
1
@CoolestVeto Ich denke, die andere Herausforderung sollte als Duplikat dieser abgeschlossen werden.
mbomb007

Antworten:

4

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]
pbochniak
quelle
2
Willkommen bei PPCG ! Ich hoffe, Sie haben eine tolle Zeit hier.
Undichte Nonne
1
@ pbochinak Ich glaube, ich hätte eine gültige gefunden. f(6551)gibt 25*8*9*7+9*8+(13 Zeichen) zurück, während 9999***52*-(11 Zeichen) besser ist. Verifiziert mit meiner eigenen evalFunktion oben (in der Frage).
Undichte Nonne
4
@pbochniak Wie der Kommentar vor mir zeigt, ist diese Antwort in ihrem aktuellen Zustand ungültig. Es wird empfohlen, es vorübergehend zu löschen, während Sie an einem Fix arbeiten (um zu verhindern, dass es zu Abstimmungen kommt).
Dennis
1
Ihre Zeit kann nur seinwhile c:
Ven
Sie können ;Zuweisungen zu Variablen (die Bytes in eingerückten Blöcken speichern) trennen, den Tipp des Vens verwenden, Leerzeichen zwischen einem Symbol und allem anderen entfernen und tloslegen.
CalculatorFeline
4

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

Tonne Hospel
quelle
Was machen die Dollarzeichen? (Ich spreche überhaupt nicht Perl)
Undichte Nonne
1
@KennyLau $greift auf den Skalarwert zu. Wo in den meisten Sprachen Sie schreiben würden, a=4wird Perl verwenden $a=4. Wird aber auch für einen skalaren Zugriff auf komplexere Variablen verwendet. ZB $a{$b}holt sich aus dem Hash (Karte, Wörterbuch) %aden Skalarwert, der am$b
Ton
2

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.

mIllIbyte
quelle
Willkommen bei PPCG ! Ich hoffe, Sie haben eine tolle Zeit hier.
Undichte Nonne
Dies besteht meinen 6551-Test perfekt. Was ist die effektive Reichweite dieses Programms?
Undichte Nonne
Ich glaube, es ist 9999. Können Sie diese Informationen bitte zu Ihrer Lösung hinzufügen?
Undichte Nonne
Es sollte 9998 auch sein, einige Bytes durch Initialisierung essen kann i, jund kvor main().
Undichte Nonne
1
@Kenny Lau - Danke für die Bearbeitung. Beim Erweitern der Reichweite ist mir aufgefallen, dass es tatsächlich etwas länger dauert, die Reichweite zu vergrößern. Ich habe diese Information in die Antwort aufgenommen.
MIllIbyte
2

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.
Ken 'Joey' Mosher
quelle
"[t] akes [...] forever for some values" Haben Sie es getestet? Welche Werte?
Undichte Nonne
@KennyLau Ich schrieb nur einen Test, ist die Berechnung f(i)von 0 <= i <= 6551(erfassen den 6551Wert , der Sie verwenden die ursprüngliche Vorlage ungültig @pbochniak). Im Moment läuft es nur ein paar Minuten und hier ist die letzte Ausgabe des Tests: 91 : 49+7* 3.020 s (total 108.174 s, worst 89: 5.827 s) Update - es wurde gerade mit dem Wert 92 beendet: 92 : 149+7*+ 258.761 s (total 366.935 s, worst 92: 258.761 s)
Ken 'Joey' Mosher
@KennyLau: Der Test wurde über eine Stunde lang ausgeführt und ist nur bis zum Wert gültig. Die 113vollständige Testausgabe finden Sie hier (Pastebin), wenn Sie interessiert sind.
Ken 'Joey' Mosher
2

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.

Sp3000
quelle
Was macht der ;Eam Ende?
Undichte Nonne
@KennyLau Das ist der NameError für die Kündigung, da Enirgendwo anders definiert
Sp3000
Wow, solche Klugheit.
Undichte Nonne
1

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.

aditsu
quelle
1

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 .

Maltysen
quelle
0

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.

RootTwo
quelle
Hinweis: Eine Unterteilung ist erforderlich.
Undichte Nonne