CODEWITHSUNDEEP
python-3.x
tslnc04
tslnc04

Reputation: 17

Carry numbers in list

I am making a code guessing program that asks for an input of an example key code, then the program tries combinations of characters and finds how long it took.

What I need to do is have a function that takes in a list of numbers, and returns a list of numbers, the hard thing being that the length could be anything. I currently have this:

def increment(nums):

    nums[len(nums) - 1] += 1
    for i in range(len(nums)):
        if nums[-i + 1] == 62:
            nums[-i + 1] = 0
            nums[-i] += 1

    if nums[0] == 62:
        return [0 for n in nums]

    return nums

I am trying to make the last index increase, when that reaches 62, increment the second to last by 1, then set the last to 0, continuing on and on. Then, when the first number reaches 62, it returns a list of zeros.

The expected output is as follows:

[0,0,0,1]
[0,0,0,2]
[0,0,0,3]
[0,0,0,4]
...
[0,0,0,61]
[0,0,1,0]
...

The current output is as follows:

[0,0,0,1]
[0,0,0,2]
[0,0,0,3]
[0,0,0,4]
...
[0,62,0,0]

At this point I am confused. Is there anything I am doing wrong?

Upvotes: 0

Views: 70

Answers (2)

ShadowRanger
ShadowRanger

Reputation: 155363

Your indices in the carry loop are off, you're adding 1 and nothing, when you want to subtract 1 and 2:

def increment(nums):

    nums[-1] += 1  # len(nums) - 1 is a slow verbose way to index at -1 in Python
    for i in range(len(nums)):
        if nums[-i - 1] == 62:  # Change + 1 to - 1
            nums[-i - 1] = 0    # Change + 1 to - 1
            nums[-i - 2] += 1   # Change no adjustment to -2

    if nums[0] == 62:
        nums[:] = [0] * len(nums)  # Always mutate argument to match return

    return nums

This will still fail when you hit the wraparound case (due to an index out of bounds issue on the increment), and it involves more small math operations than needed, so we can improve it a bit and fix the bug by adjusting the range to run one fewer times, and remove two of the index fixups:

# Run one fewer times, iterate as negative numbers directly, and start
# from -1, not 0 so no adjustment needed for two of three lookups
for i in range(-1, -len(nums), -1):
    if nums[i] == 62:
        nums[i] = 0
        nums[i - 1] += 1

If speed was important, you could get a bit more clever with enumerate so you're usually not even doing indexing, but this is close to what you already had, and premature optimization is the root of all evil. :-)

Note that if the goal is just to make an iterator that produces lists of this form sequentially, as I mention in the comments, the itertools module provides simpler ways to do this. For memory reasons, we can't use itertools.cycle (it would end up eventually storing the entire run of values, about 15 million of them for the four element case), but we can simulate it using chain:

from itertools import chain, product, repeat

carrygen = chain.from_iterable(product(range(62), repeat=4) for _ in repeat(None))
next(carrygen)  # To skip all zero entry the first time around
carrygen = map(list, carrygen) # Returns lists instead of tuples
for nums in carrygen:
    print(nums)

which would output indefinitely starting with until you break the loop or kill the process:

[0,0,0,1]
[0,0,0,2]
[0,0,0,3]
[0,0,0,4]
...
[0,0,0,61]
[0,0,1,0]
...

Upvotes: 1

glibdud
glibdud

Reputation: 7840

I don't think your list indices are working like you expect in your for loop, but rather than try to unravel that, I'd suggest that this would be a good use for a recursive function:

def increment(nums):
    # Condition for ending the recursion when nums is empty
    if not nums:
        return []
    # Check if we're overflowing the last item...
    if nums[-1] < 61:
        # ...if not, just increment it and return
        nums[-1] += 1
        return nums
    else:
        # ...if so, strip it off, increment the rest of the list, and
        # tack on a 0 to the end
        return increment(nums[:-1]) + [0]

Upvotes: 0

Related Questions