21
Background
In some possible futures, the world will convert their numerical systems from decimal (base 10 or b10
) to some other base (binary b2
, octal b8
, hexadecimal b16
, or even unary b1
, in which case we're screwed!). Thus, in preparation for this possible world-changing event, you decide to base-proof all of your programs. This can be done by using only singular 0
s and 1
s in conjunction with operators to replace the existing number constants.
However, there's just one problem: You have a ton of programs to change, and manually converting each number to an expression would take weeks! Thus, you decide to write a program (or function) to decide for you what expression should replace each number.
Input
The input will be a positive integer. Your code must be able to handle any integer up to 1000.
(If your code supports decimals and/or negative inputs, see Scoring below.)
Output
Your code must output an expression that evaluates to the input in at least one language. This may be any language; it does not have to be the same one your program or function is written in. Also, this expression does not need to be a full program or function.
For clarity, the output may contain any of these operations:
- increment / decrement
- add / sum
- subtract / negate
- multiply / double (only if it doesn't directly involve the number
2
!) - divide / modulo
- exponents / logarithms
- square / sqrt (again, only if these don't directly involve the number
2
!) - bitwise operations (bOR, bAND, bNOT, bXOR, bit-shifts)
- setting / getting variables
- stack manipulation
You may not use eval()
or any similar functions in the output. You may also not use in the output any functions that perform an action(s) other than the ones mentioned above.
Oh, and one more thing: since we want the output to be valid in as many bases as possible, the only number constants it may contain are 0
and 1
. Numbers such as 10
(ten) are disallowed, unless the language interprets it as a 1
and a 0
. Using strings to contain numbers is not allowed either, as is using characters such as CJam's A
-K
(which represent 10
-20
).
Test-cases
(All outputs are in JavaScript, but may work in other languages.)
Input 1:
2
Possible output 1:
1+1
Input 2:
13
Possible output 2:
(a=1+1+1)*a+a+1
Input 3:
60
Possible output 3:
(b=(a=1+1+1+1)*a)*a-a
Input 4:
777
Possible output 4:
(c=(b=((a=1+1+1+1)*a-a+1)*a)*a+b)+c+c-a+1
Input 5:
1000
Possible output 5:
Math.pow((a=1+1+1)*a+1,a)
Scoring
The goal of this challenge is to shorten your code's output as much as possible. Your score will be calculated in this way:
Base score: The average byte-count of all outputs for integers 1 to 1000.
Decimal score: If your code supports at least 3 decimal places, this is the average byte-count of all outputs of the sequence of numbers starting at
0.001
and ending at1000
, increasing by1.001
each time.0.001, 1.002, 2.003...998.999, 1000.000
Then take 50% off of this score.Negative score: If your code supports negative numbers and zero, this is the average byte-count of the outputs of all integers from
-1000
to0
. Then take 10% off of this score.
(The easiest way to calculate these would likely be a loop with your program/function inside.)
Your final score is the average of whichever of the above formulas apply.
If the output is non-deterministic (i.e. somewhat random; multiple runs with the same input produces multiple unique outputs), then the score for each input is determined by the largest output over ten runs on my CPU.
Also, as you don't know how precious computer data will be in the future, the byte-count of your generator code must be less than 512 bytes.
Lowest score in two weeks (on Sep 30) will be declared the winner. Congratulations to your winner, @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>
To make sure your answer shows up correctly, please start it with this header:
# Language name/Other language name, X points
Where X
is the score of your answer. Example:
# CJam/Pyth, 25.38 points
If you have any questions or suggestions, please let me know. Good luck!
Can I use variables that hold
0
or1
by default? – Dennis – 2015-09-16T16:05:24.083@Dennis I don't see any problem with that, so go ahead! – ETHproductions – 2015-09-16T16:07:57.727
I'm assuming I can't do base conversion between base 2 and the default base. – Blue – 2015-09-16T17:05:06.170
@muddyfish Nope, no base conversion allowed in the output. – ETHproductions – 2015-09-16T17:07:57.490
I guess we also are not allowed to use something like
Integer.parseInt("1000", 1+1+1+1+1+1+1+1+1+1)
? I'm pretty sureparseInt
uses only the allowed operations ;-) – Paŭlo Ebermann – 2015-09-16T20:19:36.027@PaŭloEbermann No, that would go against this rule, or at least the main intention of it: "Numbers such as
10
(ten) are disallowed, unless the language interprets it as a1
and a0
." I'll edit to make this more clear. – ETHproductions – 2015-09-16T20:21:14.560Are the constants allowed to contain loops? For example Beam
'''>\
++++++++)` = 24 – MickyT – 2015-09-16T20:33:25.300@MickyT Loops are OK, at least in that case, as Beam does not have built-in multiplication. – ETHproductions – 2015-09-16T20:37:54.033
@ETHproductions Is the 512B limit for the generating or the generated code? – mınxomaτ – 2015-09-16T21:25:40.613
@minxomat For the generating. – ETHproductions – 2015-09-16T21:26:03.753
@ETHproductions The negative score uses one step more than the base score
({-1000..0} > {1..1000})
. Intended? – mınxomaτ – 2015-09-16T21:36:28.873@minxomat Yes, this is to score the
0
case. Although now that I think about it, it may be better to include0
in the base score instead. (Also, I keep reading your username as min-mix-o-mat. ;) ) – ETHproductions – 2015-09-16T21:51:09.960Are bit shift operations on
h
also illegal? – lirtosiast – 2015-09-17T19:45:30.460@ThomasKwa Bit-shifts are OK, as long as a) it's only a shift by 1 bit (also known as doubling/halving), or b) the number of bits it is shifted by is calculated the same way as regular numbers. – ETHproductions – 2015-09-17T20:07:01.177
The z80's "shift left logical" instruction shifts a
1
into bit 0. – lirtosiast – 2015-09-17T20:11:18.050@ThomasKwa Thanks for the info. I believe that's still alright; it's not too much different from the default behavior. – ETHproductions – 2015-09-17T20:22:04.753
Which of these single instructions are legal (provided they do not contain literals other than
0
and1
: Pyth'sy
(double), a hypothetical left trit-shift by 1 on a ternary computer, a left bit shift by 2 implemented by adding a number to itself twice, square (implemented by multiplying a number by itself), cube, square root, cube root, "push a number of 1s given by the number on top of the stack", sum of all numbers from 1 to n, sum of all numbers on the stack, increment twice, addhl
to the stack pointer? – lirtosiast – 2015-09-19T15:43:44.847@ThomasKwa Doubling is fine; you're already using that in your answer (
) add hl, hl
). I'm gonna say squares, square and cube roots, sum entire stack, and "push a number of 1s given by the number on top of the stack" are fine as well. I'm not sure what you mean by "addhl
to the stack pointer"; it would be great if you could elaborate. None of the others are allowed, including "a hypothetical left trit-shift by 1 on a ternary computer", which is exactly the same as tripling. – ETHproductions – 2015-09-20T17:21:24.197The z80 has a stack pointer
sp
; when a register pair is pushed it decrements twice to point to the top of the stack, and when a register pair is popped it increments twice. I was thinking of usingpush de
andadd hl,sp
to subtract 3 from hl. – lirtosiast – 2015-09-20T18:50:37.563@ThomasKwa Alright, I guess that's OK. IMHO, it's actually a pretty clever solution to subtract 3 in 2 bytes. May I ask what
push de
is referring to? – ETHproductions – 2015-09-21T02:12:52.983push de
pushes the register pairde
onto the stack. – lirtosiast – 2015-09-21T03:50:17.507@ThomasKwa Well yeah, I guess I figured that. I should learn more about z80 machine code. Also, congratulations on your win! :) – ETHproductions – 2015-09-30T12:55:45.220