38
\$\begingroup\$

The Champernowne constant is a number that is constructed by concatenating the first n numbers, with n tending to infinity. It looks something like this:

0.123456789101112131415161718192021222324252627282930...

Now, I will describe to you the Rien number. It can be thought of as a minimization of the Champernowne constant as an integer. I will refer to the Rien number with the first n digits as Ri(n). This is how to formulate it:

  1. The first n natural numbers (the sequence {1,2,3,...}) are concatenated.
  2. This result is then sorted, according to the digit value. So 1..12 would look like 011111223456789.
  3. Since the Rien number cannot have leading zeroes, we move all 0s so that they are significant, whilst keeping the number minimized, resulting in, say, 101111223456789. This is Ri(n), in this case, Ri(12).

Here are some results for Ri(n):

n    Ri(n)
1    1
2    12
3    123
7    1234567
9    123456789
10   10123456789
15   101111111223344556789
34   10001111111111111222222222222223333333334444555666777888999
42   100001111111111111122222222222222233333333333333444444455556666777788889999
45   100001111111111111122222222222222233333333333333344444444444555556666777788889999
55   10000011111111111111122222222222222223333333333333333444444444444444455555555555566666777778888899999
100  100000000000111111111111111111112222222222222222222233333333333333333333444444444444444444445555555555555555555566666666666666666666777777777777777777778888888888888888888899999999999999999999
999  100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000011111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999

Objective Given a number 1 ≤ n < 10000 as input (via arguments, STDIN, or hardcoding if your language does not support conventional input), output/return Ri(n).

This is a , so the shortest code in bytes wins. You may use a language that was made after this contest, as long as it was not made for answering this challenge. (Of course, you can use it, if it provides an interesting solution, but mark your answer as non-competing.)

Reference implementation

I tested this in IE, so there really shouldn't be a problem. If there is a problem, there's an easy solution: get a sane browser.

function min(n) {
  var seq = [];
  for(var i = 1; i <= n; i++) seq.push(i);
  seq = seq.join("").split("").map(Number);
  var to;
  if(seq.indexOf(1) >= 0) to = seq.splice(seq.indexOf(1), 1);
  seq.sort(function(a, b) {
    return a - b;
  });
  if(to) seq = to.concat(seq);
  return seq.join("");
}
t.onchange = t.onkeyup = function() {
  h.innerHTML = min(this.value)
}
* {
  font-family: Consolas, monospace;
}
input {
  border: 2px dotted #aaaaaa;
  border-radius: 5px;
  margin: 10px;
}
<input id="t" type="number">
<div id="h">


Leaderboard

The Stack Snippet at the bottom of this post generates the catalog from the answers a) as a list of shortest solution per language and b) as an overall leaderboard.

To make sure that your answer shows up, please start your answer with a headline, using the following Markdown template:

## Language Name, N bytes

where N is the size of your submission. If you improve your score, you can keep old scores in the headline, by striking them through. For instance:

## Ruby, <s>104</s> <s>101</s> 96 bytes

If there you want to include multiple numbers in your header (e.g. because your score is the sum of two files or you want to list interpreter flag penalties separately), make sure that the actual score is the last number in the header:

## Perl, 43 + 2 (-p flag) = 45 bytes

You can also make the language name a link which will then show up in the snippet:

## [><>](http://esolangs.org/wiki/Fish), 121 bytes

var QUESTION_ID=68685,OVERRIDE_USER=44713;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>

\$\endgroup\$
  • 22
    \$\begingroup\$ I always thought 0 is the rien number. \$\endgroup\$ – flawr Jan 6 '16 at 19:36
  • \$\begingroup\$ Not sure if I'm missing something, but we can just move one of the 1s in front of the 0s, yeah? \$\endgroup\$ – FryAmTheEggman Jan 6 '16 at 19:40
  • \$\begingroup\$ @FryAmTheEggman You are correct. \$\endgroup\$ – Conor O'Brien Jan 6 '16 at 19:40
  • \$\begingroup\$ @MartinBüttner \o/ you found it. \$\endgroup\$ – Conor O'Brien Jan 6 '16 at 20:02
  • \$\begingroup\$ @CᴏɴᴏʀO'Bʀɪᴇɴ Nope that one was different. That one only allowed permutations of the entire numbers, not of their individual digits. \$\endgroup\$ – Martin Ender Jan 6 '16 at 20:05

37 Answers 37

1
\$\begingroup\$

Reng v.3.2, 36 bytes

1i#x:xe!Ø;$:1+)å(Eh
å'11µ1nran! ¡n~

Try it here!

This pushes 1 to the stack, then stores the input i into x (i#x). Then, a range of all the necessary numbers is created using :xe!Ø;$:1+)å(Eh, being ended by Ø, which goes the first i.e. next line. å takes every number and pushes the digits of that number.

On the next line, å breaks the last number into its digits, ' sorts the stack, and 11µ removes 1 1 from the stack. A 1 is then printed, and the numbers are reversed then outputted through the loop an! ¡n. The program is terminated with ~.

\$\endgroup\$
  • \$\begingroup\$ Maybe you could add an explanation about this? \$\endgroup\$ – Hannes Karppila Apr 3 '16 at 23:26
  • \$\begingroup\$ @HannesKarppila I have added an explanation. \$\endgroup\$ – Conor O'Brien Apr 3 '16 at 23:31
1
\$\begingroup\$

Seriously, 10 bytes

,Rp@εjS@$+

Try it online!

Explanation:

,Rp@εjS@$+
,Rp@        push range(1, input()+1), pop first element (1), swap
    εjS     join list on empty string, sort
       @$+  prepend the 1
\$\endgroup\$
1
\$\begingroup\$

Pyke, 9 bytes, noncompetitive

Stm`sS1R+

Explanation:

S         -      range(1,inp+1)
 t        -     ^[1:]
  m`      -    map(str,^)
    s     -   sum(^)
     S    -  sort(^)
      1R+ - 1+^

Try it here!

\$\endgroup\$
1
\$\begingroup\$

Stacked, 22 bytes

2\|>''join sorted'1'\+

Try it here! Expects input on TOS. Example on the repl:

> 15
(15)
> 2\|>''join sorted'1'\+
('101111111223344556789')

Explanation

2\|>''join sorted'1'\+
2\|>                    range from 2 to n
    ''join              join by empty string
           sorted       sort it
                 '1'\+  and prepend a '1'

A more fun version:

Stacked, 45 bytes

{*x:1[1+:yield]x 1-*}!toarr''join sorted'1'\+

Expects input as TOS. For example (on the repl):

> 15    (* the input *)
(15)
> {*x:1[1+:yield]x 1-*}!toarr''join sorted'1'\+
('101111111223344556789')
> 

Explanation

{*x:1[1+:yield]x 1-*}!toarr''join sorted'1'\+
{*x:1[1+:yield]x 1-*}                            generator function that...
  x:                                               given x
    1                                              pushes 1
     [        ]x 1-*                               and executes the inside (x-1) times:
      1+                                             adds 1 to the TOS (initially 1);
                                                     2 is the first value yielded
        :yield                                       and yields it for the generator
                     !                           initialize this generator with TOS
                      toarr                      exhaust generator into an array
                           ''join                join by empty strings
                                  sorted         sort the values
                                        '1'\+    prepend '1'.
\$\endgroup\$
0
\$\begingroup\$

Lua, 102 Bytes

How can lua be so long while all other entries are < 30 bytes... I'm sure even Java would be shorter!

t={}for i=2,...do(i..''):gsub(".",function(d)t[#t+1]=d end)end
table.sort(t)print(1 ..table.concat(t))

Ungolfed

t={}                           -- initialise t as a table
for i=2,...                    -- iterate from 2 to n
do
  (i..''):gsub(".",function(d) -- iterate over each digits in i
    t[#t+1]=d                  -- insert the digit into t
  end)
end
table.sort(t)                 -- sort t
print(1 ..table.concat(t))    -- prepend a 1 to the content of t separated by ''

I'm forced to put a space in print(1 .., else it would try to evaluate it to a decimal 1.<decimal part>, and throws an error because . isn't a valid decimal part.

\$\endgroup\$
0
\$\begingroup\$

Attache, 20 bytes

{"1"+Sort!Join[2:_]}

Try it online!

The point-free version is actually 1 byte longer: "1"&`+@Sort@Join@2&`:. This works as most of the other answers do.

\$\endgroup\$
0
\$\begingroup\$

C (gcc), 172 161 bytes

f(n){char s[++n];int d[10]={0},j=1,k;for(;sprintf(s,"%d",j),j++<n;)for(k=0;s[k];)d[s[k++]-48]++;d[printf("1")]--;for(j=0;j<10;j++)for(k=d[j];k--;putchar(j+48));}

Try it online!

\$\endgroup\$
  • \$\begingroup\$ @ceilingcat thanks. \$\endgroup\$ – Jonathan Frech Jun 21 '18 at 1:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.