14
\$\begingroup\$

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)
\$\endgroup\$
12
  • 1
    \$\begingroup\$ Related \$\endgroup\$ Sep 17, 2014 at 8:28
  • 2
    \$\begingroup\$ Its really not related to the "one ring to rule them all" problem at all. \$\endgroup\$
    – Will
    Sep 17, 2014 at 9:00
  • \$\begingroup\$ @RoyvanRijn you didn't mention anything about ascending order in your question - if i wouldn't have close vote as duplicate of, I would have on "unclear what you're asking". if the numbers must be in ascending order, then how can 10 (in your second example) can be right at the start of the sequence? \$\endgroup\$ Sep 17, 2014 at 9:09
  • 1
    \$\begingroup\$ @proudhaskeller doesn't the question specify descending order? "count down" being understood to mean descending order. \$\endgroup\$
    – Will
    Sep 17, 2014 at 9:11
  • 1
    \$\begingroup\$ Roy, I didn't vote to close as a duplicate. But explicitly mentioning related questions supplements the system's auto-guessing of related questions. @Will, of course it's related. Remove the early stopping condition and this question is asking you to implement a specific non-optimal strategy for the "one string to rule them all". \$\endgroup\$ Sep 17, 2014 at 10:08

7 Answers 7

11
\$\begingroup\$

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
\$\endgroup\$
1
  • 1
    \$\begingroup\$ Haha T-SQL, nice one! \$\endgroup\$ Sep 17, 2014 at 9:46
7
\$\begingroup\$

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.

\$\endgroup\$
1
  • 2
    \$\begingroup\$ Some standard char saves: Put things like p=o='' as optional params to the function; you can use * for and in n and r<1023 or maybe even r<1023*n; while x-1: can shave a space as while~-x. Also, it might be shorter to use a set of digits rather than a bit-mask to store which digits have been used. \$\endgroup\$
    – xnor
    Sep 17, 2014 at 21:44
5
\$\begingroup\$

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"
\$\endgroup\$
0
5
\$\begingroup\$

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
\$\endgroup\$
8
  • \$\begingroup\$ fantastic! How does the d=s,={''} work? \$\endgroup\$
    – Will
    Sep 18, 2014 at 5:39
  • 2
    \$\begingroup\$ @Will d=s,={''} is equivalent to d={''}; s,={''}. s,={''} uses sequence unpacking, a feature more commonly used in statements such as a, b = (b, a), but you can also use it to extract the only element from a single-element sequence. \$\endgroup\$
    – flornquake
    Sep 18, 2014 at 10:31
  • 1
    \$\begingroup\$ @flornquake Oh, my mistake. I think you can still do len(d)%11*n, though looks like it's moot with you using an exec loop. \$\endgroup\$
    – xnor
    Sep 18, 2014 at 19:15
  • 1
    \$\begingroup\$ @Will As background for why this clever trick is efficient, it's ironically longer to make an empty set set() than a single-element set {x}. So, flornquake initializes it with a filler member, and checks if it has all ten digits by seeing if it has eleven elements. Since the empty string needs to be initialized into s, it is made to serve as this filler member, combining these initializations to save chars. \$\endgroup\$
    – xnor
    Sep 18, 2014 at 19:17
  • 1
    \$\begingroup\$ @Will Yes, len(d)%11*n would've been nice. :) \$\endgroup\$
    – flornquake
    Sep 18, 2014 at 21:10
4
\$\begingroup\$

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
\$\endgroup\$
4
\$\begingroup\$

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";
\$\endgroup\$
2
\$\begingroup\$

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 :)

\$\endgroup\$
3
  • \$\begingroup\$ It shouldn't output what digits were recycled, only the counting down sequence after recycling \$\endgroup\$ Sep 18, 2014 at 10:24
  • \$\begingroup\$ Oh! is that ? All his examples were outputting that too. \$\endgroup\$
    – Optimizer
    Sep 18, 2014 at 10:31
  • \$\begingroup\$ @proudhaskeller Oh, I output the recycled chars too. Thanks, that'll save me some chars. \$\endgroup\$ Sep 18, 2014 at 11:50

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.