Interesting math problem

[BJörn Lindqvist]

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

 

[castironpi]

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

Hash functions create a uniform distribution too. But don't those use
shifting and modulo instead?

 

[Arnaud Delobelle]

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

OK then, using list comprehensions. It is more succint, is it easier
to read?

def slope(dist, parts):
return [(i+1)*dist/parts - i*dist/parts for i in xrange(parts)]
[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]
Smugly yours

 

[Ivan Illarionov]

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

Integer-only version:

def make_slope(distance, parts):
intstep, err = divmod(distance, parts)

steps = []
acc = 0
for i in range(parts):
acc += err
step = intstep
if acc >= parts:
step += 1
acc -= parts
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

 

[Jeff Schwab]

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)

 

[Jeff Schwab]

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

OK then, using list comprehensions. It is more succint, is it easier
to read?

def slope(dist, parts):
return [(i+1)*dist/parts - i*dist/parts for i in xrange(parts)]

That's awesome, but I sure hope you'd mix in a comment in real code.

 

[sturlamolden]

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)

Beautiful. If Python could optimize tail recursion, it would even run
fast.

 

[Marc Christiansen]

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)

Beautiful. If Python could optimize tail recursion, it would even run
fast.

This was my first thought, too. But tailcall optimisation wouldn't help
here. `make_slope` is not tail recursive, the `+` (aka list.extend) gets
executed after the recursion.

Marc

 

[Jeff Schwab]

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)

Beautiful. If Python could optimize tail recursion, it would even run
fast.

This was my first thought, too. But tailcall optimisation wouldn't help
here. `make_slope` is not tail recursive, the `+` (aka list.extend) gets
executed after the recursion.

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

q, r = divmod(distance, parts)

if r and parts % r:
q += 1

return make_slope(distance - q, parts - 1, (q,) + L)

 

[Terry Reedy]

| Marc Christiansen wrote:
| > This was my first thought, too. But tailcall optimisation wouldn't help
| > here. `make_slope` is not tail recursive, the `+` (aka list.extend)
gets
| > executed after the recursion.
|
|
| def make_slope(distance, parts, L=()):
| if parts == 0:
| return L
|
| q, r = divmod(distance, parts)
|
| if r and parts % r:
| q += 1
|
| return make_slope(distance - q, parts - 1, (q,) + L)

So mechanically rewrite (not tested) as

def make_slope(distance, parts, L=()):
if parts < 0: raise ValueError('do you want me to return?') #added
while parts:
q,r = divmod(distance, parts)
if r and parts % r: q += 1
distance, parts, L = distance-q, parts-1, (q,) + L
return L

tjr

 

[BJörn Lindqvist]

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

OK then, using list comprehensions. It is more succint, is it easier
to read?

def slope(dist, parts):
return [(i+1)*dist/parts - i*dist/parts for i in xrange(parts)]

Congratulations! You Won! Jeff Schwab's recursive approach is also
cool but this is the most interesting abuse of integer division I have
seen. I don't think any of the variants are readable at a first
glance, but with a comment it should be ok.

 

[Ivan Illarionov]

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

OK then, using list comprehensions. It is more succint, is it easier
to read?

def slope(dist, parts):
return [(i+1)*dist/parts - i*dist/parts for i in xrange(parts)]

Congratulations! You Won! Jeff Schwab's recursive approach is also
cool but this is the most interesting abuse of integer division I have
seen. I don't think any of the variants are readable at a first
glance, but with a comment it should be ok.

I really want to revive this discussion. Arnaud's approach is
definetly cool, but it turns out that in real-world situations it
doesn't work as succint as here.

Try to use it to draw a simple non-anitaliased line in a standrad
python array or buffer object. Suppose we have an array of unsigned
bytes called `buf` where each line takes `pitch` bytes. That's what I
got while trying to take advantage of this approach. No advantage at
all. And what about ability to port the code to C for speed?

def draw_line(buf, pitch, x, y, dx, dy):
if dx == dy == 0:
buf[y * pitch + x] = 0
return
xdir, ydir = 1, 1

if dx < 0:
xdir = -1
dx = abs(dx)
if dy < 0:
ydir = -1
dy = abs(dy)

if dy < dx:
steps = ((i+1) * dx / dy - i * dx / dy for i in xrange(dy))
for step in steps:
start = y * pitch + x
if xdir > 0:
buf[start : start + step] = array('B', [0] * step)
else:
buf[start - step : start] = array('B', [0] * step)
x += step * xdir
y += ydir
else:
steps = ((i+1) * dy / dx - i * dy / dx for i in xrange(dx))
for step in steps:
start = y * pitch + x
if ydir > 0:
for i in range(start, start + pitch * step, pitch):
buf = 0
else:
for i in range(start, start - pitch * step, -pitch):
buf = 0
x += xdir
y += step * ydir

Please, tell me that I'm wrong and it's really possible to draw lines,
do scan-conversion and so on with such a cool succint constructs!

 

[Arnaud Delobelle]

 > 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
 OK then, using list comprehensions.  It is more succint, is it easier
 to read?
 def slope(dist, parts):
    return [(i+1)*dist/parts - i*dist/parts for i in xrange(parts)]

Congratulations! You Won! Jeff Schwab's recursive approach is also
cool but this is the most interesting abuse of integer division I have
seen. I don't think any of the variants are readable at a first
glance, but with a comment it should be ok.

I really want to revive this discussion. Arnaud's approach is
definetly cool, but it turns out that in real-world situations it
doesn't work as succint as here.

Try to use it to draw a simple non-anitaliased line in a standrad
python array or buffer object. Suppose we have an array of unsigned
bytes called `buf` where each line takes `pitch` bytes. That's what I
got while trying to take advantage of this approach. No advantage at
all. And what about ability to port the code to C for speed?

def draw_line(buf, pitch, x, y, dx, dy):
    if dx == dy == 0:
        buf[y * pitch + x] = 0
        return
    xdir, ydir = 1, 1

    if dx < 0:
        xdir = -1
        dx = abs(dx)
    if dy < 0:
        ydir = -1
        dy = abs(dy)

    if dy < dx:
        steps = ((i+1) * dx / dy - i * dx / dy for i in xrange(dy))
        for step in steps:
            start = y * pitch + x
            if xdir > 0:
                buf[start : start + step] = array('B', [0] * step)
            else:
                buf[start - step : start] = array('B', [0] * step)
            x += step * xdir
            y += ydir
    else:
        steps = ((i+1) * dy / dx - i * dy / dx for i in xrange(dx))
        for step in steps:
            start = y * pitch + x
            if ydir > 0:
                for i in range(start, start + pitch * step, pitch):
                    buf = 0
            else:
                for i in range(start, start - pitch * step, -pitch):
                    buf = 0
            x += xdir
            y += step * ydir

Please, tell me that I'm wrong and it's really possible to draw lines,
do scan-conversion and so on with such a cool succint constructs!

I don't think my answer is suitable for drawing a line the way you are
doing it. FWIW, this is how I would go about it (not tested):

def draw_rectangle(buf, pitch, x, y, w, h):
# Make a mask for w and apply it across h lines

def draw_line(buf, pitch, x, y, w, h):
# w and h can't be < 0
if w < h:
limits = ((i, i*h/w) for i in xrange(1, w+1))
else:
limits = ((i*w/h, i) for i in xrange(1, h+1))
dx0, dy0 = 0, 0
for dx, dy in limits:
draw_rectangle(x+dx0, y+dy0, dx-dx0, dy-dy0)
dx0, dy0 = dx, dy

The positive thing is that it is trivial to extend draw_line so that
it accepts a thickness parameter as well.