CODEWITHSUNDEEP
pythonalgorithmruntime-error
The Internet
The Internet

Reputation: 8103

memoization in python, off by one errors

I'm currently taking an algorithms class. I'm testing a lot of them out in python, including dynamic programming. Here is an implementation of the bottom up rod cutting implementation.

It doesn't work because of the off-by-one error. Is there a global setting in python where I can change the default array index to be 1 and not 0? Or can someone please provide me with a better strategy for over-coming the off-by-one errors, which I encounter a million times. It's super annoying.

def bottom_up_memo_cut_rod(p,n):
    r = [ 0 for i in range(n) ]
    r[0] = 0
    for j in range(n):
        q = -1
        for i in range(j):
            q = max(q, p[i] + r[j-i])
        r[j] = q
    return r[n]

bottom_up_memo_cut_rod([1,5,8,9], 4)

answer should be 10 in this case cutting 4 into (2,2) yields the max price of 10.

Upvotes: 2

Views: 592

Answers (3)

Janne Karila
Janne Karila

Reputation: 25197

In Python, you can often avoid working with the indices altogether. That algorithm can be written like this:

def bottom_up_memo_cut_rod(p,n):
    r = [0]
    for dummy in p:
        r.append(max(a + b for a, b in zip(reversed(r),p)))
    return r[-1]

print bottom_up_memo_cut_rod([1,5,8,9], 4)
#10

Upvotes: 2

bereal
bereal

Reputation: 34282

In your case, off-by-one is a result of r[n] where len(r)==n. You either write r[n-1], or, more preferably, r[-1], which means "the last element of r", the same way r[-2] will mean "second last" etc.

Unrelated, but useful: [ 0 for i in range(n) ] can be written as [0] * n

Upvotes: -1

g.d.d.c
g.d.d.c

Reputation: 47978

There are a couple of things in Python that may help you. The built-in enumerate is a great one.

for idx, val_at_idx in enumerate(aList):
  # idx is the 0-indexed position, val_at_idx is the actual value.

You can also use list slicing with enumerate to shift indices if absolutely necessary:

for idxOffBy1, val_at_wrong_idx in enumerate(aList[1:]):
  # idx here will be 0, but the value will be be from position 1 in the original list.

Realistically though, you don't want to try to change the interpreter so that lists start at index 1. You want to adjust your algorithm to work with the language.

Upvotes: 3

Related Questions