Hintergrund

In einigen möglichen Zukünften wird die Welt ihre numerischen Systeme von dezimal (Basis 10 oder b10) auf eine andere Basis (binär b2, oktal b8, hexadezimal b16oder sogar unär b1, in diesem Fall sind wir geschraubt!) Umwandeln. In Vorbereitung auf dieses möglicherweise weltverändernde Ereignis entscheiden Sie sich daher, alle Ihre Programme auf die Basis zu stellen. Dies kann erreicht werden, indem nur singuläre 0s und 1s in Verbindung mit Operatoren verwendet werden, um die vorhandenen Zahlenkonstanten zu ersetzen.

Es gibt jedoch nur ein Problem: Sie müssen eine Menge Programme ändern, und die manuelle Konvertierung jeder Zahl in einen Ausdruck würde Wochen dauern! Sie entscheiden sich daher, ein Programm (oder eine Funktion) zu schreiben, um zu entscheiden, welcher Ausdruck jede Zahl ersetzen soll.

Eingang

Die Eingabe ist eine positive Ganzzahl. Ihr Code muss in der Lage sein, eine ganze Zahl bis zu 1000 zu verarbeiten.

(Wenn Ihr Code Dezimalstellen und / oder negative Eingaben unterstützt, lesen Sie die Informationen unter Bewertung .)

Ausgabe

Ihr Code muss einen Ausdruck ausgeben, der in mindestens einer Sprache als Eingabe ausgewertet wird. Dies kann jede Sprache sein; Es muss nicht dasselbe sein, in das Ihr Programm oder Ihre Funktion geschrieben ist. Außerdem muss dieser Ausdruck kein vollständiges Programm oder eine vollständige Funktion sein.

Der Übersichtlichkeit halber kann die Ausgabe folgende Operationen enthalten:

• inkrementieren / dekrementieren
• add / sum
• subtrahieren / negieren
• multiplizieren / verdoppeln (nur wenn es sich nicht direkt um die Zahl handelt 2!)
• Teilen / Modulo
• Exponenten / Logarithmen
• Quadrat / Quadrat (wieder nur, wenn diese nicht direkt die Zahl betreffen 2!)
• bitweise Operationen (bOR, bAND, bNOT, bXOR, Bitverschiebungen)
• Variablen setzen / holen
• Stapelmanipulation

Sie können nicht verwenden eval()oder ähnliche Funktionen in der Ausgabe. Sie dürfen in der Ausgabe auch keine Funktionen verwenden, die andere als die oben genannten Aktionen ausführen.

Oh, und noch etwas: da wir die Ausgabe gültig zu sein in so viele Basen wie möglich wollen, die einzige Zahl , Konstanten sie enthalten sind 0und 1. Zahlen wie 10(zehn) sind nicht zulässig, es sei denn, die Sprache interpretiert sie als a 1und a 0. Mit Strings Zahlen enthalten ist auch nicht erlaubt, wie es Zeichen wie CJam der Verwendung A- K(die darstellen 10- 20).

Testfälle

(Alle Ausgaben sind in JavaScript, funktionieren jedoch möglicherweise in anderen Sprachen.)

Eingang 1:

2

Mögliche Ausgabe 1:

1+1

Eingang 2:

13

Mögliche Ausgabe 2:

(a=1+1+1)*a+a+1

Eingang 3:

60

Mögliche Ausgabe 3:

(b=(a=1+1+1+1)*a)*a-a

Eingang 4:

777

Mögliche Ausgabe 4:

(c=(b=((a=1+1+1+1)*a-a+1)*a)*a+b)+c+c-a+1

Eingang 5:

1000

Mögliche Ausgabe 5:

Math.pow((a=1+1+1)*a+1,a)

Wertung

Ziel dieser Herausforderung ist es, die Ausgabe Ihres Codes so weit wie möglich zu verkürzen. Ihre Punktzahl wird folgendermaßen berechnet:

• Basisbewertung: Die durchschnittliche Byteanzahl aller Ausgaben für Ganzzahlen von 1 bis 1000.

• Dezimalpunktzahl : Wenn Ihr Code mindestens 3 Dezimalstellen unterstützt, ist dies die durchschnittliche Byteanzahl aller Ausgaben der Zahlenfolge, die um beginnt 0.001und um endet 1000, und wird 1.001jedes Mal erhöht . 0.001, 1.002, 2.003...998.999, 1000.000Dann nimm 50% von dieser Punktzahl ab.

• Negative Bewertung: Wenn Ihr Code negative Zahlen und Nullen unterstützt, ist dies die durchschnittliche Byte-Anzahl der Ausgaben aller Ganzzahlen von -1000bis 0. Dann nimm 10% von dieser Punktzahl ab.

(Der einfachste Weg, diese zu berechnen, ist wahrscheinlich eine Schleife mit Ihrem Programm / Ihrer Funktion.)

Ihre endgültige Punktzahl ist der Durchschnitt der oben genannten Formeln.

Wenn die Ausgabe nicht deterministisch ist (dh etwas zufällig ist; mehrere Durchläufe mit derselben Eingabe ergeben mehrere eindeutige Ausgaben), wird die Bewertung für jede Eingabe durch die größte Ausgabe über zehn Durchläufe auf meiner CPU bestimmt.

Da Sie nicht wissen, wie wertvoll die Computerdaten in Zukunft sein werden, muss die Byteanzahl Ihres Generatorcodes weniger als 512 Bytes betragen.

Das niedrigste Ergebnis in zwei Wochen (am 30. September) wird zum Gewinner erklärt. Herzlichen Glückwunsch an Ihren Gewinner @ThomasKwa !

Bestenliste

var QUESTION_ID=58084,OVERRIDE_USER=42545;function answersUrl(e){return"http://api.stackexchange.com/2.2/questions/"+QUESTION_ID+"/answers?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+ANSWER_FILTER}function commentUrl(e,s){return"http://api.stackexchange.com/2.2/answers/"+s.join(";")+"/comments?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+COMMENT_FILTER}function getAnswers(){jQuery.ajax({url:answersUrl(answer_page++),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){answers.push.apply(answers,e.items),answers_hash=[],answer_ids=[],e.items.forEach(function(e){e.comments=[];var s=+e.share_link.match(/\d+/);answer_ids.push(s),answers_hash[s]=e}),e.has_more||(more_answers=!1),comment_page=1,getComments()}})}function getComments(){jQuery.ajax({url:commentUrl(comment_page++,answer_ids),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){e.items.forEach(function(e){e.owner.user_id===OVERRIDE_USER&&answers_hash[e.post_id].comments.push(e)}),e.has_more?getComments():more_answers?getAnswers():process()}})}function getAuthorName(e){return e.owner.display_name}function process(){var e=[];answers.forEach(function(s){var r=s.body;s.comments.forEach(function(e){OVERRIDE_REG.test(e.body)&&(r="<h1>"+e.body.replace(OVERRIDE_REG,"")+"</h1>")});var a=r.match(SCORE_REG);a&&e.push({user:getAuthorName(s),size:+a[3],language:a[1]+'/'+a[2],lang2:a[2],link:s.share_link})}),e.sort(function(e,s){var r=e.size,a=s.size;return r-a});var s={},r=1,a=null,n=1;e.forEach(function(e){e.size!=a&&(n=r),a=e.size,++r;var t=jQuery("#answer-template").html();t=t.replace("{{PLACE}}",n+".").replace("{{NAME}}",e.user).replace("{{LANGUAGE}}",e.language).replace("{{SIZE}}",e.size.toFixed(3)).replace("{{LINK}}",e.link),t=jQuery(t),jQuery("#answers").append(t);var o=e.language;/<a/.test(o)&&(o=jQuery(o).text()),s[o]=s[o]||{lang:e.lang2,user:e.user,size:e.size,link:e.link}});var t=[];for(var o in s)s.hasOwnProperty(o)&&t.push(s[o]);t.sort(function(e,s){var E=e.lang.toLowerCase(),S=s.lang.toLowerCase();return E>S?1:E<S?-1:0});for(var c=0;c<t.length;++c){var i=jQuery("#language-template").html(),o=t[c];i=i.replace("{{LANGUAGE}}",o.lang).replace("{{NAME}}",o.user).replace("{{SIZE}}",o.size.toFixed(3)).replace("{{LINK}}",o.link),i=jQuery(i),jQuery("#languages").append(i)}}var ANSWER_FILTER="!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe",COMMENT_FILTER="!)Q2B_A2kjfAiU78X(md6BoYk",answers=[],answers_hash,answer_ids,answer_page=1,more_answers=!0,comment_page;getAnswers();var SCORE_REG=/<h\d>\s*([^\n,]*[^\s,])\/([^\n,]*[^\s,]),.*?([\.\d]+)(?=[^\n\.\d<>]*(?:<(?:s>[^\n<>]*<\/s>|[^\n<>]+>)[^\n\.\d<>]*)*<\/h\d>)/,OVERRIDE_REG=/^Override\s*header:\s*/i;

body{text-align:left!important}#answer-list,#language-list{padding:10px;width:290px;float:left}table thead{font-weight:700}table td{padding:5px}

<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script> <link rel="stylesheet" type="text/css" href="//cdn.sstatic.net/codegolf/all.css?v=83c949450c8b"> <div id="answer-list"> <h2>Leaderboard</h2> <table class="answer-list"> <thead> <tr><td></td><td>Author</td><td>Languages</td><td>Score</td></tr></thead> <tbody id="answers"> </tbody> </table> </div><div id="language-list"> <h2>Winners by Output Language</h2> <table class="language-list"> <thead> <tr><td>Language</td><td>User</td><td>Score</td></tr></thead> <tbody id="languages"> </tbody> </table> </div><table style="display: none"> <tbody id="answer-template"> <tr><td>{{PLACE}}</td><td>{{NAME}}</td><td>{{LANGUAGE}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr></tbody> </table> <table style="display: none"> <tbody id="language-template"> <tr><td>{{LANGUAGE}}</td><td>{{NAME}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr></tbody> </table>

Um sicherzustellen, dass Ihre Antwort korrekt angezeigt wird, starten Sie sie bitte mit dieser Überschrift:

# Language name/Other language name, X points

Wo Xist die Punktzahl Ihrer Antwort? Beispiel:

# CJam/Pyth, 25.38 points

Wenn Sie Fragen oder Anregungen haben, lassen Sie es mich bitte wissen. Viel Glück!

Python / Zilog Z80-Maschinencode, 11.653 11.488

import math,numpy as np
def R(n):
    if n==0:return []
    if n<0:return -R(-n)
    e=int(math.log(n,2))
    if n >= 5/3 * 2**e:
        return np.append(2**(e+1),-R(2**(e+1)-n))
    return np.append(2**e,R(n-2**e))

def strR(n):
    b = R(n)
    s = ""
    if n==0:return s
    e=max(abs(b))
    while e:
        if e in b:s+="#"
        elif -e in b:s+="+"
        s+=")"
        e//=2
    return s[:-1]

Boni: Negative Zahlen.

Angenommen, das hlRegisterpaar hat anfangs den Wert 0 und gibt das Ergebnis in zurück hl.

Es werden nur diese drei Anweisungen verwendet:

ASCII   Hex    Instruction
--------------------------
#       23     inc hl
)       29     add hl,hl
+       2B     dec hl

Wir verwenden eine kleine Modifikation der minimalen gewichtsausgeglichenen Binärdarstellung BBR2 . Da BBR2 die Gewichtung minimiert (Anzahl der Stellen ungleich Null), wir jedoch die Gewichtung plus die Anzahl der Bitverschiebungen minimieren möchten, ändern wir eine Konstante im Algorithmus von 3/2auf 5/3.

Verwenden Sie diesen Code, um die Punktzahl zu berechnen und zu überprüfen:

def verify(n):
v = 0
for c in strR(n):
    if c=="#":v += 1
    elif c=="+":v -= 1
    else: v *= 2
return v==n

print(0.5*(sum([len(strR(n)) for n in range(1,1001)])/1000 + \
           sum([len(strR(n)) for n in range(-1000,1)])/1001 * 0.9))

print(all([verify(n) for n in range(-1000,1001)]))

Beispielausgabe:

strR(486)
         '#)))))+)+))+)'

Oder in der Montage:

inc hl \ add hl,hl \ add hl,hl \ add hl,hl \ add hl,hl \ add hl,hl \ dec hl \ add hl,hl \ dec hl \ add hl,hl \ add hl,hl \ dec hl \ add hl,hl

Weitere Beispielprogramme:

-256  +))))))))
-255  +))))))))#
-254  +)))))))#)
-253  +)))))))#)#
-252  +))))))#))
-251  +))))))#))#
-250  +))))))#)#)
-249  +)))))#)))+
-248  +)))))#)))
-247  +)))))#)))#
-246  +)))))#))#)
-245  +)))))#))#)#
-244  +)))))#)#))
-243  +)))))#)#))#
-242  +))))#)))+)
-241  +))))#))))+

  -5  +))+
  -4  +))
  -3  +)+
  -2  +)
  -1  +
   0  
   1  #
   2  #)
   3  #)#
   4  #))
   5  #))#

Mögliche Optimierungen: Regeln, die die OP inc hund dec hAnweisungen, die direkt an das obere Byte der Veränderung hl, sind illegal, sondern sla hund die nicht dokumentiert sl1 h(links Bitverschiebungen von 1 auf hdieser Verschiebung in einem 0und 1respectively) sind zulässig. sla hund sl1 hsind jeweils zwei Bytes, aber sie können manchmal die Ausgabe verkürzen.

CJam / CJam, 143,263 42.713 28.899 23.901 21.903 20.468

ri
[
    ['X\2b1>e`{~{"1)*)"*}{_({(')*1\"m<"}{"1)*"*}?}?}/]s
    "X1)*"/"1)"*
    "1)1)*"/"1)))"*
    "X1)m<"/"1)))"*
    _"1)"/("1):Y"+\'Y*+
]
{,}$0=

Es gelten keine Boni.

Probieren Sie es online aus: Probelauf | Partiturrechner |Nachprüfung

Beispiel läuft

   1 X
   2 1)
   3 1))
   4 1)))
   5 1))))
   6 1))1)*
   7 1))1)*)
   8 X1))m<
   9 1)))1)*)
  10 1))))1)*
  11 1))))1)*)
  12 1))1)m<
  13 1))1)*1)*)
  14 1))1)*)1)*
  15 1))1)*)1)*)
  16 X1)))m<
  17 X1))m<1)*)
  18 1)))1)*)1)*
  19 1)))1)*)1)*)
  20 1))))1)m<

 981 1):Y)Y*)Y*)Y*Y*)Y*Y*)Y*Y*)
 982 1):Y)Y*)Y*)Y*Y*)Y*Y*)Y*)Y*
 983 1):Y)Y*)Y*)Y*Y*)Y*Y*)Y*)Y*)
 984 1):Y)Y*)Y*)Y*Y*)Y*)Y)m<
 985 1):Y)Y*)Y*)Y*Y*)Y*)Ym<Y*)
 986 1):Y)Y*)Y*)Y*Y*)Y*)Y*Y*)Y*
 987 1):Y)Y*)Y*)Y*Y*)Y*)Y*Y*)Y*)
 988 1):Y)Y*)Y*)Y*Y*)Y*)Y*)Ym<
 989 1):Y)Y*)Y*)Y*Y*)Y*)Y*)Y*Y*)
 990 1):Y)Y*)Y*)Y*Y*)Y*)Y*)Y*)Y*
 991 1):Y)Y*)Y*)Y*Y*)Y*)Y*)Y*)Y*)
 992 1):Y)Y*)Y*)Y*)Y)))m<
 993 1):Y)Y*)Y*)Y*)Y))m<Y*)
 994 1):Y)Y*)Y*)Y*)Y)m<Y*)Y*
 995 1):Y)Y*)Y*)Y*)Y)m<Y*)Y*)
 996 1):Y)Y*)Y*)Y*)Ym<Y*)Ym<
 997 1):Y)Y*)Y*)Y*)Ym<Y*)Y*Y*)
 998 1):Y)Y*)Y*)Y*)Ym<Y*)Y*)Y*
 999 1):Y)Y*)Y*)Y*)Ym<Y*)Y*)Y*)
1000 1):Y)Y*)Y*)Y*)Y*Y*)Y)m<

ß / BrainFuck, 34.201 Punkte

ß Quelle (194B):

E='++[------>+<]>++'°\c[1]<0°{E&='.'µA=ß"-ß°°c[1]),'')µE&='+++'°/B=1°(A[0]°\A[B]='.'°{µE&='--.++'°]E&=ß~A'+',A[B])&'.'&ß~A'-',A[B])°}°)°'ß"&E,'+-')+ß"&E,'-+')>0µE=ß"'ß"'E,'-+',''),'+-','')°!€E)

Wenn jemand interessiert ist, werde ich eine Erklärung hinzufügen. Die BF-Ausgabe ist bereits ziemlich optimiert, aber ich denke, ich könnte die restlichen 318B des ß-Codes verwenden, um sie zu implementieren

• eine Loop-Nesting-Optimierung,
• weitere 8bit Overflow Shortcuts,
• Entfernung von Bedienerkollisionen .

Proben:

Laufen in Windows:

$ sharps encode.ss 42
++[------>+<]>+++++++++.--.--

$ sharps encode.ss -42
++[------>+<]>++.+++++++.--.--

$ sharps encode.ss 1.427
++[------>+<]>++++++.---.++++++.--.+++++.-------

$ sharps encode.ss -946.427
++[------>+<]>++.++++++++++++.-----.++.--------.++++++.--.+++++.-------

Laufen unter Linux:

$ WINEDEBUG=-all wine sharps source.ss -4.72
++[------>+<]>++.+++++++.------.+++++++++.-----.--

Validieren Sie im Online-BF-Interpreter .

Scores:

1. Basisdurchschnitt = 37.495 .
2. Dezimaler Durchschnitt = 60.959 * 0.5 = ~30.48 .
3. Negative durchschn. = 38.4765234765235 * 0.9 = ~34.629
4. Durchschnitt der oben genannten, endgültigen Punktzahl = (37.495 + 30.48 + 34.629)/3 = 34.201.

Ruby / Ruby, 29,77885

31,873 * 0,9 (negativ) 30,872 (positiv).

Grundlegende Strategie ist die symmetrische Darstellung der Basis 3 ("ausgeglichenes ternäres"), dh wenn die Ziffern sind -1,0,1 anstelle von0,1,2

#function
f=->n{m=n  
  a='0' 
  7.times{|i|
    r=m%3;r-=r/2*3
    m=(m-r)/3
    #produce expression: replace 0 with (0*x+-1)
    #only add 0*x if there are higher base 3 digits to follow.
    #only add (..+-1) if the current base 3 digit is nonzero. 
    a.sub!('0',['','(','('][r]+(m.abs>0?'0*x':'')+['','+1)','-1)'][r])
  }
  #tidy up expression
  a.sub!('(-1)*','-')          #remove internal (-1)*
  a.sub!('(+1)*','')           #remove internal (+1)*
  a[-1]==')' && a=a[1..-2]     #remove unnecessary global brackets
  a.sub!('x','(x=1+1+1)')      #find the first x and define it as 1+1+1=3
  #special cases for small numbers 
  n.abs<8 && a=n==0?'0':['','1'+'+1'*(n-1).abs,'-1'*n.abs][n<=>0] 
  a 
}

#call like this
(1..1000).each{|p|
b=f.call(p)
puts b

Hier ist die Ausgabe von 0 bis 40 vor der Bereinigung

(+1)
((+1)*x-1)
(+1)*x
((+1)*x+1)
(((+1)*x-1)*x-1)
((+1)*x-1)*x
(((+1)*x-1)*x+1)
((+1)*x*x-1)
(+1)*x*x
((+1)*x*x+1)
(((+1)*x+1)*x-1)
((+1)*x+1)*x
(((+1)*x+1)*x+1)
((((+1)*x-1)*x-1)*x-1)
(((+1)*x-1)*x-1)*x
((((+1)*x-1)*x-1)*x+1)
(((+1)*x-1)*x*x-1)
((+1)*x-1)*x*x
(((+1)*x-1)*x*x+1)
((((+1)*x-1)*x+1)*x-1)
(((+1)*x-1)*x+1)*x
((((+1)*x-1)*x+1)*x+1)
(((+1)*x*x-1)*x-1)
((+1)*x*x-1)*x
(((+1)*x*x-1)*x+1)
((+1)*x*x*x-1)
(+1)*x*x*x
((+1)*x*x*x+1)
(((+1)*x*x+1)*x-1)
((+1)*x*x+1)*x
(((+1)*x*x+1)*x+1)
((((+1)*x+1)*x-1)*x-1)
(((+1)*x+1)*x-1)*x
((((+1)*x+1)*x-1)*x+1)
(((+1)*x+1)*x*x-1)
((+1)*x+1)*x*x
(((+1)*x+1)*x*x+1)
((((+1)*x+1)*x+1)*x-1)
(((+1)*x+1)*x+1)*x
((((+1)*x+1)*x+1)*x+1)

Und nach dem Aufräumen

0
1
1+1
1+1+1
1+1+1+1
1+1+1+1+1
1+1+1+1+1+1
1+1+1+1+1+1+1
(x=1+1+1)*x-1
(x=1+1+1)*x
(x=1+1+1)*x+1
((x=1+1+1)+1)*x-1
((x=1+1+1)+1)*x
((x=1+1+1)+1)*x+1
(((x=1+1+1)-1)*x-1)*x-1
(((x=1+1+1)-1)*x-1)*x
(((x=1+1+1)-1)*x-1)*x+1
((x=1+1+1)-1)*x*x-1
((x=1+1+1)-1)*x*x
((x=1+1+1)-1)*x*x+1
(((x=1+1+1)-1)*x+1)*x-1
(((x=1+1+1)-1)*x+1)*x
(((x=1+1+1)-1)*x+1)*x+1
((x=1+1+1)*x-1)*x-1
((x=1+1+1)*x-1)*x
((x=1+1+1)*x-1)*x+1
(x=1+1+1)*x*x-1
(x=1+1+1)*x*x
(x=1+1+1)*x*x+1
((x=1+1+1)*x+1)*x-1
((x=1+1+1)*x+1)*x
((x=1+1+1)*x+1)*x+1
(((x=1+1+1)+1)*x-1)*x-1
(((x=1+1+1)+1)*x-1)*x
(((x=1+1+1)+1)*x-1)*x+1
((x=1+1+1)+1)*x*x-1
((x=1+1+1)+1)*x*x
((x=1+1+1)+1)*x*x+1
(((x=1+1+1)+1)*x+1)*x-1
(((x=1+1+1)+1)*x+1)*x
(((x=1+1+1)+1)*x+1)*x+1

Ceylon / Ceylon, 49,86 40,95 Punkte

Die dritte Version verwendet Ceylon 1.2 für den Generator und 509 Byte Code:

import ceylon.language{S=String,I=Integer,e=expand}S q(I n)=>n==0then"0"else(n<0then"-"+p(-n,"-")else p(n,"+"));variable Map<[I,S],S>c=map{};S p(I n,S s){S v=c[[n,s]]else(n<8then s.join([1].repeat(n)))else(let(a="+-".replace(s,""))e(e{for(x in 2..8)let(l=(n^(1.0/x)).integer){for(r in l:2)if(r>1)let(w=r^x){if(w-n<n)"("+p(r,"+")+")^("+p(x,"+")+")"+(w<n then s+p(n-w,s)else(n<w then a+p(w-n,a)else""))}}}).reduce<S>((x,y)=>x.size<y.size then x else y))else"";c=[n,s]in c then c else map{[n,s]->v,*c};return v;}

Es geht auf 35,22 Punkte zurück, aber ich werde dies nicht in die Titelzeile setzen, da Celyon 1.2 erst am 29. Oktober veröffentlicht wurde. Ich glaube nicht, dass ich diesen Algorithmus in Ceylon 1.1 in dieser Größe implementieren kann.). Weitere Details hier unten, hier beschreibe ich die zweite Version. (Die erste Version ist in der Historie zu sehen - sie unterstützte nur positive Zahlen, passte aber in 256 Bytes.)

Zweite Version

Jetzt die zweite Version, die negative Ganzzahlen (und 0) unterstützt und generell eine etwas kürzere Ausgabe durch zusätzliche Verwendung erzeugt -. (Diese Version verwendet tatsächlich die erlaubte Länge, die erste hat versucht, unter 256 Bytes statt 512 zu bleiben.)

String proof(Integer n) {
    if (n == 0) { return "0"; }
    if (n < 0) { return "-" + p(-n, "-"); }
    return p(n, "+");
}
String p(Integer n, String sign) {
    if (n < 9) {
        return sign.join([1].repeat(n));
    }
    value anti = (sign == "+") then "-" else "+";
    value root = ((n^0.5) + 0.5).integer;
    return "(" + p(root, "+") + ")^(1+1)" +
       ( (root^2 < n) then sign + p(n - root^2, sign) else
         ((n < root^2) then anti + p(root^2 - n, anti) else ""));
}

Code hat die Länge 487, sodass später noch Platz für weitere Optimierungen bleibt. (Es gibt auch viele Reserven in Form von Leerzeichen und langen Variablennamen.)

Die Wertung:

Total positive: 42652
Average positive:42.652
Total negative: 43653
Average negative: 43.60939060939061
With bonus:39.24845154845155
Overall score: 40.95022577422577

Einige Beispielausgaben:

   27:  21: (1+1+1+1+1)^(1+1)+1+1
   28:  23: (1+1+1+1+1)^(1+1)+1+1+1
   29:  25: (1+1+1+1+1)^(1+1)+1+1+1+1
   30:  27: (1+1+1+1+1)^(1+1)+1+1+1+1+1
   31:  29: (1+1+1+1+1+1)^(1+1)-1-1-1-1-1
   32:  27: (1+1+1+1+1+1)^(1+1)-1-1-1-1
   33:  25: (1+1+1+1+1+1)^(1+1)-1-1-1
   34:  23: (1+1+1+1+1+1)^(1+1)-1-1

  -27:  22: -(1+1+1+1+1)^(1+1)-1-1
  -28:  24: -(1+1+1+1+1)^(1+1)-1-1-1
  -29:  26: -(1+1+1+1+1)^(1+1)-1-1-1-1
  -30:  28: -(1+1+1+1+1)^(1+1)-1-1-1-1-1
  -31:  30: -(1+1+1+1+1+1)^(1+1)+1+1+1+1+1
  -32:  28: -(1+1+1+1+1+1)^(1+1)+1+1+1+1
  -33:  26: -(1+1+1+1+1+1)^(1+1)+1+1+1
  -34:  24: -(1+1+1+1+1+1)^(1+1)+1+1


  993:  65: ((1+1+1+1+1+1)^(1+1)-1-1-1-1)^(1+1)-(1+1+1+1+1+1)^(1+1)+1+1+1+1+1
  994:  63: ((1+1+1+1+1+1)^(1+1)-1-1-1-1)^(1+1)-(1+1+1+1+1)^(1+1)-1-1-1-1-1
  995:  61: ((1+1+1+1+1+1)^(1+1)-1-1-1-1)^(1+1)-(1+1+1+1+1)^(1+1)-1-1-1-1
  996:  59: ((1+1+1+1+1+1)^(1+1)-1-1-1-1)^(1+1)-(1+1+1+1+1)^(1+1)-1-1-1
  997:  57: ((1+1+1+1+1+1)^(1+1)-1-1-1-1)^(1+1)-(1+1+1+1+1)^(1+1)-1-1
  998:  55: ((1+1+1+1+1+1)^(1+1)-1-1-1-1)^(1+1)-(1+1+1+1+1)^(1+1)-1
  999:  53: ((1+1+1+1+1+1)^(1+1)-1-1-1-1)^(1+1)-(1+1+1+1+1)^(1+1)
 1000:  55: ((1+1+1+1+1+1)^(1+1)-1-1-1-1)^(1+1)-(1+1+1+1+1)^(1+1)+1

 -993:  66: -((1+1+1+1+1+1)^(1+1)-1-1-1-1)^(1+1)+(1+1+1+1+1+1)^(1+1)-1-1-1-1-1
 -994:  64: -((1+1+1+1+1+1)^(1+1)-1-1-1-1)^(1+1)+(1+1+1+1+1)^(1+1)+1+1+1+1+1
 -995:  62: -((1+1+1+1+1+1)^(1+1)-1-1-1-1)^(1+1)+(1+1+1+1+1)^(1+1)+1+1+1+1
 -996:  60: -((1+1+1+1+1+1)^(1+1)-1-1-1-1)^(1+1)+(1+1+1+1+1)^(1+1)+1+1+1
 -997:  58: -((1+1+1+1+1+1)^(1+1)-1-1-1-1)^(1+1)+(1+1+1+1+1)^(1+1)+1+1
 -998:  56: -((1+1+1+1+1+1)^(1+1)-1-1-1-1)^(1+1)+(1+1+1+1+1)^(1+1)+1
 -999:  54: -((1+1+1+1+1+1)^(1+1)-1-1-1-1)^(1+1)+(1+1+1+1+1)^(1+1)
-1000:  56: -((1+1+1+1+1+1)^(1+1)-1-1-1-1)^(1+1)+(1+1+1+1+1)^(1+1)-1

    1:   1: 1
    2:   3: 1+1
    3:   5: 1+1+1
    4:   7: 1+1+1+1
    5:   9: 1+1+1+1+1
    6:  11: 1+1+1+1+1+1
    7:  13: 1+1+1+1+1+1+1
    8:  15: 1+1+1+1+1+1+1+1
    9:  13: (1+1+1)^(1+1)
   10:  15: (1+1+1)^(1+1)+1

    0:   1: 0
   -1:   2: -1
   -2:   4: -1-1
   -3:   6: -1-1-1
   -4:   8: -1-1-1-1
   -5:  10: -1-1-1-1-1
   -6:  12: -1-1-1-1-1-1
   -7:  14: -1-1-1-1-1-1-1
   -8:  16: -1-1-1-1-1-1-1-1
   -9:  14: -(1+1+1)^(1+1)
  -10:  16: -(1+1+1)^(1+1)-1

Wie Sie sehen, sind die negativen immer ein Byte (das führende -) länger als die entsprechenden positiven.

Die Grundidee ist dieselbe wie im vorherigen Programm: Finden Sie ein Quadrat in der Nähe unserer Zielzahl und repräsentieren Sie dessen Wurzel und den Rest rekursiv. Aber jetzt lassen wir zu, dass unser Quadrat auch etwas größer als die Zielzahl ist, was den Rest negativ macht. (Das+0.5 können die Konstante ändern, um den Algorithmus zu optimieren, aber anscheinend habe ich hier bereits das Optimum erreicht. Sowohl 0,4 als auch 0,6 liefern schlechtere Ergebnisse.)

Um negative Werte negativ zu machen (und ansonsten die gleiche Struktur wie die positiven zu haben, übergeben wir den Operator sign an unsere rekursive Funktion p- entweder "+"oder"-" . Wir können dies auch für den Schreiner in den trivialen Fällen (dh n <9) verwenden Was den Rest betrifft, wenn er positiv ist, und verwenden Sie das entgegengesetzte Vorzeichen für den Rest, wenn er negativ ist.

Die proofFunktion behandelt das Anfangszeichen (mit einem Sonderfall für 0), die pFunktion erledigt die eigentliche Arbeit mit Rekursion.

Dritte Version für Ceylon 1.2

import ceylon.language { S=String, I=Integer,e=expand }

// output a base-proof Ceylon expression for an integer
// (i.e. using only 0 and 1 as digits).
//
// Question: http://codegolf.stackexchange.com/q/58084/2338
// My Answer:  http://codegolf.stackexchange.com/a/58122/2338
//
// The goal is to produce an expression as short as possible, with
// the code staying under 512 bytes in length.
//
// This approach is to represent a positive integer as a square
// of a positive integer plus some remainder (where the remainder
// can be negative), and for negative integers replace the + on the
// outer level by -.

S q(I n) =>
        n == 0 then "0"
        else (n < 0 then "-" + p(-n, "-")
            else p(n, "+"));

// cache for values of p
variable Map<[I, S],S> c = map { };

// Transforms a positive number into a base-proof term, using
// the given sign for the summation on the outer level.
S p(I n, S s) {
    S v =
    // look into the cache
            c[[n, s]] else (
        // hard-code small numbers
        n < 8 then s.join([1].repeat(n)))
            else
    // do the complicated stuff
    (let (a = "+-".replace(s,""))
            e(e {
                    for (x in 2..8) // try these exponents
                        let (l = (n ^ (1.0 / x)).integer) // \[ sqrt[exp]{n} \] in LaTeX
                            { for (r in l:2) // lowerRoot, lowerRoot + 1
                                    if (r > 1)
                                        let (w = r ^ x)
                                            { if (w-n < n) // avoid recursion to larger or same number
                                                    // format the string as  r^x + (n-w)
                                                    "(" + p(r, "+") + ")^(" + p(x, "+") + ")" +
                                                            (w < n then s + p(n - w, s)
                                                                else (n < w then a + p(w - n, a)
                                                                    else ""))
                                            } } })
            // and now find the shortest formatted string
                .reduce<S>((x, y) => x.size < y.size then x else y))
    // this should never happen, but we can't tell the compiler
    // that at least some of the iterables are non-empty due to the if clause.
            else "";

    // this builds a new cache in each step – quite wasteful,
    // as this also happens when the value was found in the cache,
    // but we don't have more characters remaining.
    //// c = map { [n, s] -> v, *c };
    ///better way:
     c = [n,s] in c then c else map{[n,s]->v, *c}; 
    return v;
}

Die Golf-Version (dh Kommentare und Leerzeichen werden entfernt) wird mit genau 509 Byte Code oben angezeigt.

Dies verwendet dasselbe Grundprinzip wie die zweite Version, aber anstelle von nur Quadraten wird auch versucht, höhere Potenzen von Zahlen zu verwenden (versuchen Sie es mit Exponenten von 2 bis 8) und verwenden Sie das kürzeste Ergebnis. Außerdem werden die Ergebnisse zwischengespeichert, da dies ansonsten für größere Nummern mit vielen rekursiven Aufrufen unannehmbar langsam wäre.

Wertung:

Total positive: 36622
Average positive: 36.622
Total negative: 37623
Average negative: 37.58541458541458
With bonus:33.826873126873124
Overall score: 35.22443656343656

Das große eingerückte Konstrukt in der Mitte besteht aus drei ineinander verschachtelten iterablen Begriffen, die beiden inneren in einem let-Ausdruck. Diese werden dann bei zweimaliger Verwendung der Erweiterungsfunktion nicht verschachtelt, und die reduceFunktion findet die kürzeste dieser Zeichenfolgen.

Ich habe eine Feature-Anfrage eingereicht , um dies in einem einzigen Verständnis tun zu können.

Innerhalb des Verständnisses bauen wir eine Zeichenkette aus der Wurzel r, dem Exponenten xund dem Rest ( n-woder w-n) auf.

Der letAusdruck und die mapFunktion sind neu in Ceylon 1.2. maphätte durch ersetzt werden können HashMap(das hätte mehr Zeichen für den Import benötigt, obwohl es wahrscheinlich noch schneller wäre, da ich die Map nicht für jeden neuen Eintrag neu erstellen würde). Die letAusdrücke wie let (w = r ^ x)hätten durch eine ifKlausel wie ersetzt werden können if(exists w = true then r ^ x)(und dann hätte ich auch die beiden expandAufrufe nicht gebraucht ), aber das wäre noch ein bisschen länger und würde nicht in die 511 zulässigen Bytes passen.

Hier sind die Beispielausgaben, die den oben ausgewählten entsprechen, mit Ausnahme der wirklich kleinen Zahlen, alle kürzer:

   27:  15: (1+1+1)^(1+1+1)
   28:  17: (1+1+1)^(1+1+1)+1
   29:  19: (1+1+1)^(1+1+1)+1+1
   30:  21: (1+1)^(1+1+1+1+1)-1-1
   31:  19: (1+1)^(1+1+1+1+1)-1
   32:  17: (1+1)^(1+1+1+1+1)
   33:  19: (1+1)^(1+1+1+1+1)+1
   34:  21: (1+1)^(1+1+1+1+1)+1+1

  -27:  16: -(1+1+1)^(1+1+1)
  -28:  18: -(1+1+1)^(1+1+1)-1
  -29:  20: -(1+1+1)^(1+1+1)-1-1
  -30:  22: -(1+1)^(1+1+1+1+1)+1+1
  -31:  20: -(1+1)^(1+1+1+1+1)+1
  -32:  18: -(1+1)^(1+1+1+1+1)
  -33:  20: -(1+1)^(1+1+1+1+1)-1
  -34:  22: -(1+1)^(1+1+1+1+1)-1-1

  993:  39: ((1+1+1)^(1+1)+1)^(1+1+1)-1-1-1-1-1-1-1
  994:  37: ((1+1+1)^(1+1)+1)^(1+1+1)-1-1-1-1-1-1
  995:  35: ((1+1+1)^(1+1)+1)^(1+1+1)-1-1-1-1-1
  996:  33: ((1+1+1)^(1+1)+1)^(1+1+1)-1-1-1-1
  997:  31: ((1+1+1)^(1+1)+1)^(1+1+1)-1-1-1
  998:  29: ((1+1+1)^(1+1)+1)^(1+1+1)-1-1
  999:  27: ((1+1+1)^(1+1)+1)^(1+1+1)-1
 1000:  25: ((1+1+1)^(1+1)+1)^(1+1+1)

 -993:  40: -((1+1+1)^(1+1)+1)^(1+1+1)+1+1+1+1+1+1+1
 -994:  38: -((1+1+1)^(1+1)+1)^(1+1+1)+1+1+1+1+1+1
 -995:  36: -((1+1+1)^(1+1)+1)^(1+1+1)+1+1+1+1+1
 -996:  34: -((1+1+1)^(1+1)+1)^(1+1+1)+1+1+1+1
 -997:  32: -((1+1+1)^(1+1)+1)^(1+1+1)+1+1+1
 -998:  30: -((1+1+1)^(1+1)+1)^(1+1+1)+1+1
 -999:  28: -((1+1+1)^(1+1)+1)^(1+1+1)+1
-1000:  26: -((1+1+1)^(1+1)+1)^(1+1+1)

    1:   1: 1
    2:   3: 1+1
    3:   5: 1+1+1
    4:   7: 1+1+1+1
    5:   9: 1+1+1+1+1
    6:  11: 1+1+1+1+1+1
    7:  13: 1+1+1+1+1+1+1
    8:  13: (1+1)^(1+1+1)
    9:  13: (1+1+1)^(1+1)
   10:  15: (1+1+1)^(1+1)+1

    0:   1: 0
   -1:   2: -1
   -2:   4: -1-1
   -3:   6: -1-1-1
   -4:   8: -1-1-1-1
   -5:  10: -1-1-1-1-1
   -6:  12: -1-1-1-1-1-1
   -7:  14: -1-1-1-1-1-1-1
   -8:  14: -(1+1)^(1+1+1)
   -9:  14: -(1+1+1)^(1+1)
  -10:  16: -(1+1+1)^(1+1)-1

Zum Beispiel haben wir jetzt 1000 = (3 ^ 2 + 1) ^ 3 anstelle von 1000 = (6 ^ 2-4) ^ 2-5 ^ 2 + 1.

Ruby / dc, 20,296 18.414 16.968

Dynamische Programmierung! Definiert eine Liste von Funktionen, die bei einer gegebenen DC-Anweisung einen neuen Ausdruck und den numerischen Wert dieses Ausdrucks zurückgeben. Ausgehend von 1prefined wird dann eine Liste aller erreichbaren Werte bis einschließlich des gewünschten Werts erstellt.

bearbeiten:

Es wurde eine Funktion für n-1 hinzugefügt , mit der der Algorithmus in mehreren Durchgängen ausgeführt wurde. Es scheint 7 Durchgänge zu benötigen, um sich zu stabilisieren. Einige Variablennamen mussten gekürzt werden, um innerhalb von 512 Byte zu bleiben.

2 bearbeiten:

Es wurden Funktionen für n (n-1) , n (n + 1) und n ^ 3 hinzugefügt , während ich dabei war. Kürzte den Code noch weiter und landete bei genau 512 Bytes.

N = gets.to_i

fns = [
  ->(n,s){[n-1,   s+'1-']},
  ->(n,s){[n+1,   s+'1+']},
  ->(n,s){[n*2,   s+'d+']},
  ->(n,s){[n*3,   s+'dd++']},
  ->(n,s){[n*~-n, s+'d1-*']},
  ->(n,s){[n*n,   s+'d*']},
  ->(n,s){[n*-~n, s+'d1+*']},
  ->(n,s){[n*n*n, s+'dd**']},
]

lst = []*(N+1)
lst[0..2] = %w[0 1 1d+]

loop do
  prev = lst.dup

  (1..N).each do |n|
    fns.each do |f|
      m,s = f[n, lst[n]]
      lst[m] = s if m <= N && (lst[m].nil? || lst[m].size > s.size)
    end
  end

  break if lst == prev
end

puts lst[N]

Generierte Zahlen:

Die Ausgabe besteht vollständig aus fünf verschiedenen Zeichen: 1Drückt den Wert 1 auf den Stapel; ddupliziert die Oberseite des Stapels; +, -Und * knallt die beiden Spitzenwerte und drückt ihre Summe, Differenz und Produkt sind. Jeder generierte Ausdruck fügt dem Stapel nach der Ausführung nur einen Wert hinzu.

   1: 1
   2: 1d+
   3: 1dd++
   4: 1d+d+
   5: 1d+d+1+
   6: 1d+dd++
   7: 1d+dd++1+
   8: 1d+dd**
   9: 1dd++d*
  10: 1d+d+1+d+
  11: 1d+d+1+d+1+
  12: 1dd++d1+*
  13: 1dd++d1+*1+
  14: 1d+dd++1+d+
  15: 1d+d+d*1-
  16: 1d+d+d*
  17: 1d+d+d*1+
  18: 1dd++d*d+
  19: 1dd++d*d+1+
  20: 1d+d+d1+*
  21: 1d+d+d1+*1+
  22: 1d+d+1+d+1+d+
  23: 1d+dd**dd++1-
  24: 1d+dd**dd++
  25: 1d+d+1+d*

...

 989: 1d+d+d*d+d1-*1-1-1-
 990: 1d+d+d*d+d1-*1-1-
 991: 1d+d+d*d+d1-*1-
 992: 1d+d+d*d+d1-*
 993: 1d+d+d*d+d1-*1+
 994: 1d+d+d*d+d1-*1+1+
 995: 1d+d+d*d+d1-*1+1+1+
 996: 1d+d+1+dd**d+1-d+d+
 997: 1d+d+1+d+dd**1-1-1-
 998: 1d+d+1+d+dd**1-1-
 999: 1d+d+1+d+dd**1-
1000: 1d+d+1+d+dd**

Python 2.6, 78.069 - 66.265 Punkte

Senden meiner Antwort für das, was es wert ist (nicht viel in diesem Fall ... aber klar zu demonstrieren, dass es für diese Herausforderung nicht ausreicht, einfach die Ausgabe als Summe bitverschobener Werte zu komponieren, wenn man berücksichtigt, dass es keine Ziffern gibt außerhalb von 0 oder 1 kann in der Ausgabe erscheinen). Ich könnte später mit einer anderen Art der Ausgabeerzeugung zurückkommen.

Der Code selbst ist nicht zu lang (176 Zeichen):

def f(a):return'+'.join(('(1<<%s)'%['0','+'.join('1'*x)][x>0]).replace('(1<<0)','1')for x in[i for i,e in enumerate(bin(a)[::-1][:-2])if int(e)])
print"".join(f(int(input())))

Es erzeugt eine korrekte, aber ausführliche Ausgabe:

17
1+(1<<1+1+1+1)

800
(1<<1+1+1+1+1)+(1<<1+1+1+1+1+1+1+1)+(1<<1+1+1+1+1+1+1+1+1)

Snippet, das die Punktzahl berechnet:

def f(a):return'+'.join(('(1<<%s)'%['0','+'.join('1'*x)][x>0]).replace('(1<<0)','1')for x in[i for i,e in enumerate(bin(a)[::-1][:-2])if int(e)])
print sum(len("".join(f(i)))for i in range(1000))