php – NSA Challenge – "Thirteen men and one shipment"

Question:

Browsing the internet looking for challenges (to be solved with programming), I found "Thirteen men and a load", where it is said that it is part of the NSA's random challenges ( link ).


The challenge

After their last voyage, the 13 pirates from the Turing ship gather in their favorite tavern to discuss how they will share a chest of gold coins . After much debate, Captain Codegus says, "Arrrrrrrgh, the shipment needs to be distributed evenly among us." And so it is done. The captain gives the coins, one by one, and each pirate eagerly awaits his reward. As the captain nears the bottom of the pile, however, he notices that there are three more coins .

After a brief, awkward silence, one of the pirates says, "I deserve an extra coin because I loaded the ship while the rest of you slept." Another says, "Well, I deserve an extra coin because I cooked all the food along the way." Soon begins an intense exchange of kicks, punches and bottles for possession of the remaining money. The owner of the establishment, irritated by the mess, expels a particularly violent pirate who has broken a table , and he is forced to return all his coins to the group. The warning is given: “either you will be in peace or everyone will be expelled from here!”.

The pirates return to their places and the captain, who was left with only 12 pirates, continues to distribute the coins . "One for you… One for you." Now, when the pile is near the end, he notices that there are five coins left . A new fight starts. The captain, afraid that they will be expelled from the scene, sends the most stressed pirate away . Now, with only 11 members, the division works , each one receives the same amount of coins and everyone goes to sleep in peace.

Considering that there were less than 1000 coins , how many coins did the pirates divide among themselves? There is only one possible answer for a value below 1000 .


Starting from the idea of ​​solving and knowing that there would be several values ​​to be calculated, I briefly did it in php to try the solution (of course, without reading the result, so as not to lose the fun), and luckily it worked:

<?php

// 11 piratas, sobra 0
$piratas_11 = array();

$max_moedas = 1000;
while($max_moedas > 0) {

    if($max_moedas%11 == 0){
    
        array_push($piratas_11, $max_moedas);
    }

    $max_moedas--;
}


// 12 piratas, sobra 5
$piratas_12 = array();

foreach($piratas_11 as $v) {
    
    if($v%12 == 5){
    
        array_push($piratas_12, $v);
    }
}


// 13 piratas, sobra 3
$piratas_13 = array();

foreach($piratas_12 as $v) {
    
    if($v%13 == 3){
    
        array_push($piratas_13, $v);
    }
}

echo '<pre>';
print_r($piratas_13);

Result:

Array
(
    [0] => 341
)

I didn't try to do it in other ways, so:

What I would like is to know how you would do it, if there is a shorter and more efficient solution, using or not other functions, etc.

I believe that there is always a way to make the code more efficient, and in this I always learn a lot.

Answer:

You can do this with just one repeat loop. Considering that they have N coins, when it is divided between 13 pirates, there are 3 coins left, which means that N-3 is a multiple of 13 and therefore N-3 % 13 = 0 ; when divided by 12 pirates, 5 coins are left, so N-5 is a multiple of 12, which implies N-5 % 12 = 0 ; finally, when divided into 11 pirates, there are no coins left, so N is a multiple of 11, N % 11 = 0 . The value of N will be the one that satisfies all three conditions and is less than 1000.

foreach(range(0, 1000, 11) as $i) {
    if (($i - 3) % 13 == 0 and ($i - 5) % 12 == 0 and ($i % 11) == 0) {
        echo $i, PHP_EOL;
        break;
    }
}

See working on Repl.it | ideone

Note that, knowing that the result will necessarily be a multiple of 11, we don't need to run through all the values ​​from 0 to 1000, but only the multiples of 11, so the third range parameter was defined as such.

Scroll to Top