Pi's father, Danny, runs the Hackerville Zoo. He is moving to Rookieville
and wants to take all of the zoo animals with him via ship. He is
confused about how to arrange them because a few of the species
cannot be kept together in the same cabin.
There are n animals placed in a straight line. Each animal is identified
by a unique number from 1 to n in order. There are m pairs (a[i], b[i])
which imply that animals a[i] and b[i] are enemies and should not be
kept in the same cabin. Pi is good at solving problems and he came up
with following challenge: count the number of different groups that
do not contain any pair such that they are enemies. A group is defined
as an interval (x, y) such that all animals in the range from x to y form a
group. Determine the number of groups that can be formed according
to the Pi's challenge.
For example, given n = 3 animals and m = 3 pairs of enemies, a = [1, 2,
3] and b = [3, 3, 1], animal 1 is the enemy of animal 3, and animal 3 is
the enemy of animals 1 and 2. Because 3 is an enemy of both 1 and 2, it
must be in its own cabin. Animals 1 and 2 can be roomed together or
separately.
There are four possible groupings meeting the constraints:
{1, 2} , {1}, {2}, {3}.
Note that the intervals are along the original line of animals numbered consecutively from 1 to n, i.e. [1, 2, 3] in this case.
They cannot be reordered.
Function Description
Complete the function angryAnimals in the editor below. The function
must return the number of groups that can be formed according to Pi's
challenge.
angryAnimals has the following parameters:
n: an integer that denotes the number of unique animals
a[a[0],...a[m-1]]: an array of integers
b[b[0],...b[m-1]]: an array of integers
Constraints
1 ≤ n ≤ 10
1 ≤ m ≤ 10
1 ≤ a[i], b[i] ≤ n
I have been able to get different combinations but I am finding it hard to compare and remove combinations for where the enemies appear together.
function __construct($s, $k) {
if(is_array($s)) {
$this->s = array_values($s);
$this->n = count($this->s);
} else {
$this->s = (string) $s;
$this->n = strlen($this->s);
}
$this->k = $k;
$this->rewind();
}
function key() {
return $this->pos;
}
function current() {
$r = array();
for($i = 0; $i < $this->k; $i++)
$r[] = $this->s[$this->c[$i]];
return is_array($this->s) ? $r : implode('', $r);
}
function next() {
if($this->_next())
$this->pos++;
else
$this->pos = -1;
}
function rewind() {
$this->c = range(0, $this->k);
$this->pos = 0;
}
function valid() {
return $this->pos >= 0;
}
//
protected function _next() {
$i = $this->k - 1;
while ($i >= 0 && $this->c[$i] == $this->n - $this->k + $i)
$i--;
if($i < 0)
return false;
$this->c[$i]++;
while($i++ < $this->k - 1)
$this->c[$i] = $this->c[$i - 1] + 1;
return true;
}
Sample Input For Custom Testing
4
2
1
2
2
3
4
My Output
1
2
3
4
12
13
14
23
24
34
123
124
134
234
1234
15.
Expected Output
1
2
3
4
12
23
34
7.
Explanation (1), (1,2), (2), (2,3), (3), (3,4), (4) are the 7 groups that were formed according to Pi's challenge.
https://drive.google.com/file/d/18kHmOiJ8HQ8uA7BqQZ3GQ6eVZ4afn2Fm/view?usp=sharing
