47
\$\begingroup\$

Seems like an impossible task right? Well, it's actually not that hard. If we write the word Infinity as 8-bit binary ASCII code, we'll get:

01001001 01101110 01100110 01101001 01101110 01101001 01110100 01111001

This can be concatenated, and converted to the decimal value 5291279215216915577. Now that's a number we can work with...

The way you'll count down is:

  1. Output the original string as a decimal number (as shown above)
  2. Remove leading 0s in its binary representation (if any)
  3. Toggle the bits in the binary representation (1->0, 0->1)
  4. Output the number in decimal
  5. Repeat steps 2-4 as until you reach 0.

Challenge:

Create a program or function that takes a string as input, and outputs (on any suitable format) the numbers you'll get when performing the procedure above.

Test case:

I think the challenge will be fairly easy to understand, even though it's only one test case. I'll use Inf instead of Infinity to keep this fairly short.

Inf
4812390  (10010010110111001100110)
3576217  ( 1101101001000110011001)
618086   (   10010110111001100110)
430489   (    1101001000110011001)
93798    (      10110111001100110)
37273    (       1001000110011001)
28262    (        110111001100110)
4505     (          1000110011001)
3686     (           111001100110)
409      (              110011001)
102      (                1100110)
25       (                  11001)
6        (                    110)
1        (                      1)
0        (                      0)

Input: Inf 
Output:
4812390, 3576217, 618086, 430489, 93798, 37273, 28262, 4505, 3686, 409, 102, 25, 6, 1, 0 

Input: Infinity
Output:
5291279215216915577, 3932092821637860230, 679593196789527673, 473328307817319302, 103132444486104185, 40982743589751686, 31074850448176249, 4953946570787718, 4053252683953273, 450346943417222, 112603010004089, 28134478351238, 7049893737593, 1746199284614, 452823970937, 96931842950, 40507110521, 28212366214, 6147372153, 2442562438, 1852404857, 295078790, 241792121, 26643334, 6911097, 1477510, 619641, 428934, 95353, 35718, 29817, 2950, 1145, 902, 121, 6, 1, 0

Your code must support strings that can be represented as a binary number up to the limit of your language. All strings will only contain printable ASCII-characters from 32-126 (space to tilde).


Leaderboard

var QUESTION_ID=98274,OVERRIDE_USER=31516;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\$
  • 31
    \$\begingroup\$ Chuck Norris, 8 bytes: Inf:-1:0 \$\endgroup\$ – Luis Mendo Nov 2 '16 at 10:32
  • 2
    \$\begingroup\$ @LuisMendo Chuck Norris' NARS-APL: ∞..0 \$\endgroup\$ – Adám Nov 2 '16 at 11:41
  • 5
    \$\begingroup\$ @LuisMendo Are you sure you don't mean Jon Skeet? \$\endgroup\$ – mbomb007 Nov 2 '16 at 15:08

23 Answers 23

12
\$\begingroup\$

Jelly, 15 10 bytes

-5 bytes thanks to @Dennis (convert directly from base 256 after ordinal cast)

Oḅ⁹µBCḄµÐĿ

TryItOnline!

How?

Oḅ⁹µBCḄµÐĿ - Main link: s                     e.g. "Inf"
O          - cast to ordinals                 e.g. [73,110,102]
 ḅ⁹        - convert from base 256 to integer e.g. 4812390
   µ   µ   - monadic chain separations
    B      -     convert to binary
     C     -     complement
      Ḅ    -     convert to integer
        ÐĿ - loop until no longer unique and collect results 
\$\endgroup\$
  • 1
    \$\begingroup\$ The first part is just Oḅ⁹. \$\endgroup\$ – Dennis Nov 2 '16 at 11:41
  • \$\begingroup\$ Oh my, how did I miss that?! \$\endgroup\$ – Jonathan Allan Nov 2 '16 at 11:45
11
\$\begingroup\$

Python 2, 89 82 77 76 75 bytes

n=0
for c in input():n=n<<8|ord(c)
while 1:print n;n^=2**n.bit_length()-n/n

Test it on Ideone.

How it works

After initializing n to 0, the second line performs the string-to-integer conversion specified in the challenges as follows.

In each step, n is shifted 8 units to the left, then bitwise OR-ed with the the code point of the next character c. For input Inf, this goes as follows.

n                                  0
a = n<<8                           0
b = 'I'                      1001001
n = a ^ b                    1001001
a = n<<8             100100100000000
b = 'n'                      1101110
n = a ^ b            100100101101110
a = n<<8     10010010110111000000000
b = 'f'                      1100110
n = a ^ b    10010010110111001100110

Now we're ready to generate the output. To invert the bits of n, we proceed as follows.

First, we compute the bits in n's binary representation without leading zeroes. Let's call the result k. Then, we compute the kk power of 2, which has k+1 binary digits: a single 1, followed by k 0's. We subtract 1 from the result, yielding a number composed of k ones, which we then XOR with n to invert its bits. For input inf this goes as follows.

n         4812390   10010010110111001100110
k              23 
t = 2**k           100000000000000000000000
t -= 1              11111111111111111111111
n ^= t    3576217    1101101001000110011001
k              22
t = 2**k            10000000000000000000000
t -= 1               1111111111111111111111
n ^= t     618086      10010110111001100110
.
.
.
n               6                       110
k               3
t = 2**k                               1000
t -= 1                                  111
n ^= t          1                         1
k               1
t = 2**k                                 10
t -= 1                                    1
n ^= t          0                         0

On additional hurdle in the implementation is that we have to print n before the first step, after the last step, and in all steps in between. Python doesn't have do-while loops and a single print statement costs 8 bytes, so we do the following instead.

In the straightforward implementation of the update step, i.e.,

while n:print n;n^=2**n.bit_length()-1
print n

we replace the loop with an infinite one (while 1) and compute the 1 in the loop as n/n. This is equivalent while n > 0.

Once n = 0, we stay in the loop, print the state once more, then try to update it. However, 0/0 triggers a ZeroDivisionError, breaking out of the loop and exiting with an error. Note that this causes stray output to STDERR, which is allowed by default.

\$\endgroup\$
  • 2
    \$\begingroup\$ I love that -n/n trick :-) \$\endgroup\$ – ETHproductions Nov 2 '16 at 15:00
  • \$\begingroup\$ Can you explain than n/n trick? It's probably been explained in another answer somewhere but I haven't found it. What does it do here? \$\endgroup\$ – Stewie Griffin Nov 3 '16 at 7:08
  • \$\begingroup\$ @StewieGriffin n/n is 1 until n is 0, then it throws an error and causes the program to stop. \$\endgroup\$ – jazzpi Nov 3 '16 at 12:36
  • \$\begingroup\$ With an error message (I hope)? \$\endgroup\$ – Stewie Griffin Nov 3 '16 at 12:42
  • 1
    \$\begingroup\$ @StewieGriffin Indeed. Python is painfully verbose when it comes to error reporting. I've edited my answer to incorporate an explanation. \$\endgroup\$ – Dennis Nov 3 '16 at 15:06
8
\$\begingroup\$

JavaScript, 82 bytes

Saved a byte thanks to @Arnuald

for(y of prompt(n=0))n=n<<8|y.charCodeAt()
for(;alert(n)|n;)for(i=1;i<=n;i*=2)n^=i

One of the very few times when a full program outperforms a function (and ES6 does not outperform ES5)...


The above supports up to 4-letter words. Add 4 bytes to support up to 6-letter words:

for(y of prompt(n=0))n=n*256+y.charCodeAt()
for(;alert(n)|n;n=i-n-1)for(i=1;i<=n;)i*=2

\$\endgroup\$
  • \$\begingroup\$ g=a=>a[0]?a.pop().charCodeAt()+g(a)*256:0 (-1) \$\endgroup\$ – Titus Nov 2 '16 at 13:45
  • \$\begingroup\$ @Titus Thanks! Not sure why I didn't think of that \$\endgroup\$ – ETHproductions Nov 2 '16 at 13:51
  • \$\begingroup\$ n<<8|y.charCodeAt() should save a byte. for(;n;)for(i=!alert(n);i<=n;i*=2)n^=i would save another byte, but you won't display 0, which is probably required. \$\endgroup\$ – Arnauld Nov 2 '16 at 16:27
  • \$\begingroup\$ @Arnauld Thanks. I thought about doing n<<8 earlier but decided it wouldn't work because it would break for n with more than 31 bits. I suppose it doesn't matter now that I've already split it between a 31-bit version and a 53-bit version... And sadly, I don't think I can save anything on the alert while alerting both the first iteration and the last. \$\endgroup\$ – ETHproductions Nov 2 '16 at 16:41
7
\$\begingroup\$

Actually, 14 bytes

2@├¿W■├♂≈♂Y2@¿

Try it online!

Explanation:

2@├¿W■├♂≈♂Y2@¿
 @├             encode input in binary
2  ¿            convert from binary to decimal
    W           while the number is not 0:
     ■            print the number without popping
      ├           convert number to binary
       ♂≈         convert each character to an int
         ♂Y       boolean negate each int
           2@¿    convert from binary to decimal
\$\endgroup\$
6
\$\begingroup\$

05AB1E, 18 bytes

Uses CP-1252 encoding.

Çžz+b€¦J[CÐ,_#bS_J

Try it online!

Explanation

Ç                     # convert string to list of ascii codes
 žz+                  # add 256 to each
    b                 # convert to binary
     €¦               # remove the first digit of each list of digits
       J              # join
        [             # start loop
         C            # convert to decimal
          Ð           # triplicate
           ,          # print 1 copy
            _#        # if the 2nd copy is 0, break loop
              b       # convert 3rd copy to binary
               S      # split to list
                _     # negate each in list
                 J    # join
\$\endgroup\$
4
\$\begingroup\$

MATL, 13 bytes

8W:qZA`tB~XBt

Try it online!

Explanation

8W:q            % Push array [0 1 ... 255]
    ZA          % Take input string and convert it from the base defined by the
                % alphabet [0 1 ... 255] to decimal
      `         % Do...while
       t        % Duplicate
        B       % Convert to binary
         ~      % Negate
          XB    % Convert to decimal
            t   % Duplicate. Used as loop condition: exit if zero
\$\endgroup\$
4
\$\begingroup\$

Mathematica, 99 bytes

a=FromDigits;b=IntegerDigits;NestWhileList[a[1-#~b~2,2]&,a[Join@@b[ToCharacterCode@#,2,8],2],#>0&]&

Anonymous function. Takes a string as input, and returns a list of numbers as output.

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

Haskell, 109 123 118 102 97 bytes

Thanks to @nimi for saving 5 bytes!

c 0=0
c n=1-mod n 2+2*c(div n 2)
(++[0]).fst.span(>0).iterate c.foldl((+).(256*))0.map fromEnum

Usage: (++[0]).fst.span(>0).iterate c.foldl((+).(256*))0.map fromEnum $ "Infinity"

Guaranteed to work on numbers up to 29 bits by the language, usually works up to 63-bit numbers on 64-bit systems. Use map(fromIntegral.fromEnum) instead (+14 bytes) to support arbitrarily large numbers.

Works for unicode range [0..255]. Recursively flips bits.

\$\endgroup\$
  • 1
    \$\begingroup\$ You can replace takeWhile(>0) with fst.span(>0). If you go pointfree you can drop the name f, so your main function is (++[0]) ... map fromEnum. \$\endgroup\$ – nimi Nov 2 '16 at 11:05
  • \$\begingroup\$ @nimi thanks, dropping the name solves the type inference problem I had with f. \$\endgroup\$ – Angs Nov 2 '16 at 11:14
  • \$\begingroup\$ Why fromIntegral? From the challenge: "must support ... up to 63bits ... or the limit of your language", so Int should be fine. If you want to keep it, move it to map, i.e. your old version of foldl1 and map(fromIntegral.fromEnum). \$\endgroup\$ – nimi Nov 2 '16 at 11:32
  • \$\begingroup\$ @nimi OP posted a comment here (since deleted), asking if this supported 63 bits, so I assumed that was his intent. Beats me. \$\endgroup\$ – Angs Nov 2 '16 at 11:44
4
\$\begingroup\$

PHP, 132 126 123 120 108 107 bytes

foreach(unpack("C*",$argv[1])as$i)$n=$n*256+$i;for(print$n;$n;)echo _.$n=bindec(strtr(decbin($n),"01",10));
  • printing 0 after loop instead of initial value before loop saves 6 bytes.
  • unpack instead of str_split renders ord() obsolete -> -3 bytes
  • underscore _ as separator saves 3.
  • bindec instead of ltrim to remove leading zeroes: -12
  • echo in loop body saves 1 byte over print in loop head.
\$\endgroup\$
  • \$\begingroup\$ Can't $n=$n*256+$i;for(print$n;$n;) be written as for(print$n=$n*256+$i;$n;)? Since the assignment part will execute once, this should work. And instead of echo _.$n=[...], you should use echo _,$n=[...] instead. It won't save any byte, but will speed the code a tiny tiny tiny tiny bit and will separate statements. That means that, for example, echo _,$a?5:6; can be written instead of echo _.($a?5:6);. This may be helpful in the future. \$\endgroup\$ – Ismael Miguel Nov 4 '16 at 18:56
  • \$\begingroup\$ @IsmaelMiguel The assignment part is a loop. I actually use the comma when I don´t need the dot; it is a remnant from the print in this case. Alone not worth an edit; but thanks. \$\endgroup\$ – Titus Nov 5 '16 at 8:45
  • \$\begingroup\$ Oh, right... It is inside the foreach(unpack("C*",$argv[1])as$i)... Silly me... And yes, changing a period for a comma to have the same effect isn't worth the trouble. \$\endgroup\$ – Ismael Miguel Nov 5 '16 at 13:41
4
\$\begingroup\$

Perl, 65 bytes

53 bytes code + 12 for -Mbigint -p.

Thanks to @Dada for saving me 13 bytes!

$_=unpack"B*";say(0+"0b$_"),s/^0+//,y/10/01/while$_>0

Fairly straightforward approach, only different to most of these is that the number is stored as binary and printed out in decimal. I'm sure it can be improved, perhaps with storing details in an array. -Mbigint is a bit inconvenient but necessary.

Usage

echo -n 'Inf' | perl -Mbigint -pE'$_=unpack"B*";say(0+"0b$_"),s/^0+//,y/10/01/while$_>0'
4812390
3576217
618086
430489
93798
37273
28262
4505
3686
409
102
25
6
1
0
echo -n 'Infinity' | perl -Mbigint -pE'$_=unpack"B*";say(0+"0b$_"),s/^0+//,y/10/01/while$_>0'
5291279215216915577
3932092821637860230
679593196789527673
473328307817319302
103132444486104185
40982743589751686
31074850448176249
4953946570787718
4053252683953273
450346943417222
112603010004089
28134478351238
7049893737593
1746199284614
452823970937
96931842950
40507110521
28212366214
6147372153
2442562438
1852404857
295078790
241792121
26643334
6911097
1477510
619641
428934
95353
35718
29817
2950
1145
902
121
6
1
0
\$\endgroup\$
  • 1
    \$\begingroup\$ Unpack my friend, unpack! perl -Mbigint -lpE'$_=unpack"B*";say(0+"0b$_"),s/^0+//,y/10/01/while$_>0' (I have no idea how to use unpack usually, I just got lucky when googling how to convert a string to binary ;-) ) \$\endgroup\$ – Dada Nov 2 '16 at 18:35
  • \$\begingroup\$ Ahhh, I always forget about unpack the syntax always blows my mind! I'll update, thank you! \$\endgroup\$ – Dom Hastings Nov 2 '16 at 18:40
  • \$\begingroup\$ There is perlpacktut that should help... I've read the first 10 line dozens of time, but I should really take the time to read the rest! \$\endgroup\$ – Dada Nov 2 '16 at 18:43
  • \$\begingroup\$ @Dada I'm sure I've read it many times, it just never stays in... Thanks again -13 is no small feat! I had to switch to echo -n is the only other change. \$\endgroup\$ – Dom Hastings Nov 2 '16 at 18:46
4
\$\begingroup\$

Pyth, 12 bytes

.usi!MjN2 2C

A program that takes input of a quoted string and prints the result as a list of integers.

Verify all test cases

How it works

.usi!MjN2 2C  Program. Input: Q
           C  Convert Q to an integer by code-points using base-256 (implicit input)
.u            Apply the following function A(N) until a repeat occurs, storing the results
              in a list:
      jN2       Convert to binary as a list
    !M          Map negation over the above
   i      2     Convert from binary to integer
  s             Integer (Converts final False to 0)
              Implicitly print
\$\endgroup\$
3
\$\begingroup\$

Python 3, 99 95 bytes

x=int.from_bytes(bytes(input(),'utf-8'),'big')
while x:print(x);x^=2**x.bit_length()-1
print(0)

Main idea is to convert string to bytes to to number. Each iteration print the output and XOR with all 1s to progress towards zero.

\$\endgroup\$
  • \$\begingroup\$ You don't need parentheses around 2**x.bit_length()-1. Order of operations for power and subtraction are higher than xor. Also, that while can be on a single line. \$\endgroup\$ – mbomb007 Nov 2 '16 at 15:13
  • \$\begingroup\$ Write the while loop on one line (remove the newline and indent) \$\endgroup\$ – FlipTack Nov 2 '16 at 15:37
  • \$\begingroup\$ Try starting the program with P=print and then using P() instead of print() \$\endgroup\$ – Cyoce Nov 3 '16 at 0:41
3
\$\begingroup\$

Python 2, 117 115 bytes

Saving 2 bytes thanks to Cyoce.

Assumes input enclosed in quotes, e.g. "Inf"

s=input()
n=sum(ord(s[-i-1])<<i*8for i in range(len(s)))
while n:
 print n;k,m=n,1
 while k:k/=2;m*=2
 n^=m-1
print 0

m counts up to the highest digit, so m-1 is a XOR mask to perform the desired operation. The longest part is converting the input into the initial bit sequence.

Example:

"Inf"
4812390
3576217
618086
430489
93798
37273
28262
4505
3686
409
102
25
6
1
0

"Infinity"
5291279215216915577
3932092821637860230
679593196789527673
473328307817319302
103132444486104185
40982743589751686
31074850448176249
4953946570787718
4053252683953273
450346943417222
112603010004089
28134478351238
7049893737593
1746199284614
452823970937
96931842950
40507110521
28212366214
6147372153
2442562438
1852404857
295078790
241792121
26643334
6911097
1477510
619641
428934
95353
35718
29817
2950
1145
902
121
6
1
0
\$\endgroup\$
  • \$\begingroup\$ You can replace -i-1 with ~i \$\endgroup\$ – Cyoce Nov 3 '16 at 0:42
3
\$\begingroup\$

Ruby, 104 101 100 81 80 65 bytes

19 bytes saved thanks to @WayneConrad!
15 Bytes saved thanks to @philomory!
1 byte saved thanks to @LeeW!

p n=$*[0].unpack('B*')[0].to_i(2)
p n^=2**n.bit_length-1while n>0

Takes input via command line arguments.

Inspired by @JimmyJohnson's Python answer

\$\endgroup\$
  • \$\begingroup\$ You may be able to save a few characters by replacing i.to_s(2).rjust 8,'0' with "%08b"%i \$\endgroup\$ – Wayne Conrad Nov 2 '16 at 21:32
  • \$\begingroup\$ Also, I think inject(:+) can be replaced with join \$\endgroup\$ – Wayne Conrad Nov 2 '16 at 21:33
  • \$\begingroup\$ @WayneConrad thanks for the help! Not sure how I forgot about those \$\endgroup\$ – Cyoce Nov 2 '16 at 21:50
  • \$\begingroup\$ Glad I could help! Thank you for teaching me the #bit_length method, which I didn't know about. \$\endgroup\$ – Wayne Conrad Nov 3 '16 at 14:05
  • 1
    \$\begingroup\$ Switching to unpack followed by [0] rather than messing with gsub will save 11 bytes. Switching to $*[0] instead of gets.chop (using a command line argument instead of console input) will save another 9, first line becomes p n=$*[0].unpack('B*')[0].to_i(2). \$\endgroup\$ – philomory Nov 4 '16 at 3:38
3
\$\begingroup\$

Labyrinth, 104 103 bytes

'  )25 }_';:_';_2/;{
''', 6 2 1   1   { (
 ' | / _ _   _}*2_ $
 * _ :!\ }2_\     !:
 652       @'''''''

Try it Online!

Explanation:

Color-coded image of source code

The instruction pointer starts at the top-left most non-wall character (walls include spaces and any letter except v).

Orange:

This loop gets the input one character at a time as an ASCII code, adding it to the current value and multiplying the current value by 256.

  • ' No-op
  • , Push the ascii code of the next input char to the top of the stack or -1 if EOF. At this point if input was received, the code will turn right (moving down) because the top of the stack is potive. Otherwise it will turn left because the top of the stack is negative.
  • | Pop the top two items from the stack and push the result of a bitwise OR.
  • _ Push zero
  • 256 Each digit seen pops x and pushes x*10+digit. So this combined with the push zero previous push 256 to the top of the stack.
  • * Pop y, pop x, push x*y. At this point since the top of the stack is positive the code will turn right to continue around the loop.

Blue:

  • ) Increment the top of the stack. When the end of input is reached, the code will turn left to get to this point with a -1 on the stack which will get incremented to zero.
  • 256 Having the top of the stack 0 allows us to push this 256.
  • / Pop y, pop x push x/y (integer division). Since we were multiplying the input by 256 each loop, we need to revert the last multiplication.
  • : Duplicate the top of the stack so we have a copy of the current value for later.
  • ! Pop the top of the stack and print the integer value to STDOUT.
  • \ Print a new line.
  • _2 Push a two to the top of the stack.
  • } Move the top of the stack to the top of the auxiliary stack.

Red:

This loop flips the bits of the current value by XOR with a particular value calculated in the inner (green) loop. It then outputs the current value and exits the program if the current value is zero.

  • _ Push zero (control flow).
  • ; Discard the top of the stack (control flow).
  • : Duplicate the current value. The copy will be used to calculate the XOR.
  • _ Push zero (control flow).
  • (Green loop)
  • $ Pop y, pop x, Push x XOR y.
  • :! Duplicate the current value and print the integer representation.
  • If the current value is 0, we continue straight into the @ and terminate.
  • \ Print a new line.
  • _2} Push 2 and move to the aux stack.
  • _1 Push 1 (control flow).

Green:

This loop calculates the value by which we need to XOR the current value. This is done by repeatedly doubling the top of the auxiliary stack while halving a copy of the current value on the stop of the main stack until it reaches 0.

  • _ Push zero (control flow).
  • ; Discard the current value which is only used to enforce control flow.
  • _2 Push 2 in order to halve the current value.
  • / Divide
  • { Move the top of the aux stack to the top of the main stack.
  • _2* Double the top of the stack
  • } Move the top of the main stack back to the aux stack.
  • _1 Push one for control flow.
  • After exiting the loop:
  • ; Discard the left over zero from calculating the XOR.
  • { Move the calculated XOR to the main stack.
  • ( Subtract one from XOR value.
\$\endgroup\$
2
\$\begingroup\$

PowerShell v2+, 158 bytes

for($a=-join([char[]]$args[0]|%{([int][convert]::ToString(+$_,2)).ToString('0'*8)});$a){[convert]::ToInt64($a,2);$a=$a.TrimStart('0')-split0-replace1,0-join1}

Yeah, so, converting bases in PowerShell is really sucky. And we get to do it twice here.

OK, so this is just a for loop on $a -- i.e., we loop so long as $a exists. We'll eventually reach an empty string (which is falsey), so that's how we'll terminate.

The setup of the loop, $a=-join([char[]]$args[0]|%{([int][convert]::ToString(+$_,2)).ToString('0'*8)}), takes the input $args[0], casts it as a char-array, and loops through each character. We use the .NET [convert]::ToString(int,base) to convert each to a binary string. However, that doesn't include leading zeros, so we need to re-cast that string as an [int] and call its .ToString() method with 8 zeros as the mask. Then those strings are encapsulated in parens and -joined together, then saved into $a.

Inside the loop, we [convert]::ToInt64(string,base) to convert the binary number to a decimal number. That gets left on the pipeline and is subsequently flushed when the loop resets (and therefore implicitly printed). The next section performs the calculations -- we .TrimStart() to remove any leading zeros, -split0 to split on zeros and get a string-array of 1s, -replace those ones with zeros, and finally -join the array back together with 1s. Then, the loop begins again.

PS C:\Tools\Scripts\golfing> .\count-down-from-infinity.ps1 'PPCG'
1347437383
800046264
273695559
263175352
5260103
3128504
1065799
1031352
17223
15544
839
184
71
56
7
0
\$\endgroup\$
2
\$\begingroup\$

CJam, 17 16 18 bytes

q256b0{_p2b:!2bj}j

Try it online!

q256b   e# read printable ascii to integer
0       e# value for terminal case
{       e# recursive function
  _p    e#   print current number
  2b    e#   create binary representation with no leading zeros
  :!    e#   flip bits
  2b    e#   convert binary back to integer
  j     e#   recursive call
}j      e# end

NOTE: The old 16 byte version didn't behave correctly with empty strings:

q256b{_p2b:!2b}h

Also, thanks to Dennis for suggesting p which saves 1 byte over N\ putting newlines into the stack.

\$\endgroup\$
  • \$\begingroup\$ _p2b:!2b saves a byte. Also, you should use l; r will fail if the input contains spaces. \$\endgroup\$ – Dennis Nov 3 '16 at 1:17
  • \$\begingroup\$ @Dennis Thanks, though this now makes me worry if a empty string is an issue. \$\endgroup\$ – Linus Nov 3 '16 at 1:32
  • \$\begingroup\$ Right. q will work correctly with empty strings. \$\endgroup\$ – Dennis Nov 3 '16 at 1:41
2
\$\begingroup\$

J, 24 bytes

256-.&.#:^:*^:a:@#.a.&i.

Explanation will come later!

\$\endgroup\$
  • 2
    \$\begingroup\$ Welcome to PPCG! Permalink for the interested: Try it online! \$\endgroup\$ – Dennis Dec 17 '18 at 13:14
1
\$\begingroup\$

Retina, 116 bytes

Byte count assumes ISO 8859-1 encoding. Line 5 contains non-printable bytes. It's T`\x00-\xFF.

-2`
±
s{`±(.)
$&$1
}T`-`_o`±.
[^±]+
$.&
±

\d+
$*
+`(1+)\1
${1}0
01
1


{*(`1
01
+`10
011
^0+

)M`1
^0+

T`01`10

Try it online

Don't try this with input longer than two characters. (It times out using the online interpreter.) We gotta convert the binary to unary before decimal. :D

Unfortunately, there's a trailing zero and linefeed, but I decided to assume that was okay because the output is still correct.

Explanation

-2`         # Convert ASCII to decimal (ord)
±
s{`±(.)
$&$1
}T`-`_o`±.
[^±]+
$.&
±

\d+         # Decimal to binary
$*
+`(1+)\1
${1}0
01
1


{*(`1       # Loop; Loop print and undo; Convert binary to unary
01
+`10
011
^0+

)M`1        # Unary to decimal; End print and undo
^0+         # Remove leading zeros

T`01`10     # Flip bits; (implicit loop end)
\$\endgroup\$
1
\$\begingroup\$

Ruby - 70 bytes

λ cat inf.rb
n,=$*[0].unpack 'B*';loop{p n.to_i(2);n.tr!('10','01').sub!(/^0*/,'')}
λ ruby inf.rb Hello
310939249775
788572378000
310939249775
238816564112
36061342831
32658133904
1701604463
445879184
90991727
43226000
23882863
9671568
7105647
1282960
814191
234384
27759
5008
3183
912
111
16
15
0
inf.rb:1:in `block in <main>': undefined method `sub!' for nil:NilClass (NoMethodError)
        from inf.rb:1:in `loop'
        from inf.rb:1:in `<main>'

The program exits with an exception after completing, but my understanding is that that is fine as long as the error output goes to STDERR rather than STDOUT (which it does).

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

C, 147 135 133 125 122 121 117 115 103 bytes

Saved 5 bytes thanks to @Cyoce!

Saved 2 bytes thanks to @Cyoce and @cleblanc!

Saved 12 bytes thanks to @ceilingcat

i,n;main(p,v)char**v;{while(*v[1])i=i*256+*v[1]++;for(;printf("%d\n",n=i),i;i^=p-1)for(p=2;n/=2;)p*=2;}

Ungolfed:

int i;
int main (c,v) {
    char**v;
    while (*v[1]) /* put first command line argument into i as binary */
        i = i*256 + *v[1]++;
    while (i != 0) { 
        printf("%d\n",i);
        int p = 2,n = i;
        while (n /= 2) /* calculate smallest power of 2 > i */
            p *= 2;
        i ^= p - 1; /* flip bits */
    }
}
\$\endgroup\$
  • \$\begingroup\$ I think you can leave out the int declarations \$\endgroup\$ – Cyoce Nov 2 '16 at 20:52
  • \$\begingroup\$ You can also save a byte by converting the last while loop into a for loop \$\endgroup\$ – Cyoce Nov 2 '16 at 21:04
  • \$\begingroup\$ And you can change while(1) to for(;;) \$\endgroup\$ – Cyoce Nov 2 '16 at 23:31
  • \$\begingroup\$ @Cyoce I tried removing int declarations everywhere and got gcc -std=89 errors. But thanks for the for(;;) tip. I'll keep on trying to remove the int declarations :))) \$\endgroup\$ – Noodle9 Nov 3 '16 at 0:24
  • \$\begingroup\$ sorry, I didn't test it. I think it will work if you move them to the top (i;main(c,v)char**v;{...}). On mobile right now so I can't be sure \$\endgroup\$ – Cyoce Nov 3 '16 at 0:26
0
\$\begingroup\$

C, 129 120 117 110 107 105 Bytes

long long i,m,n;f(char*v){for(;*v;i<<=8,i+=*v++);for(;printf("%llu,",i),n=i;i^=m-1)for(m=2;n>>=1;m<<=1);}

Tested with

main (int c, char**v) {
    f(v[1]);
}

output

5291279215216915577,3932092821637860230,679593196789527673,473328307817319302,103132444486104185,40982743589751686,31074850448176249,4953946570787718,4053252683953273,450346943417222,112603010004089,28134478351238,7049893737593,1746199284614,452823970937,96931842950,40507110521,28212366214,6147372153,2442562438,1852404857,295078790,241792121,26643334,6911097,1477510,619641,428934,95353,35718,29817,2950,1145,902,121,6,1,0,
\$\endgroup\$
  • \$\begingroup\$ I think you can move i=0 to the declaration of i and leave the initialization section of the for loop blank \$\endgroup\$ – Cyoce Nov 2 '16 at 21:28
  • \$\begingroup\$ @Cyoce The function needs to work each time it's called and since i is implicit global int it needs to be initialized every time f(...) is called. \$\endgroup\$ – cleblanc Nov 3 '16 at 13:30
  • \$\begingroup\$ @Cyoce You were right after all. The function doesn't exit until i is zero again so it's still re-useable. \$\endgroup\$ – cleblanc Nov 3 '16 at 20:41
  • \$\begingroup\$ 102 bytes \$\endgroup\$ – ceilingcat May 25 at 17:27
0
\$\begingroup\$

C#, 360 359 bytes

using w=System.Console;using q=System.Convert;s={System.Func<int,int,string>S=q.ToString;string t="",f="";for(int i=0;i<s.Length;i++)t+=i>0?S(s[i],2).PadLeft(8,'0'):S(s[i],2);w.WriteLine(q.ToInt64(t,2).ToString());while(t!="0"){f="";foreach(var n in t)f+=n=='0'?'1':'0';t=f.TrimStart(new char[]{'0'});t+=t==""?"0":"";w.WriteLine(q.ToInt64(t,2).ToString());}};

Full program:

using w = System.Console;
using q = System.Convert;

class a
{
    static void Main()
    {
        System.Action<string> b = s =>
        {
            System.Func<int,int,string> S = q.ToString;
            string t = "", f = ""; // Var does not work here
            for(int i = 0; i < s.Length; i++)
                t += i > 0 ? S(s[i], 2).PadLeft(8, '0') : S(s[i], 2);
            w.WriteLine(q.ToInt64(t, 2).ToString());
            while(t != "0")
            {
                f = "";
                foreach (var n in t) f += n== '0' ? '1' : '0';
                t = f.TrimStart(new char[] { '0' });
                t += t == "" ? "0" : "";
                w.WriteLine(q.ToInt64(t, 2).ToString());
            }
        };

        b("Inf");
        b("Infinity");
        w.Read(); // prevent close in VS
    }
}
\$\endgroup\$
  • \$\begingroup\$ I don't do C#, but can var t="";var f=""; be var t="",f="" instead? Saves 5 bytes. \$\endgroup\$ – corsiKa Nov 4 '16 at 19:56
  • \$\begingroup\$ @corsiKa Yeah I tried that but it gave me an error, I guess cause it's var and not string. \$\endgroup\$ – Yodle Nov 4 '16 at 20:01
  • \$\begingroup\$ Actually, string does save one byte, so I guess I'll do it that way. \$\endgroup\$ – Yodle Nov 4 '16 at 20:02
  • \$\begingroup\$ Also can you make a z variable for zero to save those nasty quotes? \$\endgroup\$ – corsiKa Nov 4 '16 at 20:05
  • \$\begingroup\$ Just tried, it actually raises the bytecount because I can't replace both the string "0" and char '0' :( \$\endgroup\$ – Yodle Nov 4 '16 at 21:00

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.