Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

My favorite programming problem to teach: Digit length (2019)

jstrieb.github.io

Post reply on HN
Print view View original

41–50 of 60 posts

Re: My favorite programming problem to teach: Digit length (2019)

#41

Post by lelanthran »

Doxin wrote: post #38
lelanthran wrote: post #32

Earlier quoted context omitted.

> In Python it's as simple as len(str(x)). I consider that to be wrong - leading zeros are not part of the number and should be ignored. Using `len(str(x))` results in `2` for the input `"01"`.

It's assumed the input is an int. If not you can do len(str(int(x))) to make sure it is which strips leading zeroes off in the process.

That's really my beef with languages like Python - typing is an afterthought. I literally get more safety from C than I do from Python:

    def numDigits(num):
        return len(str(num))
    
    print (numDigits(1))      # Returns the correct answer
    print (numDigits("1"))    # Returns the correct answer
    print (numDigits("01"))   # Returns the incorrect answer
The "returns the wrong answer" is the problem. If the input is the wrong type, I expect there to be an error raised, not silently give me wrong answers.

Re: My favorite programming problem to teach: Digit length (2019)

#42

Post by lelanthran »

Thorrez wrote: post #39
lelanthran wrote: post #32

Earlier quoted context omitted.

> In Python it's as simple as len(str(x)). I consider that to be wrong - leading zeros are not part of the number and should be ignored. Using `len(str(x))` results in `2` for the input `"01"`.

The input "01" fails all the other solutions as well. You can't divide or take the log of a string.

> The input "01" fails all the other solutions as well. You can't divide or take the log of a string.

The other solutions fail differently - they generates an error and stop processing.

The `len(str())` failure doesn't generate an error, and doesn't stop processing, it simply returns the wrong answer.

So, the `len` approach is wrong, the other approaches are right.

Re: My favorite programming problem to teach: Digit length (2019)

#43

Post by romwell »

smarklefunf wrote: post #33
Strilanc wrote: post #23

It's very strange to me that the teacher would push the students from the correct solution using a loop, towards an incorrect solution using a logarithm. A logarithm could work in a language like C where ints can't get too large, but Python has arbitrary precision integers so any solution using floating point numbers is doomed. For example, the code given in the post returns 16 instead of 15 for 999_999_999_999_999.

I've come to the retrospective conclusion decades after educational abuse that professors like this are more interested in showboating their mathematics knowledge than drive students to find good pragmatic solutions. i.e. I know this super complex answer in which is it happens to be the only purely accurate thing. Can you guess it? vs what I would like to see which is: here are the foundational concepts, bring them a…

Professors?

This post was written by an undergraduate student.

A professor would use that as a teaching opportunity to discuss the folly of relying on floating point numbers.

Re: My favorite programming problem to teach: Digit length (2019)

#44

Post by romwell »

Strilanc wrote: post #23

It's very strange to me that the teacher would push the students from the correct solution using a loop, towards an incorrect solution using a logarithm. A logarithm could work in a language like C where ints can't get too large, but Python has arbitrary precision integers so any solution using floating point numbers is doomed. For example, the code given in the post returns 16 instead of 15 for 999_999_999_999_999.

>It's very strange to me that the teacher would push the students from the correct solution using a loop, towards an incorrect solution using a logarithm

That's because the teacher here is an undergraduate student who has yet to learn from painful experience :)

Re: My favorite programming problem to teach: Digit length (2019)

#45

Post by fanf2 »

MrJohz wrote: post #11
chrismorgan wrote: post #5

> a clever, unintuitive solution to a difficult problem If you approach from the mathematics side of things, building on log₁₀ is the completely obvious approach to use. If it seems unintuitive, that’s just because you don’t understand logarithms. > the autograding test cases did not include a test using a power of 10. That’s a pretty glaring oversight. Boundary cases are probably the most important things to cover i…

I'm not sure about the property-based testing thing. In this example, yes, you can easily write a test case that compares against the string-based algorithm. But in general, this is one of the biggest weaknesses of PBT, which is that you need to find a good property to test. In a lot of cases, the most useful property is "for all inputs, the result is the right answer", but we don't know the right answer until we've…

Counting digits is very closely adjacent to the general category of parsing and printing (or serialization/deserialization), which are both tricky to get right and have simple correctness tests. They are perfect candidates for property-based testing.

Re: My favorite programming problem to teach: Digit length (2019)

#46

Post by schoen »

kristopolous wrote: post #28
chacham15 wrote: post #13

Am I the only one who, in response to: "dont use loops" thought of the following: int numDigits(int num){ if (num

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

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

Re: My favorite programming problem to teach: Digit length (2019)

#47

Post by schoen »

I'm belatedly warming up to the idea that the digit length of the number zero is actually zero in various senses. (A footnote in the article points out that we could define it this way and then some students' simpler solutions would actually be considered correct.)

Yes, we obviously normally use a single digit to write zero, but we could logically write it as the empty string "" if we had a way to indicate that a specific number was meant. (Relative to that, writing 0 is just as unnecessary as writing 00 or 000, because we can have a rule that all leading zeroes need not be written.)

As another example of this intuition, suppose that we wrote all integers with a trailing decimal point. In that case the numbers from 1 to 10 would be "1.", "2.", "3.", "4.", "5.", "6.", "7.", "8.", "9.", and "10.", while zero could quite logically just be "." with no digits (as it has only leading zeroes, or we could say "nothing in the ones' place").

Quite a lot of arithmetic algorithms would probably work just fine with these conventions! In fact, they might have fewer exceptions or special cases than they do when they expect an explicit 0.

For instance, using the "zero is written as empty string" convention, Python int() (here simplified to assume input strings of zero or more decimal digits) and str() could look like

  def int(s):
      n = 0
      for c in s:
          n *= 10
          n += "0123456789".find(c)
      return n

  def str(n):
      s = ""
      while n:
          n, d = divmod(n, 10)
          s = "0123456789"[d] + s
      return s
Seems pretty general! Yes, it's annoying or confusing if the output is going to be viewed by a human user in a larger string context without delimiters, as we probably don't want to see things like "I ate tomatoes" instead of "I ate 0 tomatoes".

Re: My favorite programming problem to teach: Digit length (2019)

#49

Post by psychoslave »

schoen wrote: post #46
kristopolous wrote: post #28

Earlier quoted context omitted.

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

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

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

Re: My favorite programming problem to teach: Digit length (2019)

#50

Post by psychoslave »

schoen wrote: post #47

I'm belatedly warming up to the idea that the digit length of the number zero is actually zero in various senses. (A footnote in the article points out that we could define it this way and then some students' simpler solutions would actually be considered correct.) Yes, we obviously normally use a single digit to write zero, but we could logically write it as the empty string "" if we had a way to indicate that a spe…

Aren’t you mixing up 0 the digit and 0 the number here?

Certainly we can use the empty string to denote the number zero, but it doesn’t mean that we have a straight forward convention for how we denote any number which have some null value in some power lower than the most significant one.

Not that it’s impossible to come with some convention that ditches 0 as intermediary digit. For example 302009==3e5+2e3+9 will evaluate to true in many languages out there. In Ruby we even have `302009 === 3e5+2e3+9+''.to_i` that is evaluated to true.

But this notation loses the conveniences afforded by a positional fixed base numeral system provides.

Post reply on HN