$line) { // If the line has a digit it's a new person if (preg_match('/(?\w+)\s+(?\d+)/', $line, $matches)) { $accuserName = $matches['name']; $accusations = getAccusationsFromLine($lines, $line_num, $matches['numNames']); $accuser = getOrCreatePerson($accuserName); $people[$accuserName]['accusing'] = $accusations; // Add the accusations to this accuser // Loop through each accused person and update their accusedby record foreach ($accusations as $accusedName) { $accused = getOrCreatePerson($accusedName); $people[$accusedName]['accusedby'][] = $accuserName; } unset($matches); } } /* Loop through each person and use his relationships to determine who his telling the truth */ $personCounter = 0; foreach ($people as $name => $relationships) { if ($personCounter == 0) { // Make the first person be honest since actual honesty/dishonesty doesn't matter $honest[] = $name; $personCounter++; } establishTruthiness($name); } /* Output the final results */ $groupNumbers = array(count($liars), count($honest)); rsort($groupNumbers); echo "{$groupNumbers[0]} {$groupNumbers[1]}\n"; /* Functions referenced to process each person are below */ function getAccusationsFromLine($lines, $startLine, $numLines) { /* Returns an array of people accused of lying */ $accusations = array(); foreach (array_slice($lines, $startLine, $numLines) as $name) { $accusations[] = trim($name); } return $accusations; } function getOrCreatePerson($name) { $personExists = array_key_exists($name, $GLOBALS['people']); if ($personExists == false) { // Person is not yet in array, so let's add the person $person = array('accusing' => array(), 'accusedby' => array()); $GLOBALS['people'][$name] = $person; } else { $person = $GLOBALS['people'][$name]; } return $person; } function establishTruthiness($name) { $truthiness = ''; $relationships = $GLOBALS['people'][$name]; // For people accused by or who accuse this person, it doesn't matter in which group they fall // So put them all into one easier to manage array $relatedNames = array_unique(array_merge($relationships['accusedby'], $relationships['accusing'])); /* Easiest: check if this person is already recorded as honest or a liar */ if (in_array($name, $GLOBALS['honest']) == true) { $truthiness = 'honest'; } elseif (in_array($name, $GLOBALS['liars']) == true) { $truthiness = 'liar'; } else { /* Hardest: check this persons accusers and accusations to establish honest or liar */ foreach ($relatedNames as $relatedName) { $relatedTruthiness = establishTruthiness($relatedName); // Let's get recursive switch ($relatedTruthiness) { case 'honest': // Accused is honest, so this person lies or the accuser is honest so this person lies $GLOBALS['liars'][] = $name; // Register this person as a liar $truthiness = 'liar'; break; case 'liar': // Accused is a liar, so this person is honest or the accuser lies so this person is honest $GLOBALS['honest'][] = $name; // Register this person as honest $truthiness = 'honest'; break; } } } switch ($truthiness) { case 'honest': $GLOBALS['liars'] = array_unique(array_merge($GLOBALS['liars'], $relatedNames)); // Register accused and accusers as liars break; case 'liar': $GLOBALS['honest'] = array_unique(array_merge($GLOBALS['honest'], $relatedNames)); // Register accused and accusers as honest break; } return $truthiness; } ?>