Interesting math problem

[Jeff Schwab]

BJörn Lindqvist wrote:
> Here is an interesting math problem:
> 
> You have a number X > 0 and another number Y > 0. The goal is to
> divide X into a list with length Y. Each item in the list is an
> integer. The sum of all integers is X. Each integer is either A or A +
> 1, those should be "evenly distributed."
> 
> Example:
> 
> 17 // 5 = 3 gives the list [3, 3, 4, 3, 4]
> 16 // 4 = 4 gives the list [4, 4, 4, 4]
> 113 // 50 = 2 gives the list [2, 3, 2, 3, 3, 2, 3, 2, 3, 3, 2, 3, 2,
> 3, 3, 2, 3, 2, 3, 3, 2, 3, 2, 3, 3, 2, 3, 2, 3, 3, 2, 3, 2, 3, 3, 2,
> 3, 2, 3, 3, 2, 3, 2, 3, 3, 2, 3, 2, 3, 3]
> 
> This algorithm is used a lot in programming. For example, for
> projecting a line on a pixel display. Your mission, should you choose
> to accept it, is to improve the code given below which is my best
> attempt and make it more succinct and easier to read. Preferably by
> using list comprehensions, map or even reduce....
> 
> def make_slope(distance, parts):
>     step = distance / float(parts)
>     intstep = int(step)
>     floatstep = step - intstep
> 
>     steps = []
>     acc = 0.0
>     for i in range(parts):
>         acc += floatstep
>         step = intstep
>         if acc > 0.999:
>             step += 1
>             acc -= 1.0
>         steps.append(step)
>     return steps
> 
> # Test code
> distance = 130
> parts = 50
> L = make_slope(distance, parts)
> assert(len(L) == parts)
> assert(sum(L) == distance)
> print L

def make_slope(distance, parts):
     if parts == 0:
         return []

     q, r = divmod(distance, parts)

     if r and parts % r:
         q += 1

     return [q] + make_slope(distance - q, parts - 1)


def self_test(distance=130, parts=51):
     L = make_slope(distance, parts)
     assert(len(L) == parts)
     assert(sum(L) == distance)
     print L

if __name__ == '__main__':
     for distance in range(1, 200):
         for parts in range(1, 200):
             self_test(distance, parts)