Countdown and recycle

Question

Countdown

Your goal for this code-golf challenge is to count down and meanwhile recycle numbers. Let me explain.

First your application reads a number, either as program argument or using stdin. Next you'll simply need to count down like this: 10 9 8 7 6 (in descending order)

But wait, there is more!

Recycling

There are situations where we can print every number, but don't list every number, we can do recycling! Let me give a quick example:

Input: 110

Output:   11091081071061051041031021010099... etc
Recycled:  10                        1

We've now still listed all the numbers, 110, 109, 108, but we've recycled a 0 and a 1.

Another example:

Input: 9900

Output:   9900989989897989698959894... etc
Recycled:        9 98  

Code-golf challenge

• Read a number (argument or stdin)
• Output the countdown in descending order while recycling all possible numbers (to stdout or file)
• Stop when you reach 1 OR the moment you've recycled 0 to 9 (whatever happens first)

Simple example (until 1 reached):

Input: 15
Output: 15141312110987654321

(Notice the 110 instead of 1110)

More advanced example (all recycled):

Input: 110
Output:   110910810710610510410310210100998979695949392919089887868584838281807978776757473727170696867665646362616059585756554535251504948474645443424140393837363534332313029282726252423221
Recycled:  10                            9                    8                    7                    6                    5                    4                    3                    2

(We've recycled all 0-9)

Answer 1

T-SQL - 291 277 267 217 199 191 166 158 153 145 142 128 117

After approaching this in a new way, I managed to get down to 145(142 after a couple minor tweaks), not too shabby. That means I might be able to compete for silver or bronze. ^^

DECLARE @ INT=100;WITH N AS(SELECT 1A UNION ALL SELECT A+1FROM N WHERE A<@)SELECT LEFT(A,LEN(A)-1+A%11)FROM N ORDER BY-A

This doesn't print a list, it selects the results. The question never gave specifics about output, so this should be fine. This still has the same limit of 100 on the input, partly because I'm abusing the fact that every 11th term under 100 loses a character and partly because of the default 100 recursion limit on common table expressions.

DECLARE @ INT=100;

WITH N AS
(
    SELECT 1A
    UNION ALL
    SELECT A+1
    FROM N
    WHERE A<@
)

SELECT LEFT(A,LEN(A)-1+A%11)
FROM N
ORDER BY-A

Answer 2

Python 143 147

def t(n):
 p=o='';r=0 # p is previous string, o is output string, r is recycled bitmap
 while n and r<1023: # 1023 is first 10 bits set, meaning all digits have been recycled
    s=`n`;i=-1 # s is the current string representation of n
       # i is from end; negative offsets count backwards in strings
    while p.endswith(s[:i])-1:i-=1 # find common ending with prev; s[:0] is '',
       # which all strings end with
    for j in s[:i]:r|=1<<int(j) # mark off recycled bits
    o+=s[i:];p=s;n-=1 # concatenate output, prepare for next number
 print o # done

First level indent is space, second level is tab char.

Answer 3

Python 2: 119 117

Marking this as community wiki because it is just a more golfed version of Will's answer.

n=input()
d=s,={''}
exec"t=`n`;i=len(t)\nwhile(s*i)[-i:]!=t[:i]:i-=1\ns+=t[i:];d|=set(t[:i]);n-=len(d)<11;"*n
print s

Answer 4

Ruby, 145 139 130 bytes

n=gets.to_i
d=*?0..?9
s=''
n.times{|i|j=(t=(n-i).to_s).size;j-=1 while s[-j,j]!=u=t[0,j];d-=u.chars;s=t;$><<t[j..-1];exit if[]==d}

Similar approach to Will's, except I'm not using a bit mask, but a set-like array of unused digits instead. Input is via STDIN.

There's an alternative version using while instead of times but whatever I try, the number of bytes is the same:

n=gets.to_i
d=*?0..?9
s=''
(j=(t=n.to_s).size;j-=1 while s[-j,j]!=u=t[0,j];d-=u.chars;s=t;$><<t[j..-1];exit if[]==d;n-=1)while 0<n

Answer 5

Haskell, 154 149 147 145 128 120 119 117 bytes

import Data.List
(r%x)n|n>0&&r<":"=[(r\\t)%(x++(show n\\t))$n-1|t<-tails x,isPrefixOf t$show n]!!0|0<1=x
h=['0'..]%""

adding in the recycling-checking cost a lot of characters... sigh

golfed a bit by remembering what digits weren't recycled yet and stopping when the list is empty. then golfed a bit more by moving to explicit recursion and a few more tricks.

example output:

*Main> h 110
"110910810710610510410310210100998979695949392919089887868584838281807978776757473727170696867665646362616059585756554535251504948474645443424140393837363534332313029282726252423221"

Answer 6

CJam, 80 77 65 57 54 Characters

Probably not at all optimized, but a After a lot of optimizations and debugging here is the direct conversion of my ES6 answer in CJam:

Mr{s:C_,{:H<M_,H->=!_CH@-@}g:T>+:MCT<_O@-+:O,A<Ci(*}h;

Try it online here. The function takes the number as STDIN and outputs the recycled countdown, stopping in between if recycling is complete.

I will try to golf it further.

How it works:

Basic idea is that for each countdown number C, check if the first H digits are equal to the last H digits of the resultant string, where H goes from number of digits in C to 0

Mr                                    "Put an empty string and input on stack";
  { ... }h;                           "Run while top element of stack is true, pop when done";
s:C                                   "Store string value of top stack element in C"
   _,                                 "Put the number of characters in C to stack";
     { ... }g                         "Run while top element of stack is true";
:H<                                   "Store the digit iteration in H and slice C";
   M                                  "M is the final output string in making";
    _,H-                              "Take length of M and reduce H from it";
        >                             "Take that many digits of M from end and..."
         =!_                          "Compare with first H digits of C, negate and copy";
            CH@                       "Put C and H on stack and bring the above result to top of stack";
               -                      "Reduce H if the matched result was false";
                @                     "Bring the matched result on top in order continue or break the loop"
             :T                       "Store top stack element in T after the loop";
               >+:M                   "Take everything but first T digits of C and add it to M and update M";
                   CT<_               "Take first T digits of C and copy them";
                       O@             "Put saved digits on stack, and rotate top three elements";
                         -            "Remove all occurence of first T digits of C from O";
                          +:O         "Add first T digits of C to O and update O";
                             ,A<      "Compare number of saved digits with 10";
                                Ci(   "Decrement integer value of C and put it on stack";
                                   *  "If number of saved digits greater than 9, break loop";

Answer 7

JavaScript ES6, 149 146 characters

Such verbose, much characters, wow.

C=n=>{s=c='';while(n>0&s.length<10){j=1;while(t=(n+'').slice(0,-j++))if(c.endsWith(t)){s+=~s.search(t)?'':t;break}c+=(n--+'').slice(1-j)}return c}

Run it in latest Firefox's Web Console.

After running, it creates a method C which you can use like

C(12)
12110987654321

UPDATE: Sometimes, plain old return is shorter than arrow function closure :)