Last active
August 29, 2015 14:20
-
-
Save kohnmd/3a3155471154e755e4c5 to your computer and use it in GitHub Desktop.
CareerCup min range
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
<?php | |
/** | |
* CareerCup min range. | |
* | |
* This is NOT a working solution. By dumb luck it happened to solve the problem | |
* for the example lists, but completely crumbles when presented with: | |
* - more than 3 lists. | |
* - sadistic lists like: | |
* array(0, 1, 2, 3, 4) | |
* array(5, 6, 7, 8, 9) | |
* array(10, 11, 12, 13, 14) | |
* | |
* @link http://www.careercup.com/question?id=16759664 | |
*/ | |
require_once 'item.php'; | |
require_once 'range.php'; | |
// Define lists | |
$list1 = array(4, 10, 15, 24, 26); | |
$list2 = array(0, 9, 12, 20); | |
$list3 = array(5, 18, 22, 30); | |
$k = 3; // number of lists | |
// Arange list items into a merged array | |
$items = array(); | |
for ($i = 1; $i <= $k; $i++) { | |
$listName = 'list' . $i; | |
foreach ($$listName as $listItem) { | |
$items[] = new item($i, $listItem); | |
} | |
} | |
// Sort merged array by values | |
usort($items, array('item', 'compare_items')); | |
// Find the smallest range | |
$minRange = null; | |
for ($i = 0; $i < count($items) - 2; $i++) { | |
$curRange = new range($items[$i], $items[$i+2]); | |
// Skip if both items come from the same list | |
if ($curRange->itemMax->list == $curRange->itemMin->list) { | |
continue; | |
} | |
// Skip if current range is larger than existing minimum range, or | |
// if the item between the current two is not in the third list | |
if (!is_null($minRange) | |
&& ($minRange->amount() < $curRange->amount() | |
|| $items[$i+1]->list == $curRange->itemMax->list | |
|| $items[$i+1]->list == $curRange->itemMin->list) | |
) { | |
continue; | |
} | |
// Current range is value, and smaller than the existing minimum range | |
$minRange = $curRange; | |
} | |
print_r($minRange->values()); |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
<?php | |
class item | |
{ | |
public $list; | |
public $value; | |
public function __construct($list, $value) | |
{ | |
$this->list = $list; | |
$this->value = $value; | |
} | |
public static function compare_items(item $a, item $b) | |
{ | |
if ($a->value == $b->value) { | |
return 0; | |
} | |
return ($a->value < $b->value) ? -1 : 1; | |
} | |
} |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
<?php | |
class range | |
{ | |
public $itemMin; | |
public $itemMax; | |
public function __construct(item $itemMin, item $itemMax) | |
{ | |
$this->itemMin = $itemMin; | |
$this->itemMax = $itemMax; | |
} | |
public function amount() | |
{ | |
return $this->itemMax->value - $this->itemMin->value; | |
} | |
public function values() | |
{ | |
return array($this->itemMin->value, $this->itemMax->value); | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment