Sailors, coconuts and a monkey problem: Difference between revisions

;C.f:

* [https://www.youtube.com/watch?v=U9qU20VmvaU Monkeys and Coconuts - Numberphile] (Video) Analytical solution.

<br><br>

 

=={{header|Bc}}==

This script implements a solution in the coconuts function for a number of sailors > 1 and a number of monkeys between 1 and sailors-1. It also executes the coconuts function for some values of sailors/monkeys.

 

print "coconuts(", sailors, ", ", monkeys, ") = "

if (sailors < 2 || monkeys < 1 || sailors <= monkeys) {

coconuts(5, 4)

coconuts(6, 1)

 

{{out}}

This is a translation of the second C solution. The output lists the number of sailors, the size of the original pile, and the final share each sailor receives the following morning.

 

nvg10*g10:+>#1$<

#>\:01g1-%#^_:0v

-|:-1\+1<+/-1g1<

1>$01g.">-",,48v

 

{{out}}

=={{header|Bracmat}}==

{{trans|Tcl}} (Though without the <code>assert</code> procedure.)

= a b

. !arg:(?a.?b)&(div$(!a.!b).mod$(!a.!b))

& minnuts$!n

)

 

Output:

 

=={{header|C}}==

int valid(int n, int nuts)

}

return 0;

{{out}}

<pre>2: 11

But it's faster to search backwards: if everyone receives some coconuts,

see if we can backtrack to the original pile:

 

// calculates if everyone got some nuts in the end, what was the original pile

}

return 0;

{{out}}

sailers: original pile, final share

</pre>

 

{{trans|Java}}

{

static bool valid(int n, int nuts)

}

}

 

<pre>2: 11

8: 117440505

9: 387420481</pre>

 

=={{header|D}}==

{{trans|Kotlin}}

import std.stdio;

 

}

}

 

{{out}}

{{trans|Ruby}}

===Brute Force===

def valid?(sailor, nuts), do: valid?(sailor, nuts, sailor)

n - 1 - d

end)

 

{{out}}

 

===Faster version===

def coconuts(sailor), do: coconuts(sailor, sailor)

defp coconuts(sailor, nuts) do

Enum.each(2..9, fn sailor ->

IO.puts "#{sailor}: #{Sailor.coconuts(sailor)}"

 

{{out}}

=={{header|Forth}}==

{{trans|uBasic/4tH}}

over * over 1- rot 0 ?do

over over mod if dup xor swap leave else over over / 1+ rot + swap then

;

 

{{out}}

<pre>2: 11 1

8: 117440505 5044200

9: 387420481 14913080 ok</pre>

 

=={{header|Haskell}}==

This program works by applying a function to increasing multiples of the number of sailors. The function takes a potential final number of coconuts (at the time the sailors awaken) and works backwards to get to the initial number of coconuts. At every step, it will abort the computation if the current number of coconuts can't arise as a result of splitting the previous pile.

 

 

-- Takes the number of sailors and the final number of coconuts. Returns

tryFor :: Int -> Int -> Maybe Int

tryFor s = foldr (>=>) pure $ replicate s step

 

-- Gets the number of sailors from the first command-line argument and

main :: IO ()

main = do

Examples:

<pre>

Here, we assume an answer which is less than 10000, and try each possibility, constraining ourselves to the list of answers which are valid. (As it happens, there's only one of those.)

 

 

These sailors must count coconuts extremely quickly.

When we do this with six sailors, it turns out that we have to assume a larger initial value:

 

 

If it were not obvious which of the answers here was the minimum value we could additionally pick the smallest value from the list. But that would require typing two extra characters (for example, replace I. with i.&1), and most people already have so much trouble reading J that the extra code would surely be too much.

=={{header|Java}}==

{{trans|C}}

 

static boolean valid(int n, int nuts) {

}

}

<pre>2: 11

3: 25

( As in the recursive Python example )

 

 

// wakeSplit :: Int -> Int -> Int -> Int

return intNuts;

});

 

{{out}}

 

 

===ES6===

 

// wakeSplit :: Int -> Int -> Int -> Int

 

) : intNuts;

 

 

 

 

let v = x;

 

 

 

 

{{Out}}

 

=={{header|jq}}==

 

If your jq does not have "until" defined, here is its definition:

 

===Simulation===

# the night-time squirreling away of the coconuts by "sailors" sailors, then give 1 to the

# monkey, let one sailor squirrel away (1/sailors) coconuts, and yield the remaining number;

 

# Test whether the input is a valid number of coconuts with respect to the story:

'''Five sailors''':

Find the minimum number of coconuts if there are 5 sailors --

start at 1 as there must be at least one to give to the monkey during the night:

{{out}}

3121

Find the minimum number of coconuts if there are 6 sailors --

start at 1 as there must be at least one to give to the monkey during the night:

{{out}}

233275

 

===Working backwards===

# the surreptitious squirreling away by one sailor,

# then emit the number of coconuts which that sailor originally

" and each sailor finally ended up with \(.[0])." ;

{{out}}

With 3 sailors, there were originally 25 coconuts, and each sailor finally ended up with 2.

With 4 sailors, there were originally 765 coconuts, and each sailor finally ended up with 60.

With 6 sailors, there were originally 233275 coconuts, and each sailor finally ended up with 13020.

With 7 sailors, there were originally 823537 coconuts, and each sailor finally ended up with 39990.

 

=={{header|Kotlin}}==

 

fun main(args: Array<String>) {

}

}

 

{{out}}

</pre>

 

 

 

 

 

 

my @shares;

}

}

 

}

}

}

 

{{out}}

Sailors 1: Coconuts 1:

1st takes 0, gives 1 to the monkey.

 

Sailors 2: Coconuts 3:

 

Sailors 5: Coconuts 3121:

 

Sailors 7: Coconuts 823537:

 

Sailors 15: Coconuts 437893890380859361:

 

=={{header|Phix}}==

The morning pile must be a multiple of sailors, so this only tries multiples of sailors! Needed an ugly kludge for solve(1),

the limit of 1 billion suffices for solve(9), above that gets run-time type check errors as capacity of ints are blown anyway.

{{out}}

<pre>

Sailor #6 takes 15624, giving 1 to the monkey and leaving 78120

In the morning each sailor gets 13020 nuts

</pre>

 

You may want to read [http://paddy3118.blogspot.co.uk/2015/05/solving-monkey-and-coconuts-problem.html Solving the Monkey and coconuts problem] to get more background on the evolution of the Python code.

===Python: Procedural===

"Parameterised the number of sailors using an inner loop including the last mornings case"

nuts = 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 ",

 

{{out}}

===Python: Recursive===

 

if depth is None:

depth = sailors

nuts = monkey_coconuts(sailors)

print("For %i sailors the initial nut count is %i" % (sailors, nuts))

 

{{out}}

===by solving Diophantine equation===

The following is a more or less general solution for arbitrary number of sailors and varying numbers of coconuts the monkey gets. The monkey can be given more coconuts than there are sailors each turn. This is not part of task requirement.

def dioph(a, b, c):

aa,bb,x,y = a, b, 0, 1

 

# many sailors, many nuts

 

=={{header|Racket}}==

{{trans|Python}}

 

(define (wake-and-split nuts sailors depth wakes)

(printf "For ~a sailors the initial nut count is ~a\n" sailors (first (last wakes)))

(map displayln (reverse wakes))

{{out}}

<pre>For 5 sailors the initial nut count is 3121

(93745 15624 1)

(78120 13020 0)</pre>

 

=={{header|REXX}}==

===uses a subroutine===

{{trans|C}} {from the 1^st '''C''' example}<br>

/*{Tars is an old name for sailors.} */

/*──────────────────────────────────────────────────────────────────────────────────────*/

valid: procedure; parse arg n,nuts /*obtain the number sailors & coconuts.*/

do k=n by -1 for n /*step through the possibilities. */

end /*k*/

Programming note: &nbsp; The parentheses in the last REXX ('''return''') statement aren't necessary, but help for readability. <br>

 

<pre>

sailors=5 coconuts=3121

This REXX version is the same as the above version (but the defaults are different),

<br>and it also eliminates the use of a subroutine, making it faster.

 

do n=2 to 9 /*traipse through number of sailors. */

<pre>

sailors=2 coconuts=11

===shows the shares===

{{trans|C}} {from the 2^nd '''C''' example}<br>

/*──────────────────────────────────────────────────────────────────────────────────────*/

total: procedure; parse arg n,nuts /*obtain the number sailors & coconuts.*/

do k=0 for n /*step through the possibilities. */

if nuts//nn\==0 then return 0 /*Not one coconut left? No solution. */

end /*k*/

<pre>

sailors=2 coconuts=11 share=1

sailors=8 coconuts=117440505 share=5044200

sailors=9 coconuts=387420481 share=14913080

</pre>

 

=={{header|Ruby}}==

===Brute Force===

sailor.times do

return false if (nuts % sailor) != 1

n -= 1 + div

end

{{out}}

[3121, 624, 1]

[2496, 499, 1]

[112495, 18749, 1]

[93745, 15624, 1]

===Faster version===

{{works with|Ruby|2.1+}}

sailor.step(by:sailor) do |nuts|

flag = sailor.times do

(2..9).each do |sailor|

puts "#{sailor}: #{coconuts(sailor)}"

{{out}}

3: 25

4: 765

7: 823537

8: 117440505

n, g = [start], [start/sailors]

(1..iter).each{|s|

n, start, step = [], sailors*(sailors-1), 1

(2..sailors).each{|s|

start,step = n[0][0], step*(sailors-1)

}

return n

end

{{out}}

[[6, 10, 16, 25], [2, 3, 5, 8]]

Number of sailors = 4

[[134217720, 150994936, 169869304, 191102968, 214990840, 241864696, 272097784, 306110008, 344373760, 387420481], [14913080, 16777215, 18874367, 21233663, 23887871, 26873855, 30233087, 34012223, 38263751, 43046720]]

Number of sailors = 10

n = ng(100)

The number of coconuts requires is as follows, the whole output is at [[Sailors, coconuts and a monkey problem/Ruby output 100]]

 

=={{header|Sidef}}==

{{trans|Bc}}

if ((sailors < 2) || (monkeys < 1) || (sailors <= monkeys)) {

return 0

2.to(9).each { |sailor|

say "#{sailor}: #{coconuts(sailor)}";

{{out}}

<pre>

This is a very straightforward implementation. The "overnight" proc attempts to fulfill the activities of the night, throwing an error (through "assert") if it cannot. "minnuts" keeps trying to call it with more nuts until it succeeds. On success, "overnight" will return a list which narrates the night's activities.

 

if {![uplevel 1 [list expr $expr]]} {

if {$msg eq ""} {

puts "Solution with $n sailors:"

minnuts $n

 

{{out}}

{{trans|C}}

For performance reasons, we limit ourselves to seven sailors.

t = 0

For x = 1 Step 1 While t = 0

b@ = b@ + 1 + b@ / a@

Next

{{out}}

<pre>2: 11 1

 

0 OK, 0:127</pre>

 

=={{header|zkl}}==

{{trans|Python}}

nuts,wakes:=sailors,List();

while(True){

println("On each waking, the nut count, portion taken, and monkeys share are:\n ",

wake_stats.concat("\n "));

{{out}}

<pre>

</pre>

{{trans|C}}

nuts *= n;

foreach k in (n){

break;

}

{{out}}

<pre>