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

51–60 of 60 posts

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

#51

Post by Doxin »

lelanthran wrote: post #41
Doxin wrote: post #38

Earlier quoted context omitted.

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 expec…

Fair enough I suppose. Though I should mention that python is much better at these than a lot of dynamically typed languages. All of these give errors in python but return nonsense in e.g. javascript:

    1+"1"
    []+{}
    ({}).foo
    []/2
Of course there's the type checkers for python like mypy and pyright but in my experience the type systems these provide are wildly underpowered for statically typing even slightly more complex idiomatic python.

Re the num digits example: One way to go about this is to add asserts for checking the input types, though generally in python it's considered more idiomatic to check how an object behaves than what type it is.

In any case in practice I find that by far most type systems, bolted on or built in or otherwise, are more of a hassle than they are worth. One of the few exceptions I've found so far is D. When you rewrite the num digits function in D such that it accepts any type like the python example does, it should be of no surprise that it has the exact same bug as the python version:

    int numDigits(T)(T num){
        return num.to!string.length
    }
I'm not entirely sure what my point is other than to point out that typing in python isn't an afterthought. it just uses a different type system to what you're used to which allows for bugs you're not used to.

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

#52

Post by t-3 »

For base 2/16 this is pretty easy if you use assembly, because most ISAs have instructions to count the leading zeros, so for eg. aarch64 to get length of hex integer (assuming you're not trying to do anything weird like signed hex - negative numbers will always be max width this way):

  hlen:
        // int hlen(uint64_t x)
        // takes an integer, returns length of hex string
        mov     x9,     #16             // max width
        clz     x0,     x0              // count binary leading zeros
        cmp     x0,     #64
        lsr     x0,     x0,     #2      // 4 bits per hex digit
        sub     x0,     x9,     x0
        cinc    x0,     x0,     eq      // if num = 0, add 1
        ret
Decimal requires looping (well, only ~20 comparisons needed for 64-bit so maybe that could be unrolled but same thing either way), so it's simpler to just use high level.

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

#53

Post by dingaling »

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…

Why would mathematics be "completely obvious" when one is dealing with how a computer stores and represents data?

The 'clever' solution fails miserably on value zero and needs hard-coding to handle it. That looks like using the wrong tool.

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

#54

Post by chrismorgan »

dingaling wrote: post #53
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…

Why would mathematics be "completely obvious" when one is dealing with how a computer stores and represents data? The 'clever' solution fails miserably on value zero and needs hard-coding to handle it. That looks like using the wrong tool.

You’re misunderstanding me. I said that if you approach from the mathematics side of things, building on log₁₀ is the completely obvious approach to use. That is, if you’re already a mathematician, of course you’ll see if you can use logarithms, because that will be the way you’ll think—because you’ll view it as a mathematical and algorithmic task.

As for the handling of zero, well, that’s not about mathematics or about how a computer stores or represents data—that’s about how humans represent data. We choose to special-case zero, allowing it to have a leading zero which we never allow for anything else. All solutions in software will need to special-case zero.

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

#55

Post by benmmurphy »

i feel like using the log operator for avoiding a loop is also cheating as well because under the hood there is likely to be a loop. i would have expected the non-looping solution to use either recursion or some abuse of itertools which is really just using a loop as well.

  import itertools
  def digitLength(n):
    if n == 0:
      return 1
    *_, last = itertools.takewhile(lambda acc: acc[0] != 0, itertools.accumulate(itertools.repeat(None), lambda acc, x: (acc[0]//10, acc[1] + 1), initial=(n, 0)))
    return last[1]
the problem is interesting in python because i think the looping solution is not optimal because it performs N divisions for an arbitrarily large integer whereas I think there should be a solution that performs O(log(N)) multiplications for an arbitrarily large integer. in other languages with fixed integers its not really an issue how many operations you do since its effectively constant.

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

#56

Post by dang »

abpavel wrote: post #2

This is a fantastic example of how seemingly simple programming tasks can teach deep concepts. His methodical approach to uncovering edge cases and alternative solutions demonstrates the importance of critical thinking and comprehensive testing in software development, a valuable lesson for all developers.

Could you please stop posting like this and these?

https://news.ycombinator.com/item?id=40593805

https://news.ycombinator.com/item?id=40593787

https://news.ycombinator.com/item?id=40593761

https://news.ycombinator.com/item?id=40593688

https://news.ycombinator.com/item?id=40593664

We don't want generated comments on HN, or even human-generated summaries. They are too generic to produce interesting conversation, besides which we want people to actually look at, and perhaps even read, articles.

Fortunately your earlier comments look fine so this should be easy to fix!

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

#57

Post by schoen »

psychoslave wrote: post #50
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 ev…

I mean that the number 0 specifically can be written by empty string, so that we would count like

"", "1", "2", "3", "4", ..., "9", "10", "11", "12", ..., "99", "100", "101", ...

The only change is the empty string being a valid name for a number (the number zero).

I don't mean to suggest getting rid of place value or the digit 0! This is more like making the place value system more consistent with respect to a corner case.

And the practical reason that we can't make this change is that we don't have a way to distinguish in writing between the absence of any string and the presence of the empty string.

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

#58

Post by MrJohz »

fanf2 wrote: post #45
MrJohz wrote: post #11

Earlier quoted context omitted.

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.

But how do you do PBT here without having a known-correct algorithm available? Because that scenario is seldom the case in practice.

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

#59

Post by kristopolous »

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

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.

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

#60

Post by schoen »

psychoslave wrote: post #49
schoen wrote: post #46

Earlier quoted context omitted.

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.

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.
Post reply on HN