0

This is a simple code,

def door_traversal():
    arr = []
    for i in range(1, 101, 1):
        arr.append(0)
    for i in range(1, 101, 1):
        for j in range(i, 101, i):
            arr[j] = not arr[j]

    count = 0
    for i in range(1, 101, 1):
        if arr[i] == 1:
            count += 1
    return count

I get the following error,

arr[j] = not arr[j]
IndexError: list index out of range

When I run the code in the debugger, I see that after executing the inner loop for the first time the program counter skips, it's never running the inner loop 100 times. I'm new to Python, any help appreciated.

6
  • 1
    Yes it is running - you're getting an exception in your inner loop. That's a different problem altogether Commented Aug 17, 2016 at 13:29
  • What do you mean it skips? Isn't that what you told the range to do? Skip by the value of i? Your list only has 100 elements and index starts at 0, not 1 Commented Aug 17, 2016 at 13:31
  • 1
    Is it because you are starting at index 1 and ending at index 100 instead of starting at index 0 and ending at index 99? Python uses 0-based indexing. Commented Aug 17, 2016 at 13:31
  • Yup but I can choose to start at 1 right? Commented Aug 17, 2016 at 13:33
  • @CodeMonkey why don't you want to start at zero? You can't re-index your list and magically make it start at 1, you're going to have to always create an empty/None element at the beginning of your list. That's going to make your future life terrible Commented Aug 17, 2016 at 13:37

5 Answers 5

2

Python list indices always start from zero. Thus, the following creates a list containing 100 elements, with indices from 0 to 99 (not from 1 to 100 as you might be expecting):

for i in range(1, 101, 1):
    arr.append(0)

Now, the following can try to access the element at index 100, which does not exist:

for i in range(1, 101, 1):
    for j in range(i, 101, i):
        arr[j] = not arr[j]

Hence the exception.

Sign up to request clarification or add additional context in comments.

3 Comments

Why does the element at index 100 not exist?
@CodeMonkey Because you appended to the list 100 times, and lists always start at index 0. The value of i in your append loop is irrelevant... only the number of times it loops matters.
Actually got it finally. Poor dumb me. Apologies.
2

you're accessing the indices from 1 to 101 but the first index of a list is 0, you should iterate with for i in range(100)

def door_traversal():
    arr = [0 for i in range(100)]

    for i in range(100):
        for j in range(100):
            arr[j] = not arr[j]

    count = 0
    for i in range(100):
        if arr[i] == 1:
            count += 1
    return count

if you want to use custom indices maybe you could use a dictionary

def door_traversal():
    arr = {}
    for i in range(1, 101, 1):
        arr[i] = 0
    for i in range(1, 101, 1):
        for j in range(i, 101, i):
            arr[j] = not arr[j]

    count = 0
    for i in range(1, 101, 1):
        if arr[i] == 1:
            count += 1
    return count

5 Comments

I don't want to start at 0, that's by choice, that's why i'm using the range function with (start:stop:skip).
ok but when you append elements to a list they will start from 0 anyway
You've completely changed my program logic, this is not what I want. I understand that index 0 exists, but I just don't want to do anything with that. Do you mean in python I can't start iterating a list from an arbitrary index.
you can access whatever index you want, the question is: does that list have the index? if you append 100 elements to a list the last valid index will be 99
@CodeMonkey it's not the starting position that is the problem, it's the end. range(1,101) will do what you want it to do, create a list with 100 elements. However, the one hundredth element still has a list index of 99, regardless. Calling arr[100] will fail.
1

You have some pretty fundamental errors in your understanding.

First, lists in python always start with an index of 0. A list of size 3 looks like this:

three = [0, 1, 2]

The indexes are the values themselves. And yes, you could ignore the first element, and create a list like so:

names = [None, 'Wayne', 'CodeMonkey', 'King Arthur']

But it has 4 elements. Everywhere in your code you're going to have to adjust this. Want to know the length? len(names) - 1. And so on and so forth. And if you're splitting your list, you're going to have to add values to those lists if you want consistent behavior:

these_names = names[:2]
those_names = [None] + names[2:]

That's pretty painful. Don't do that - just get used the the fact that the index of an element in the list means the start of the list + index elements. So the item at the start of the list is the list name, e.g. arr, plus [0] elements.

Here's your code re-written in a way that works, under the assumption that everything else is correct.

def door_traversal():                                             
    # If you really want a list with 101 elements,
    # So you can access the last item with `arr[100]` rather than `arr[99]`.               
    # If you're using Python2, `range` is a list                  
    # already.                                                     
    arr = list(0 for _ in range(101))
    # Or use a list comprehension
    arr = [0 for _ in range(101)]

    # There are probably better ways to do this, but it works now 
    # also, no need to provide the step size if it's 1            
    for i in range(1, 101):                                       
        for j in range(i, 101, i):                                
            arr[j] = not arr[j]                                   

    count = 0                                                     
    for i in range(1, 101, 1):                                    
        if arr[i] == 1:                                           
            count += 1                                            
    return count                                                  

print(door_traversal())                                           

Also, I probably would rename arr to doors, or visited_doors, if that's what they represent.

Comments

0

In this line you add 100 items to arr

    for i in range(1, 101, 1):
        arr.append(0)

So your arr array is 100 items long. Then in this loop:

    for i in range(1, 101, 1):
        for j in range(i, 101, i):
            arr[j] = not arr[j]

You say for i in between 1 and 101 you want to run the inner loop over j. The problem is that indices start at zero in Python, so arr[101] does not exist, only arr[100] If you want to ignore the index zero element, that's fine, you can start iterating through the array at index one, but the final element in the array will still be at place 100, as you have only added one hundred items to the list!

You can solve this with:

def door_traversal():
    arr = []
    for i in range(100):
        arr.append(0)

    for i in range(1, 100):
        for j in range(i, 100, i):
            arr[j] = not arr[j]

    count = 0
    for i in range(0, 100):
        if arr[i] == 1:
            count += 1
    return count

2 Comments

I understand that indices start at 0, but I still want to run from 1. My understanding is that range is non inclusive. So to run from 1 to 100, should I make the initial call 1 to 102. I'm not understanding really.
Fixed I think. If you want to run from 1, that's fine, you can start from 1, however your list only has 100 items in, therefore you cannot access any items after 100.
0

Index problems aside, please consider the following python idioms (with comments which are for pedagogical purposes only):

def door_traversal():
    """got doc?"""  # why does this func. exist?

    arr = [0] * 100  # list concatenation

    for i in range(1, 101, 1):
        for j in range(i, 101, i):
            arr[j] = not arr[j]
    return arr.count(1)  # use the list method

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.