Sailors, coconuts and a monkey problem: Difference between revisions
Sailors, coconuts and a monkey problem (view source)
Revision as of 22:48, 2 April 2024
, 1 month ago→{{header|Uiua}}
(→{{header|Clojure}}: Add implementation.) |
|||
(11 intermediate revisions by 5 users not shown) | |||
Line 32:
{{trans|Python}}
<
V nuts = sailors
L
Line 50:
V (nuts, wake_stats) = monkey_coconuts(sailors)
print("\nFor #. sailors the initial nut count is #.".format(sailors, nuts))
print("On each waking, the nut count, portion taken, and monkeys share are:\n "wake_stats.map(ws -> String(ws)).join(",\n "))</
{{out}}
Line 76:
=={{header|AutoHotkey}}==
<
{
sailor := A_Index+4
Line 105:
result["Remaining"] := coconut
return result
}</
{{out}}
<pre>---------------------------
Line 127:
=={{header|AWK}}==
<syntaxhighlight lang="awk">
# syntax: GAWK -f SAILORS_COCONUTS_AND_A_MONKEY_PROBLEM.AWK
# converted from LUA
Line 151:
return((nuts != 0) && (nuts % n == 0))
}
</syntaxhighlight>
{{out}}
<pre>
Line 167:
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) {
Line 189:
coconuts(5, 4)
coconuts(6, 1)
coconuts(101, 1)</
{{out}}
Line 214:
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
^g10,+55<.,9.,*<</
{{out}}
Line 233:
=={{header|Bracmat}}==
{{trans|Tcl}} (Though without the <code>assert</code> procedure.)
<
= a b
. !arg:(?a.?b)&(div$(!a.!b).mod$(!a.!b))
Line 288:
& minnuts$!n
)
)</
Output:
Line 310:
=={{header|C}}==
<
int valid(int n, int nuts)
Line 328:
}
return 0;
}</
{{out}}
<pre>2: 11
Line 342:
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
Line 364:
}
return 0;
}</
{{out}}
sailers: original pile, final share
Line 380:
=={{header|C sharp|C#}}==
{{trans|Java}}
<
{
static bool valid(int n, int nuts)
Line 405:
}
}
}</
<pre>2: 11
Line 418:
=={{header|C++}}==
{{trans|C#}}
<
bool valid(int n, int nuts) {
Line 440:
return 0;
}</
{{out}}
<pre>2: 11
Line 454:
A rather non-Clojure-like solution:
<
(with-local-vars [coconuts initial-coconut-count, hidings 0]
(while (and (> @coconuts sailors) (= (mod @coconuts sailors) 1)
Line 472:
(str "\tIn the morning, each sailor gets another " (/ @coconuts sailors) " coconuts."))
(println "\tThe monkey gets no more.\n"))))
</syntaxhighlight>
{{Out}}
Line 496:
=={{header|D}}==
{{trans|Kotlin}}
<syntaxhighlight lang="d">
import std.stdio;
Line 529:
}
}
</syntaxhighlight>
{{out}}
Line 613:
{{trans|Ruby}}
===Brute Force===
<
def valid?(sailor, nuts), do: valid?(sailor, nuts, sailor)
Line 631:
n - 1 - d
end)
end)</
{{out}}
Line 654:
===Faster version===
<
def coconuts(sailor), do: coconuts(sailor, sailor)
defp coconuts(sailor, nuts) do
Line 669:
Enum.each(2..9, fn sailor ->
IO.puts "#{sailor}: #{Sailor.coconuts(sailor)}"
end)</
{{out}}
Line 685:
=={{header|Forth}}==
{{trans|uBasic/4tH}}
<syntaxhighlight lang="text">: total
over * over 1- rot 0 ?do
over over mod if dup xor swap leave else over over / 1+ rot + swap then
Line 697:
;
9 sailors</
{{out}}
<pre>2: 11 1
Line 711:
=={{header|FreeBASIC}}==
{{trans|Yabasic}}
<
Dim As Integer cocos = 11
Line 740:
Next ns
Sleep
</syntaxhighlight>
=={{header|Go}}==
{{trans|Kotlin}}
<
import "fmt"
Line 777:
}
}
}</
{{out}}
Line 788:
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.
<
import Data.Maybe (mapMaybe)
import System.Environment (getArgs)
Line 812:
s:_ -> read s
a = head . mapMaybe (tryFor n) $ [n,2 * n ..]
print a</
Examples:
<pre>
Line 827:
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.)
<
3121</
These sailors must count coconuts extremely quickly.
Line 834:
When we do this with six sailors, it turns out that we have to assume a larger initial value:
<
233275 513211 793147</
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.
Line 841:
=={{header|Java}}==
{{trans|C}}
<
static boolean valid(int n, int nuts) {
Line 858:
}
}
}</
<pre>2: 11
3: 25
Line 875:
( As in the recursive Python example )
<
// wakeSplit :: Int -> Int -> Int -> Int
Line 897:
return intNuts;
});
})();</
{{out}}
<syntaxhighlight lang
===ES6===
<
"use strict";
Line 964:
// MAIN ---
return main();
})();</
{{Out}}
<syntaxhighlight lang
=={{header|jq}}==
Line 975:
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;
Line 998:
# Test whether the input is a valid number of coconuts with respect to the story:
def valid(sailors): nighttime(sailors) | morning(sailors);</
'''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
Line 1,009:
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
Line 1,036:
" and each sailor finally ended up with \(.[0])." ;
range(2;9) | solve</
{{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.
Line 1,044:
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.
With 8 sailors, there were originally 117440505 coconuts, and each sailor finally ended up with 5044200.</
=={{header|Julia}}==
{{trans|C#}}
<
function validnutsforsailors(sailors, finalpile)
for i in sailors:-1:1
Line 1,071:
runsim()
</syntaxhighlight>
{{output}}
<pre>
Line 1,086:
=={{header|Kotlin}}==
<
fun main(args: Array<String>) {
Line 1,112:
}
}
}</
{{out}}
Line 1,195:
=={{header|Lua}}==
{{trans|C}}
<
local k = n
local i = 0
Line 1,214:
end
print(n..": "..x)
end</
{{out}}
<pre>2: 11
Line 1,226:
=={{header|Mathematica}} / {{header|Wolfram Language}}==
<
SequenceOk[n_, k_] := Module[{m = n, q, r, valid = True},
Do[
Line 1,249:
i = 1;
While[! SequenceOk[i, 6], i++]
i</
{{out}}
<pre>3121
Line 1,256:
=={{header|Modula-2}}==
<
FROM FormatString IMPORT FormatString;
FROM Terminal IMPORT WriteString,WriteLn,ReadChar;
Line 1,308:
ReadChar
END Coconuts.</
=={{header|Nim}}==
{{trans|Kotlin}}
<
var coconuts = 11
Line 1,335:
else:
break # Failed. Continue search with more coconuts.
inc coconuts, ns</
{{out}}
Line 1,416:
=={{header|Objeck}}==
{{trans|C}}
<
class Program {
function : Total(n : Int, nuts : Int) ~ Int {
Line 1,440:
}
}
</syntaxhighlight>
{{out}}
<pre>
Line 1,456:
Use of <code>bigint</code> required or program silently fails for number of sailors > 13
{{trans|Raku}}
<
for $sailors (1..15) { check( $sailors, coconuts( 0+$sailors ) ) }
Line 1,492:
if ($sailors % 2 == 0 ) { ($sailors ** $sailors - 1) * ($sailors - 1) }
else { $sailors ** $sailors - $sailors + 1 }
}</
{{out}}
<pre style="height:60ex;overflow:scroll;">
Line 1,678:
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.
<!--<
<span style="color: #008080;">procedure</span> <span style="color: #000000;">solve</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">sailors</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">m</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">sm1</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">sailors</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span>
Line 1,708:
<span style="color: #000000;">solve</span><span style="color: #0000FF;">(</span><span style="color: #000000;">5</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">solve</span><span style="color: #0000FF;">(</span><span style="color: #000000;">6</span><span style="color: #0000FF;">)</span>
<!--</
{{out}}
<pre>
Line 1,726:
Sailor #6 takes 15624, giving 1 to the monkey and leaving 78120
In the morning each sailor gets 13020 nuts
</pre>
=={{header|Picat}}==
<syntaxhighlight lang="picat">main ?=>
between(2,9,N), % N: number of sailors
once s(N),
fail.
main => true.
s(N) =>
next_candidate(N+1,N,C), % C: original number of coconuts
divide(N,N,C,Cr), % Cr: remainder
printf("%d: original = %d, remainder = %d, final share = %d\n",N,C,Cr,Cr div N).
next_candidate(From,_Step,X) ?=> X = From.
next_candidate(From,Step,X) => next_candidate(From+Step,Step,X).
divide(N,0,C,Cr) => C > 0, C mod N == 0, Cr = C.
divide(N,I,C,Cr) =>
(C-1) mod N == 0,
Q = (C-1) div N,
C1 = Q*(N-1),
divide(N,I-1,C1,Cr).
</syntaxhighlight>
{{out}}
<pre>
2: original = 11, remainder = 2, final share = 1
3: original = 25, remainder = 6, final share = 2
4: original = 765, remainder = 240, final share = 60
5: original = 3121, remainder = 1020, final share = 204
6: original = 233275, remainder = 78120, final share = 13020
7: original = 823537, remainder = 279930, final share = 39990
8: original = 117440505, remainder = 40353600, final share = 5044200
9: original = 387420481, remainder = 134217720, final share = 14913080
</pre>
Line 1,731 ⟶ 1,765:
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
Line 1,752 ⟶ 1,786:
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))</
{{out}}
Line 1,776 ⟶ 1,810:
===Python: Recursive===
<
if depth is None:
depth = sailors
Line 1,800 ⟶ 1,834:
nuts = monkey_coconuts(sailors)
print("For %i sailors the initial nut count is %i" % (sailors, nuts))
</syntaxhighlight>
{{out}}
Line 1,808 ⟶ 1,842:
===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
Line 1,851 ⟶ 1,885:
# many sailors, many nuts
#for i in range(1, 5): print(10**i, calcnuts([1]*10**i + [0])[0])</
=={{header|R}}==
The only tricky bit is reading comprehension. For example, it's easy to miss that the coconut count after the final nighttime visit must be strictly positive and divisible by the number of sailors.
<syntaxhighlight lang="rsplus">coconutsProblem <- function(sailorCount)
{
stopifnot(sailorCount > 1) #Problem makes no sense otherwise
initalCoconutCount <- sailorCount
repeat
{
initalCoconutCount <- initalCoconutCount + 1
coconutCount <- initalCoconutCount
for(i in seq_len(sailorCount))
{
if(coconutCount %% sailorCount != 1) break
coconutCount <- (coconutCount - 1) * (sailorCount - 1)/sailorCount
if(i == sailorCount && coconutCount > 0 && coconutCount %% sailorCount == 0) return(initalCoconutCount)
}
}
}
print(data.frame("Sailors" = 2:8, "Coconuts" = sapply(2:8, coconutsProblem)))</syntaxhighlight>
{{out}}
<pre> Sailors Coconuts
1 2 11
2 3 25
3 4 765
4 5 3121
5 6 233275
6 7 823537
7 8 117440505</pre>
=={{header|Racket}}==
{{trans|Python}}
<
(define (wake-and-split nuts sailors depth wakes)
Line 1,879 ⟶ 1,942:
(printf "For ~a sailors the initial nut count is ~a\n" sailors (first (last wakes)))
(map displayln (reverse wakes))
(newline))</
{{out}}
<pre>For 5 sailors the initial nut count is 3121
Line 1,905 ⟶ 1,968:
This will test combinations of sailors and coconuts to see if they form a valid pairing. The first 6 are done using brute force, testing every combination until a valid one is found. For cases of 7 to 15 sailors, it uses a carefully crafted filter to drastically reduce the number of trials needed to find a valid case (to one, as it happens... :-) )
<syntaxhighlight lang="raku"
my @teens = 'th' xx 10;
my @suffix = lazy flat (@ones, @teens, @ones xx 8) xx *;
Line 1,940 ⟶ 2,003:
multi sub coconuts ( $sailors where { $sailors % 2 == 0 } ) { ($sailors - 1) * ($sailors ** $sailors - 1) }
multi sub coconuts ( $sailors where { $sailors % 2 == 1 } ) { $sailors ** $sailors - $sailors + 1 }</
{{out}}
<pre>
Line 1,981 ⟶ 2,044:
{{trans|C}} {from the 1<sup>st</sup> '''C''' example}<br>
<
parse arg L H .; if L=='' then L= 5 /*L not specified? Then use default.*/
if H=='' then H= 6 /*H " " " " default.*/
Line 1,997 ⟶ 2,060:
nuts=nuts - (1 + nuts % n) /*subtract number of coconuts from pile*/
end /*k*/
return (nuts \== 0) & \(nuts//n \== 0) /*see if number coconuts>0 & remainder.*/</
Programming note: The parentheses in the last REXX ('''return''') statement aren't necessary, but help for readability. <br>
Line 2,009 ⟶ 2,072:
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. */
Line 2,020 ⟶ 2,083:
end /*$*/
say 'sailors='n " coconuts="$ /*display number of sailors & coconuts.*/
end /*n*/ /*stick a fork in it, we're all done. */</
{{out|output|text= when using the default inputs:}}
<pre>
Line 2,036 ⟶ 2,099:
{{trans|C}} {from the 2<sup>nd</sup> '''C''' example}<br>
<
parse arg L H .; if L=='' then L= 2 /*L not specified? Then use default.*/
if H=='' then H= 9 /*H " " " " " */
Line 2,053 ⟶ 2,116:
nuts= nuts + 1 + nuts % nn /*bump the number coconuts to the pile.*/
end /*k*/
return nuts /*see if number coconuts>0 & remainder.*/</
{{out|output|text= when using the default inputs:}}
<pre>
Line 2,067 ⟶ 2,130:
=={{header|Ring}}==
<
# Project : Sailors, coconuts and a monkey problem
Line 2,100 ⟶ 2,163:
next
see "In the morning each sailor gets " + m/sailors + " nuts" + nl + nl
</syntaxhighlight>
Output:
<pre>
Line 2,123 ⟶ 2,186:
=={{header|Ruby}}==
===Brute Force===
<
sailor.times do
return false if (nuts % sailor) != 1
Line 2,140 ⟶ 2,203:
n -= 1 + div
end
end</
{{out}}
<pre>5 sailors => 3121 coconuts
Line 2,160 ⟶ 2,223:
===Faster version===
{{works with|Ruby|2.1+}}
<
sailor.step(by:sailor) do |nuts|
flag = sailor.times do
Line 2,172 ⟶ 2,235:
(2..9).each do |sailor|
puts "#{sailor}: #{coconuts(sailor)}"
end</
{{out}}
<pre>2: 11
Line 2,183 ⟶ 2,246:
9: 387420481</pre>
===A function to find the solution see [[User_talk:Nigel_Galloway#Inflammatory_stuff]] for a description===
<
def _ng (sailors, iter, start) #a method that given a possible answer applies the constraints of the tale to see if it is correct
n, g = [start], [start/sailors]
Line 2,200 ⟶ 2,263:
end
</syntaxhighlight>
===A possible use of the function===
<
{{out}}
The output consists of two list. The first is the number of nuts in each pile, the second the number of nuts taken by each dishonest sailor. So in the case of three, start with 25 nuts, the first sailor takes 8 and discards 1 leaving a pile of 16. The second sailor takes 5 and discards 1 leaving 10. The last dishonest sailor takes 3 discards 1 leaving 6 nuts, which can be shared equally between the 3 (2 each).
Line 2,221 ⟶ 2,284:
Number of sailors = 10
[[31381059600, 34867844001, 38742048891, 43046720991, 47829689991, 53144099991, 59048999991, 65609999991, 72899999991, 80999999991, 89999999991], [3138105960, 3486784400, 3874204889, 4304672099, 4782968999, 5314409999, 5904899999, 6560999999, 7289999999, 8099999999, 8999999999]]</pre>
Did someone ask the value for 100 sailors?<
n = ng(100)
(0..100).each{|g| puts "#{n[0][100-g]}:#{n[1][100-g]}"}</
The number of coconuts requires is as follows, the whole output is at [[Sailors, coconuts and a monkey problem/Ruby output 100]]
<pre>9899999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999901</pre>
Line 2,229 ⟶ 2,292:
=={{header|Scala}}==
{{Out}}Best seen running in your browser either by [https://scalafiddle.io/sf/jBSqGXg/0 ScalaFiddle (ES aka JavaScript, non JVM, be patient)] or [https://scastie.scala-lang.org/lZXMc4YBSl2htEBw4D2TUQ Scastie (remote JVM)].
<
var x = 0
Line 2,246 ⟶ 2,309:
}
}</
=={{header|Sidef}}==
{{trans|Bc}}
<
if ((sailors < 2) || (monkeys < 1) || (sailors <= monkeys)) {
return 0
Line 2,265 ⟶ 2,328:
2.to(9).each { |sailor|
say "#{sailor}: #{coconuts(sailor)}";
}</
{{out}}
<pre>
Line 2,282 ⟶ 2,345:
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 ""} {
Line 2,330 ⟶ 2,393:
puts "Solution with $n sailors:"
minnuts $n
}</
{{out}}
Line 2,356 ⟶ 2,419:
{{trans|C}}
For performance reasons, we limit ourselves to seven sailors.
<syntaxhighlight lang="text">For n = 2 To 7
t = 0
For x = 1 Step 1 While t = 0
Line 2,381 ⟶ 2,444:
b@ = b@ + 1 + b@ / a@
Next
Return (b@)</
{{out}}
<pre>2: 11 1
Line 2,391 ⟶ 2,454:
0 OK, 0:127</pre>
=={{header|Uiua}}==
<syntaxhighlight lang="Uiua">
# Produce candidate list of final numbers
⊚=0◿5⇡2000
# Five times: only keep piles that can be split by 4, do so,
# multiply by five and add one. Return the first value.
⊢⍥(+1×5÷4⊏⊚=0◿4.)5
⊚=0◿6⇡100000
⊢⍥(+1×6÷5⊏⊚=0◿5.)6
</syntaxhighlight>
{{out}}
<pre>
3121
233275
</pre>
Or for a terse point-free loop through different numbers of sailors:
<syntaxhighlight lang="Uiua">
+2⇡7
≡(
↘1×,⇡10000000
⊟:⊢⍥(+1×+1⟜÷⟜(⊏⊚=0◿)-1:,,),
)
</syntaxhighlight>
{{out}}
<pre>
╭─
╷ 2 11
3 25
4 765
5 3121
6 233275
7 823537
8 117440505
╯
</pre>
=={{header|VBA}}==
<
Public Sub coconuts()
Dim sailors As Integer
Line 2,421 ⟶ 2,523:
Debug.Print sailors, minimum, finalshare
Next sailors
End Sub</
<pre>Sailors Pile Final share
2 11 1
Line 2,431 ⟶ 2,533:
=={{header|Wren}}==
{{trans|Kotlin}}
<
for (ns in 2..9) {
var hidden = List.filled(ns, 0)
Line 2,457 ⟶ 2,559:
coconuts = coconuts + ns
}
}</
{{out}}
Line 2,540 ⟶ 2,642:
=={{header|Yabasic}}==
{{trans|D}}
<
for ns = 2 to 9
Line 2,566 ⟶ 2,668:
coconuts = coconuts + ns
loop
next</
=={{header|zkl}}==
{{trans|Python}}
<
nuts,wakes:=sailors,List();
while(True){
Line 2,593 ⟶ 2,695:
println("On each waking, the nut count, portion taken, and monkeys share are:\n ",
wake_stats.concat("\n "));
}</
{{out}}
<pre>
Line 2,615 ⟶ 2,717:
</pre>
{{trans|C}}
<
nuts *= n;
foreach k in (n){
Line 2,630 ⟶ 2,732:
break;
}
}</
{{out}}
<pre>
|