Задний план

В некоторых возможных видах будущего мир преобразует свои числовые системы из десятичной (основание 10 или b10) в некоторую другую базу (двоичную b2, восьмеричную b8, шестнадцатеричную b16или даже унарную b1, в этом случае мы облажались!). Таким образом, готовясь к этому возможному изменяющему мир событию, вы решаете проверить все свои программы. Это можно сделать, используя только сингулярные 0s и 1s в сочетании с операторами для замены существующих числовых констант.

Однако есть только одна проблема: вам нужно изменить массу программ, и ручное преобразование каждого числа в выражение займет недели! Таким образом, вы решаете написать программу (или функцию), чтобы решить, какое выражение должно заменить каждое число.

вход

На входе будет положительное целое число. Ваш код должен быть в состоянии обработать любое целое число до 1000.

(Если ваш код поддерживает десятичные дроби и / или отрицательные значения, см. Оценка ниже.)

Выход

Ваш код должен выводить выражение, которое оценивает ввод по крайней мере на одном языке. Это может быть любой язык; оно не обязательно должно быть тем же, в котором написана ваша программа или функция. Кроме того, это выражение не обязательно должно быть полной программой или функцией.

Для ясности вывод может содержать любую из следующих операций:

• увеличение / уменьшение
• добавить / сумма
• вычесть / отрицать
• умножить / удвоить (только если это не связано непосредственно с числом 2!)
• разделить / по модулю
• показатели / логарифмы
• квадрат / sqrt (опять же, только если они не связаны непосредственно с числом 2!)
• побитовые операции (bOR, bAND, bNOT, bXOR, битовые сдвиги)
• установка / получение переменных
• манипулирование стеком

Вы не можете использовать eval()или любые подобные функции в выводе. Вы также не можете использовать в выходных данных любые функции, которые выполняют действия, отличные от упомянутых выше.

Да, и еще одна вещь: так как мы хотим, чтобы вывод был действительным в максимально возможном количестве баз, единственные числовые константы, которые он может содержать, это 0и 1. Числа, такие как 10(десять), не допускаются, если только язык не интерпретирует их как a 1и a 0. Использование строк, содержащих числа, также недопустимо, как и использование символов, таких как CJam A- K(которые представляют 10- 20).

Тест-кейсы

(Все выходные данные в JavaScript, но могут работать на других языках.)

Вход 1:

2

Возможный вывод 1:

1+1

Вход 2:

13

Возможный вывод 2:

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

Вход 3:

60

Возможный вывод 3:

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

Вход 4:

777

Возможный вывод 4:

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

Вход 5:

1000

Возможный вывод 5:

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

счет

Цель этой задачи - максимально сократить вывод вашего кода. Ваша оценка будет рассчитана следующим образом:

• Базовая оценка: среднее число байтов всех выходных данных для целых чисел от 1 до 1000.

• Десятичная оценка: если ваш код поддерживает как минимум 3 десятичных знака, это среднее число байтов всех выходных данных последовательности чисел, начинающихся с 0.001и заканчивающихся на 1000, увеличивающихся с 1.001каждым разом. 0.001, 1.002, 2.003...998.999, 1000.000Тогда возьмите 50% от этой оценки.

• Отрицательная оценка: если ваш код поддерживает отрицательные числа и ноль, это среднее число байтов выходных данных всех целых чисел от -1000до 0. Тогда возьмите 10% от этой оценки.

(Самый простой способ рассчитать их - это цикл с вашей программой / функцией внутри.)

Ваша итоговая оценка является средним значением любой из приведенных выше формул.

Если выходные данные являются недетерминированными (т. Е. В некоторой степени случайными; многократные прогоны с одним и тем же входом дают несколько уникальных выходов), то оценка для каждого входа определяется по наибольшему результату за десять прогонов на моем ЦП.

Кроме того, поскольку вы не знаете, насколько ценными будут компьютерные данные в будущем, количество байт кода вашего генератора должно быть меньше 512 байт.

Самый низкий результат за две недели (30 сентября) будет объявлен победителем. Поздравляем вашего победителя, @ThomasKwa !

Leaderboard

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>

Чтобы убедиться, что ваш ответ отображается правильно, начните его с этого заголовка:

# Language name/Other language name, X points

Где Xоценка вашего ответа. Пример:

# CJam/Pyth, 25.38 points

Если у вас есть какие-либо вопросы или предложения, пожалуйста, дайте мне знать. Удачи!

Машинный код 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]

Бонусы: отрицательные числа.

Предполагается, что hlпара регистров изначально содержит 0 и возвращает результат в hl.

Используются только эти три инструкции:

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

Мы используем небольшую модификацию сбалансированного двоичного представления минимального веса BBR2 . Поскольку BBR2 минимизирует вес (количество ненулевых цифр), но мы хотим минимизировать вес плюс количество битовых сдвигов, мы меняем постоянную в алгоритме с 3/2на 5/3.

Чтобы вычислить счет и проверить, используйте этот код:

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

Пример вывода:

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

Или в сборке:

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

Еще примеры программ:

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

Возможные оптимизации: правила О.П. , что inc hи dec hинструкция, которые непосредственно изменяют верхние байты hl, является незаконной, но sla hи не имеющими документы sl1 h(левый бит сдвигает на 1 на hэтом сдвиг в 0и1 , соответственно) разрешены. sla hи sl1 hдва байта каждый, но иногда они могут сократить выход.

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=

Бонусы не применяются.

Попробуйте онлайн: пример прогона | счет калькулятор | проверка

Пример работает

   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 балла

ß источник (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)

Если кому-то будет интересно, я добавлю объяснение. Вывод BF уже довольно оптимизирован, но я думаю, что я мог бы использовать оставшиеся 318B кода ß для реализации

• оптимизация вложенных циклов,
• больше 8-битных ярлыков переполнения,
• удаление оператора .

Образцы:

Бег в окнах:

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

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

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

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

Запуск в Linux:

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

Подтвердите в онлайн-переводчике BF .

Счет:

1. База средняя = 37.495.
2. Десятичное среднее = 60.959 * 0.5 = ~30.48.
3. Отрицательный средний = 38.4765234765235 * 0.9 = ~34.629
4. Средняя из вышеперечисленных, итоговая оценка = (37.495 + 30.48 + 34.629)/3 = 34.201.

Рубин / Ruby, 29,77885

31,873 * 0,9 (отрицательно) 30,872 (положительно).

Базовая стратегия - симметричное базовое представление 3 («сбалансированная троичная»), т. Е. Когда цифры -1,0,1вместо0,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

Вот вывод от 0 до 40 до очистки

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

И после уборки

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

Цейлон / Цейлон, 49,86 40,95 балла

Третья версия использует Ceylon 1.2 для генератора и 509 байт кода:

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

Он опустился до 35,22 балла, но я не буду помещать это в строку заголовка, потому что Celyon 1.2 был опубликован только 29 октября. Я не думаю, что смогу реализовать этот алгоритм в Ceylon 1.1 в таком размере.). Более подробно там, здесь я опишу вторую версию. (Первую версию можно увидеть в истории - она ​​поддерживала только положительные числа, но вмещалась в 256 байтов.)

Вторая версия

Теперь вторая версия, которая поддерживает отрицательные целые числа (и 0) и, как правило, создает немного более короткий вывод, используя дополнительно -. (Эта версия на самом деле использует разрешенную длину, первая пыталась остаться в 256 байтах вместо 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 ""));
}

Код имеет длину 487, поэтому еще есть место для дальнейшей оптимизации. (Есть также много резервов в виде пробелов и длинных имен переменных.)

Подсчет очков:

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

Некоторые примеры выходов:

   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

Как видите, отрицательные всегда на один байт (ведущий -) длиннее соответствующих положительных.

Основная идея та же, что и в предыдущей программе: найти квадрат рядом с нашим целевым числом и рекурсивно представить его корень и остаток. Но теперь мы допускаем, что наш квадрат также будет немного больше целевого числа, что делает остаток отрицательным. ( +0.5Можно изменить на другую константу, чтобы настроить алгоритм, но, похоже, я уже достиг оптимального значения - и 0,4, и 0,6 дают худшие результаты.)

Чтобы сделать отрицательные значения отрицательными (и в противном случае иметь ту же структуру, что и положительные, мы передаем оператор signнашей рекурсивной функции p- то есть либо, "+"либо "-". Мы можем использовать это также для соединения в тривиальных случаях (т.е. n <9) что касается остатка, если он положительный, и используйте противоположный знак для остатка, если он отрицательный.

В proofфункции ручки начальный знак (с особым случаем для 0), то pфункция выполняет фактическую работу, с помощью рекурсии.

Третья версия, для Цейлона 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;
}

Версия для игры в гольф (то есть комментарии и удаленные пробелы) размещена сверху, ровно в 509 байтах кода.

При этом используется тот же базовый принцип, что и во второй версии, но вместо квадратов он также пытается использовать более высокие степени чисел (пробуя показатели от 2 до 8) и использует самый короткий результат. Он также кэширует результаты, так как в противном случае это было бы неприемлемо медленно для больших номеров со многими рекурсивными вызовами.

Подсчет очков:

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

Большая конструкция с отступом в середине - это три вложенных итерируемых понимания, внутренние два внутри выражения let. Затем они не передаются, используя функцию расширения дважды, и reduceфункция находит самую короткую из этих строк.

Я подал запрос на функцию, чтобы иметь возможность сделать это в одном понимании.

Внутри понимания мы строим строку из корня r, показателя степени xи остатка ( n-wили w-n).

letВыражение и mapфункции являются новыми в Цейлоне 1.2. mapможно было бы заменить на HashMap(для этого потребовалось бы больше символов для импорта, хотя, вероятно, это было бы еще быстрее, поскольку я не буду строить карту новой для каждой новой записи). Эти letвыражения , как let (w = r ^ x)могли бы быть заменены с помощью ifоговорки , как if(exists w = true then r ^ x)(и тогда я не нуждался бы в двух expandвызовов либо), но это все равно будет немного больше, не вписывается в 511 разрешенных байтов.

Вот пример выходных данных, соответствующих выбранным выше, все они, за исключением действительно небольших чисел, короче:

   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

Например, теперь у нас есть 1000 = (3 ^ 2 + 1) ^ 3 вместо 1000 = (6 ^ 2-4) ^ 2-5 ^ 2 + 1.

Рубин / постоянный ток, 20,296 18,414 16,968

Динамическое программирование! Определяет список функций, которые с учетом инструкции dc возвращают новое выражение и числовое значение этого выражения. Затем, начиная с 1предопределенного, он создает список всех достижимых значений вплоть до требуемого значения.

редактировать:

Добавил функцию для n-1 и заставил ее запускать алгоритм через несколько проходов. Кажется, нужно 7 проходов, чтобы стабилизироваться. Пришлось сократить некоторые имена переменных, чтобы они оставались в пределах 512 байт.

редактировать 2:

Добавлены функции для n (n-1) , n (n + 1) и n ^ 3, пока я был на этом. Еще немного укоротил код, высадив ровно 512 байт.

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]

Сгенерированные номера:

Вывод полностью состоит из пяти различных символов: 1помещает значение 1 в стек; dдублирует вершину стека; +, -и * выводит два верхних значения и выводит их сумму, разность и произведение соответственно. Каждое сгенерированное выражение добавляет только одно значение в стек после выполнения.

   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 балла

Отправляю мой ответ для того, что он стоит (не много в этом случае ... но ясно демонстрирует, что для этой задачи недостаточно просто думать о том, чтобы составить результат как сумму значений со сдвигом в битах; если принять во внимание, что нет цифр за пределами 0 или 1 может появиться на выходе). Я мог бы вернуться позже с другим способом генерации результатов.

Сам код не слишком длинный (176 символов):

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

Он генерирует правильный, но подробный вывод:

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)

Фрагмент, который вычисляет счет:

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