How to resolve the algorithm Sailors, coconuts and a monkey problem step by step in the Python programming language
How to resolve the algorithm Sailors, coconuts and a monkey problem step by step in the Python programming language
Table of Contents
Problem Statement
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 he tosses it to a monkey and 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 in turn gets up 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 remaining coconuts are divided into five equal piles for each of the sailors, whereupon it is found that the pile of coconuts divides equally amongst the sailors with no remainder. (Nothing for the monkey in the morning.)
Let's start with the solution:
Step by Step solution about How to resolve the algorithm Sailors, coconuts and a monkey problem step by step in the Python programming language
Function monkey_coconuts with Parameterized Sailors (Inner Loop)
This function determines the initial number of coconuts needed to ensure each sailor receives an equal share every morning, including the last morning when there is only one coconut left. It uses an inner loop to check if the current number of coconuts (nuts) is valid.
Parameters:
sailors: The number of sailors (default is 5).
Function monkey_coconuts with Parameterized Sailors (Recursion)
This function performs the same task as the previous one, but it uses recursion to check if the current number of coconuts (nuts) is valid.
Parameters:
sailors: The number of sailors (default is 5).
Function wake_and_split
This helper function checks if a given number of coconuts (n0) can be distributed equally among n sailors on each waking, leaving one extra coconut for the last waking.
Parameters:
n0: The number of coconuts.sailors: The number of sailors.depth: The current depth (number of wakings remaining).
Function calcnuts
This function calculates the initial number of coconuts needed to ensure each sailor receives an equal share every morning, including the last morning when there is only one coconut left. It does this by finding the smallest integer x that satisfies the Diophantine equation:
(n-1)^n * x + n^(n+1) * y = (the total number of coconuts taken)
Parameters:
rems: A list of the number of coconuts taken by each sailor on each morning, with the last element being the number taken on the last morning.min_share: The minimum number of coconuts each sailor should receive on the last morning.
Function distribute
This function prints the distribution of coconuts among the sailors on each morning.
Main Program
The main program calls the monkey_coconuts function for several values of sailors and prints the results. It also calls the calcnuts function to calculate the initial number of coconuts needed for different numbers of sailors and prints the results.
Source code in the python programming language
def monkey_coconuts(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_coconuts(sailors)
print("\nFor %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))
def wake_and_split(n0, sailors, depth=None):
if depth is None:
depth = sailors
portion, remainder = divmod(n0, sailors)
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_coconuts(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_coconuts(sailors)
print("For %i sailors the initial nut count is %i" % (sailors, nuts))
# gives one solution of (x,y) for a x + by = c
def dioph(a, b, c):
aa,bb,x,y = a, b, 0, 1
while True:
q,a,b = a//b, b, a%b
x,y = y - q*x, x
if abs(a) == 1: break
if y*aa % bb != 1: y = -y
x,y = y*c, (c - aa*y*c)//bb
#assert(x*aa + y*bb == c)
return x,y
# rems: what monkey got each turn
# min_share: each sailor needs to get at least this many in the final round
def calcnuts(rems, min_share = 0):
n, r = len(rems) - 1, 0
c = (n - 1)**n
for x in rems: r,c = r + x*c, c//(n-1)*n
a, b = (n-1)**n, n**(n+1)
x, y = dioph(a, -b, r)
k = (min_share - y + a - 1)//a
return x + k*b, y + k*a
def distribute(nuts, monkey_nuts):
n = len(monkey_nuts) - 1
print("\n%d sailors, %d nuts:"%(n, nuts))
for r in monkey_nuts[:-1]:
p = (nuts - r)//n
print("\tNuts %d, hide %d, monkey gets %d" % (nuts, p, r))
nuts = p*(n - 1)
r = monkey_nuts[-1]
p = (nuts - r)//n
print("Finally:\n\tNuts %d, each share %d, monkey gets %d" % (nuts, p, r))
for sailors in range(2, 10):
monkey_loot = [1]*sailors + [0]
distribute(calcnuts(monkey_loot, 1)[0], monkey_loot)
# many sailors, many nuts
#for i in range(1, 5): print(10**i, calcnuts([1]*10**i + [0])[0])
You may also check:How to resolve the algorithm Pythagorean triples step by step in the Wren programming language
You may also check:How to resolve the algorithm Pierpont primes step by step in the M2000 Interpreter programming language
You may also check:How to resolve the algorithm Align columns step by step in the ooRexx programming language
You may also check:How to resolve the algorithm Balanced brackets step by step in the AppleScript programming language
You may also check:How to resolve the algorithm Zhang-Suen thinning algorithm step by step in the Perl programming language