46
\$\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\$
10
  • 26
    \$\begingroup\$ I always thought 0 is the rien number. \$\endgroup\$
    – flawr
    Jan 6, 2016 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\$ Jan 6, 2016 at 19:40
  • \$\begingroup\$ @FryAmTheEggman You are correct. \$\endgroup\$ Jan 6, 2016 at 19:40
  • \$\begingroup\$ @MartinBüttner \o/ you found it. \$\endgroup\$ Jan 6, 2016 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\$ Jan 6, 2016 at 20:05

50 Answers 50

1
2
2
\$\begingroup\$

Python 2, 60 bytes

P=input();print"1"+"".join(sorted(`range(2,P+1)`)[P*2-4:-2])

Indexing for the win. :-)


Python 2, 60 bytes

P=input();print"1"+"".join(sorted(`range(-P,-1)`))[P*3-5:-2]

Just an alternative.

\$\endgroup\$
2
\$\begingroup\$

Seriously, 10 bytes

,u2xεjS'1+

Hex Dump:

2c753278ee6a5327312b

Try It Online

Explanation:

,            Read input
 u2x         Push range from 2..n
    εj       Join into string
      S      Sort
       '1+   Prepend a "1"
\$\endgroup\$
2
\$\begingroup\$

05AB1E, 6 bytes

Note: This submission uses features that postdate this challenge and is therefore not competitive

Code:

Lß?J{?

Explanation:

L      # Creates the list [1 .. input]
 ß     # Extract the smallest value of the list
  ?    # Print this value (always 1)
   J   # ''.join(list)
    {  # Sort the string
     ? # Print this value

Uses ISO 8859-1 encoding

\$\endgroup\$
3
  • \$\begingroup\$ How does this work? \$\endgroup\$
    – lirtosiast
    Jan 21, 2016 at 20:43
  • \$\begingroup\$ @ThomasKwa Explanation added \$\endgroup\$
    – Adnan
    Jan 21, 2016 at 20:44
  • \$\begingroup\$ Whoa. This is fantastic! \$\endgroup\$ Jan 21, 2016 at 20:59
2
\$\begingroup\$

Mathcad, 86 "bytes"

The function s(n) uses a for loop to build up the Champernowne "integer" by converting each number to its string form and concatenating them together. The string is then converted to its equivalent vector of ASCII codes and sorted. The function then swaps any leading zeros with the first one, finally converting the vector back to a string.

To check the function, I put the test cases into a vector vn, then applied s to vn using the vectorize operator. I then check the results against the given test case values.

enter image description here


Mathcad is mathematical application based on 2D worksheets comprised of "regions" each of which can be text, a mathematical expression, program, plot or scripted component.

A mathematical or programming instruction is picked from a palette toolbar or entered using a keyboard shortcut. For golfing purposes, an operation ("byte") is taken to be the number of keyboard operations necessary to create a name or expression (for example, to set the variable a to 3, we would write a:=3. The definition operator := is a single keypress ":", as are a and 3 giving a total of 3 "bytes". The programming for operator requires typing ctl-shft-# (or a single click on the programming toolbar) so again is equivalent to 1 byte.

\$\endgroup\$
2
\$\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\$
2
  • \$\begingroup\$ Maybe you could add an explanation about this? \$\endgroup\$ Apr 3, 2016 at 23:26
  • \$\begingroup\$ @HannesKarppila I have added an explanation. \$\endgroup\$ Apr 3, 2016 at 23:31
2
\$\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\$
2
\$\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\$
2
\$\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\$
2
\$\begingroup\$

Japt, 8 bytes

ô ¤¬ñ i1

Try it

ô ¤¬ñ i1     :Implicit input of integer
ô            :Range [0,input]
  ¤          :Slice off the first 2 elements
   ¬         :Join
    ñ        :Sort
      i1     :Prepend 1
\$\endgroup\$
2
\$\begingroup\$

C (gcc), 172 161 158 156 bytes

  • Saved eleven fourteen sixteen bytes thanks to ceilingcat.
f(n){char*z,s[++n];int d[10]={0},j=1,k=0;for(;sprintf(s,"%d",j),j++<n;)for(z=s;*z;)d[*z++-48]++;for(d[printf("1")]--;k<10;)for(j=d[k++];j--;putchar(k+47));}

Try it online!

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

Thunno 2 O, 5 bytes

RḢ¢JṠ

Try it online!

Explanation

RḢ¢JṠ  # Implicit input
R      # Push the range [1..input]
 Ḣ     # Extract first item (1)
  ¢    # Print without newline
   J   # Join the list
    Ṡ  # Sort the resulting string
       # Implicit output
\$\endgroup\$
1
\$\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\$
1
\$\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\$
1
\$\begingroup\$

Husk, 8 bytes

:'1Oṁs…2

Try it online!

Corrected my previous answer.

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

Java (JDK), 153 151 bytes

i->{var s="";for(int j=0;j++<i;)s+=j;var c=s.toCharArray();java.util.Arrays.sort(c);return new String(c).replaceFirst("1","0").replaceFirst("^.","1");}

Try it online!

-2 Thanks to Ceilingcat!

\$\endgroup\$
2
  • \$\begingroup\$ Oh right, I always use that but then realize that it doesn't work (as it increments before the first iteration) though here I can abuse that fact. \$\endgroup\$
    – 0xff
    Oct 21, 2021 at 6:38
  • \$\begingroup\$ Suggest getBytes() instead of toCharArray() \$\endgroup\$
    – ceilingcat
    Jan 16, 2023 at 15:39
1
\$\begingroup\$

Ly, 19 bytes

n[sSl,]ppar1y[fu,]p

Try it online!

n                    - read count of numbers to use from STDIN
 [s l,]              - loop that many times, using backup cell to save loop var
   S                 - push digits of "int" at the top of the stack
       pp            - drop "0" and "1" from the stack
         ar          - sort digits, reverse stack
           1         - push "1" onto the stack
            y        - push the stack size onto the stack
             [  ,]   - loop over over stack, use backup cell for loop var
              fu     - flip loop var and digit, print digit
                  p  - delete loop var
\$\endgroup\$
1
\$\begingroup\$

R, 60 bytes

a=\(n)cat(1,sort(unlist(strsplit(c("",1:n)[-2],""))),sep="")
\$\endgroup\$
1
\$\begingroup\$

Raku, 46 bytes

{{S/(0*)(.)/$1$0/}([~] ([~] 1..$_).comb.sort)}

Try it online!

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

PowerShell Core, 44 bytes

"1"+-join(1.."$args"-ne1|%{"$_"|% t*y}|sort)

Try it online!

"1"+-join(1.."$args"-ne1|%{"$_"|% t*y}|sort)­⁡​‎‎⁡⁠⁡‏⁠‎⁡⁠⁢‏⁠‎⁡⁠⁣‏⁠‎⁡⁠⁤‏‏​⁡⁠⁡‌⁢​‎⁠‎⁡⁠⁣⁣‏⁠‎⁡⁠⁣⁤‏⁠‎⁡⁠⁤⁡‏⁠‎⁡⁠⁤⁢‏⁠‎⁡⁠⁤⁣‏⁠‎⁡⁠⁤⁤‏⁠‎⁡⁠⁢⁡⁡‏⁠‎⁡⁠⁢⁡⁢‏⁠‎⁡⁠⁢⁡⁣‏⁠‎⁡⁠⁢⁡⁤‏⁠‎⁡⁠⁢⁢⁡‏⁠‎⁡⁠⁢⁢⁢‏⁠‎⁡⁠⁢⁢⁣‏⁠‎⁡⁠⁢⁢⁤‏⁠‎⁡⁠⁢⁣⁡‏⁠‎⁡⁠⁢⁣⁢‏⁠‎⁡⁠⁢⁣⁣‏⁠‎⁡⁠⁢⁣⁤‏⁠‎⁡⁠⁢⁤⁡‏⁠‎⁡⁠⁢⁤⁢‏⁠‎⁡⁠⁢⁤⁣‏⁠‎⁡⁠⁢⁤⁤‏⁠‎⁡⁠⁣⁡⁡‏⁠‎⁡⁠⁣⁡⁢‏⁠‎⁡⁠⁣⁡⁣‏⁠‎⁡⁠⁣⁡⁤‏⁠‎⁡⁠⁣⁢⁡‏⁠‎⁡⁠⁣⁢⁢‏⁠‎⁡⁠⁣⁢⁣‏⁠‎⁡⁠⁣⁢⁤‏⁠‎⁡⁠⁣⁣⁡‏⁠‎⁡⁠⁣⁣⁢‏⁠‎⁡⁠⁣⁣⁣‏‏​⁡⁠⁡‌⁣​‎‎⁡⁠⁢⁡‏⁠‎⁡⁠⁢⁢‏⁠‎⁡⁠⁢⁣‏⁠‎⁡⁠⁢⁤‏⁠‎⁡⁠⁣⁡‏⁠‎⁡⁠⁣⁢‏⁠‎⁡⁠⁣⁣⁤‏‏​⁡⁠⁡‌­
"1"+                                          # ‎⁡‎⁢Always return a 1
          1.."$args"-ne1|%{"$_"|% t*y}|sort   # ‎⁢‎⁣Generate a range from 2 to the $a, convert to characters, sort them
    -join(                                 )  # ‎⁣Join them into a string
💎

Created with the help of Luminespire.

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

Ruby, 73 bytes

n,s=gets.to_i,"";(2..n).each{|i|s+=i.to_s};p ("1"+s.chars.sort.join).to_i

Attempt This Online!

\$\endgroup\$
1
2

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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