(Potential massive search-space) Is this an exponential problem?

[htyj6g9jv1ev6]

I'm writing a piece of software, however, my math skills are VERY rusty at the moment.

The problem is as follows:

1. There is a journey consisting of 256 steps
2. The person, can either i) walk, or ii) hop
3. The person can choose what to do at each step
4. I want to compute a list of all possible journey

I'm wondering if my attempt is futile... As the search-space may be too huge if this problem is indeed exponential.

My specific question is, how many ways are there through this journey? How many combinations of "walk" and "hop"?

I'm hoping that I'm wrong and the answer is not 2^256 (or around that area...). Otherwise I will have to abandon my simplistic brute force algorithm :D

Thank you!

 

[craigi]

I'm writing a piece of software, however, my math skills are VERY rusty at the moment.

The problem is as follows:

1. There is a journey consisting of 256 steps
2. The person, can either i) walk, or ii) hop
3. The person can choose what to do at each step
4. I want to compute a list of all possible journey

I'm wondering if my attempt is futile... As the search-space may be too huge if this problem is indeed exponential.

My specific question is, how many ways are there through this journey? How many combinations of "walk" and "hop"?

I'm hoping that I'm wrong and the answer is not 2^256 (or around that area...). Otherwise I will have to abandon my simplistic brute force algorithm :D

Thank you!

The answer is simply 2^256.

Test it out for smaller steps sizes.

2^1 = 2: 0,1
2^2 = 4: 00,01,10,11
2^3 = 8: 000,001,010,011,100,101,110,111

0 corresponding to walk
1 corresponding to hop

If you want to write your algorithm, it's incredibly easy. Just count from 0 to 2^256-1 writing out the number in 256 digit binary at each iteration. You'll need storage for 256 bits of precision, so you're not going to be able to rely on the built-in types, but you can handle this easily with nested loops. For 32-bit precision, you'll need 8 nested loops, then just write out the counters in 32-bit binary, in order.

The cool thing about this is that the order that the paths come out in, means that the early ones are valid for smaller step sizes too, so you can see where your computer stops making progress.

Was there a particular reason why you needed 256 steps?
Also is there a particular reason that you need a list of them?