Result is little bit different by the result. How to filter PHP array to get the exact result?

Question

Task requirements:

Adam has been given a bag of candies from his mother. His mother told him to share half of it with his sister Berit. Adam likes diversity so he wants as many different types of candies as possible, while giving the rest to Berit. If Adam has received an odd number of candies he can keep one more than he gives to Berit. The exercise is to sort through the candies Adam has been given and return the candies that he should give to Berit.

The values after => is the values that should be returned for each test case.

$candiesTests = [
[1, 1, 2, 3], // Test1 => 1,3
[1, 1, 2, 3, 4], // Test2 => 1,4
[1, 1, 2, 2, 3, 4, 5, 5], // Test3 => 1,2,5,5
[1, 1, 2, 2, 3, 4, 5, 5, 1, 1, 5], // Test4 => 1,1,1,2,5
];

function getBeritsCandies(array $candies): array
{

$quota = floor(count($candies)/2);                        // Berit's share

$k = array_count_values($candies);
$berit = [];
arsort($k);                                               // start with ones we have most of
foreach ($k as $t => &$n) {
    if ($n > 1 ) {                                        // if we have multiple, Berit can can have all but 1
        $m = $n - 1;                                      // until she has her quota
        for ($i=0; $i<$m; $i++) {
            if (count($berit) == $quota) break;
            $berit[] = $t;
            --$n;
        }
    }
    elseif (count($berit) < $quota) {
        $berit[] = $t;
        --$n;
    }
}
return $berit;

return [];
}

foreach ($candiesTests as $candies) {
   $beritsCandies = getBeritsCandies($candies);
   echo('Berits candies: '.implode(', ', $beritsCandies).PHP_EOL);
}

For now I'm getting this result:

Berits candies: 1, 2 Berits candies: 1, 2 Berits candies: 1, 2, 5, 3 Berits candies: 1, 1, 1, 5, 5

Where's the problem or what I'm doing wrong?

Thank you for your help.

Answer 1

There are two factors influencing your result.

1. More fundamental is that you are pushing data directly/first before pushing data into Adam as described in the rules/story. When you prioritize Adam and give Berit every thing that is left over, your results will more closely align with the commented desired results.

2. Less significantly is your choice to arsort() the candy counts. While filling Adam's payload, you could choose to not sort at all, sort by candy ints (keys), sort by count ints (values), and then you could choose to sort ascending or descending. Depending on your iteration and conditions, all approaches can provide correct results.

The below snippet will implement an ascending candy-based sort with ksort() (which is effectively a no-sort because of the ordering of your inputs), then loop in a fashion where Adam is fully satisfied, then Berit gets the leftovers. I most strongly urge you to use more intuitive/expressive/declarative variable names for the sake of your future programming career.

It returns both payloads to fully demonstrate the approach.

Code: (Demo)

function distributeCandies(array $candies): array
{

    $quota = ceil(count($candies) / 2);                        // Berit's share
    
    $adam = []; // fill first
    $berit = []; // the leftovers

    $candyCounts = array_count_values($candies);
    ksort($candyCounts);

    // fill Adam
    while ($candyCounts) {
        foreach ($candyCounts as $candy => &$count) {
            $adam[] = $candy;
            --$count;
            if (!$count) {
                unset($candyCounts[$candy]);
            }
            if (count($adam) == $quota) {
                break 2;
            }
        }
    }

    // fill Berit
    foreach ($candyCounts as $candy => $count) {
        array_push($berit, ...array_fill(0, $count, $candy));
    }
    return [$adam, $berit];
}

foreach ($candiesTests as $candies) {
   $distribution = distributeCandies($candies);
   echo 'Adams candies:  '
        . implode(', ', $distribution[0])
        . PHP_EOL
        . 'Berits candies: '
        . implode(', ', $distribution[1])
        . PHP_EOL . '---' . PHP_EOL;
}