# NSA Challenge - "Thirteen men and one shipment"

17

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

The challenge :

After your last trip, the 13 pirates of the Turing ship gather in their favorite tavern to discuss how they will split a gold coin chest . After much debate, Captain Codigo says, "Arrrrrrrrrrrrrrrrrrrrrrrgh, the shipment needs to be distributed equally between us." And so it is done. The captain gives the coins, one by one, and each pirate anxiously awaits his reward. As the captain approaches the end of the stack, however, he realizes that there are three more coins .

After a brief and embarrassing 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 had broken a table , and he is obliged to return all his coins to the group. The warning is given: "Either you stay in peace or everyone will be driven out of here!".

The pirates return to their seats and the captain, who has only 12 pirates, continues to distribute the coins . "One for you ... Another for you." Now, when the stack is near the end, he notices there are five coins left . A new fight breaks out. The captain, afraid that they will be expelled from the place, sends the pirate more stressed though . Now with only 11 members, the division goes , each receives the same amount of coins and everyone goes to sleep in peace.

Given that there were less than 1000 coins , how many coins did the pirates split between them? 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 calculate, I briefly made `php` to try to solve it (of course, without reading the result, not to lose the grace), and fortunately it worked: p>

``````<?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 did not try to do it in other ways, so:

What I would like to know is how you would do it, whether there is a shorter and more efficient way of solving it, using other functions, etc.

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

asked by anonymous 19.03.2018 / 02:22

17

You can do this with just a loop of repetition. Considering that they have% coins, when divided among 13 pirates, there are 3 coins left, which means that% with% is a multiple of 13 and therefore% with%; when divided by 12 pirates, there are 5 coins left, so `N` is a multiple of 12, which implies `N-3` ; Finally, when divided into 11 pirates, there are no coins left, and therefore `N-3 % 13 = 0` is a multiple of 11, `N-5` . The `N-5 % 12 = 0` value 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 at Repl.it | Ideone

Note that knowing that the result will necessarily be a multiple of 11, we do not need to go through all values from 0 to 1000, but only the multiples of 11, so the third parameter of `N` has been defined as such.

19.03.2018 / 03:20
5

So far my improved version based on the general, focusing on the minimum of variables and functions:

``````for (\$c = 1000; \$c > 0; \$c--) {

if((\$c%11 == 0) && (\$c%12 == 5) && (\$c%13 == 3)){
echo \$c;
}
}
``````

19.03.2018 / 13:08
4

``````\$max = 1000;

while (\$max > 0) {

if(\$max%11 == 0 && (\$max-5)%12 == 0 && (\$max-3)%13 == 0){
echo \$max;
}

\$max--;
}
``````

19.03.2018 / 04:05