Solving a recursive sequence
I've been solving some Google Foobar issues lately for fun and now I'm stuck with one for over 4 days. A recursive function is defined like this:
R(0) = 1
R(1) = 1
R(2) = 2
R(2n) = R(n) + R(n + 1) + n (for n > 1)
R(2n + 1) = R(n - 1) + R(n) + 1 (for n >= 1)
The challenge is to write a function answer(str_S)
where str_S
is the base-10 string representation of the integer S that returns the largest n
such that R(n) = S
. If there is no such n, return "None". Also, S will be a positive integer at most 10 ^ 25.
I had a lot of knowledge about recursive functions and about solving recurrent relationships, but no luck. I brought up the first 500 numbers and I didn't find anything to do with each one. I have used the following code which uses recursion so it gets very slow when the numbers start to get big.
def getNumberOfZombits(time):
if time == 0 or time == 1:
return 1
elif time == 2:
return 2
else:
if time % 2 == 0:
newTime = time/2
return getNumberOfZombits(newTime) + getNumberOfZombits(newTime+1) + newTime
else:
newTime = time/2 # integer, so rounds down
return getNumberOfZombits(newTime-1) + getNumberOfZombits(newTime) + 1
The challenge also included some test cases, so they:
Test cases
==========
Inputs:
(string) str_S = "7"
Output:
(string) "4"
Inputs:
(string) str_S = "100"
Output:
(string) "None"
I don't know if I need to resolve the recurrence to anything simpler, but since there is one for even and one for odd numbers and this is very difficult for me (I didn't learn about this in school yet, so all that I know about this subject - these are internet articles).
So, any help that can help me at all to complete this task would be appreciated :)
source to share
Instead of simplifying this function mathematically, I simplified the algorithm in Python. As suggested by @LambdaFairy, I have implemented memoization in the getNumberOfZombits (time) function. This optimization sped up the function a lot .
Then I moved on to the next step, trying to figure out how this number of rabbits contributed. I had analyzed this function before while watching its graph and I knew that the even numbers got higher outputs in the first place, and it was only after a while that the odd numbers hit the same level. Since we need the highest input for this output, I first had to look for even numbers and then into odd numbers.
As you can see, odd numbers always take longer than even to reach the same output.
The problem is that we couldn't look for numbers increasing by 1 every time (it was too slow). What I did to solve was to implement a binary search algorithm. First, I would search for even numbers (with a binary search similar to an algorithm) until I found one answer, or I had no more numbers to search for. Then I did the same thing with odd numbers (again, with a binary search algorithm similar to the algorithm), and if an answer was found, I would replace whatever I had with it (since it was necessarily more than the previous answer) ...
I have the original code that I used to solve it, so if anyone needs it, I don't mind sharing it :)
source to share
The key to solving this puzzle was using binary search.
As you can see from the sequence generators, they rely on roughly n / 2 recursion, so computing R (N) takes about 2 * log2 (N) recursive calls; and of course you need to do this for both odd and even.
It's not that bad, but you need to figure out where to look for N, which will give you the input. To do this, I first applied a search for upper and lower bounds for N. I went through N in powers of 2 until I had N and 2N, which were the lower and upper bounds, respectively, for each sequence (odd and even).
With these constraints, I could do a binary search between them to quickly find the value of N, or nonexistence.
source to share