Contexte

Dans certains futurs possibles, le monde convertira leurs systèmes numériques de la décimale (base 10 ou b10) à une autre base (binaire b2, octale b8, hexadécimale b16ou même unaire b1, auquel cas nous sommes foutus!). Ainsi, en prévision de cet éventuel événement qui changera le monde, vous décidez d'éprouver à la base tous vos programmes. Cela peut être fait en utilisant uniquement des 0s et 1s singuliers conjointement avec des opérateurs pour remplacer les constantes numériques existantes.

Cependant, il n'y a qu'un seul problème: vous avez une tonne de programmes à modifier, et la conversion manuelle de chaque nombre en une expression prendrait des semaines! Ainsi, vous décidez d'écrire un programme (ou une fonction) pour décider pour vous quelle expression doit remplacer chaque nombre.

Contribution

L'entrée sera un entier positif. Votre code doit être capable de gérer n'importe quel entier jusqu'à 1000.

(Si votre code prend en charge les décimales et / ou les entrées négatives, voir Score ci-dessous.)

Production

Votre code doit générer une expression qui évalue l'entrée en au moins une langue. Cela peut être n'importe quelle langue; il ne doit pas nécessairement être le même que celui dans lequel votre programme ou fonction est écrit. De plus, cette expression n'a pas besoin d'être un programme ou une fonction complète.

Pour plus de clarté, la sortie peut contenir l'une de ces opérations:

• incrémenter / décrémenter
• ajouter / somme
• soustraire / annuler
• multiplier / doubler (seulement si cela n'implique pas directement le nombre 2!)
• diviser / modulo
• exposants / logarithmes
• square / sqrt (encore une fois, seulement si ceux-ci n'impliquent pas directement le nombre 2!)
• opérations au niveau du bit (bOR, BAND, bNOT, bXOR, décalage de bits)
• définition / obtention de variables
• manipulation de pile

Vous ne pouvez pas utiliser eval()ou toute fonction similaire dans la sortie. Vous ne pouvez pas non plus utiliser dans la sortie des fonctions qui exécutent une ou plusieurs actions autres que celles mentionnées ci-dessus.

Oh, et encore une chose: puisque nous voulons que la sortie soit valide dans autant de bases que possible, les seules constantes numériques qu'elle peut contenir sont 0et 1. Des nombres tels que 10(dix) sont interdits, sauf si la langue l'interprète comme un 1et un 0. L'utilisation de chaînes pour contenir des nombres n'est pas autorisée non plus, tout comme l'utilisation de caractères tels que CJam A- K(qui représentent 10- 20).

Cas de test

(Toutes les sorties sont en JavaScript, mais peuvent fonctionner dans d'autres langues.)

Entrée 1:

2

Sortie possible 1:

1+1

Entrée 2:

13

Sortie possible 2:

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

Entrée 3:

60

Sortie possible 3:

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

Entrée 4:

777

Sortie possible 4:

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

Entrée 5:

1000

Sortie possible 5:

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

Notation

Le but de ce défi est de raccourcir autant que possible la sortie de votre code. Votre score sera calculé de cette manière:

• Score de base: nombre moyen d'octets de toutes les sorties pour les entiers 1 à 1000.

• Score décimal: si votre code prend en charge au moins 3 décimales, il s'agit du nombre moyen d'octets de toutes les sorties de la séquence de nombres commençant par 0.001et se terminant par 1000, augmentant de 1.001chaque fois. 0.001, 1.002, 2.003...998.999, 1000.000Ensuite, retirez 50% de ce score.

• Score négatif: si votre code prend en charge les nombres négatifs et zéro, il s'agit du nombre moyen d'octets des sorties de tous les entiers de -1000à 0. Ensuite, retirez 10% de ce score.

(Le moyen le plus simple de les calculer serait probablement une boucle avec votre programme / fonction à l'intérieur.)

Votre score final est la moyenne de la formule applicable ci-dessus.

Si la sortie n'est pas déterministe (c'est-à-dire quelque peu aléatoire; plusieurs exécutions avec la même entrée produisent plusieurs sorties uniques), alors le score de chaque entrée est déterminé par la plus grande sortie sur dix exécutions sur mon processeur.

De plus, comme vous ne savez pas à quel point les données informatiques seront précieuses à l'avenir, le nombre d'octets de votre code générateur doit être inférieur à 512 octets.

Le score le plus bas en deux semaines (le 30 septembre) sera déclaré vainqueur. Félicitations à votre gagnant, @ThomasKwa !

Classement

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>

Pour vous assurer que votre réponse s'affiche correctement, veuillez commencer par cet en-tête:

# Language name/Other language name, X points

Où Xest le score de votre réponse. Exemple:

# CJam/Pyth, 25.38 points

Si vous avez des questions ou des suggestions, faites-le moi savoir. Bonne chance!

Code machine Python / Zilog Z80, 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]

Bonus: nombres négatifs.

Suppose que la hlpaire de registres contient initialement 0 et renvoie le résultat hl.

Seules ces trois instructions sont utilisées:

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

Nous utilisons une petite modification de la représentation binaire équilibrée de poids minimum BBR2 . Puisque BBR2 minimise le poids (nombre de chiffres non nuls), mais nous voulons minimiser le poids plus le nombre de décalages de bits, nous modifions une constante dans l'algorithme de 3/2à 5/3.

Pour calculer le score et vérifier, utilisez ce code:

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

Exemple de sortie:

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

Ou en 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

Plus d'exemples de programmes:

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

Optimisations possibles: les règles OP interdisant les instructions inc het dec h, qui modifient directement l'octet supérieur hl, mais sla hles non documentées sl1 h(les décalages du bit gauche de 1 sur hce décalage dans a 0et 1respectivement) sont autorisées. sla het sl1 hsont deux octets chacun, mais ils peuvent parfois raccourcir la sortie.

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=

Aucun bonus ne s'applique.

Essayez-le en ligne: exemple de course | calculateur de score | vérification

Exemple d'exécutions

   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 points

ß source (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)

Si quelqu'un est intéressé, j'ajouterai une explication. La sortie BF est déjà assez optimisée, mais je suppose que je pourrais utiliser les 318B restants de code ß pour implémenter

• une optimisation d'imbrication de boucle,
• plus de raccourcis de débordement 8 bits,
• suppression des collisions par l'opérateur .

Échantillons:

Exécution sous Windows:

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

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

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

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

Sous Linux:

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

Validez dans l' interpréteur BF en ligne .

Scores:

1. Moyenne de base = 37.495.
2. Moyenne décimale = 60.959 * 0.5 = ~30.48.
3. Négative moyenne = 38.4765234765235 * 0.9 = ~34.629
4. Moyenne de ce qui précède, score final = (37.495 + 30.48 + 34.629)/3 = 34.201.

Rubis / Rubis, 29.77885

31,873 * 0,9 (négatif) 30,872 (positif).

La stratégie de base est une représentation symétrique en base 3 ("ternaire équilibré"), c'est-à-dire lorsque les chiffres sont -1,0,1au lieu de0,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

Voici la sortie de 0 à 40 avant le nettoyage

(+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)

Et après le nettoyage

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

Ceylan / Ceylan, 49,86 40,95 points

La troisième version utilise Ceylon 1.2 pour le générateur et 509 octets de 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;}

Il descend à 35,22 points, mais je ne mettrai pas cela dans la ligne de titre car Celyon 1.2 n'a été publié que le 29 octobre. Je ne pense pas que je serais en mesure d'implémenter cet algorithme dans Ceylon 1.1 dans cette taille.). Plus de détails là-bas, je vais décrire ici la deuxième version. (La première version peut être vue dans l'histoire - elle ne supportait que les nombres positifs, mais elle tenait en 256 octets.)

Deuxième version

Maintenant, la deuxième version, qui prend en charge les entiers négatifs (et 0), et crée généralement une sortie un peu plus courte en utilisant en plus -. (Cette version utilise en fait la longueur autorisée, la première a essayé de rester sous 256 octets au lieu de 512.)

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 ""));
}

Le code a une longueur de 487, il y a donc encore de la place pour plus d'optimisations plus tard. (Il existe également de nombreuses réserves sous forme d'espaces et de noms de variables longs.)

Le score:

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

Quelques exemples de sorties:

   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

Comme vous pouvez le voir, les négatifs sont toujours d'un octet (le début -) plus longs que les positifs correspondants.

L'idée de base est la même que le programme précédent: trouver un carré près de notre nombre cible, et représenter sa racine et le reste de manière récursive. Mais maintenant, nous permettons à notre carré d'être également plus grand que le nombre cible, ce qui rend le reste négatif. (La +0.5peut être changée en une constante différente pour modifier l'algorithme, mais il semble que j'aie déjà atteint l'optimum ici - 0.4 et 0.6 donnent des résultats moins bons.)

Pour rendre les valeurs négatives négatives (et autrement avoir la même structure que les positives, nous passons l'opérateur signà notre fonction récursive p- c'est-à-dire soit "+"ou "-". Nous pouvons également l'utiliser pour le jointeur dans les cas triviaux (c'est-à-dire n <9)) comme pour le reste s'il est positif, et utilisez le signe opposé pour le reste s'il est négatif.

La prooffonction gère le signe initial (avec un cas spécial pour 0), la pfonction fait le travail réel, avec récursivité.

Troisième version, pour 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;
}

La version golfée (c'est-à-dire les commentaires et les espaces supprimés) est affichée en haut, avec exactement 509 octets de code.

Cela utilise le même principe de base que la deuxième version, mais au lieu de simplement des carrés, il essaie également d'utiliser des puissances de nombres plus élevées (en essayant des exposants de 2 à 8), et utilise le résultat le plus court. Il met également en cache les résultats, sinon cela serait trop lent pour de plus grands nombres avec de nombreux appels récursifs.

Notation:

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

La grande construction en retrait au milieu sont trois compréhensions itérables imbriquées, les deux intérieures à l'intérieur d'une expression let. Celles-ci sont ensuite non imbriquées à l'aide de la fonction d'expansion deux fois, et la reducefonction trouve la plus courte de ces chaînes.

J'ai déposé une demande de fonctionnalité pour pouvoir le faire en une seule compréhension.

À l'intérieur de la compréhension, nous construisons une chaîne à partir de la racine r, de l'exposant xet du reste ( n-wou w-n).

L' letexpression et la mapfonction sont nouvelles dans Ceylan 1.2. mapaurait pu être remplacé par HashMap(qui aurait eu besoin de plus de caractères pour l'importation, bien que ce serait probablement encore plus rapide, car je ne construirais pas la carte nouvelle pour chaque nouvelle entrée). Les letexpressions comme let (w = r ^ x)auraient pu être remplacées en utilisant une ifclause comme if(exists w = true then r ^ x)(et alors je n'aurais pas eu besoin des deux expandappels non plus), mais cela serait encore un peu plus long, ne cadrant pas dans les 511 octets autorisés.

Voici les exemples de sorties correspondant à ceux sélectionnés ci-dessus, tous sauf les très petits nombres sont plus courts:

   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

Par exemple, nous avons maintenant 1000 = (3 ^ 2 + 1) ^ 3, au lieu de 1000 = (6 ^ 2-4) ^ 2-5 ^ 2 + 1.

Ruby / dc, 20.296 18.414 16,968

Programmation dynamique! Définit une liste de fonctions qui, étant donné une instruction dc, renvoient une nouvelle expression et la valeur numérique de cette expression. Ensuite, en commençant par 1prédéfini, il construit une liste de toutes les valeurs accessibles jusqu'à et y compris la valeur souhaitée.

Éditer:

Ajout d'une fonction pour n-1 et l'a fait exécuter l'algorithme à travers plusieurs passes. Il semble avoir besoin de 7 passes pour se stabiliser. J'ai dû raccourcir certains noms de variables pour rester dans les 512 octets.

modifier 2:

Ajout de fonctions pour n (n-1) , n (n + 1) et n ^ 3 pendant que j'y étais. Raccourci un peu plus le code, atteignant exactement 512 octets.

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]

Numéros générés:

La sortie se compose entièrement de cinq caractères différents: 1pousse la valeur 1 sur la pile; dduplique le haut de la pile; +, -Et * saute les deux valeurs de début et pousse leur somme, la différence, et le produit, respectivement. Chaque expression générée ajoute une seule valeur à la pile après l'exécution.

   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 points

Soumettre ma réponse pour ce qu'elle vaut (pas beaucoup dans ce cas ... mais démontrer clairement que pour ce défi, il ne suffit pas de simplement penser à composer la sortie comme une somme de valeurs décalées en bits; si l'on prend en compte qu'aucun chiffre en dehors de 0 ou 1 peut apparaître dans la sortie). Je pourrais revenir plus tard avec une manière différente de générer de la sortie.

Le code lui-même n'est pas trop long (176 caractères):

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

Il génère une sortie correcte mais détaillée:

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)

Extrait qui calcule le score:

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