[Tutor] newbie looking for code suggestions

[Danny Yoo]

> > I see that you're calculating it by finding the maximum number out of
> > the number range; it might just be easier to take the maximum outright
> > and use that.  Let's pretend we had a function that, given the lower
> > and upper ranges, tells us what the highest possible digit total can
> > be:
> >
> > ###
> > def maximum_digit_total(min_number, max_number):
> >     ## fix me!  We should really look at min_number and
> >     ## max_number here.
> >     return 9*6
> > ###

[some text cut]

> Thanks Danny, that helps some.  I still have a problem with that
> maximum_digit_total, though.  Can you explain what you meant for that?
> I thought I was being pretty slick when I put in a function that would
> add all the digits for the upper limit and use that as a digit total,
> but my wife tested the program for me and put in a range from 1 to 200.
> Of course, you can have a higher digit total than 2 in that range.  So,
> that's why I put it in the loop, since the only way I could think to
> calculate it was a simple compare and replace type of deal and I didn't
> want to have to run through a million number sequence twice.


Very true --- if the lower and upper range wraps around a power of ten,
then I think that's a special case that we can calculate really fast...
but for the general case of any range (like from 1 to 200), I'm not seeing
an obvious way of doing it yet.  An interesting problem!



Is it really necessary for us to go through the whole range to get the
maximum digit total?  I didn't think so at first, but now I'm not so sure.
I'll have to think about it some more.



Here's a heuristic approach that I'm taking on the problem: I don't yet
know if it's correct yet.

###
import string, operator

def maximum_digit_total(min_number, max_number):
    return sum(int_to_list(find_maximum_digits(min_number, max_number)))


def find_maximum_digits(min_number, max_number):
    width = max(len(str(min_number)), len(str(max_number)))
    maximum_digits = map(int, string.zfill(min_number, width))
    for i in range(width):
        while maximum_digits[width - i - 1] != 9:
            maximum_digits[width - i - 1] += 1
            if list_to_int(maximum_digits) > max_number:
                maximum_digits[width - i - 1] -= 1
                break
    return list_to_int(maximum_digits)


def list_to_int(digits):
    return int(''.join(map(str, digits)))

def int_to_list(number):
    return map(int, str(number))

def sum(l):
    return reduce(operator.add, l)
###

Here's a brief explanation of what find_maximum_digits() is doing: I first
convert things so that I'm working with a list of integers, just to make
manipulation easier.  My answer starts off being the lower limit, and
slowly try to improve the answer by incrementing, but by least significant
digits first.  I stop and undo things whenever I go over the max_number.



Here are a few tests I've done on this:

###
>>> maximum_digit_total(1, 1000)
27
>>> maximum_digit_total(1, 1)
1
>>> maximum_digit_total(1, 2)
2
>>> maximum_digit_total(1, 10)
9
>>> maximum_digit_total(1, 200)
19
>>> maximum_digit_total(1, 199)
19
>>> maximum_digit_total(199, 200)
19
>>> maximum_digit_total(1, 10**6)
54
###


But this should not be taken as conclusive proof that the function is
correct... *grin* By the way, this would be a great opportunity for
someone to show how to formulate the informal tests I've done as unit
tests.


I have to go at the moment though; I'll try to come back to this in the
evening.  Good luck!