4
\$\begingroup\$

I've been able to reduce my solution to constant time. Is it possible to reduce this by any constant factor further? (Besides trivialities i.e. inserting constants, not lazy importing). Specifically, I'd like to speed up fastMinPayout if there is a way to do it without using log.

Lovely Lucky LAMBs

Being a henchman isn't all drudgery. Occasionally, when Commander Lambda is feeling generous, she'll hand out Lucky LAMBs (Lambda's All-purpose Money Bucks). Henchmen can use Lucky LAMBs to buy things like a second pair of socks, a pillow for their bunks, or even a third daily meal! However, actually passing out LAMBs isn't easy. Each henchman squad has a strict seniority ranking which must be respected - or else the henchmen will revolt and you'll all get demoted back to minions again!

There are 4 key rules which you must follow in order to avoid a revolt:

  1. The most junior henchman (with the least seniority) gets exactly 1 LAMB. (There will always be at least 1 henchman on a team.)
  2. A henchman will revolt if the person who ranks immediately above them gets more than double the number of LAMBs they do.
  3. A henchman will revolt if the amount of LAMBs given to their next two subordinates combined is more than the number of LAMBs they get. (Note that the two most junior henchmen won't have two subordinates, so this rule doesn't apply to them. The 2nd most junior henchman would require at least as many LAMBs as the most junior henchman.)
  4. You can always find more henchmen to pay - the Commander has plenty of employees. If there are enough LAMBs left over such that another henchman could be added as the most senior while obeying the other rules, you must always add and pay that henchman.

Note that you may not be able to hand out all the LAMBs. A single LAMB cannot be subdivided. That is, all henchmen must get a positive integer number of LAMBs.

Write a function called answer(total_lambs), where total_lambs is the integer number of LAMBs in the handout you are trying to divide. It should return an integer which represents the difference between the minimum and maximum number of henchmen who can share the LAMBs (that is, being as generous as possible to those you pay and as stingy as possible, respectively) while still obeying all of the above rules to avoid a revolt.

For instance, if you had 10 LAMBs and were as generous as possible, you could only pay 3 henchmen (1, 2, and 4 LAMBs, in order of ascending seniority), whereas if you were as stingy as possible, you could pay 4 henchmen (1, 1, 2, and 3 LAMBs). Therefore, answer(10) should return 4-3 = 1

To keep things interesting, Commander Lambda varies the sizes of the Lucky LAMB payouts: you can expect total_lambs to always be between 10 and 1 billion (10 ^ 9).


''' Recursive form
Rules:
1) A0 = 1
2) An+1 !> 2*An
3) An-1 + An-2 !> An
4) n -> inf

Rewritten:
1) A0 = 1
2) An <= 2*An-1
3) An >= An-1 + An-2
4) n -> inf

Therefore:

A0 = 1, A-1 = 0, A-2 = 0
An-1 + An-2 <= An <= 2*An-1
'''


def maxPayout(LAMBs):
    '''
    Given An-1 + An-2 <= An <= 2*An-1
    An is maximized when An = 2*An-1
    '''
    # payouts[0] and payouts[1] exist as 'dummy' payouts
    payouts = [0, 0, 1]
    LAMBs -= payouts[-1]

    while (LAMBs >= 0):
        payouts.append(2*payouts[-1])
        LAMBs -= payouts[-1]

    # -2 for first two 'dummy' payouts and -1 for extra payout
    return len(payouts) - 2 - 1


def minPayout(LAMBs):
    '''
    Given An-1 + An-2 <= An <= 2*An-1
    An is minimized when An = An-1 + An-2
    '''
    # payouts[0] and payouts[1] exist as 'dummy' payouts
    payouts = [0, 0, 1]
    LAMBs -= payouts[-1]

    while (LAMBs >= 0):
        payouts.append(payouts[-1] + payouts[-2])
        LAMBs -= payouts[-1]

    # -2 for first two 'dummy' payouts and -1 for extra payout
    return len(payouts) - 2 - 1


def solution(total_lambs):
    return minPayout(total_lambs) - maxPayout(total_lambs)


def fastMaxPayout(LAMBs):
    '''
    Since maxPayout follows An = 2*An-1, maxPayout follows
    geometric sequence that can be reduced to exponential.

    An = 2^n

    Then we solve for sum(An = 2^n) <= LAMBs and the geometric
    series' sum formula follows:

    Sn = A0 * 1-r^n / (1-r)
    Sn = 1 * 1-2^n / (1-2)
    Sn = 2^n - 1

    Now we finally solve (Sn = 2^n - 1) <= LAMBs

    2^n <= LAMBs + 1
    n <= log2(LAMBs + 1)
    n = floor(log2(LAMBs + 1)) = (LAMBs + 1).bit_length() - 1
    '''
    return (LAMBs + 1).bit_length() - 1


def fastMinPayout(LAMBs):
    '''
    Since minPayout follows An = An-1 + An-2, minPayout follows
    a shifted Fibonnacci sequence. Apply Binet's formula to
    derive the nth Fibonnacci sequence.

    An-1 = Fn = ((1+sqrt(5) / 2)^n - (1-sqrt(5) / 2)^n) / sqrt(5)

    Substitute constants for variables to simplify

    let a = 1+sqrt(5) / 2
    let b = 1-sqrt(5) / 2
    let x = An-1 * sqrt(5)

    x = a^n - b^n
    a^n = x + b^n
    n = loga(x + b^n)ls

    And since lim n->inf b^n = 0, Binet's formula approximates:

    n = loga(x)

    Now we finally solve (Sn = An+2 - 1) >= LAMBs

    n+3 = loga(An+2 * sqrt(5)) = loga((An+2 - 1 + 1) * sqrt(5))
    n = loga((LAMBs + 1) * sqrt(5)) - 3
    '''
    from math import log, ceil, sqrt
    return int(ceil(log((LAMBs + 1 + 0.5)*sqrt(5), (1+sqrt(5)) / 2)) - 3)


def fastSolution(total_lambs):
    return fastMinPayout(total_lambs) - fastMaxPayout(total_lambs)


print(solution(143), fastSolution(143))
\$\endgroup\$
  • 2
    \$\begingroup\$ It's really nice that you provided the description of the problem, but would it be possible for you to move it out of the code section? \$\endgroup\$ – pacmaninbw May 1 at 19:22
5
\$\begingroup\$

FP arithmetic

Besides trivialities i.e. inserting constants

This is kind of a constant, but perhaps you'll view it as non-trivial. For one thing it allows turning a division into a (cheaper) multiplication.

Rather than supplying two args to math.log(), use this faster technique:

    # one-time init
    rad_five = sqrt(5)
    phi = (1 + sqrt(5)) / 2
    recip_phi = 1 / phi

    # compute log base b, that is, base phi
    log((LAMBs + 1 + 0.5) * rad_five) * recip_phi

Invoking with 1 arg and then multiplying definitely runs faster.

lookup table

We accept a number that is at most a billion, then compute lots of detailed mantissa bits, only to have ceil() discard most of them. Which is to say that the only input values you really care about are the ones that bump the log result past the next integer lattice point. Store such values in an ordered lookup table. Repeated multiplication by phi will help you find them.

At runtime, compute the relevant log result using binary search on the lookup table.

And yeah, you're right, you want to promote the imports to top-of-file.

\$\endgroup\$
  • 1
    \$\begingroup\$ I like both your suggestions. The first one isn't a 'constant' insertion per say for me because it changes how the logarithm operates. Secondly you make a good point about the look up table. I am thinking the arguments are rounded and delegated to a memoized function. \$\endgroup\$ – Michael Choi May 2 at 19:39
  • \$\begingroup\$ Hmm after actual testing, it seems that the functions do not return the same results. I am not sure what trick you are using but it may not apply here. \$\endgroup\$ – Michael Choi May 2 at 21:53
3
\$\begingroup\$

PEP-8

  • Python convention uses snake_case for variable and function names
  • Your spacing around numerical operators is not consistent

comments

Your comments are clear and they explain why something is done

payouts list

This list is unnecessary. You only use its last element and its length. Better would be to use just variables, just like a standard fibonacci generators, and itertools.count to keep track of the number of payouts

def max_payouts(lambs):
    payout = 1
    for i in count():
        if lambs <= 0:
            return i
        payout *= 2
        lambs -= payout


def min_payouts(lambs):
    a, b = 0, 1
    for i in count():
        if lambs <= 0:
            return i
        a, b = b, a + b
        lambs -= b
\$\endgroup\$
  • 1
    \$\begingroup\$ Hmm, ok that makes sense. Do you mind explaining min_payouts line a, b = b, a + b? I haven't seen that syntax before and I'm not quite sure what its doing. \$\endgroup\$ – Michael Choi May 2 at 17:43

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.