How to assign all input values into an array based on key availability without conflict?

user_4189128 0
Viewed 172

I am looking for a slot filling technique. I have 8 "slots" represented as a flat array. I also have a multidimensional array where keys are subjects and values are subarrays containing indexed elements (slots).

The multidimensional array ($emp) may contain, for example, the subject Tamil which is available at slots 1 through 5, and/or English which is only available during slots 4, 5, or 6. All subjects on offer will have an array of available slots -- even if only one slot is available.

Subject Availability:

$emp = array(
    "tamil"   => array(1, 2, 3, 4, 5),
    "english" => array(4, 5, 6),
    "maths"   => array(1, 5, 8),
    "social"  => array(1, 2, 5),
    "pt"      => array(1),
    "hindi"   => array(3, 4, 7)
);

I need to assign the following subjects the exact number of times -- while obeying subject availability AND without encountering a "slot conflict" -- in my output array ($sort):

  • Tamil 2 times
  • PT 1 time
  • Maths 2 times
  • Social 1 time
  • Hindi 1 time
  • English 1 time

All 8 slots must be filled. All subjects must occur only once with exception to Tamil and Math which must occur exactly twice.

Output may be:

$slot[3] = 'tamil',
$slot[7] = 'Hindi', 
$slot[6] = 'English',
$slot[1] = 'Pt',
$slot[5] = 'Maths',
$slot[8] = 'Maths',
$slot[4] = 'Tamil',
$slot[2] = 'Social'.

I have tried to code this myself, but I was unsuccessful.

for ($i = 1; $i < 9; $i++) {
    $var = $subarray[$i];
    if (count($var) <= 1) { 
        $filledslots[$i] = $var[0];
    } else {
        $empty[$i] = '';
    }
}
$subjects = array_flat($subarray); 
$count_values = array(); 
$subjects = array_diff($subjects, $filledslots);
foreach ($subjects as $value) { 
   $count_values[$value] = 0; 
   foreach ($empty as $key => $val) {
       $res = $subarray[$key];
       if (in_array($value, $res)) {
           $count_values[$value] = $count_values[$value] + 1;
       }
   }
   if ($count_values[$value] == 1) {
       //$filledslots[1] = $count_values[$value];
       foreach ($empty as $key => $val) {
           $res = $subarray[$key]; 
           if (in_array($value, $res)) {
               $filledslots[$key] = $value;
           }
       }
   }
}
print_r(($filledslots));
recursion sorting arrays algorithm php
1 Answers

Here is a working recursive technique that will return the first qualifying data set.

It works by removing elements from the "required subjects" array and the "available slots" array while adding elements to the "filled slots" array.

The use of array_replace() to push qualifying values into the 3rd parameter being delivered in the recursive call prevents disrupting the state of the $filledSlots variable that will continue to be used by the foreach loops.

The function: (Demo)

function fillSlots($requiredSubjects, $availableSlots, $filledSlots = []) {
    if (!$requiredSubjects) {
        ksort($filledSlots);
        return $filledSlots;
    }
    foreach ($requiredSubjects as $rIndex => $subject) {
        foreach ($availableSlots[$subject] as $sIndex => $slot) {
            if (!isset($filledSlots[$slot])) {
                unset($requiredSubjects[$rIndex], $availableSlots[$subject][$sIndex]);
                $result = fillSlots(
                    $requiredSubjects,
                    $availableSlots,
                    array_replace($filledSlots, [$slot => $subject])
                );
                if ($result) {
                    return $result;
                }
            }
        }
    }
}

The input variables:

$subjectSlots = [
    "tamil"   => [1, 2, 3, 4, 5],
    "english" => [4, 5, 6],
    "maths"   => [1, 5, 8],
    "social"  => [1, 2, 5],
    "pt"      => [1],
    "hindi"   => [3, 4, 7]
];
$requiredSubjects = ['tamil', 'tamil', 'pt', 'maths', 'maths', 'social', 'hindi', 'english'];

To allow the function to perform thousands of times faster (I benchmarked because I was curious), prepare the input data so that subjects with fewer slots are iterated first.

Pre-execution sorting: (See the effect)

usort($requiredSubjects, function($a, $b) use ($subjectSlots) {
    return $subjectSlots[$a] <=> $subjectSlots[$b];  // sort by length, then by values
});

The initial call:

var_export(fillSlots($requiredSubjects, $subjectSlots));

Output:

array (
  1 => 'pt',
  2 => 'social',
  3 => 'tamil',
  4 => 'tamil',
  5 => 'maths',
  6 => 'english',
  7 => 'hindi',
  8 => 'maths',
)
user_29434030
Related