[Tutor] newbie looking for code suggestions

[Bob Roher]

Danny Yoo wrote:
>>> 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!
>

Well, it looks good.  I'm still trying to figure out exactly what
you did there, though.  Once I figure out map() and reduce() a
little better I should be able to understand it.

Another approach I was thinking of was only using the last half
of the range (i.e. [(min+max)/2, max] ) to test for the
maximum_digit_total.  I can't think of any range of numbers where
the max digit total wouldn't be in the last half of the range.
For example, 1 to 100.  The max would be at 99, which falls in
the range [50,100].  Another arbitrary range, 1 to 1997, would
have a max at 999, which is the halfway point between those two
numbers.  I haven't tested this fully yet, but it looks accurate
so far.