[Tutor] newbie looking for code suggestions

[Danny Yoo]

> > 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)
> > ###
>
>
> 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.



If it helps, we can try it by hand.  Let's take the tricky range between
172 and 255.  The reason this is "tricky" is because our lower end of the
range is NOT 1, nor is our upper range in the even hundreds.  We have to
think deviously.  *grin*


The approach I'm taking is to start off with a guaranteed wrong answer,
and slowly turn it right.  I think I have a better understanding of the
problem now, and I hope I can explain it well.


Pretend that we all we know right now is that we have a starting number:

    starting = [1, 7, 2]

and we have some sort of maximum number 'maximum':

    target = [2, 5, 5]

What we're told off, initially, is that 'starting' is guaranteed to be
already smaller than our target, and at any given time, we can tell if
starting is ever larger than target, just by doing a simple comparision.

Our goal is to fiddle around with our starting number, and to get as many
digits as high as possible, without going over our maximum.


Well, we know that least significant digits matter the least, so perhaps
incrementing them will allow us to cautiously tread toward an answer.  We
can start by incrementing the right hand side of our starting number:

    [1, 7, 2] --->  [1, 7, 3] ---> ...all the way up to ...
                                   ---> [1, 7, 9]

And we stop incrementing the one's position.  We don't need to check
against [1, 8, 0]: if we do, that won't help, because rather than getting
closer toward maximizing the digit sum, we've taken a huge step backwards!

Let's see if we can do good by continuously improving our answer.  (This
is a "greedy" way of getting an answer, but in this case, I believe a
greedy solution does work.)

Now that we've improved our answer as far as we can get in the units
position, we start stepping, more courageously, through the units:

    [1, 7, 9] ---> [1, 8, 9] ---> [1, 9, 9]

... and we still haven't gone over the maximum limit of [2, 5, 5] yet, so
we're still good.  We're more confident now, so let's start incrementing
the hundreds position!

    [1, 9, 9] ---> [2, 9, 9] .... wait!

We've gone over!  So we can't improve the situation by incrementing the
hundreds position.  Our best answer, then, is the one we just calculated:
[1, 9, 9].


My mind is still sputtering a bit, but I think that when I can organizing
the ideas properly, I can give a formal induction proof of why this works.
But can someone else do it?  *grin*



> 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.

The case of [172--255] breaks this, as:

###
>>> (255 + 172) / 2
213
###

is out of the ballpark: our best answer can't be between 213 and 255,
because 199 beats everything in there:

###
>>> def digit_sum(n):
...     digits = map(int, str(n))
...     sum = 0
...     for d in digits: sum = sum + d
...     return sum
...
>>> digit_sum(199)
19
>>> max([digit_sum(x) for x in range(213, 256)])
15
###



> I can't think of any range of numbers where the max digit total wouldn't
> be in the last half of the range.

Diabolical is the key here.  If we're afraid of human bias, we don't pick
the numbers ourselves, but allow Python to pick them for us:

###
>>> import random
>>> random.randrange(1000)
895
>>> random.randrange(1000)
724
###



> 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.

The problem is that both endpoints are involved, and we've got to shake
around the left point as much as we do the right side.  That is, we've got
to move both ends in parallel.  Furthermore, we should try to stray get
away from nice round numbers.  The example:

min=277, max=388

is another great example where we could think go ahead and 'print 378' as
our answer, where in reality it's 299.



Again, thank you.  This was an even more fun problem than the original
problem that we started from.  *grin* Best of wishes to you!