7
\$\begingroup\$

Breeding like rabbits

Write a function answer(str_S) which, given the base-10 string representation of an integer \$S\$, returns the largest n such that \$R(n) = S\$. Return the answer as a string in base-10 representation. If there is no such n, return "None". S will be a positive integer no greater than \$10^{25}\$

where \$R(n)\$ is the number of zombits at time \$n\$:

$$\begin{align*} R(0) &= 1 \\ R(1) &= 1 \\ R(2) &= 2 \\ R(2n) &= R(n) + R(n+1) + n \quad\text{(for $n > 1$)} \\ R(2n+1) &= R(n-1) + R(n) + 1 \quad\text{(for $n \geq 1$}) \end{align*}$$

Test cases

>>> answer('7')
'4'
>>> answer('100')
None

My program is correct but it is not scalable since the range of \$S\$ can be a very large number like \$10^{25}\$.

Could anyone help me with some suggestions on improving the code further so that it can cover any input case?

def answer(str_S):

    d = {0: 1, 1: 1, 2: 2}
    str_S = int(str_S)
    i = 1
    while True:

        if i > 1:
            d[i*2] = d[i] + d[i+1] + i
            if d[i*2] == str_S:
                return i*2
            elif d[i*2] > str_S:
                return None

        if i>=1:
            d[i*2+1] = d[i-1] + d[i] + 1
            if d[i*2+1] == str_S:
                return i*2 + 1
            elif d[i*2+1] > str_S:
                return None

        i += 1

print answer('7')
\$\endgroup\$
  • 3
    \$\begingroup\$ In the future, please declare your cross-postings and include attribution for challenges. \$\endgroup\$ – 200_success Sep 13 '15 at 18:03
7
\$\begingroup\$

Comments on your code:

  • I’m surprised by the requirement that the input to answer() has to be a string, not an int.

    Since an int seems to be the natural input, I’d put most of the processing code in a separate function that only deals in ints, and do the string mangling at the very far edges of the program. Something like:

    def answer(str_S):
        result = answer_from_int(int(str_S))
        if result is None:
            return None
        else:
            return str(result)
    

    That allows you to separate the processing logic from the (somewhat unusual) interface.

  • There are no comments or docstrings in your code, which means that

    1. I don’t know what it’s supposed to do, and
    2. I don’t know why you wrote it this way.

    Knowing either of those would make the code substantially easier to read, review and maintain. Get into the habit of writing comments and docstrings – when you’re debugging your old code, you’ll thank yourself for it.

  • Choose more descriptive variable names. You can usually find more appropriate names than single characters, and the result is significantly more readable code. It’s much easier to follow the control flow if I’m following names instead of letters.


Comments on your approach:

You’re right, this won’t scale. You’re caching a huge number of results, most of which aren’t used. I did some quick experiments, and found that \$R(n) \approx 2n\$, which means that a 10^25 lookup is going to require a dict with 10^25 entries. Ouch.

You’re building up to find \$S\$, even if \$S\$ is huge. We can approach it much faster.

Here are a few suggestions:

  • Computing a single value \$R(n)\$ only needs a small subset of the values \$R(1)\$ to \$R(n-1)\$. By using the recurrence relations, you can get to it in very few operations (I think O(log n).)

    So rather than computing and caching every value you might need, only do that for the results you actually need. This will result in significant occupancy and processing savings.

    But how do we know which values of \$R(n)\$ we should look at?

  • Let's split the sequence into odd and even results, which I’ll define with the notation $$R_O(n) = R(2n) \qquad R_E(n) = R(2n+1)$$ Since all \$R(n)\$ are positive, both of these sequences are monotonically increasing. Further note that \$R(n) \geq n\$ for all \$n\$.

    As such, I know that if there is some \$n\$ such that \$R(n)=S\$, it must have \$0 \leq n \leq S\$. So we can do a binary search in the odd/even subsequences for \$S\$, and quickly find out whether it’s in either of the sequences (and then which has the larger value of \$n\$).

Here’s a skeleton class I wrote that allows me to efficiently compute zombit counts. The code isn’t complicated, so you can try filling it out:

class Zombit(dict):

    def __init__(self):
        # set up the initial values

    def lookup(self, N):
        # Get the value R(N), either from the cache or by computing from
        # the recurrence relations.  Remember to cache the result!

I can use this to look up \$R(6\cdot10^{300})\$ in a fraction of a second and with minimal occupancy. You’ll easily be within the bounds of the question, and then some. (Trying to go higher, I ran into Python’s max recursion depth.)

Setting up the binary search is a bit harder, but still not too complicated.

\$\endgroup\$
  • \$\begingroup\$ I am going to write the code for it. This is such a clever idea. Thank you \$\endgroup\$ – python Sep 12 '15 at 16:48
  • 3
    \$\begingroup\$ Using strings is probably a way to accommodate large numbers in a language-independent way. \$\endgroup\$ – 200_success Sep 13 '15 at 19:32
  • \$\begingroup\$ Doesn't R(n)>=n for all n breakdown for R5? R5=R(2*2+1)=R(1)+R(2)+1=1+2+1=4<5 \$\endgroup\$ – David Grinberg Dec 13 '16 at 5:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.