On: My favorite programming problem to teach: Digit le...

[chacham15]

Am I the only one who, in response to: "dont use loops" thought of the following:

   int numDigits(int num){
     if (num < 0){
       return numDigits(-1 * num);
     }
     if (num < 10){
       return 1;
     }
     if (num < 100){
       return 2;
     }
     if (num < 1000){
       return 3;
     }
     if (num < 10000){
       return 4;
     }
     if (num < 100000){
       return 5;
     }
     if (num < 1000000){
       return 6;
     }
     if (num < 10000000){
       return 7;
     }
     if (num < 100000000){
       return 8;
     }
     if (num < 1000000000){
       return 9;
     }
     return 10; // cant be more than 10 since sizeof(int) == 4, otherwise extend to 19
   }

[lelanthran → chacham15]

Might not work (I think Python supports bignums, not too sure).

I did this which will work with any length of number[1], and appears to work for all edge cases, including numbers that start with zero and doesn't use loops:

     (defun num-digits (n)
       (if (< n 10)
         1
         (+ 1 (num-digits (floor n 10)))))

[1] Millions of digits, if your computer has the RAM for it.

[kristopolous → chacham15]

The statements will duck type to numbers so you could just be really silly and do something like:

   return 1 + (n >= 10) + (n >= 100) + (n >= 1e3) + (n >= 1e4) + (n >= 1e5) + (n >= 1e6) + (n >= 1e7) + (n >= 1e8) + (n >= 1e9) ...

[schoen → kristopolous]

Heh, that gives this nice expression

  sum(n>=10**i for i in range(100))

for (for example) inputs up to a googol. Or with your fix for the base case,

  1 + sum(n>=10**i for i in range(1, 100))

Another cute way that hides the loop

  from itertools import count, takewhile
  1 + len(list(takewhile(lambda x: 10**x <= n, count(1))))

[kristopolous → schoen]

a way that follows the rules and also does what you're trying to do:

    def noloops(n):

      x = lambda n, digits: (n / 1e9, digits + (n >= 10) + (n >= 100) + (n >= 1e3) + (n >= 1e4) + (n >= 1e5) + (n >= 1e6) + (n >= 1e7) + (n >= 1e8) + (n >= 1e9))

      y = lambda n, digits: x(*x(*x(*x(*x(*x(n, digits))))))

      return y(*y(*y(*y(*y(*y(n, 1))))))[1]

Now we have it up to 324 digits without any loops.

[psychoslave → schoen]

How is that hiding the loop? I would expect takewhile to be a loop although I never used this Python facility.

[schoen → psychoslave]

All of the itertools functions are implemented using loops, but they heavily abstract over them so that users can think in terms of "streams" (or officially "iterators") without writing loop-oriented code themselves.

[MrJohz → chacham15]

Unfortunately in Python, integers have no fixed maximum size and can grow indefinitely, so your algorithm would need to be long enough to cover all the numbers that can conceivably fit in a computer's memory. I guess there's still a finite size there, but I'm not sure how the memory usage scales with digit length, so I don't know what the largest number would be.

[chacham15 → MrJohz]

Good point, I was thinking in Python 2 (where there are integer limits)

[Doxin → chacham15]

Not since python 2.5 if I recall correctly. Python has had unlimited size integers for a long time now.