Solving the Monkey and coconuts problem

Numberphile had another great video which introduced me to the Monkey and coconut problem

The problem statement paraphrased from the video is:

Five sailors are shipwrecked on an island and collect a large pile of coconuts during the day. That night the first sailor wakes up and decides to take his first share early so tries to divide the pile of coconuts equally into five piles but finds that there is one coconut left over so tosses it to a monkey, he then hides "his" one of the five equally sized piles of coconuts and pushes the other four piles together to form a single visible pile of coconuts again and goes to bed.

To cut a long story short, each of the sailors gets up singly, once during the night and performs the same actions of dividing the coconut pile into five, finding that one coconut is left over and giving that single remainder coconut to the monkey.

In the morning (after the surreptitious and separate action of each of the five sailors during the night), The pile of coconuts are divided into five equal piles for each of the sailors and whereupon it is found that the pile of coconuts divides equally amongst the sailors with no remainder. (Nothing for the monkey in the morning).

The task is to calculate the minimum size of the initial pile of coconuts collected during the first day.

I choose to find a solution using a Python program.

Initial thoughts.

Thinking about how I could solve it I thought that I would write something that had a lot of cut-n-pasted code for the night time activities of each sailor followed by a slightly different copy where there is no remainder which models the next days final distribution.

That would lead to me creating another version using a loop for the night time activities and possibly folding in the last days division

Finally I could look at creating a recursive version.

The progression looked like a good idea and I set out to do just that.

First cut-n-paste code

I have removed the print statements that allowed me to debug this initial version but a quick google showed that this was giving the right answer and looked correct.

def monkey_coconuts_5sailors():
    "Hard coded and copy-pasted for only five sailors"
    nuts = sailors = 5
    while True:
        n0, wakes = nuts, []
        portion, remainder = divmod(n0, sailors)
        wakes.append((n0, portion, remainder))
        if portion <= 0 or remainder !=1:
            nuts += 1
            continue
        n0 = n0 - portion - remainder
        portion, remainder = divmod(n0, sailors)
        wakes.append((n0, portion, remainder))
        if portion <= 0 or remainder !=1:
            nuts += 1
            continue
        n0 = n0 - portion - remainder
        portion, remainder = divmod(n0, sailors)
        wakes.append((n0, portion, remainder))
        if portion <= 0 or remainder !=1:
            nuts += 1
            continue
        n0 = n0 - portion - remainder
        portion, remainder = divmod(n0, sailors)
        wakes.append((n0, portion, remainder))
        if portion <= 0 or remainder !=1:
            nuts += 1
            continue
        n0 = n0 - portion - remainder
        portion, remainder = divmod(n0, sailors)
        wakes.append((n0, portion, remainder))
        if portion <= 0 or remainder !=1:
            nuts += 1
            continue
        #
        n0 = n0 - portion - remainder
        portion, remainder = divmod(n0, sailors)
        wakes.append((n0, portion, remainder))
        if portion <= 0 or remainder !=0:
            nuts += 1
            continue
        else:
            break
    return nuts, wakes
 
nuts, wake_stats = monkey_coconuts_5sailors()
print('##', monkey_coconuts_5sailors.__doc__)
print("Initial nut count =", nuts)
print("On each waking, the nuts, portion taken, and monkeys share are:\n ", 
      wake_stats)

The output:

## Hard coded and copy-pasted for only five sailors
Initial nut count = 3121
On each waking, the nuts, portion taken, and monkeys share are:
  [(3121, 624, 1), (2496, 499, 1), (1996, 399, 1), (1596, 319, 1), (1276, 255, 1), (1020, 204, 0)]

Turn the copy-pasted code into a loop

Note that their is slightly different logic in the last section of code above and that is reflected in this second version

def monkey_coconuts1(sailors=5):
    "Parameterised the number of sailors using an inner loop"
    nuts = sailors
    while True:
        n0, wakes = nuts, []
        for sailor in range(sailors):
            portion, remainder = divmod(n0, sailors)
            wakes.append((n0, portion, remainder))
            if portion <= 0 or remainder !=1:
                nuts += 1
                break
            n0 = n0 - portion - remainder
        else:
            portion, remainder = divmod(n0, sailors)
            wakes.append((n0, portion, remainder))
            if portion <= 0 or remainder !=0:
                nuts += 1
                continue
            break
    return nuts, wakes
 
nuts, wake_stats = monkey_coconuts1(sailors=5)
print('\n##', monkey_coconuts1.__doc__)
print("Initial nut count =", nuts)
print("On each waking, the nuts, portion taken, and monkeys share are:\n ", 
      wake_stats)

Output:

## Parameterised the number of sailors using an inner loop
Initial nut count = 3121
On each waking, the nuts, portion taken, and monkeys share are:
  [(3121, 624, 1), (2496, 499, 1), (1996, 399, 1), (1596, 319, 1), (1276, 255, 1), (1020, 204, 0)]

Fold in the logic for the morning division

The code for the morning is similar to the code for each sailors nightly excursion except that there is no remainder for the monkey. This last procedural code version folds this last case into the loop with extra logic around the remainder checking.

I also take the opportunity to solve the case of there being six sailors not five.

def monkey_coconuts2(sailors=5):
    "Parameterised the number of sailors using an inner loop including the last mornings case"    
    nuts = sailors
    while True:
        n0, wakes = nuts, []
        for sailor in range(sailors + 1):
            portion, remainder = divmod(n0, sailors)
            wakes.append((n0, portion, remainder))
            if portion <= 0 or remainder != (1 if sailor != sailors else 0):
                nuts += 1
                break
            n0 = n0 - portion - remainder
        else:
            break
    return nuts, wakes
 
if __name__ == "__main__":
    for sailors in [5, 6]:
        nuts, wake_stats = monkey_coconuts2(sailors)
        print('\n##', monkey_coconuts2.__doc__)
        print("For %i sailors the initial nut count is %i" % (sailors, nuts))
        print("On each waking, the nut count, portion taken, and monkeys share are:\n ", 
              ',\n  '.join(repr(ws) for ws in wake_stats))

Output:

## Parameterised the number of sailors using an inner loop including the last mornings case
For 5 sailors the initial nut count is 3121
On each waking, the nut count, portion taken, and monkeys share are:
  (3121, 624, 1),
  (2496, 499, 1),
  (1996, 399, 1),
  (1596, 319, 1),
  (1276, 255, 1),
  (1020, 204, 0)

## Parameterised the number of sailors using an inner loop including the last mornings case
For 6 sailors the initial nut count is 233275
On each waking, the nut count, portion taken, and monkeys share are:
  (233275, 38879, 1),
  (194395, 32399, 1),
  (161995, 26999, 1),
  (134995, 22499, 1),
  (112495, 18749, 1),
  (93745, 15624, 1),
  (78120, 13020, 0)

Using Recursion

Function monkey_coconuts3 sets up for the recursive calling of wake_and_split which has a depth parameter to control the maximum depth of recursion and returns either None or the last integer division of nuts to sailors (in the morning) on success.

def wake_and_split(n0, sailors, depth=None):
    if depth is None:
        depth = sailors
    portion, remainder = divmod(n0, sailors)
    #print((n0, portion, remainder, depth))
    if portion <= 0 or remainder != (1 if depth else 0):
        return None
    else:
        return n0 if not depth else wake_and_split(n0 - portion - remainder, sailors, depth - 1)
 
 
def monkey_coconuts3(sailors=5):
    "Parameterised the number of sailors using recursion including the last mornings case"    
    nuts = sailors
    while True:
        if wake_and_split(n0=nuts, sailors=sailors) is None:
            nuts += 1
        else:
            break
    return nuts
 
if __name__ == "__main__":
    for sailors in [5, 6]:
        nuts = monkey_coconuts3(sailors)
        print('\n##', monkey_coconuts3.__doc__)
        print("For %i sailors the initial nut count is %i" % (sailors, nuts))

Output:

# Parameterised the number of sailors using recursion including the last mornings case
For 5 sailors the initial nut count is 3121

## Parameterised the number of sailors using recursion including the last mornings case
For 6 sailors the initial nut count is 233275

Rosetta Code Task

Oh yes, I also created a new task:   Sailors, coconuts and a monkey problem  from the last two versions of Python code.

END.