3

Lately I've been solving some challenges from Google Foobar for fun, and now I've been stuck in one of them for more than 4 days. It is about a recursive function defined as follows:

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 writing a function answer(str_S) where str_S is a base-10 string representation of an integer S, which returns the largest n such that R(n) = S. If there is no such n, return "None". Also, S will be a positive integer no greater than 10^25.

I have investigated a lot about recursive functions and about solving recurrence relations, but with no luck. I outputted the first 500 numbers and I found no relation with each one whatsoever. I used the following code, which uses recursion, so it gets really slow when numbers start getting 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, here they are:

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 solve the recurrence relation to anything simpler, but as there is one for even and one for odd numbers, I find it really hard to do (I haven't learned about it in school yet, so everything I know about this subject is from internet articles).

So, any help at all guiding me to finish this challenge will be welcome :)

Gonçalo Santos
  • 41
  • 1
  • 6
  • 1
    I think you have to know some advanced maths and use fast matrix exponentiation. – Piotr Dabkowski Dec 04 '14 at 19:49
  • 1
    This might help: http://stackoverflow.com/questions/1988804/what-is-memoization-and-how-can-i-use-it-in-python – Lambda Fairy Dec 04 '14 at 21:14
  • @LambdaFairy maybe this is it! I thought it wouldn't make that much of a difference but it turned out to be MUCH, much faster than before! Thanks! I'll try to implement it with this now, I'll tell you if it did the trick :D – Gonçalo Santos Dec 04 '14 at 22:12
  • @LambdaFairy, yes, it did work :) I had tried it before, but I must have made some error coding it and it turned out about the same velocity. Also, I didn't know that it was called Memoization. Well, with some other optimizations, I got it to work and find the answer in less than a second! Thanks! – Gonçalo Santos Dec 05 '14 at 14:53
  • @GonçaloSantos Do add your answer and accept it. It will enlighten all of us :) – Bhargav Rao Jan 02 '15 at 19:45
  • @BhargavRao Ohh, ok, I'll definitely do it! I'm a bit busy at the moment, but I'll do it as soon as I can :) – Gonçalo Santos Jan 03 '15 at 19:05

2 Answers2

1

Instead of trying to simplify this function mathematically, I simplified the algorithm in Python. As suggested by @LambdaFairy, I implemented memoization in the getNumberOfZombits(time) function. This optimization sped up the function a lot.

Then, I passed to the next step, of trying to see what was the input to that number of rabbits. I had analyzed the function before, by watching its plot, and I knew the even numbers got higher outputs first and only after some time the odd numbers got to the same level. As we want the highest input for that output, I first needed to search in the even numbers and then in the odd numbers.

As you can see, the odd numbers take always more time than the even to reach the same output. Plot of the function

The problem is that we could not search for the numbers increasing 1 each time (it was too slow). What I did to solve that was to implement a binary search-like algorithm. First, I would search the even numbers (with the binary search like algorithm) until I found one answer or I had no more numbers to search. Then, I did the same to the odd numbers (again, with the binary search like algorithm) and if an answer was found, I replaced whatever I had before with it (as it was necessarily bigger than the previous answer).

I have the source code I used to solve this, so if anyone needs it I don't mind sharing it :)

Gonçalo Santos
  • 41
  • 1
  • 6
0

The key to solving this puzzle was using a binary search.

As you can see from the sequence generators, they rely on a roughly n/2 recursion, so calculating R(N) takes about 2*log2(N) recursive calls; and of course you need to do it for both the odd and the even.

Thats not too bad, but you need to figure out where to search for the N which will give you the input. To do this, I first implemented a search for upper and lower bounds for N. I walked up N by powers of 2, until I had N and 2N that formed the lower and upper bounds respectively for each sequence (odd and even).

With these bounds, I could then do a binary search between them to quickly find the value of N, or its non-existence.

Sean
  • 1