NSA Challenge - "Thirteen men and a shipment"

Question

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

---

The challenge

After his last trip, the 13 pirates of the ship Turing gather in their favorite tavern to discuss how will share a chest of gold coins. After much debate, Captain Codus says: "Arrrrrgh, the shipment needs to be distributed equally 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 approaches the end of the pile, however, he realizes that there are three coins more.

After a brief and embarrassing silence, one of the pirates says: "I deserve an extra coin because I carried the ship while the rest of you slept". Another states, "Well, I deserve an extra penny because I cooked all the food along the way". Soon begins an intense exchange of kicks, punches and claws for possession of the remaining money. The owner of the establishment, angered 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 you will all be expelled from here!".

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

Whereas there were less than 1000 coins, how many coins pirates have divided? 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 in php to try the solution (of course, without reading the result, not to lose the grace), and fortunately 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);

Upshot:

Array
(
    [0] => 341
)

I haven’t tried other ways, so:

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

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

Answer 1

You can do this with just a repeat loop. Whereas they have N coins, when it is divided between 13 pirates, 3 coins remain, which means that N-3 is a multiple of 13 and therefore, N-3 % 13 = 0; when divided by 12 pirates, 5 coins remain, 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, and therefore, N is multiple of 11, N % 11 = 0. The value of N will be the one who meets the 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 multiple of 11, we do not need to go through all the values from 0 to 1000, but only the multiples of 11, so the third parameter of range was defined as such.

Answer 2

For now my version improved based on the general, focusing on minimal variables and functions:

for ($c = 1000; $c > 0; $c--)
    if (($c%11 == 0) && ($c%12 == 5) && ($c%13 == 3))
        echo $c;

Answer 3

$max = 1000;

while ($max > 0) {

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

    $max--;
}