My Favorite Programming Problem to Teach: Digit Length

I think if you tell stuff like this upfront it is totally acceptable: “Reduce the number of digits in a given float without converting it to a String”.

Even students with previous knowledge could take this as a challenge where they learn something.

The entire problem is arbitrary. It's not a real-world problem looking for a solution. It's a programming exercise.

I've taught CS courses before, and have seen plenty of self-proclaimed self-taught know-it-alls who seem to be more stackoverflow-copy-pasters than anything else.

This also fails my personal rule to always need to have a reason to do something mean - like failing someone on a problem, and no reason to do something nice - like saying it’s fine since it works.

Thinking outside the box is of course valuable, but the teachers have specific concept they want to teach and constraints like that help them accomplish that.

When it comes to tests, it’s not as easy. At tests it’s is more about solving the actual problem, but one could still argue that the test is meant to test how well one has learned what was thought, not to solve the problem.

I think this is totally fair in this case.

Thankfully this TA agreed with you (as do I). He said it looked good, and I think that's the shortest lab I ever had.

I'd just picked up python and was having so much fun going through the project Euler problems.

I can't remember which question it was for but we had to know the length of an integer. At that point I hadn't learnt about type conversion so had to implement it the way the author wants his students to do it.

I remember fondly as well that I hadn't learnt about the modulo operator and had to implement that by myself as well.

I couldn't believe it when I got the answer and progressed to the forum where others shared their answers and they were doing it on one line with %!

Good times!

I once got points taken off for using a recursive function as part of my solution. I didn't know the language before, nor did I have much experience with recursive functions as a formal concept.

I didn't even know at that time that recursive functions were a special thing that had to be taught to me.

If you prefer, you can view the problem restrictions as a means to encourage students to develop a more general algorithm for solving the problem, rather than a programmatic implementation specific to Python. Hopefully this makes them seem less arbitrary.

    >>> import math
    >>>
    >>> for i in range(1, 20):
    ...     n = int('9' * i)
    ...     digitLengthClever2 = math.floor(math.log10(n) + 1)
    ...     float_value = math.log10(n)
    ...     print(f'{n:<20} {digitLengthClever2:>2}  {float_value}')
    ...
    9                     1  0.9542425094393249
    99                    2  1.99563519459755
    999                   3  2.9995654882259823
    9999                  4  3.9999565683801923
    99999                 5  4.999995657033466
    999999                6  5.999999565705301
    9999999               7  6.99999995657055
    99999999              8  7.999999995657055
    999999999             9  8.999999999565706
    9999999999           10  9.99999999995657
    99999999999          11  10.999999999995657
    999999999999         12  11.999999999999567
    9999999999999        13  12.999999999999957
    99999999999999       14  13.999999999999996  # <-
    999999999999999      16  15.0                # <- 
    9999999999999999     17  16.0
    99999999999999999    18  17.0
    999999999999999999   19  18.0
    9999999999999999999  20  19.0

EDIT: Setting Decimal module's precision manually via getcontext() may be required if you work with "long" numbers.

    import math
    import numpy as np
    from decimal import getcontext, Decimal

    def digit_length_correct(n):
        return len(str(n))
    
    def digit_length_clever_2(n):
        if n ==0:
            return 1
        else:
            return math.floor((np.log10(Decimal(n)))) + 1 # You can use np.floor() and eschew the use of math. module altogether, but I left it intact to show the minimal necessary modifications
    
    def generate_cases(n):
        getcontext().prec = n + 3
        return (
        [10 ** i for i in range(n)] +
        [(10 ** i) - 1 for i in range(n)]
    )
    
    cases = generate_cases(300)
    
    for t in cases:
        a = digit_length_correct(t)
        b = digit_length_clever_2(t)
        assert a == b, (t, a, b)
    
    for t in cases[-2:]:
        print(t)
        print(digit_length_correct(t))
        print(digit_length_clever_2(t))

So, the discussion of this problem can be extended further into a discussion of specs, tradeoffs, benchmarking, etc.

One could say as well: this isn't programming, this is low level language tricks.

You don't need to know "how integers are manipulated into cpu" when learning to program, and at an introductory class like that described in the article you shouldn't either. There's a reason SICP at MIT was in Lisp and then Python.

I also very much doubt it would be "much more fun doing it in Assembly language".

The author went at length to explain how this is a useful exercize for programming, as it introduces edge cases, alternative implementations, testing, etc.

> Evaluating different solutions leads to natural questions about the definitions implicit in the problem statement: mathematically, what is digit length?

OF COURSE! This is a MATHEMATICAL problem that is posed as a PROGRAMMING question. This has always confused me and I could never justify until reading this article why I felt them to be irrelevant to showcasing my programming knowledge. At the very least just tell people, this is the mathematical reasoning behind it, and watch the person implement it.

    def digitlength(n):
        digits = 1
        while (n > 9):
            digits += 1
            n /= 10
        return digits

Edit: In C, the version that loops is 15 times faster than the version that allocates a new string. Python is weird.

> As a result, solutions using strings are disallowed on problem sets and quizzes until they are taught.

    def digit_length(n):
        totlen = 0
        n += not n
        while n > 0:
            klen = 1
            k = 10
            while n > k * k:
                k = k * k
                klen *= 2
            n = n // k
            totlen += klen
        return totlen

  fn digit_length_recursive(input: usize) -> usize {
      if input == 0 {
          0
      } else {
          1 + digit_length_recursive(input / 10)
      }
  }

  fn digit_length(input: usize) -> usize {
      std::cmp::max(digit_length_recursive(input), 1)
  }