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 – 2016-09-16T08:51:46.477
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 – 2016-09-16T08:57:14.493
@xnor If any given integer gets printed after a finite amount of time, it's fine. – Fatalize – 2016-09-16T09:04:51.413
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 – 2016-09-16T09:07:28.307
1@xnor The only constraint is that any integer must be printed after a finite amount of time. – Fatalize – 2016-09-16T09:10:16.023
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 – 2016-09-16T09:10:53.297
3@xnor Changed, though that kinds of ruins the very name of the challenge. – Fatalize – 2016-09-16T09:14:23.230
@Fatalize Is unary output allowed too? – flawr – 2016-09-16T09:25:44.287
@flawr No, unless your language only supports that. – Fatalize – 2016-09-16T09:28:20.380
If the default data type is
double
floating point can we use that? That will work for integers up to2^53
– Luis Mendo – 2016-09-16T09:40:20.773@LuisMendo Yes if the decimal part is always the same (
.0
I assume). – Fatalize – 2016-09-16T09:41:29.5406@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 – 2016-09-16T09:54:12.783
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 – 2016-09-16T09:58:07.363
@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 – 2016-09-16T11:02:27.3932Do you accept
-0
as a valid representation of0
? (Provided there is no other0
or+0
in the output.) – Martin Ender – 2016-09-16T11:49:55.110@MartinEnder Yes. – Fatalize – 2016-09-16T11:51:03.753
Last bullet point clearly contradicts the first sentence. – MatthewRock – 2016-09-16T14:00:24.960
1Doesn't the program need to terminate once it's printed all of the integers to be correct? – cleblanc – 2016-09-16T14:14:08.573
@cleblanc - presumably, unless you have arbitrary sized integers in your language. – Periata Breatta – 2016-09-16T16:40:06.750
Second-to-last bullet point: Is there supposed to be a space or two around the first
,
? – Joe – 2016-09-17T04:08:28.827@Joe Yes, fixed. For some reason copying unbreakable spaces from the sandbox to here transformed it to a normal space. – Fatalize – 2016-09-17T08:02:43.917
How can we do it "provably"? – Buffer Over Read – 2016-09-18T00:21:24.870
@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 – 2016-09-18T07:08:56.070
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 – 2016-09-19T17:26:55.233