Aftelrijmpje, wie blijft over?
Bijna iedereen kent die aftelrijmpjes wel.
Iene miene mutte is er 1 van.
Als je dat met 6 mensen doet, blijft uiteindelijk nummer 1 over.
Maar wie blijft er over als er veel meer mee doen? Stel 2.500.000 deelnemers.
Bij 100, 10.000 en 1.000.000 mensen blijven respectievelijk over: #10, #5898 en #154107.
Ik weet niet hoe dit eenvoudig op te lossen is met pen en papier.
Heb Excel geprobeerd, zonder succes.
Mijn idee was nu om het eens te proberen via php. Door een array te maken.
Met elke deelnemer een waarde tussen 1 en 18 (volgens mij het aantal woorden van iene miene mutte). En dan steeds die 18e te verwijderen.
Dat in een loop, zodat er uiteindelijk 1 over blijft.
Ben aan het stoeien geweest met unset, array_splice en array_value bezig geweest.
Iemand die mee kan/wil denken?
Code (php)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
$y = 1;
$array = array();
$array[] = 0; // startwaarde array = 0. Deze gevuld, zodat combinatie voor mij wat makkelijker leesbaar is
for ($x = 1; $x <= 180; $x++) // loop met klein aantal waarden om array te vullen
{
$array[] = $y;
$y++;
if($y == 18) // het idee: het aftelrijmpje heeft 18 woorden. Door zo te nummeren, kan ik makkelijk verwijderen.
{
$y =1;
}
}
// print_r($array);
// echo "<hr>";
for($n = 1 ; $n < 10 ; $n++) // een loop om daarbinnen elementen te verwijderen
{
for($z = 17; $z < 180; $z=$z+18) // 1e element is 17e om te verwijderen, daarna stteds de 18.
{
unset($array[$z]); // verwijder element
}
// print_r($array);
}
$array = array();
$array[] = 0; // startwaarde array = 0. Deze gevuld, zodat combinatie voor mij wat makkelijker leesbaar is
for ($x = 1; $x <= 180; $x++) // loop met klein aantal waarden om array te vullen
{
$array[] = $y;
$y++;
if($y == 18) // het idee: het aftelrijmpje heeft 18 woorden. Door zo te nummeren, kan ik makkelijk verwijderen.
{
$y =1;
}
}
// print_r($array);
// echo "<hr>";
for($n = 1 ; $n < 10 ; $n++) // een loop om daarbinnen elementen te verwijderen
{
for($z = 17; $z < 180; $z=$z+18) // 1e element is 17e om te verwijderen, daarna stteds de 18.
{
unset($array[$z]); // verwijder element
}
// print_r($array);
}
Gewijzigd op 06/03/2021 17:10:30 door Obelix Idefix
Code (php)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
<?php
$aantalWinnaars = 6;
$spelers = array();
$overslaan = 18;
// maak een lijst aan met spelers
for($i = 0 ; $i < 100 ; $i++) {
$spelers[] = "Speler " . ($i + 1);
}
$winnaarKeys = ineMineMutte($spelers, $aantalWinnaars, $overslaan);
print_r($winnaarKeys);
foreach($winnaarKeys as $key) {
echo $spelers[$key] . "<br>\n";
}
function ineMineMutte($spelers, $aantalWinnaars, $overslaan)
{
$i = 0;
$winnaars = array();
if($aantalWinnaars >= count($spelers)) {
throw new Exception("Aantal winnaars moet kleiner zijn dan aantal spelers.");
}
if($overslaan < 0) {
throw new Exception("Het aantal spelers dat overgeslagen moet worden moet een positief getal zijn.");
}
while(1) { // oneindige lus
foreach($spelers as $key => $speler) { // loop door alle spelers
if(!in_array($key, $winnaars)) { // speler kan slechts één keer winnen
if($i == $overslaan) { // de 18e speler zeg maar
$winnaars[] = $key; // voeg toe aan winnaars
$i = 0; // opnieuw tellen naar 18
if(count($winnaars) == $aantalWinnaars) { // indien we voldoende winnaars hebben
return $winnaars;
}
} else {
$i++;
}
}
}
}
}
?>
$aantalWinnaars = 6;
$spelers = array();
$overslaan = 18;
// maak een lijst aan met spelers
for($i = 0 ; $i < 100 ; $i++) {
$spelers[] = "Speler " . ($i + 1);
}
$winnaarKeys = ineMineMutte($spelers, $aantalWinnaars, $overslaan);
print_r($winnaarKeys);
foreach($winnaarKeys as $key) {
echo $spelers[$key] . "<br>\n";
}
function ineMineMutte($spelers, $aantalWinnaars, $overslaan)
{
$i = 0;
$winnaars = array();
if($aantalWinnaars >= count($spelers)) {
throw new Exception("Aantal winnaars moet kleiner zijn dan aantal spelers.");
}
if($overslaan < 0) {
throw new Exception("Het aantal spelers dat overgeslagen moet worden moet een positief getal zijn.");
}
while(1) { // oneindige lus
foreach($spelers as $key => $speler) { // loop door alle spelers
if(!in_array($key, $winnaars)) { // speler kan slechts één keer winnen
if($i == $overslaan) { // de 18e speler zeg maar
$winnaars[] = $key; // voeg toe aan winnaars
$i = 0; // opnieuw tellen naar 18
if(count($winnaars) == $aantalWinnaars) { // indien we voldoende winnaars hebben
return $winnaars;
}
} else {
$i++;
}
}
}
}
}
?>
Gewijzigd op 07/03/2021 10:42:11 door Frank Nietbelangrijk
- Nummer 18 moet er uit (bij 6 spelers dus uiteindelijk, in het 3e rondje, speler 6).
- Daarna ga je met degene daarnaast weer verder, en dan weer de 18e (speler 3), enz.
- Dan heb je nog speler 1,2,4,5 over; valt speler 2 er dus uit.
- Dan 5, dan 4, en houd je dus speler 1 over.
Fijn, een potje golf op zondag:
Code (php)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
<?php
/**
* Array met spelers elimineren, net zolang tot er 1 over is.
* $players Array met spelersnamen.
* $target Degene die er uit moet (computers tellen vanaf 0, dus dit is het "aantal
* woorden" - 1).
*/
function ienemienemutte($players,$target){
$index = 0;
while(($count = count($players)) > 1){ //pas stoppen als er nog maar 1 speler is
$players = array_values($players); //numerieke, opvolgende key
unset($players[$index = ($index + $target) % $count]); //target verwijderen (via
//de modulus (%) wordt rekening gehouden de kans dat we "rond" zijn = opnieuw
//vooraan beginnen)
}
return array_pop($players); //enige overgebleven speler = winnaar
}
/**
* Array met spelersnamen (base-1) maken.
* $count Aantal spelers.
*/
function players($count){
$players = [];
for($i = 1; $i <= $count; $i++) $players[] = "speler $i";
return $players;
}
print(ienemienemutte(players(6),17)."<br>\n"); //speler 1
print(ienemienemutte(players(100),17)."<br>\n"); //speler 10
print(ienemienemutte(players(10000),17)."<br>\n"); //speler 5898
//print(ienemienemutte(players(1000000),17)."<br>\n");
?>
/**
* Array met spelers elimineren, net zolang tot er 1 over is.
* $players Array met spelersnamen.
* $target Degene die er uit moet (computers tellen vanaf 0, dus dit is het "aantal
* woorden" - 1).
*/
function ienemienemutte($players,$target){
$index = 0;
while(($count = count($players)) > 1){ //pas stoppen als er nog maar 1 speler is
$players = array_values($players); //numerieke, opvolgende key
unset($players[$index = ($index + $target) % $count]); //target verwijderen (via
//de modulus (%) wordt rekening gehouden de kans dat we "rond" zijn = opnieuw
//vooraan beginnen)
}
return array_pop($players); //enige overgebleven speler = winnaar
}
/**
* Array met spelersnamen (base-1) maken.
* $count Aantal spelers.
*/
function players($count){
$players = [];
for($i = 1; $i <= $count; $i++) $players[] = "speler $i";
return $players;
}
print(ienemienemutte(players(6),17)."<br>\n"); //speler 1
print(ienemienemutte(players(100),17)."<br>\n"); //speler 10
print(ienemienemutte(players(10000),17)."<br>\n"); //speler 5898
//print(ienemienemutte(players(1000000),17)."<br>\n");
?>
Die laatste heb ik in commentaar gezet, omdat dat bij mij enorm lang duurde. De eerste 3 klopten wel met je opgave, dus ik ga er vanuit die laatste ook (en uiteindelijk voor 2.5M dus ook - als je maar voldoende geduld / CPU power hebt).
De volgende uitdaging is dus om het proces zo te optimaliseren dat dit antwoord ook binnen redelijke tijd wordt verkregen.
-----
De meeste tijd bleek in de herindexering van $players te zitten (dmv array_values() - vooral bij grotere arrays). Die moet er dus uit. Dat heb ik gedaan door een speler niet echt te verwijderen, maar alleen zijn naam. Pas als de hele kring een keer aan de beurt is geweest wordt de lijst met spelers in 1x opgeschoond (mbv array_filter()). Bij de "grotere kringen" scheelt dat dus enorm vaak tussentijds opschonen. Ondanks dat je nu dus steeds "alle stoelen moet nalopen" (ook de reeds lege), en niet zoals in bovenstaande versie direct naar het volgende "slachtoffer" kunt "springen", is dit toch vele malen sneller/efficiënter.
Code (php)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
<?php
function ienemienemutte($players,$target){
$index = 0; //begin in eerste instantie bij de 1e speler in de kring; in de volgende
//ronde van de while-lus hieronder gaan we verder met de index van de ronde ervoor
while(count($players = array_filter($players)) > 1) //"verwijderde" spelers echt
//verwijderen
foreach($players as $key => $player) //kring langslopen (begin bij huidige index)
if($player && ($index++ == $target)) //"verwijderde" spelers overslaan; de 2e
//voorwaarde wordt dus alleen "uitgevoerd" (= index opgehoogd) als de speler
//nog in het spel is
$players[$key] = $index = 0; //speler "verwijderen", teller resetten
return array_pop($players);
}
?>
function ienemienemutte($players,$target){
$index = 0; //begin in eerste instantie bij de 1e speler in de kring; in de volgende
//ronde van de while-lus hieronder gaan we verder met de index van de ronde ervoor
while(count($players = array_filter($players)) > 1) //"verwijderde" spelers echt
//verwijderen
foreach($players as $key => $player) //kring langslopen (begin bij huidige index)
if($player && ($index++ == $target)) //"verwijderde" spelers overslaan; de 2e
//voorwaarde wordt dus alleen "uitgevoerd" (= index opgehoogd) als de speler
//nog in het spel is
$players[$key] = $index = 0; //speler "verwijderen", teller resetten
return array_pop($players);
}
?>
Gewijzigd op 07/03/2021 23:20:24 door Rob Doemaarwat
Ik ga beide z.s.m. testen/vergelijken (en bestuderen).
Ik begrijp nu waarom ik er zelf niet uit ben gekomen ;-)
Het script levert me niet de verwachte antwoorden op. Bij 6 deelnemers zou nummer 1 de overblijven/winnen.
Bij 100, 10.000 en 1.000.000 mensen blijven respectievelijk over: #10, #5898 en #154107.
Het script van @Rob doet dat wel. Dank daarvoor.
Is er nog een mogelijkheid om het aantal spelers "onbeperkt" groot te maken?
Heb het aantal als test eens flink verhoogd, maar liep aan tegen Fatal error: Allowed memory size
Heb dat proberen op te lossen met
Code (php)
1
ini_set('memory_limit', '2048M'); // or you could use 1G
het geheugen op te hogen. Tot 1G. De melding blijft komen bij een heel groot aantal deelnemers.
Is daar nog een oplossing voor?
Mocht je boven je RAM limiet uit willen dan kun je de hele array op schijf opslaan (en dus steeds door de file heen akkeren), maar dan zal het allemaal wel heel traag worden. Of er even een avondje wiskunde aan wijden, waardoor je niet alles "na hoeft te spelen", maar _uitrekent_ wie er wint (?).
Rob Doemaarwat op 10/03/2021 13:44:08:
Mocht je boven je RAM limiet uit willen dan kun je de hele array op schijf opslaan (en dus steeds door de file heen akkeren), maar dan zal het allemaal wel heel traag worden.
Geen idee hoe dat te doen.
Rob Doemaarwat op 10/03/2021 13:44:08:
Of er even een avondje wiskunde aan wijden, waardoor je niet alles "na hoeft te spelen", maar _uitrekent_ wie er wint (?).
Mijn wiskundekennis is nog minder dan die van PHP....
Obelix Idefix op 10/03/2021 14:17:46:
Geen idee hoe dat te doen.
Bijvoorbeeld voor elke "speler" een regel in een (tekst-) bestand plaatsen, dus
Code (php)
1
2
3
2
3
speler 1
speler 2
enz
speler 2
enz
Ipv door een array te lopen ga je dan
Code (php)
Als je je "array" wilt aanpassen schrijf je de aanpassingen naar een nieuw bestand, enz.
Nu is je limiet opeens de grote van je schijf (ik vermoed dat er eerder een beperking op je geduld zit).
Gewijzigd op 10/03/2021 15:03:05 door Rob Doemaarwat