0
\$\begingroup\$

This will be my very first post on stackexchange so bear with me.

Create a program that counts from 0 to 1,000,000,000. Now the trick is to not print all these characters but to only print how many zeroes are in that number. And keep track of the total amount of zeroes you've encountered. For example

10

Will output;

1
2

because 10 has 1 zero in it. The two represents how many 0's you've seen in total, in this case the only zero you have encountered previously is 0 itself so you've seen a total of 2 zeroes. The highest score will be given to the shortest code (no surprise here).

I hope that this is not too easy and that I've posted enough information, given the fact that I'm completely new here I'm not entirely sure about this.

\$\endgroup\$
5
  • 1
    \$\begingroup\$ You should have posted it in the sandbox if you weren't sure about that question. Remove your code-challenge tag, and that should be ok. \$\endgroup\$
    – Fabinout
    Commented Jan 14, 2014 at 9:54
  • 10
    \$\begingroup\$ This is similar to Count the zeros, differing only in two things: 1. shortest code rather than fastest - but given the length of some of the answers there this is a significant difference; 2. lack of parameter. It's generally a bad idea to hard-code the parameters in the question, because the shortest answer will usually be one which prints the solution without doing any real work. \$\endgroup\$ Commented Jan 14, 2014 at 10:16
  • \$\begingroup\$ It's not clear from your question if you want the number of zeroes for a single entry (and all zeroes up to that point), or for all numbers in a given range. Could you please clarify? \$\endgroup\$
    – SQB
    Commented Jan 14, 2014 at 15:32
  • \$\begingroup\$ The program counts to 1000,000,000 and with every number it has to calculate the number of zeroes in the current number and add them to the total amount of zeroes that is has seen. Then it moves on the the next number hand repeats this process until it reaches a billion. The final output should be 9, 788888899. \$\endgroup\$
    – Nils
    Commented Jan 14, 2014 at 15:37
  • \$\begingroup\$ Hi Sofa. Since you were asking for feedback, here's mine: 1) don't tell golfers how to write their algorithms (that removes some of the joy of coding, doesn't it?), and 2) heed @PeterTaylor's advice and parameterize the question with n to prevent a submission of something like this: puts 9, 788888899. \$\endgroup\$ Commented Jan 14, 2014 at 18:34

8 Answers 8

3
\$\begingroup\$

Python (brute force, 80 chars)

def r(n):
    l=[str(i).count('0') for i in xrange(n+1)]
    return l[-1],sum(l)

Just to asure, i got the task right, it evaluates to:

r(10)
>>> (1, 2)
r(1000000000)
>>> (9, 788888899)
\$\endgroup\$
5
  • 1
    \$\begingroup\$ You can make it even shorter by using i instead of str(i). I can't type the needed code, since it uses the char, that declares code on StackExchange. You have to surround i with `` \$\endgroup\$
    – user14325
    Commented Jan 14, 2014 at 15:37
  • \$\begingroup\$ @user14325 You mean `i`? (This is how I typed that: "You mean `\`i\``?") \$\endgroup\$
    – Doorknob
    Commented Jan 14, 2014 at 16:05
  • \$\begingroup\$ similar def s(n): print `n`.count('0'), sum(`i`.count('0') for i in xrange(n+1)) cuts to 67 chars \$\endgroup\$
    – njzk2
    Commented Jan 14, 2014 at 16:11
  • \$\begingroup\$ that is what i meant. Or even shorter: replace xrange by range. This makes the function slower but fast code is not the target here. \$\endgroup\$
    – user14325
    Commented Jan 14, 2014 at 17:10
  • \$\begingroup\$ @user14325 thanks, didn't know that one with `i`! However, using range I would consider cheating, as it won't work for r(1000000000). \$\endgroup\$
    – flonk
    Commented Jan 14, 2014 at 19:14
3
\$\begingroup\$

(Oracle) SQL, 146 144 chars / 122 chars

SELECT*FROM(SELECT l,SUM(REGEXP_COUNT(l,'0'))d FROM(SELECT LEVEL-1l FROM dual CONNECT BY LEVEL<=&a+1)GROUP BY ROLLUP(l))WHERE &a=l OR l IS NULL;

Expanded:

SELECT *
FROM (
   SELECT
      l,
      SUM(REGEXP_COUNT(l, '0')) d
   FROM (
      SELECT LEVEL - 1 l
      FROM dual
      CONNECT BY LEVEL <= &a + 1
   )
   GROUP BY ROLLUP(l)
)
WHERE &a = l
   OR l IS NULL;

Edit: no need to name the column, and * doesn't need spaces around it.


Okay, so we need it for all numbers from 0 to n. Let me put on my thinking cap... Try

SELECT c,SUM(c)OVER(ORDER BY l)FROM(SELECT l,REGEXP_COUNT(l,'0')c FROM(SELECT LEVEL-1l FROM dual CONNECT BY LEVEL<=&a+1));

Expanded:

SELECT
   c,
   SUM(c) OVER(ORDER BY l)
FROM (
   SELECT 
      l,
      REGEXP_COUNT(l, '0') c
   FROM (
      SELECT LEVEL - 1 l
      FROM dual
      CONNECT BY LEVEL <= &a + 1
   )
);
\$\endgroup\$
2
\$\begingroup\$

C, 90 bytes

r;i;j;main(t){for(;i<=10e8;j=++i){for(r=0;j;j/=10)j%10||r++;t+=r;}printf("%d\n%d\n",r,t);}

ungolfed:

r;i;j;main(t) {
    for (;i<=10e8;j=++i) {
        for (r=0;j;j/=10)
            j%10||r++;
        t+=r;
    }
    printf("%d\n%d\n",r,t);
}
\$\endgroup\$
3
  • 1
    \$\begingroup\$ you can save some characters by changing ?0: to || and by moving j=i from inner loop's init into outer's loop increment (j=i++) \$\endgroup\$
    – mniip
    Commented Jan 14, 2014 at 14:06
  • 2
    \$\begingroup\$ Why is this the accepted answer? The Python solution is shorter, and in general there is no accepted answer in questions like these, just scores in different languages. \$\endgroup\$
    – SQB
    Commented Jan 14, 2014 at 15:21
  • \$\begingroup\$ @mniip, cool thanks! Made the changes that you suggested. \$\endgroup\$
    – treamur
    Commented Jan 14, 2014 at 18:38
2
\$\begingroup\$

GolfScript 34 32

0 10.(?,{`{48=},,}%{(.p@+.p\.}do

Explanation:

The initial 0 will be the counter for the number of 0s seen thus far. A billion is 10^9, and 10.(? generates a billion by taking 10, copying it, decrementing, and then exponentiating. The , then generates an array of all numbers for 0 to a billion - 1. If we need to include one billion, add a ) before the ,.

The next block takes a number, converts it to a string by doing ''+, then filtering down to the characters that equals '0' (ASCII value 48) by doing {48=}, and then counting the length of the array by doing ,. Map this block across all the numbers in our array with %.

The next block expects two elements on the stack: the total 0s seen, and then the array of 0-counts for each integer not yet printed. Each time the block is executed it pops the first element of the array with (, copies and then prints it with .p, moves the total counter to the front with @, adds the current number, and then rearranges the stack to be in the right order. The do will run this block until the array is empty.

\$\endgroup\$
2
  • \$\begingroup\$ int ''+ is just int `, saving two. \$\endgroup\$ Commented Jan 14, 2014 at 19:59
  • \$\begingroup\$ @PeterTaylor Good catch! \$\endgroup\$
    – Ben Reich
    Commented Jan 14, 2014 at 20:11
1
\$\begingroup\$

APL (30)

Brute-forced. There is no lazy evaluation, so it generates the whole list from 0 to 1e9 at once. So you need at least a 7GB workspace, or it will just say WS FULL.

In case you don't have a huge server to use, the program can be proven to work by lowering 1e9 to a saner amount.

(⊃⌽Z),+/¯1↓Z←{'0'+.=⍕⍵}¨0,⍳1e9

Explanation:

  • 0,⍳1e9: the list from 0 up to and including 1e9
  • Z←{'0'+.=⍕⍵}¨: count the zeroes in each number, and store the list in Z.
  • +/¯1↓Z: the sum of all but the last item in Z (the total amount of zeroes encountered)
  • ⊃⌽Z: the last item in Z (the amount of zeroes in 1e9).
\$\endgroup\$
0
\$\begingroup\$

C# - 223 chars:

using System.Linq;class P{static void Main() { G(10); } static void G(int i){System.Console.Write("{0},{1}",i.ToString().Count(l => l == '0'),Enumerable.Range(0, i + 1).SelectMany(b => b.ToString()).Count(l => l == '0'));}}

Expanded:

using System.Linq;
class P
{
    static void Main() { G(10); } 
    static void G(int i)
    {
        System.Console.Write("{0},{1}", 
            i.ToString().Count(l => l == '0'), 
            Enumerable.Range(0, i + 1).SelectMany(b => b.ToString()).Count(l => l == '0'));
    }
}
\$\endgroup\$
0
\$\begingroup\$

Python 81 chars

def x(y):
    o=0
    for i in xrange(y+1):
        o+=`i`.count('0')
    print `y`.count('0'),o
\$\endgroup\$
4
  • \$\begingroup\$ I can't vote up yet, so I wanted to say that I really like this one. \$\endgroup\$
    – Nils
    Commented Jan 14, 2014 at 15:29
  • \$\begingroup\$ fix indentation, also get rid of extra white-spaces. \$\endgroup\$
    – Wasi
    Commented Jan 14, 2014 at 15:46
  • \$\begingroup\$ @Alkis, please fix it... it's not working. \$\endgroup\$
    – Timtech
    Commented Jan 14, 2014 at 15:52
  • \$\begingroup\$ Fixed it! Sorry \$\endgroup\$
    – user14730
    Commented Jan 14, 2014 at 15:56
0
\$\begingroup\$

J (33)

Warning: uses an ungodly amount of memory.

({:,+/@}:)(+/@('0'=":))"0 i.1e9+1

Explanation:

  • i.1e9+1: generate a list of numbers from 0 up to and including 1e9.
  • (+/@('0'=":))"0: for each number ("0), convert it to a string (#:), and see how many zeroes there are ('0'=).
  • ({:,+/@}:): display the last item in the list ({:), followed by the sum of all but the last item in the list (+/@}:)
\$\endgroup\$
1
  • 1
    \$\begingroup\$ I'm confused here. I hear tell that god is omniscient -- so a large amount of memory ought be godly. Are you warning us that this is memory efficient? \$\endgroup\$
    – boothby
    Commented Jan 14, 2014 at 18:57

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