52
5
Write a program or function which will provably print all integers exactly once given infinite time and memory.
Possible outputs could be:
0, 1, -1, 2, -2, 3, -3, 4, -4, …
0, 1, 2, 3, 4, 5, 6, 7, 8, 9, -1, -2, -3, -4, -5, -6, -7, -8, -9, 10, 11, …
This is not a valid output, as this would never enumerate negative numbers:
0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, …
The output must be in decimal, unless your language does not support decimal integer (in that case use the natural representation of integers your language uses).
Your program has to work up to the numbers with the biggest magnitude of the standard integer type of your language.
Each integer must be separated from the next using any separator (a space, a comma, a linebreak, etc.) that is not a digit nor the negative sign of your language.
The separator must not change at any point.
The separator can consist of multiple characters, as long as none of them is a digit nor the negative sign (e.g.
,
is as valid as just,
).Any supported integer must eventually be printed after a finite amount of time.
Scoring
This is code-golf, so the shortest answer in bytes wins
Leaderboard
var QUESTION_ID=93441,OVERRIDE_USER=41723;function answersUrl(e){return"https://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"https://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[2],language:a[1],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).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.language,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){return e.lang>s.lang?1:e.lang<s.lang?-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).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,]),.*?(\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>Language</td><td>Size</td></tr></thead> <tbody id="answers"> </tbody> </table> </div><div id="language-list"> <h2>Winners by 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>
Related, related, related. – Fatalize – 8 years ago
4If our language supports infinite lists, can we output the list from a function rather than printing? (Calling print on such a list would print its elements one at a time forever.) – xnor – 8 years ago
@xnor If any given integer gets printed after a finite amount of time, it's fine. – Fatalize – 8 years ago
1May we give an expression that evaluates to an infinite list? I realized that in Haskell, a function that takes no inputs look just like an expression. – xnor – 8 years ago
1@xnor The only constraint is that any integer must be printed after a finite amount of time. – Fatalize – 8 years ago
6I feel like the requirement on arbitrary-size integers does nothing but discourage languages without such integers from participating. They either have to have an import they can use or solve a totally different challenge from everyone else. – xnor – 8 years ago
3@xnor Changed, though that kinds of ruins the very name of the challenge. – Fatalize – 8 years ago
@Fatalize Is unary output allowed too? – flawr – 8 years ago
@flawr No, unless your language only supports that. – Fatalize – 8 years ago
If the default data type is
double
floating point can we use that? That will work for integers up to2^53
– Luis Mendo – 8 years ago@LuisMendo Yes if the decimal part is always the same (
.0
I assume). – Fatalize – 8 years ago6@xnor, languages with arbitrary precision integers still have to solve a different problem from everyone else, so all that that change has accomplished is to make this problem boringly trivial in a lot of languages. – Peter Taylor – 8 years ago
3@PeterTaylor Yeah, this is unfortunate. The wrapping solutions don't feel to me like they are printing any negatives, but I don't see a way to firmly specify the difference when it's a matter of representation. – xnor – 8 years ago
@flawr and Fatalize: In sed you have no integer type, so an unary string is the most natural format. I already gave an answer in sed, but that is ~200 bytes, because I emulate the increment of integers. If I want to use unary, how should I represent negative numbers? Like -000 for -3?
– seshoumara – 8 years ago2Do you accept
-0
as a valid representation of0
? (Provided there is no other0
or+0
in the output.) – Martin Ender – 8 years ago@MartinEnder Yes. – Fatalize – 8 years ago
Last bullet point clearly contradicts the first sentence. – MatthewRock – 8 years ago
1Doesn't the program need to terminate once it's printed all of the integers to be correct? – cleblanc – 8 years ago
@cleblanc - presumably, unless you have arbitrary sized integers in your language. – Periata Breatta – 8 years ago
Second-to-last bullet point: Is there supposed to be a space or two around the first
,
? – Joe – 8 years ago@Joe Yes, fixed. For some reason copying unbreakable spaces from the sandbox to here transformed it to a normal space. – Fatalize – 8 years ago
How can we do it "provably"? – Buffer Over Read – 8 years ago
@seshoumara I guess that would be acceptable, though I don't see why you would use a language with no integers for such a challenge. – Fatalize – 8 years ago
2The arbitrarily long integers is not a big delimiter. Languages without them can still golf decently using string arrays (instead of integer arithmetic). See my ~300 byte C answer for example. – LambdaBeta – 8 years ago