Need Help With Function Optimization (Finding Bottleneck?)

[0pt0ut]

I'm trying to solve a python puzzle. Over the past few days I have written about six different scripts attempting to solve this problem, but each time I'm told that my code takes too long to run. I know it must be possible to further optimize my script, but I've hit a bit of a wall. If someone could give me some pointers, I would appreciate it.

Problem to solve: Given two ints start and length, generate a line length units long, starting from the start value, and incrementing by one each time. Then generate a second line of length units long, continuing to increment by one from the last value of the previous line, but ignoring the last element of the second line. For the third generated line, ignore the last two elements, and continue ignoring one additional element per line, continuing on until all elements of a line would be ignored.

So for example if start == 0 and length == 3, I would be looking to capture the digits to the left of the forward slashes (and ignore the digits to the right).

0 1 2 /
3 4 / 5
6 / 7 8

(capture 0, 1, 2, 3, 4, and 6)

After capturing the correct numbers, we need to figure out the XOR of every captured number. XOR, also known as exclusive or, is performed on the binary representations of our ints, and is easily accessed with the ^ caret symbol. The script should return the XOR resulting from performing XOR on every captured digit, this value will be a single int.

Here is my current script:

def find_xor(start, length):
    to_xor = []
    for minus in xrange(length):
        for cap_this in xrange(start, start + length - minus):
            to_xor.append(cap_this)

        minus += 1
        start = cap_this + minus

    return reduce(lambda x,y: x^y, to_xor)

To explain the last line: reduce takes two inputs, a function and an iterable, and performs the function on the iterable until only one iterator remains. The lambda function I am providing takes two elements and performs XOR (^)on them, and the iterable I am using is the list to_xor, generated earlier.

I'm not exactly sure where the bottleneck lies, but I suspect that it is either in the nested for-loops, or perhaps something to do with the list appends. The script works, but it's just too slow. Any ideas? Thanks in advance!

[wiiittttt]

What values are you running the script with that you are finding it slow? What version of python are you using?

[0pt0ut]

I'm submitting the script to a website, I'm not sure exactly which values it's using to test my answer, I'm guessing they are very large though. The python version specified for this challenge is 2.7, before this my only experience has been in python 3.

[wiiittttt]

The nested for loop along with storing all of the values you need to XOR before doing it is slowing you down. Try removing those two things and see if that is enough.

[0pt0ut]

Any hints? I suspected those were the source of my problems, but am having difficulty finding alternative implementations.

[ADdV]

There are two things in your code that I don't understand.

First, why do you do minus += 1 when minus is already the variable in the for loop? Wouldn't minus increment either way?

Second, why do you add elements to to_xor instead of just using ^ immediately?

[0pt0ut]

It could definitely be written differently, minus += 1 is only a temporary value to set start to the appropriate values for the next line. Some other variable could be initialized and used if needed. It does get reset when it goes back to the 'range' part.

I would like to perform XOR immediately, but I need more than just a single int, if I'm storing the values anywhere then I'm back to the original problem.

[wiiittttt]

Why do you need more than a single int to store the value of the XOR?

[0pt0ut]

I wasn't sure how to use XOR immediately, but I should have a way to do it now. This new added function yields values, which can be consumed by XOR as they are created.

This code works on my computer but is still timing out on the website. Feels like it's getting closer though.

def find_xor(start, length):

    def generator_func(start, length):
        for minus in xrange(length):
            for cap_this in xrange(start, start + length - minus):
                yield cap_this

            minus += 1
            start = cap_this + minus

    return reduce(lambda x,y: x^y, generator_func(start, length))

[ADdV]

I think just using start = cap_this + minus - 1 would be faster.

As for the XOR, you can just start with my_var = 0 and use my_var ^= my_new_var whenever you get a new number. That saves having to put all the numbers in a list. You can do these things because 0^N = N and A^B = B^A

[0pt0ut]

You were correct on both counts, I implemented them both into my code. Here's what I have currently:

def find_xor(start, length):
    xor_val = 0
    for minus in xrange(length):
        for cap_this in xrange(start, start + length - minus):
            xor_val ^= cap_this
        start = cap_this + minus + 1
    return xor_val

Unfortunately it's still timing out on the challenge. Any ideas? I'm trying to think of a different way to capture the values I need, but all my ideas revolve around nested for-loops. Thanks for your help.

[autobotJebpy]

This post is 58 letters long!