Skip to content

Commit 2bf2ab5

Browse files
yuriymaradegonSchiele
authored andcommitted
Add PHP example based on DS extension for chapter 08 - greedy algorithms (egonSchiele#97)
* Add PHP example based on DS extension for chapter 08 - greedy algorithms * Add code formatting * Add code formatting / 2
1 parent ac08df2 commit 2bf2ab5

File tree

1 file changed

+36
-0
lines changed

1 file changed

+36
-0
lines changed
Lines changed: 36 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,36 @@
1+
<?php
2+
// You need to install Data Structures (DS) extension.
3+
// More details here - http://php.net/manual/en/book.ds.php
4+
use \Ds\Set;
5+
6+
$statesNeeded = new Set(["mt", "wa", "or", "id", "nv", "ut", "ca", "az"]);
7+
$stations = [];
8+
$stations["kone"] = new Set(["id", "nv", "ut"]);
9+
$stations["ktwo"] = new Set(["wa", "id", "mt"]);
10+
$stations["kthree"] = new Set(["or", "nv", "ca"]);
11+
$stations["kfour"] = new Set(["nv", "ut"]);
12+
$stations["kfive"] = new Set(["ca", "az"]);
13+
$finalStations = new Set();
14+
15+
while (!$statesNeeded->isEmpty()) {
16+
$bestStation = null;
17+
$statesCovered = new Set();
18+
foreach (array_keys($stations) as $station) {
19+
$states = $stations[$station];
20+
$covered = new Set($statesNeeded);
21+
$covered = $covered->filter(function ($value) use ($states) {
22+
return $states->contains($value);
23+
});
24+
if ($covered->count() > $statesCovered->count()) {
25+
$bestStation = $station;
26+
$statesCovered = $covered;
27+
}
28+
}
29+
$statesNeeded = new Set($statesNeeded);
30+
$statesNeeded = $statesNeeded->filter(function ($value) use ($statesCovered) {
31+
return !$statesCovered->contains($value);
32+
});
33+
$finalStations->add($bestStation);
34+
}
35+
36+
print_r($finalStations); // ["kone", "ktwo", "kthree", "kfive"]

0 commit comments

Comments
 (0)