68
\$\begingroup\$

Randall Munroe's book "xkcd, volume 0" uses a rather odd number system for the page numbers. The first few page numbers are

1, 2, 10, 11, 12, 20, 100, 101, 102, 110, 111, 112, 120, 200, 1000, 1001, ...

This looks a bit like ternary, but notice that he skips from 20 straight to 100, from 120 to 200 and from 200 to 1000. One way to define this sequence is to say that it enumerates all ternary numbers that contain at most one 2 and no 1 after that 2. You can find this on OEIS in entry A169683. This number system is known as skew binary.

Your task is to find the representation of a given positive integer N in this number system.

You may write a program or function, taking input via STDIN (or closest alternative), command-line argument or function argument and outputting the result via STDOUT (or closest alternative), function return value or function (out) parameter.

Output may be a string, a number with a decimal representation equal to the skew binary representation, or a list of digits (as integers or characters/strings). You must not return leading zeroes.

This is code golf, so the shortest answer (in bytes) wins.

Fun fact: There is actually some merit to this number system. When incrementing a number, you will always change at most two adjacent digits - you'll never have to carry the change through the entire number. With the right representation that allows incrementing in O(1).

Test Cases

1 => 1
2 => 2
3 => 10
6 => 20
7 => 100
50 => 11011
100 => 110020
200 => 1100110
1000 => 111110120
10000 => 1001110001012
100000 => 1100001101010020
1000000 => 1111010000100100100
1048576 => 10000000000000000001

1000000000000000000 => 11011110000010110110101100111010011101100100000000000001102

I will give a bounty to the shortest answer which can solve the last test case (and any other input of similar magnitude, so don't think about hardcoding it) in less than a second.

Leaderboards

Here is a Stack Snippet to generate both a regular leaderboard and an overview of winners by language.

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

<script>site = 'meta.codegolf'; postID = 5314; isAnswer = true; QUESTION_ID = 51517</script><script src='https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js'></script><script>jQuery(function(){var u='https://api.stackexchange.com/2.2/';if(isAnswer)u+='answers/'+postID+'?order=asc&sort=creation&site='+site+'&filter=!GeEyUcJFJeRCD';else u+='questions/'+postID+'?order=asc&sort=creation&site='+site+'&filter=!GeEyUcJFJO6t)';jQuery.get(u,function(b){function d(s){return jQuery('<textarea>').html(s).text()};function r(l){return new RegExp('<pre class="snippet-code-'+l+'\\b[^>]*><code>([\\s\\S]*?)</code></pre>')};b=b.items[0].body;var j=r('js').exec(b),c=r('css').exec(b),h=r('html').exec(b);if(c!==null)jQuery('head').append(jQuery('<style>').text(d(c[1])));if (h!==null)jQuery('body').append(d(h[1]));if(j!==null)jQuery('body').append(jQuery('<script>').text(d(j[1])))})})</script>

\$\endgroup\$
8
  • 34
    \$\begingroup\$ I've had that book since it first came out and never noticed the page numbering. \$\endgroup\$
    – Alex A.
    Jun 10, 2015 at 14:57
  • 2
    \$\begingroup\$ @AlexA. I have it on my Kindle where you can't do any interesting page numbering. \$\endgroup\$ Jun 11, 2015 at 17:48
  • 21
    \$\begingroup\$ @LegionMammal978: Tragic. \$\endgroup\$
    – Alex A.
    Jun 11, 2015 at 17:49
  • 1
    \$\begingroup\$ @SuperJedi224 Consensus seems to be no, so sorry (I'd make an exception from consensus if that was the only sort of input your language could handle, but that doesn't seem to be the case). \$\endgroup\$ Jun 16, 2015 at 21:33
  • 4
    \$\begingroup\$ This reminds me of how I used to count when I was 3. I reasoned: "there's no fifty-ten, so after one-hundred-nine must be two-hundred." I only realized my mistake upon seeing the difference between 59->60 and 109->110, with the extra 0. \$\endgroup\$
    – Cyoce
    Dec 17, 2015 at 5:58

27 Answers 27

33
+100
\$\begingroup\$

CJam, 24 23 22 21 19 bytes

ri_)2b,,W%{2\#(md}/

This is an O(log n) approach, where n is the input, that completes the last test case instantly. It converts n directly to skew binary, using modular division by the values of the digit 1.

This code finishes with an error that goes to STDERR with the Java interpreter, which is allowed according to the consensus on Meta.

If you try this code in the CJam interpreter, just ignore everything but the last line of output.

The error can be eliminated, at the cost of 2 bytes, by prepending 2> to W%.

Thanks to @MartinBüttner for golfing off one byte.

Background

The skew binary representation ak...a0 corresponds to the integer n = (2k+1-1)ak+...+(21-1)a0.

Since both (2k-1) + ... + (21-1) = 2k+1 - (k + 2) and (2k-1) + ... + 2(2j-1) = 2k+1 - (2j+1 - 2j + k + 1) are less than 2k+1-1, the values of ak to a0 can be recovered by successive modular division by 2k+1-1, 2k-1, etc.

To begin, we have to find the value of 2k+1-1 first. Since n is at most 2(2k+1-1), the integer n + 1 must be strictly smaller than 2k+2.

Thus, taking the integer part of the binary logarithm of n + 1 yields k + 1.

Finally, we observe that the integer n + 1 has ⌊log2(n + 1)⌋ digits in base 2.

How it works

ri    e# Read an integer N from STDIN.
2b,   e# Push the number of binary digits of N + 1, i.e, K + 2 = log(N + 1) + 1.
,W%   e# Push the range [K+1 ... 0].
{     e# For each J in the range:
  2\# e#   J -> 2**J
  (   e#     -> 2**J - 1
  md  e#   Perform modular division of the integer on the stack (initially N)
      e#   by 2**J - 1: N, 2**J - 1 -> N/(2**J - 1), N%(2**J - 1)
}/    e#

In the last two iterations, we perform modular division by 1 and 0. The first pushes an unwanted 0 on the stack. The last attempts to execute 0 0 md, which pops both unwanted 0s from the stack, exits immediately instead of pushing anything and dumps the stack to STDOUT.

\$\endgroup\$
28
\$\begingroup\$

Python 2, 67 bytes

def f(n):x=len(bin(n+1))-3;y=2**x-1;return n and n/y*10**~-x+f(n%y)

Seems to work for the given test cases. If I've got this right, this should be about O(place values set in output), so it does the last case with ease.

Call like f(100). Returns a decimal representation equal to the skew binary.

Python 3, 65 bytes

def g(n,x=1):*a,b=n>x*2and g(n,x-~x)or[n];return a+[b//x,b%x][:x]

Slightly less efficient but still logarithmic, so the last case is near-instant.

Call like g(100). Returns a list of digits.

\$\endgroup\$
3
  • \$\begingroup\$ does 2and compile in 3? I'm in 2 and 2and2 throws a syntax error \$\endgroup\$ Jun 12, 2015 at 15:30
  • 3
    \$\begingroup\$ @TankorSmash 2and2 wouldn't work because it'd get parsed as 2 and2 - try 2and 2, which should work if your Python version is new enough (tested in Python 2.7.10) \$\endgroup\$
    – Sp3000
    Jun 12, 2015 at 15:34
  • \$\begingroup\$ Oh nice, you're right. Even on 2.7.3 it works. \$\endgroup\$ Jun 12, 2015 at 15:38
12
\$\begingroup\$

Pyth, 17 bytes

Ljb3ye.f!-P-yZ01Q

This is somewhat ridiculously slow - O(output^log_2(3)). It's exponential in the length of the input, but not doubly exponential, like some of the answers on the page. Some ideas taken from @Dennis's answer, here.

Demonstration.

It makes use of .f, Pyth's "loop until n matches have been found" function.

\$\endgroup\$
12
\$\begingroup\$

CJam, 22 21 20 bytes

ri_me,3fb{0-W<1-!},=

This is an O(enn) approach, where n is the input. It lists the first ⌊en non-negative integers in base 3, eliminates those that have 2s or 1s after the first 2 (if any) and selects the n+1th.

Try it online in the CJam interpreter.

How it works

ri    e# Read an integer N from STDIN.
_me,  e# Push [0 ... floor(exp(N))-1].
3fb   e# Replace each integer in the range by the array of its digits in base 3.
{     e# Filter; for each array A:
  0-  e#   Remove all 0's.
  W<  e#   Remove the last element.
  1-  e#   Remove all 1's.
  !   e#   Logical NOT. Pushes 1 iff the array is empty.
},    e#   If ! pushed 1, keep the array.
=     e# Select the (N+1)th element of the filtered array.
\$\endgroup\$
0
9
\$\begingroup\$

Pyth, 20 bytes

Jt^2hslhQ#p/=%QJ=/J2

Runs in O(log(input())), well under a second for the final test case. Based around a run until error loop. No trailing newline.

Demonstration.

Explanation:

Jt^2hslhQ#p/=%QJ=/J2
                        Implicit: Q is the input.
      lhQ                          log(Q+1,2)
     slhQ                    floor(log(Q+1,2))
    hslhQ                    floor(log(Q+1,2))+1
  ^2hslhQ                 2^(floor(log(Q+1,2))+1)
 t^2hslhQ                 2^(floor(log(Q+1,2))+1)-1
Jt^2hslhQ               J=2^(floor(log(Q+1,2))+1)-1
         #              until an error is thrown:
            =%QJ        Q=Q%J
                =/J2    J=J/2
           /            The value Q/J, with the new values of Q and J.
          p             print that charcter, with no trailing newline.

J is initialized to the value of the smallest skew binary digit position that is larger than the input. Then, each time through the loop, we do the following:

  • Remove each digit of value J from Q with =%QJ. For instance, if Q=10 and J=7, Q becomes 3, which corresponds to the skew binary changing from 110 to 10. This has no effect in the first iteration.
  • Change J to the next smaller skew binary base value with =/J2. This is floored division by 2, changing J=7 to J=3, for instance. Because this happens before the first digit is output, J is intialized one digit position higher than needed.
  • Find the actual digit value with /QJ (effectively).
  • Print that value with p, instead of Pyth`s default printing, to avoid the trailing newline.

This loop will repeat until J becomes zero, at which point a divide by zero error will be thrown, and the loop will end.

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

ES6, 105 bytes

f=n=>{for(o=0;n--;c?o+=Math.pow(3,s.length-c):o++)s=t(o),c=s.search(2)+1;return t(o);},t=a=>a.toString(3)

Usage is: f(1048576) => `"10000000000000000001"

Test the last argument at your own peril. I gave up after 5 seconds.

And pretty print with comments!

f=n=>{ //define function f with input of n (iteration)
    for(o=0; //define o (output value in decimal)
        n--; //decrement n (goes towards falsy 0) each loop until 0
        c?o+=Math.pow(3,s.length-c):o++) //if search finds a 2, increment output by 3^place (basically moves the 2 to the left and sets the place to 0), else ++
        s=t(o), //convert output to base 3      
        c=s.search(2)+1; //find the location of 2, +1, so a not-found becomes falsy 0.
    return t(o); //return the output in base 3
},

t=a=>a.toString(3);  //convert input a to base 3
\$\endgroup\$
7
  • 5
    \$\begingroup\$ Btw, unnamed functions are perfectly acceptable, so you don't need f=. \$\endgroup\$ Jun 10, 2015 at 19:07
  • 2
    \$\begingroup\$ -16 bytes: f=n=>{for(o=0;~n--;o+=c?Math.pow(3,s.length+c):1)s=o.toString(3),c=~s.search(2);return s} \$\endgroup\$
    – nderscore
    Jun 11, 2015 at 4:20
  • \$\begingroup\$ @nderscore Pretty cool :D \$\endgroup\$
    – Compass
    Jun 11, 2015 at 13:04
  • 1
    \$\begingroup\$ -7 bytes if you use ES7: replace Math.pow(3,s.length+c) with 3**(s.length+c). \$\endgroup\$ Jun 11, 2015 at 18:24
  • 3
    \$\begingroup\$ @GustavoRodrigues I haven't even finished learning ES6! @_@ \$\endgroup\$
    – Compass
    Jun 11, 2015 at 18:36
7
\$\begingroup\$

Retina, 55 bytes

^
0a
(+`12(.*a)1
20$1
0?2(.*a)1
10$1
0a1
1a
)`1a1
2a
a
<empty line>

Takes input in unary.

Each line should go to its own file but you can run the code as one file with the -s flag. E.g.:

> echo 11111|retina -s skew
12

Method: Executes incrementation on a string input number times starting from the string 0.

We use the following incrementation rules:

  • if contains 2: ^2 -> ^12; 02 -> 12; 12 -> 20
  • if doesn't contain 2: 0$ -> 1$; 1$ -> 2$

(There can be at most one 2 in the string; ^ and $ marks the start and end of the string in the rules.)

More information about Retina.

\$\endgroup\$
7
\$\begingroup\$

Java, 154 148

n->{String s="0";for(;n-->0;)s=s.contains("2")?s.replaceAll("(^|0)2","10").replace("12","20"):s.replaceAll("1$","2").replaceAll("0$","1");return s;}

This answer take the form of a single anonymous function that takes an integer argument and returns the answer as a String. Below is a complete class for testing this solution.

import java.util.function.Function;
public class Skew {
    public static void main(String[] args){
        Function<Integer,String> skew = n->{String s="0";for(;n-->0;)s=s.contains("2")?s.replaceAll("(^|0)2","10").replace("12","20"):s.replaceAll("1$","2").replaceAll("0$","1");return s;};

        for(String s:args){
            System.out.println(skew.apply(Integer.parseInt(s)));
        }
    }
}
\$\endgroup\$
5
\$\begingroup\$

Bash + coreutils, 52

dc -e3o0[r1+prdx]dx|grep -v 2.\*[12]|sed -n $1{p\;q}

This is a brute-forcer, so its rather slow for larger numbers.

Output:

$ ./xkcdnum.sh 1000
111110120
$ 
\$\endgroup\$
5
\$\begingroup\$

Java, 337 335 253 246 244 bytes

A method that takes in the index as a long and returns the result as a string

Uses a long for the index so can theoretically handle the last test case, but I really wouldn't suggest it.

String f(long i){List<Long>l=new ArrayList<>();l.add(0L);for(;i-->0;){int j=l.indexOf(2);if(j!=-1){l.set(j,0L);if(j==0){l.add(0,1L);}else{l.set(j-1,l.get(j-1)+1);}}else{j=l.size()-1;l.set(j,l.get(j)+1);}}String s="";for(long q:l)s+=q;return s;}
\$\endgroup\$
2
  • 4
    \$\begingroup\$ You could shorten this quite a bit by making it a function instead of a full program (and taking input as an argument instead of from a Scanner). \$\endgroup\$
    – Geobits
    Jun 10, 2015 at 15:14
  • 2
    \$\begingroup\$ You don't need the braces in the if(j == 0) statement (four bytes). You don't need to declare k; you can just use j again (four more). You can use generic type inference (in Java 7) in your List declaration (new ArrayList<>();) (another 4) \$\endgroup\$
    – durron597
    Jun 10, 2015 at 16:04
4
\$\begingroup\$

Haskell, 73 72

Thanks to @nimi for 1 byte!

This solution won't be winning any bounty, the last couple tests take an inordinate amount of time to run, but, I think I've golfed it fairly well.

i(2:b)=1:0:b
i[b]=[b+1]
i(b:2:c)=b+1:0:c
i(b:c)=b:i c
s=(iterate i[0]!!)

This solution is a rather naïve approach that calculates the skew binary number n by incrementing 0 n times.

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

CJam, 24 bytes

Q{0\+2a/())+a\+0a*}ri*si

This is an O(n log n) approach, where n is the input. It starts with the skew binary representation of 0 and increments the corresponding integer n times.

Try it online in the CJam interpreter.

Background

Incrementing a number in skew binary can be done by following two easy steps:

  1. Replace an eventual 2 by a 0.

  2. If a 2 has been replaced, increment the digit to its left.

    Otherwise, increment the last digit.

How it works

Q     e# Push an empty array.
{     e# Define an anonymous function:
  0\+ e#   Prepend a 0 to the array.
  2a/ e#   Split the array at 2's.
  (   e#   Shift out the first chunk of this array.
  )   e#   Pop the last digit.
  )+  e#   Increment it and append it to the array.
  a\+ e#   Prepend the chunk to the array of chunks.
  0a* e#   Join the chunks, using [0] as separator.
      e#   If there was a 2, it will get replaced with a 0. Otherewise, there's
      e#   only one chunk and joining the array dumps the chunk on the stack.
}     e#
ri*   e# Call the function int(input()) times.
si    e# Cast to string, then to integer. This eliminates leading 0's.
\$\endgroup\$
0
4
\$\begingroup\$

VBA, 209 147 142 bytes

Sub p(k)
For i=1To k
a=StrReverse(q)
If Left(Replace(a,"0",""),1)=2Then:q=q-2*10^(InStr(a,2)-1)+10^InStr(a,2):Else:q=q+1
Next
msgbox q
End Sub

My math is inefficient and my golfing could use work. But it's my first attempt at PoG and thought I'd give this one a try. Sort of a Brute Force way though.

It's just counting by 1 unless the last digit is a 2 then steps back by 2 and jumps forward 10. Plus the trailing 0's.

This stops working at 65534 because VBA insists on giving output in scientific notation, but the logic should work fine for even higher numbers

Looking forward to golfing suggestions, VBA is not very golf-friendly but it's not often represented, and I think it can beat Java for length.

Edit1: Thanks Manu for helping shave off 62 bytes

Edit2: Swapped debug.print for msgbox as output. Saved 5 bytes

\$\endgroup\$
4
  • 1
    \$\begingroup\$ You can remove the brackets from Debug.Print (q). Also, you can remove most of the whitespace (the editor will put them back, but they aren't necessary). You don't need to declare k as Long, simply write k. It will be a variable of the type Variant and the code will still work. With these tips you should get down to ~165 bytes. \$\endgroup\$ Jun 11, 2015 at 6:19
  • \$\begingroup\$ Some more thoughts: You can leave out the first and last argument of InStr, they are optional. Trim() isn't necessary, since you don't have whitespace. Applied correctly, I get to 147 bytes. \$\endgroup\$ Jun 11, 2015 at 10:20
  • 1
    \$\begingroup\$ Thanks for the Help Manu, One quick question, Output should be the Standard Output. I'm unsure what that would be in VBA. debug.print q would be the Standard output? msgbox q is shorter but Again seems like its not quite the standard output. Sheet1.cells(1,1) seems like the Typical output but assumes its running in excel. I'm just not quite sure on how strict code-golf is about these sort of things. \$\endgroup\$
    – JimmyJazzx
    Jun 11, 2015 at 17:16
  • \$\begingroup\$ Congratulations, you beat the java answer ;) I don't know either... Just use MsgBox, if someone complains, you can still change it back. \$\endgroup\$ Jun 11, 2015 at 17:24
4
\$\begingroup\$

Javascript ES6, 99 86 78 76 72 chars

f=n=>{for(s="1";--n;s=s.replace(/.?2|.$/,m=>[1,2,10][+m]||20));return s}

// Old version, 76 chars:
f=n=>{for(s="1";--n;s=s.replace(/02|12|2|.$/,m=>[1,2,10][+m]||20));return s}

// Old version, 86 chars:
f=n=>{for(s="1";--n;s=s.replace(/(02|12|2|.$)/,m=>[1,2,10,,,,,,,,,,20][+m]));return s}

// Old version, 99 chars:
f=n=>{for(s="1";--n;s=s.replace(/(^2|02|12|20|.$)/,m=>({0:1,1:2,2:10,12:20,20:100}[+m])));return s}

Test:

;[1,2,3,6,7,50,100,200,1000,10000,100000,1000000,1048576].map(f) == "1,2,10,20,100,11011,110020,1100110,111110120,1001110001012,1100001101010020,1111010000100100100,10000000000000000001"

Fun fact: There is actually some merit to this number system. When incrementing a number, you will always change at most two adjacent digits - you'll never have to carry the change through the entire number. With the right representation that allows incrementing in O(1).

Thank you for the fact - it is the base of my solution :)

\$\endgroup\$
1
  • \$\begingroup\$ How could I leave unnecessary braces in the regex? o_O \$\endgroup\$
    – Qwertiy
    Jun 12, 2015 at 9:14
3
\$\begingroup\$

Octave, 107 101 bytes

Should be O(log n) if I'm figuring this right...

function r=s(n)r="";for(a=2.^(uint64(fix(log2(n+1))):-1:1)-1)x=idivide(n,a);r=[r x+48];n-=x*a;end;end

Pretty-print:

function r=s(n)
  r="";
  for(a=2.^(uint64(fix(log2(n+1))):-1:1)-1)
    x=idivide(n,a);
    r=[r x+48];
    n-=x*a;
  end
end

I was somewhat stymied addressing the final challenge, since Octave by default treats everything as floating point numbers and I didn't have the necessary precision to calculate the last one. I got around that by spending precious bytes to force everything to be an unsigned integer. The result of the last one was too big to treat as a number, so the result is a string.

Output (I'm including 1e18 - 1 to show I can do that accurately, and the last set of outputs shows how long it takes to calculate that value):

octave:83> s(uint64(1e18))
ans = 11011110000010110110101100111010011101100100000000000001102

octave:84> s(uint64(1e18)-1)
ans = 11011110000010110110101100111010011101100100000000000001101

octave:85> tic();s(uint64(1e18)-1);toc()
Elapsed time is 0.0270021 seconds.
\$\endgroup\$
3
\$\begingroup\$

T-SQL, 221 189 177 bytes

EDIT: The original versions of this code would produce incorrect output for some numbers, this has been corrected.

With every query here, just add the number to calculate before the first comma.

Everyone know that T-SQL is the best golfing language. Here is a version that will calculate even the last test case. On the machine I tested it on, it ran in under a second, I'd be interested to see how it runs for everyone else.

DECLARE @ BIGINT=,@T VARCHAR(MAX)='';WITH M AS(SELECT CAST(2AS BIGINT)I UNION ALL SELECT I*2FROM M WHERE I<@)SELECT @T += STR(@/(I-1),1),@%=(I-1)FROM M ORDER BY I DESC SELECT @T

And here it is again, but readable:

DECLARE 
    @ BIGINT=,
    @T VARCHAR(MAX)='';
    
WITH M AS
(
    SELECT
        CAST(2 AS BIGINT) I
        
    UNION ALL
       
    SELECT I * 2
    FROM M
    WHERE I < @
)

SELECT 
    @T+=STR(@/(I-1),1),
    @%=(I-1)
FROM M 
ORDER BY I DESC

SELECT @T

If I only use ints, this can be a bit shorter, coming out at 157 bytes:

DECLARE @ INT=,@T VARCHAR(MAX)='';WITH M AS(SELECT 2I UNION ALL SELECT I*2FROM M WHERE I<@)SELECT @T+=STR(@/(I-1),1),@%=(I-1)FROM M ORDER BY I DESC SELECT @T

And once more again, more readable:

DECLARE 
    @ INT=,
    @T VARCHAR(MAX)='';
    
WITH M AS
(
    SELECT
        2I
        
    UNION ALL
       
    SELECT 
        I * 2
    FROM M
    WHERE I < @
)

SELECT 
    @T+=STR(@/(I-1),1),
    @%=(I-1)
FROM M 
ORDER BY I DESC

SELECT @T
\$\endgroup\$
4
  • \$\begingroup\$ Remember @ is a valid identifier in sql and you most likely can get away with Char(8000) which is still cheaper than nvarchar(max). You can also convert to char instead of varchar, or use the str function. \$\endgroup\$
    – Michael B
    Jun 15, 2015 at 14:49
  • \$\begingroup\$ @MichaelB Oh, I thought that I had used @, silly me. The CHAR(8000) advice is pretty good, I'll try that. I always seem to forget about the existence of STR() thanks for the heads up. \$\endgroup\$ Jun 15, 2015 at 15:08
  • \$\begingroup\$ doesn't actually help. However, you can rewrite the part after the CTE into:: select @t=concat(@t,@/i) that should be smaller. Requires sql2012 though. \$\endgroup\$
    – Michael B
    Jun 15, 2015 at 15:14
  • \$\begingroup\$ @MichaelB ah. CONCAT, I'm on 2008. So I can't test it without using an SQL fiddle right now. Good call though. \$\endgroup\$ Jun 15, 2015 at 15:18
3
\$\begingroup\$

Turing Machine Code, 333 293 bytes

I'm using an encoding as used here.

This machine uses 9 states and 11 colors.

If binary input is permissible, this can be reduced to a mere 4 colors, saving a few tens of bytes in the process.

0 _ _ l 1
0 * * r 0
1 9 8 l 2 
1 8 7 l 2
1 7 6 l 2
1 6 5 l 2
1 5 4 l 2
1 4 3 l 2
1 3 2 l 2
1 2 1 l 2
1 1 0 l 2
1 0 9 l 1
1 _ _ r 8
2 _ _ l 3
2 * * l 2
3 _ 1 r 4
3 * * l 5
4 _ _ r 0
4 * * r 4
5 * * l 5
5 _ _ r 6
6 _ _ l 7
6 2 0 l 7
6 * * r 6
7 _ 1 r 4
7 0 1 r 4
7 1 2 r 4
8 _ _ * halt
8 * _ r 8

If the above link isn't working (sometimes it works for me, other times the page refuses to load) you may also test this using this java implementation.

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

Perl, 66 bytes

Number is to be input through STDIN.

$_=1;$c=<>;s/(.*)(.?)2(.*)/$1.$2+1 .$3.0/e||$_++while(--$c);print;
\$\endgroup\$
4
  • \$\begingroup\$ Could you explain how your solution works? I don't see how you need (.?) in $2 since (.*) in $1 should be greedy and get that character first. But if it gets removed the code doesn't produce the correct results anymore! By the way, you don't need the final ;. \$\endgroup\$
    – CJ Dennis
    Jun 12, 2015 at 14:18
  • \$\begingroup\$ @CJDennis Thanks for that byte saved. Anyway, the .? will get the digit coming right before the two unless there is no digit there (e.g. 20). In cases such as 120 or 10020, the regex groups like this: ()(1)2(0) and (10)(0)2(0). Then the first group is simply ignored, the second group (which is always either one digit if possible or blank) is incremented, and the third group (always consisting of zeroes) is ignored and a zero is added. I simply used the OEIS entry as my guide for this regex. \$\endgroup\$
    – fvla
    Jun 12, 2015 at 14:34
  • \$\begingroup\$ I got your code down to 53 bytes: $c=<>;s/(.*)2(.*)/$1+1 .$2.0/e||$_++while($c--);print. I was right, the (.?) never captured anything. \$\endgroup\$
    – CJ Dennis
    Jun 13, 2015 at 3:34
  • \$\begingroup\$ Can be optimized to $_=1;$c=<>;s/(.?)2/1+$1.0/e||$_++while(--$c);print, which is 50 bytes. .* at the beginning or end can be optimized away, if you just replace it with the original text. Also there is no reason to add the 0 at the end, as there are always only zeros in the original $3. \$\endgroup\$
    – Thraidh
    Jun 13, 2015 at 12:37
2
\$\begingroup\$

Pyth, 19 bytes

m/=%Qtydtd^L2_SslhQ

Logarithmic complexity. Easily finishes in the necessary amount of time. Output in the form of a list of digits.

Demonstration.

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

Perl, 84 70 67 bytes

$n=<>;$d*=2while($d++<$n);$_.=int($n/$d)while($n%=$d--,$d/=2);print

Not very golfy, Getting better but it does work very quickly!

Dennis's suggestion gets it down to 51 (50 bytes + -p switch)

$d*=2while$d++<$_;$\.=$_/$d|0while$_%=$d--,$d/=2}{

It must be called like perl -p skew_binary.pl num_list.txt where num_list.txt contains a single line with the number to encode on it.

\$\endgroup\$
13
  • \$\begingroup\$ @frederick we're on the edge of our seats waiting for 2. \$\endgroup\$
    – Rob Grant
    Jun 12, 2015 at 12:54
  • \$\begingroup\$ @RobertGrant He golfed his comment from two things to one thing! \$\endgroup\$
    – CJ Dennis
    Jun 12, 2015 at 13:02
  • \$\begingroup\$ Two things: 1. Instead of using $ARGV[0], use <> as input. It will take input from stdin unless there are any files as arguments. 2. For odd counting schemes like this, use regular expressions. Instead of doing odd math operations, you can replace digits in a number as if it is a string. The best part is that you can use math operations (like increment) on it at the same time, provided that it is a string consisting completely of digits. Check the documentation for the regular expression operators, as they can be very useful in so many occasions. \$\endgroup\$
    – fvla
    Jun 12, 2015 at 13:11
  • \$\begingroup\$ Sorry, I pressed enter and it saved before I finished the comment. \$\endgroup\$
    – fvla
    Jun 12, 2015 at 13:12
  • \$\begingroup\$ @frederick don't be so modest. We know what happened! \$\endgroup\$
    – Rob Grant
    Jun 12, 2015 at 13:19
2
\$\begingroup\$

JavaScript (Node.js), 40 bytes

v=>(g=n=>n>v?'':g(n-~n)+(v-(v%=n))/n)(1)

Try it online!

This solution does not work on last testcase. It just cause stack overflow on it.

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

Mathematica, 65

Should be quite fast enough, although I have to admit I peeked at the other submissions before making this.

f = (n = #;
     l = 0; 
     While[n > 0,
      m = Floor[Log2[1 + n]];
      l += 10^(m - 1);
      n -= 2^m - 1
     ]; l)&

Usage:

f[1000000000000000000]

Output:

11011110000010110110101100111010011101100100000000000001102

Starts giving MaxExtraPrecision error messages somewhere past 10^228 (for which it calculates the result in .03 seconds on my machine)

After removing the MaxExtraPrecision limit, it will handle numbers up to around 10^8000 in a second.

Input:

Timing[Block[{$MaxExtraPrecision = Infinity}, f[10^8000]];]

Output:

{1.060807, Null}
\$\endgroup\$
1
\$\begingroup\$

C, 95 bytes

void f(unsigned long i,int*b){for(unsigned long a=~0,m=0;a;a/=2,b+=!!m)m|=*b=i/a,i-=a**b;*b=3;}

This accepts an integer and a buffer in which to return the digits. The results are stored in b, terminated with value 3 (which can't occur in the output). We don't have to handle input of 0 (as the question specified only positive integers), so there's no special-casing to avoid empty output.

Expanded code

void f(unsigned long i,int*b)
{
    for (unsigned long a=~0, m=0;  a;  a/=2, b+=(m!=0)) {
        *b = i/a;               /* rounds down */
        i -= *b * a;
        m = m | *b;             /* m != 0 after leading zeros */
    }
    *b=3;                       /* add terminator */
}

We operate by successive subtraction, starting with the most significant digit. The only complication is that we use the variable m to avoid printing leading zeros. A natural extension to unsigned long long may be made if desired, at the cost of 10 bytes.

Test program

Pass numbers to be converted as command arguments. It converts the int array buffer to a printable digit string. Runtime is less than one millisecond for input 1000000000000000000.

#include <stdio.h>
#include <stdlib.h>
int main(int argc, char**argv)
{
    while (*++argv) {
        unsigned long i = strtoul(*argv, NULL, 10);
        int result[1024];
        f(i,result);

        /* convert to string */
        char s[1024];
        {char*d=s;int*p=result;while(*p!=3)*d++=*p+++'0';*d=0;}
        printf("%lu = %s\n", i, s);
    }

    return EXIT_SUCCESS;
}

Test results

$ ./51517 $(seq 20)
1 = 1
2 = 2
3 = 10
4 = 11
5 = 12
6 = 20
7 = 100
8 = 101
9 = 102
10 = 110
11 = 111
12 = 112
13 = 120
14 = 200
15 = 1000
16 = 1001
17 = 1002
18 = 1010
19 = 1011
20 = 1012
\$\endgroup\$
1
  • \$\begingroup\$ I guess a C++ version is similar, but can use auto a=~0ull for a slight advantage... \$\endgroup\$ Oct 16, 2015 at 14:58
0
\$\begingroup\$

CoffeeScript, 92 69 bytes

Based of Qwertiy's answer and updates:

f=(n)->s='1';(s=s.replace /(.?2|.$)/,(m)->[1,2,10][+m]||20)while--n;s

# older version, 92 bytes
f=(n)->s='1';(s=s.replace /(^2|02|12|20|.$)/,(m)->{0:1,1:2,2:10,12:20,20:100}[+m])while--n;s
\$\endgroup\$
3
  • 2
    \$\begingroup\$ Converting to other language without even simple optimization by removing unnecessary braces in the regex doesn't seem cool for me... \$\endgroup\$
    – Qwertiy
    Jun 12, 2015 at 9:39
  • \$\begingroup\$ @Qwertiy I've provided attribution to your answer, and with both of the answers I can't produce the same results without the brackets in the regex \$\endgroup\$ Jun 12, 2015 at 14:18
  • \$\begingroup\$ The whole occurrence is replaced. Why do you need it to be inside of the group? JS version works in Firefox without brackets. \$\endgroup\$
    – Qwertiy
    Jun 12, 2015 at 20:22
0
\$\begingroup\$

Japt, 31 bytes

_r/?2|.$/g_÷C ç20 ª°Zs3}}gU['0]

Try it online!

Almost direct port of this JS solution. No idea if there's better way.

Unpacked & How it works

X{Xr/?2|.$/gZ{Z÷C ç20 ||++Zs3}}gU['0]

X{     Declare a function...
Xr       Accept a string, replace the regex...
/?2|.$/g   /.?2|.$/   (g is needed to match *only once*, opposite of JS)
Z{       ...with the function... (matched string will be 0,1,2,02 or 12)
Z÷C        Implicitly cast the matched string into number, divide by 12
ç20        Repeat "20" that many times (discard fractions)
||         If the above results in "", use the next one instead
++Z        Increment the value
s3         Convert to base-3 string (so 0,1,2 becomes 1,2,10)
}}
gU['0] Repeatedly apply the function on "0", U (input) times
\$\endgroup\$
0
\$\begingroup\$

Stax, 16 bytes

üxëàè£öΦGΩ│Je5█ò

Run and debug it

I'm not sure exactly what the formal complexity class is, but it's fast enough to do all the test cases in a tenth of a second on this machine.

Unpacked, ungolfed, and commented, it looks like this. In this program, the x register originally contains the input.

z       push []
{       start block for while loop
 |X:2N  -log2(++x)
 {^}&   increment array at index (pad with 0s if necessary)
 xc:G-X unset high bit of x; write back to x register
w       while; loop until x is falsy (0)
$       convert to string

Run this one

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

Husk, 16 bytes

!mdfö¬f≠1hfImB3N

Try it online! or Verify first 100 values

Same method as Dennis' CJam answer.

\$\endgroup\$

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.