Eliminating impossible choices

Question

I'm having a bit of trouble just trying to wrap my head around this problem programatically. This isn't exactly what I'm doing, but to simplify things, say we have a certain number of balls and a certain number of people. Each person must choose exactly one ball and the people may be limited to the type of ball they can choose. The objective is to determine what options the people have to choose from after eliminating all impossible combinations.

Example 1:

In a simple case, say we have two people and one red ball and one green ball. Person 1 can choose either ball, but person 2 can only choose the green ball. This can be illustrated like:

Person 1: RG
Person 2: G

Since we know that person 2 must choose the green ball, this means that person 1 cannot choose that ball and therefore must choose the red ball. So this can be simplified to:

Person 1: R
Person 2: G

So in this case we know exactly what each person will chose.

Example 2:

Now let's add a bit of complexity. Now we have 4 people that need to chose from 2 red balls, 1 green ball and 4 blue balls. Person 1 can choose any ball, person 2 and 3 can choose the red or green balls and person 4 must choose a red ball. So we have the following choices:

Person 1: RRGBBBB
Person 2: RRG
Person 3: RRG
Person 4: RR

Since person 4 only has one type of option, we know that person must choose a red ball. We can therefore eliminate 1 red ball from all other people:

Person 1: RGBBBB
Person 2: RG
Person 3: RG
Person 4: RR

However this is where it gets really tricky. As we can see, person 2 and 3 must choose one red and one green ball, we just don't know which one will choose which. However since we only have 1 of each ball remaining, red and green can also be eliminated as an option from person 1:

Person 1: BBBB
Person 2: RG
Person 3: RG
Person 4: RR

Now we can remove duplicates from each entry to be left with the following options:

Person 1: B
Person 2: RG
Person 3: RG
Person 4: R

We know the choice of person 1 and person 4, and person 2 and 3 have a choice between red and green.

---

To solve this, what I do is loop over the people and first if the people only have one ball type, remove that person from the array and put it in the results array (since I know that is what that person must choose) and then remove one of that ball type from every other person in the array if present.

After this, it seems to me like the rule is:

If there are $n number of people who all have the same $n number of options (or a subset of them), these options can be removed from all other people, where $n is less than the total number of people.

So what I do is loop through the people again and check for other people that have the same options available (or a subset of those options) and if that is equal to the total number of options for that person, remove them from the options for all other people.

Here's what I have so far that will solve these two cases:

// The quantity of each ball
$balls = array(
    'r' => 1,
    'g' => 1,
    'b' => 1,
    'k' => 1,
);
// The options available for each person
$options = array(
    array('r', 'g', 'b', 'k'),
    array('r', 'g'),
    array('r', 'b'),
    array('b', 'g'),
);

// Put both of these together into one array
$people = [];
foreach ($options as $option) {
    $person = [];
    foreach ($option as $ball_key) {
        $person[$ball_key] = $balls[$ball_key];
    }
    $people[] = $person;
}

print_r($people);
// This produces an array like:
// Array
// (
//     [0] => Array
//         (
//             [r] => 2
//             [g] => 1
//             [b] => 4
//         )
//
//     [1] => Array
//         (
//             [r] => 2
//             [g] => 1
//         )
//
//     [2] => Array
//         (
//             [r] => 2
//             [g] => 1
//         )
//
//     [3] => Array
//         (
//             [r] => 2
//         )
//
// )

// This will be used to hold the final result
$results = [];

do {
    // If anything changes, this needs to be set to true. Any time anything
    // changes we loop through everything again in case it caused a cascading
    // effect
    $has_change = false;

    // Step 1:
    // Find out if there are any people who have only one option and remove it
    // from the array and add it to the result and subtract one from all other
    // people with this option
    foreach ($people as $p_index => $p_options) {
        if (count($p_options) === 1) {
            $color = key($p_options);

            foreach ($people as $p_index_tmp => $p_options_tmp) {
                // It's the current person, so skip it
                if ($p_index_tmp === $p_index) {
                    continue;
                }

                if (isset($p_options_tmp[$color])) {
                    // Subtract 1 from this color from this person and if zero,
                    // remove it.
                    if (--$people[$p_index_tmp][$color] === 0) {
                        unset($people[$p_index_tmp][$color]);
                    }

                    $has_change = true;
                }
            }

            // Add to results array and remove from people array
            $results[$p_index] = array($color => 1);
            unset($people[$p_index]);
        }
    }

    // Step 2:
    // If there are $n number of people who all have the same $n number of
    // options (or a subset of them), these options can be removed
    // from all other people, where $n is less than the total number of people
    foreach ($people as $p_index => $p_options) {
        $num_options = array_sum($p_options);
        if ($num_options < count($people)) {
            // Look for other people with no different options from the ones
            // that this person has
            $people_with_same_options = [];
            foreach ($people as $p_index_tmp => $p_options_tmp) {
                foreach (array_keys($p_options_tmp) as $color) {
                    if (array_search($color, array_keys($p_options)) === false) {
                        // This color was not found in the options, so we can
                        // skip this person.
                        // (Make sure we break out of both foreach loops)
                        continue 2;
                    }
                }
                // This person has all the same options, so append to the array
                $people_with_same_options[] = $p_index_tmp;
            }

            // Remove these options from the other people if the number of
            // people with only these options is equal to the number of options
            if (count($people_with_same_options) === $num_options) {
                foreach ($people as $p_index_tmp => $p_options_tmp) {
                    if (array_search($p_index_tmp, $people_with_same_options) === false) {
                        foreach (array_keys($p_options) as $option) {
                            unset($people[$p_index_tmp][$option]);

                            $has_change = true;
                        }
                    }
                }
            }
        }
    }
}
while ($has_change === true);

// Combine any remaining people into the result and sort it
$results = $results + $people;
ksort($results);

print_r($results);

This produces the following result:

Array
(
    [0] => Array
        (
            [b] => 1
        )

    [1] => Array
        (
            [r] => 1
            [g] => 1
        )

    [2] => Array
        (
            [r] => 1
            [g] => 1
        )

    [3] => Array
        (
            [r] => 1
        )

)

Example 3:

This example does not work with the above code. Suppose there is 1 red ball, 1 green ball, 1 blue ball, one yellow ball and 4 people. Person 1 can choose any ball, person 2 can choose red or green, person 3 can choose green or blue, person 4 can choose red or blue.

Visually this would look like:

Person 1: RGBY
Person 2: RG
Person 3: GB
Person 4: RB

Since the 3 colors red, green and blue are the only options for persons 2, 3 and 4, they are completely contained within these 3 people and they can therefore can all be eliminated from person 1, meaning person 1 must choose yellow. If person 1 were to choose anything but yellow, it would be impossible for the other people to choose their balls.

Putting it into my PHP program, I have these input values:

// The quantity of each ball
$balls = array(
    'r' => 1,
    'g' => 1,
    'b' => 1,
    'y' => 1,
);
// The options available for each person
$options = array(
    array('r', 'g', 'b', 'y'),
    array('r', 'g'),
    array('r', 'b'),
    array('b', 'g'),
);

However I can't think of how to loop through to find cases like this without iterating through every single possible combination of people. Any ideas how this could be done?

Answer 1

I prefer a more OOP-like approach to this. So I basically started from scratch. I hope that's ok with you.

So, the following looks (admittedly) pretty ugly and I haven't tested it with anything but your three examples yet, but here it goes:

class Ball {
    private $color;
    public function __construct($color) {
        $this->color = $color;
    }
    public function getColor() {
        return $this->color;
    }
}
class Ball_resource extends Ball {
    private $num_available;

    public function __construct($color, $number) {
        parent::__construct($color);
        $this->num_available = $number;
    }
    public function take() {
        $this->num_available--;
    }

    public function isExhausted() {
        return $this->num_available <= 0;
    }
}
class Person {
    /**
     *
     * @var Ball
     */
    private $allowed_balls = array();

    public function addConstraint($color) {
        $this->allowed_balls[$color] = new Ball($color);
        return $this;
    }
    public function getConstraints() {
        return $this->allowed_balls;
    }

    public function getNumberOfConstraints() {
        return count($this->allowed_balls);
    }

    /**
     * return true if removal was successful; false otherwise
     */
    public function removeConstraint(Ball $ball) { // todo remove
        if (isset ($this->allowed_balls [$ball->getColor()])) {
            unset ($this->allowed_balls [$ball->getColor()]);
            return true;
        }
        else {
            // this means our puzzle isn't solvable
            return false;
        }
    }
}
class Simplifier {
    /**
     *
     * @var Person
     */
    private $persons = array ();
    /**
     *
     * @var Ball_resource
     */
    private $availableBalls = array ();

    public function addPerson(Person $person) {
        $this->persons[] = $person;
        return $this;
    }
    public function addBallRessource(Ball_resource $ball_resource) {
        $this->availableBalls[] = $ball_resource;
        return $this;
    }


    public function getChoices() {      
        $queue = $this->persons; // shallow copy

        while (count($queue) > 0) {
            // find most constrained person(s)
            $numberOfConstraints = 1; // each person must have at least one constraint
            while (true) {
                $resolve_queue = array();
                foreach($queue as $person) {
                    if ($person->getNumberOfConstraints() === $numberOfConstraints) {
                        $resolve_queue[] = $person;
                    }
                }
                // find mutually dependent constraint groups connected with a person
                $first_run = true;
                foreach ($resolve_queue as $startPerson) {
                    // check if we havent already been removed via dependencies
                    if ($first_run || !self::contains($queue, $startPerson)) {
                        $dependent_persons = $this->findMutuallyDependentPersons($startPerson, $resolve_queue);
                        // make a set out of their combined constraints
                        $combinedConstraints = $this->getConstraintsSet($dependent_persons);
                        $this->adjustResources($dependent_persons);
                        $this->removeFromQueue($dependent_persons, $queue);
                        // substract each ball of this set from all less constrained persons
                        $this->substractConstraintsFromLessConstrainedPersons($queue, $combinedConstraints, $numberOfConstraints);
                        $first_run = false;
                        continue 3;
                    }
                }
                $numberOfConstraints++;
            }

        }
        return $this->persons; // has been altered implicitly   
    }

    private static function contains(array $haystack, Person $needle) {
        foreach ($haystack as $person) {
            if ($person === $needle) return true;
        }
        return false;
    }

    private function findMutuallyDependentPersons(Person $startPerson, array $persons) {
        // add recursion
        $output = array();
        //$output[] = $startPerson;
        foreach($persons as $person) {
            foreach ( $person->getConstraints () as $constraint ) {
                foreach ( $startPerson->getConstraints () as $targetConstraint ) {
                    if ($constraint->getColor () === $targetConstraint->getColor ()) {
                        $output [] = $person;
                        continue 3;
                    }
                }
            }   
        }
        return $output;
    }

    private function getConstraintsSet(array $persons) {
        $output = array();
        foreach ($persons as $person) {
            foreach ($person->getConstraints() as $constraint) {
                foreach($output as $savedConstraint) {
                    if ($savedConstraint->getColor() === $constraint->getColor()) continue 2;                   
                }
                $output[] = $constraint;
            }
        }
        return $output;
    }

    private function substractConstraintsFromLessConstrainedPersons(array $persons, array $constraints, $constraintThreshold) {
        foreach ($persons as $person) {
            if ($person->getNumberOfConstraints() > $constraintThreshold) {
                foreach($constraints as $constraint) {
                    foreach($this->availableBalls as $availableBall) {
                        if ($availableBall->isExhausted()) {
                            $person->removeConstraint($constraint);
                        }
                    }                   
                }
            }
        }
    }

    private function adjustResources(array $persons) {
        foreach($persons as $person) {
            foreach($person->getConstraints() as $constraint) {
                foreach($this->availableBalls as &$availableBall) {
                    if ($availableBall->getColor() === $constraint->getColor()) {
                        $availableBall->take();
                    }
                }
            }
        }
    }

    private function removeFromQueue(array $persons, array &$queue) {       
        foreach ($persons as $person) {
            foreach ($queue as $key => &$availablePerson) {
                if ($availablePerson === $person) {
                    unset($queue[$key]);
                }
            }
        }
    }
}

The whole thing is called like this:

// Example 2
{
    $person1 = new Person();
    $person1->addConstraint("R")->addConstraint("R")->addConstraint("G")->addConstraint("B")->addConstraint("B")->addConstraint("B")->addConstraint("B");
    $person2 = new Person();
    $person2->addConstraint("R")->addConstraint("R")->addConstraint("G");
    $person3 = new Person();
    $person3->addConstraint("R")->addConstraint("R")->addConstraint("G");
    $person4 = new Person();
    $person4->addConstraint("R")->addConstraint("R");

    $redBalls = new Ball_resource("R", 2);
    $greenBalls = new Ball_resource("G", 1);
    $blueBalls = new Ball_resource("B", 4);

    $simplifier = new Simplifier();
    $simplifier->addPerson($person1)->addPerson($person2)->addPerson($person3)->addPerson($person4);
    $simplifier->addBallRessource($redBalls)->addBallRessource($greenBalls)->addBallRessource($blueBalls);
    $output = $simplifier->getChoices();

    print_r($output);
}

And likewise for Example 3:

// Example 3
{
    $person1 = new Person();
    $person1->addConstraint("R")->addConstraint("G")->addConstraint("B")->addConstraint("Y");
    $person2 = new Person();
    $person2->addConstraint("R")->addConstraint("G");
    $person3 = new Person();
    $person3->addConstraint("G")->addConstraint("B");
    $person4 = new Person();
    $person4->addConstraint("R")->addConstraint("B");

    $redBalls = new Ball_resource("R", 1);
    $greenBalls = new Ball_resource("G", 1);
    $blueBalls = new Ball_resource("B", 1);
    $yellowBalls = new Ball_resource("Y", 1);   

    $simplifier = new Simplifier();
    $simplifier->addPerson($person1)->addPerson($person2)->addPerson($person3)->addPerson($person4);
    $simplifier->addBallRessource($redBalls)->addBallRessource($greenBalls)->addBallRessource($blueBalls)->addBallRessource($yellowBalls);
    $output = $simplifier->getChoices();

    print_r($output);
}

I have omitted the original output for brevity. But for the the second example it essentially equals your last respective listing in the question and for Example 3 it produces the equivalent of:

Person 1: Y
Person 2: RG
Person 3: GB
Person 4: RB

Answer 2

What I decided to do in the end was a semi brute force, however I tweaked it so that it doesn't have to go through every single combination, so in most cases there should be far less iterations than every single combination possible.

The total number of combinations is equal to exp(2,count(balls)) (i.e. 2^{types of balls}), so if we have 20 types of balls, that's 1048576 different combinations of balls that we would have to check if we were to check every one. Not only is that too many iterations, I actually ran out of memory way before this with only 16 ball colors.

To get every single combination possible, you can use this function (Source):

function getAllCombinations($balls) {
    // initialize by adding the empty set
    $results = array(array( ));

    foreach ($balls as $color => $number) {
        foreach ($results as $combination) {
            $results[] = array_merge(array($color), $combination);
        }
    }

    return $results;
}

However if we go back to our original rule:

If there are $n number of people who all have the same $n number of options (or a subset of them), these options can be removed from all other people, where $n is less than the total number of people.

as we can see, we can skip any future iterations if we have already exceeded $n number of options. Note, when we have multiple number of the same color of ball that counts as multiple balls in this function.

Once we get the different possible sub-sets, we loop over the people to see if we have $n different people using that subset and remove those values from all other people. This is what I came up with in the end:

/**
 * This just gets a sum of the number of balls a person can choose
 * from
 */
function getNumberOfOptions($person, $balls) {
    $n = 0;
    foreach ($person as $allowed_ball) {
        $n += $balls[$allowed_ball];
    }
    return $n;
}

/**
 * This function finds all the subsets of the balls array that we can look for
 * in the people array later to remove options from them
 */
function getBallSubsets($balls, $max_n) {
    // initialize by adding the empty set
    $results = array(array( ));

    // Remove all balls that have more options than max_n
    foreach ($balls as $color => $number) {
        if ($number > $max_n) {
            unset($balls[$color]);
        }
    }

//    $n = 0;
    foreach ($balls as $color => $number) {
        foreach ($results as $combination) {
//            $n++;
            $set = array_merge(array($color), $combination);
            if (getNumberOfOptions($set, $balls) <= $max_n) {
                $results[] = $set;
            }
        }
    }

//    echo $n; exit;  
    return $results;
}

function removeFromOthers($colors, $people, $skip_indexes) {
    foreach ($people as $p_index => $person) {
        if (array_search($p_index, $skip_indexes) === false) {
            foreach ($colors as $color) {
                $index = array_search($color, $person);
                if ($index !== false) {
                    unset($people[$p_index][$index]);
                }
            }
        }
    }
    return $people;
}

function getOptions($people, $balls) {
    $ball_subsets = getBallSubsets($balls, count($people) -1);

    foreach ($ball_subsets as $sub) {
        $num_colors = count($sub);
        $num_people = getNumberOfOptions($sub, $balls);

        // Loop through people and if we find $n people with only the elements
        // from this subset, we can remove these elements from all other people
        $found = [];
        $found_colors = [];
        foreach ($people as $p_index => $person_arr) {
            foreach ($person_arr as $color) {
                // Contains another color, so skip this one
                if (array_search($color, $sub) === false) {
                    continue 2;
                }
            }
            $found[] = $p_index;
            foreach ($person_arr as $color) {
                if (array_search($color, $found_colors) === false) {
                    $found_colors[] = $color;
                }
            }
        }
        if (count($found) === $num_people && count($found_colors) == $num_colors) {
            $people = removeFromOthers($sub, $people, $found);
        }
        else {
            unset($found);
        }
    }
    return $people;
}

// The quantity of each ball
$balls = array(
    'r' => 3,
    'g' => 2,
    'b' => 1,
    'k' => 16,
);
// The options available for each person
$people = array(
    array('r', 'g', 'b', 'k'),
    array('r', 'g'),
    array('r', 'b'),
    array('b', 'g'),
);

print_r($people);
$options = getOptions($people, $balls);
print_r($options);

This seems to work for any values I have tried. In the above example, we have 4 different ball colors (2^4 = 16 total combinations), however we only need to do 6 iterations in our getBallSubsets() function, so this is much more efficient than brute forcing every single possible combination.