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

11–20 of 60 posts

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

#11

Post by MrJohz »

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 written the algorithm, and there's not usually much point writing two algorithms unless, like here, one of those algorithms is trivial correct but inappropriate for some reason.

More generally, I feel like the more trivial a property is to check, the simpler the code to implement it is, and the less useful the test is in general. In the extreme case, a getter/setter pair is very easy to test with PBT, but you rarely need to be testing your getters and setters.

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

#12

Post by MrJohz »

vsnf wrote: post #9
MrJohz wrote: post #7

Earlier quoted context omitted.

And more importantly, because it sidesteps the interesting pedagogy around edge cases and testing that the instructor is interested in.

The correct solution here is to give credit for the problem to acknowledge genuine clever problem solving, and then offer extra credit for doing it the pedagogical way.

There is no correct solution here. A classroom is not a test environment.

The goal is to learn, and the point of the exercises is to teach a specific concept. If a student finds a different way around the problem, that may show that they're already proficient in other skills, but they haven't necessarily learned the concept being taught in this class yet. A good instructor would probably acknowledge the solution, but add extra boundaries to the task to get the student to explore the problem in a way that lets them encounter the testing difficulties discussed here.

It's like smuggling a calculator into a class about mental maths strategies: you'll probably do very well in the final test, but you won't have learned anything!

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

#14

Post by _xnmw »

nicbou wrote: post #4

Wouldn't len(str(num)) be adequate here? This is a quite literal translation of what the code should be doing: measuring the length of the text representation of a number. The mathematical approach seems a little convoluted, although it serves the purpose of teaching a lesson.

Len() and str() are a loop under the hood.

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

#15

Post by dmurray »

I would prefer a solution based on multiplication than division.

If the number is less than 10, return one, otherwise is it less than 100, ...

You should prefer the simplest tool that can do the job. Multiplication is simpler than division. You could digress about floating point errors (Python has infinite-precision integers, but not infinite- precision floats) or performance (division may be in some contexts meaningfully slower) but those are just digressions, the important thing is that it's more complicated.

The edge cases also seem completely clear to me in this approach, you won't accidentally write Of course, the division and log and string methods are all fine in practice, but I'm surprised not to see this alternative mentioned.

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

#17

Post by dang »

js2 wrote: post #3

(2019). Original submission was discussed at the time: https://news.ycombinator.com/item?id=21500434

Thanks! Macroexpanded:

My Favorite Programming Problem to Teach: Digit Length - https://news.ycombinator.com/item?id=21500434 - Nov 2019 (106 comments)

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

#19

Post by MrJohz »

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

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