php - Eliminating impossible choices -
i'm having bit of trouble trying wrap head around problem programatically. isn't i'm doing, simplify things, have number of balls , number of people. each person must choose 1 ball , people may limited type of ball can choose. objective determine options people have choose after eliminating impossible combinations.
example 1:
in simple case, have 2 people , 1 red ball , 1 green ball. person 1 can choose either ball, person 2 can choose green ball. can illustrated like:
person 1: rg person 2: g since know person 2 must choose green ball, means person 1 cannot choose ball , therefore must choose red ball. can simplified to:
person 1: r person 2: g so in case know each person chose.
example 2:
now let's add bit of complexity. have 4 people need chose 2 red balls, 1 green ball , 4 blue balls. person 1 can choose ball, person 2 , 3 can choose red or green balls , person 4 must choose red ball. have following choices:
person 1: rrgbbbb person 2: rrg person 3: rrg person 4: rr since person 4 has 1 type of option, know person must choose red ball. can therefore eliminate 1 red ball other people:
person 1: rgbbbb person 2: rg person 3: rg person 4: rr however gets tricky. can see, person 2 , 3 must choose 1 red , 1 green ball, don't know 1 choose which. since have 1 of each ball remaining, red , green can eliminated option person 1:
person 1: bbbb person 2: rg person 3: rg person 4: rr now can remove duplicates each entry left following options:
person 1: b person 2: rg person 3: rg person 4: r we know choice of person 1 , person 4, , person 2 , 3 have choice between red , green.
to solve this, loop on people , first if people have 1 ball type, remove person array , put in results array (since know person must choose) , remove 1 of ball type every other person in array if present.
after this, seems me rule is:
if there
$nnumber of people have same$nnumber of options (or subset of them), these options can removed other people,$nless total number of people.
so loop through people again , check other people have same options available (or subset of options) , if equal total number of options person, remove them options other people.
here's have far solve these 2 cases:
// quantity of each ball $balls = array( 'r' => 1, 'g' => 1, 'b' => 1, 'k' => 1, ); // options available each person $options = array( array('r', 'g', 'b', 'k'), array('r', 'g'), array('r', 'b'), array('b', 'g'), ); // put both of these 1 array $people = []; foreach ($options $option) { $person = []; foreach ($option $ball_key) { $person[$ball_key] = $balls[$ball_key]; } $people[] = $person; } print_r($people); // produces 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 // ) // // ) // used hold final result $results = []; { // if changes, needs set true. time // changes loop through again in case caused cascading // effect $has_change = false; // step 1: // find out if there people have 1 option , remove // array , add result , subtract 1 other // people option foreach ($people $p_index => $p_options) { if (count($p_options) === 1) { $color = key($p_options); foreach ($people $p_index_tmp => $p_options_tmp) { // it's current person, skip if ($p_index_tmp === $p_index) { continue; } if (isset($p_options_tmp[$color])) { // subtract 1 color person , if zero, // remove it. if (--$people[$p_index_tmp][$color] === 0) { unset($people[$p_index_tmp][$color]); } $has_change = true; } } // add results array , remove people array $results[$p_index] = array($color => 1); unset($people[$p_index]); } } // step 2: // if there $n number of people have same $n number of // options (or subset of them), these options can removed // other people, $n less total number of people foreach ($people $p_index => $p_options) { $num_options = array_sum($p_options); if ($num_options < count($people)) { // other people no different options ones // person has $people_with_same_options = []; foreach ($people $p_index_tmp => $p_options_tmp) { foreach (array_keys($p_options_tmp) $color) { if (array_search($color, array_keys($p_options)) === false) { // color not found in options, can // skip person. // (make sure break out of both foreach loops) continue 2; } } // person has same options, append array $people_with_same_options[] = $p_index_tmp; } // remove these options other people if number of // people these options equal number of options if (count($people_with_same_options) === $num_options) { foreach ($people $p_index_tmp => $p_options_tmp) { if (array_search($p_index_tmp, $people_with_same_options) === false) { foreach (array_keys($p_options) $option) { unset($people[$p_index_tmp][$option]); $has_change = true; } } } } } } } while ($has_change === true); // combine remaining people result , sort $results = $results + $people; ksort($results); print_r($results); this produces 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 above code. suppose there 1 red ball, 1 green ball, 1 blue ball, 1 yellow ball , 4 people. person 1 can choose ball, person 2 can choose red or green, person 3 can choose green or blue, person 4 can choose red or blue.
visually like:
person 1: rgby person 2: rg person 3: gb person 4: rb since 3 colors red, green , blue options persons 2, 3 , 4, contained within these 3 people , can therefore can eliminated person 1, meaning person 1 must choose yellow. if person 1 choose yellow, impossible other people choose balls.
putting php program, have these input values:
// quantity of each ball $balls = array( 'r' => 1, 'g' => 1, 'b' => 1, 'y' => 1, ); // options available each person $options = array( array('r', 'g', 'b', 'y'), array('r', 'g'), array('r', 'b'), array('b', 'g'), ); however can't think of how loop through find cases without iterating through every single possible combination of people. ideas how done?
i prefer more oop-like approach this. started scratch. hope that's ok you.
so, following looks (admittedly) pretty ugly , haven't tested 3 examples yet, here 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 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 { // 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 constrained person(s) $numberofconstraints = 1; // each person must have @ least 1 constraint while (true) { $resolve_queue = array(); foreach($queue $person) { if ($person->getnumberofconstraints() === $numberofconstraints) { $resolve_queue[] = $person; } } // find mutually dependent constraint groups connected person $first_run = true; foreach ($resolve_queue $startperson) { // check if havent been removed via dependencies if ($first_run || !self::contains($queue, $startperson)) { $dependent_persons = $this->findmutuallydependentpersons($startperson, $resolve_queue); // make set out of combined constraints $combinedconstraints = $this->getconstraintsset($dependent_persons); $this->adjustresources($dependent_persons); $this->removefromqueue($dependent_persons, $queue); // substract each ball of set 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 $person) { if ($person === $needle) return true; } return false; } private function findmutuallydependentpersons(person $startperson, array $persons) { // add recursion $output = array(); //$output[] = $startperson; foreach($persons $person) { foreach ( $person->getconstraints () $constraint ) { foreach ( $startperson->getconstraints () $targetconstraint ) { if ($constraint->getcolor () === $targetconstraint->getcolor ()) { $output [] = $person; continue 3; } } } } return $output; } private function getconstraintsset(array $persons) { $output = array(); foreach ($persons $person) { foreach ($person->getconstraints() $constraint) { foreach($output $savedconstraint) { if ($savedconstraint->getcolor() === $constraint->getcolor()) continue 2; } $output[] = $constraint; } } return $output; } private function substractconstraintsfromlessconstrainedpersons(array $persons, array $constraints, $constraintthreshold) { foreach ($persons $person) { if ($person->getnumberofconstraints() > $constraintthreshold) { foreach($constraints $constraint) { foreach($this->availableballs $availableball) { if ($availableball->isexhausted()) { $person->removeconstraint($constraint); } } } } } } private function adjustresources(array $persons) { foreach($persons $person) { foreach($person->getconstraints() $constraint) { foreach($this->availableballs &$availableball) { if ($availableball->getcolor() === $constraint->getcolor()) { $availableball->take(); } } } } } private function removefromqueue(array $persons, array &$queue) { foreach ($persons $person) { foreach ($queue $key => &$availableperson) { if ($availableperson === $person) { unset($queue[$key]); } } } } } the whole thing called 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 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 original output brevity. the second example equals last respective listing in question , example 3 produces equivalent of:
person 1: y person 2: rg person 3: gb person 4: rb 
Comments
Post a Comment