Banana Camel puzzle

banana_camel_puzzle.py

#!/usr/bin/env python3

# Approximately solves the camel/bananas problem from
# https://www.youtube.com/watch?v=pDoar4zh5tI.

# NOTE: I really enjoyed going back to this  from a fresh perspective as
# I first saw it many years ago as a problem in a math class.

# The approach here is to _assume_ you are moving bananas in segments of a fixed
# length, d, and then ask how many bananas you can move in total with segments
# of that length. It's natural to start with 1 and then notice that this is
# inefficient becasuse the last trip for a given segment will eventually be
# nearly-empty (i.e., the camel will be using nearly 0 of its 1000-banana
# capacity). For example, consider 1-mile segments. With 3000 bananas to start,
# you have to do 3 forward trips (and 2 backward trips), for a total of 5
# bananas eaten per 1-mile segment. That's not so bad for the first mile, but by
# the time you reach mile 200, you're burning an entire trip to bring over very
# few bananas (at which point you now have 2000 bananas and are efficient with
# just 2 forward trips).
#
# By slicing the segments smaller and smaller, you approach the optimal
# solution. I haven't worked out the calculus, but I assume that integrating
# over the infinitesimals would give the exact same answer as the "traditional"
# solution. This is also a very intuitive way to solve the problem because it
# makes it very clear where the inefficiencies are coming from (and why they
# start to disappear as segment length goes down). Once you realize that you
# want all forward trips to operate at maximum capacity, it leads you right to
# the more traditional 3-legged solution.

import sys


def main():
    print("segment length\tbananas moved")
    for length in (1.0, 1 / 2, 1 / 5, 1 / 10, 1 / 100, 1 / 10000):
        n = solve_for_trip_length(length)
        print(f"{length}\t\t{n}")


def solve_for_trip_length(distance):
    n = 3000
    segments, rem = divmod(1000, distance)
    segments = int(segments)
    if rem > 0:
        segments += 1
    for segment in range(segments + 1):
        mile = segment * distance
        n = max_moved_naive(n, distance)
    return n


def max_moved_naive(n, distance):
    """Assuming you start at the "left" with `n` bananas, what's the max number
    of bananas you can move to the "right" assuming left and right are
    `distance` miles apart?"""

    def n_right_trips(n):
        # How many one-way trips are requred to the right?
        a, b = divmod(n, 1000)
        return a + (0 if b == 0 else 1)

    if n <= distance:
        return 0.0

    right_trips = n_right_trips(n)
    lengths = (right_trips - 1) * 2 + 1
    return n - (lengths * distance)


if __name__ == "__main__":
    main()