The Zoo problem

I just discovered TopCoder, and I got hooked. I’m going to post here some of of the easiest archived problems and their solutions (I’ll start with the hard ones later).

This one is called simply “Zoo” and it is about a fox that wants to know if zoo’s rabbits are taller than cats. This guy is kind of blind, so he can’t distinguish between rabbits and cats or between a shorter and taller animal either. But he can ask each animal the following question:

“How many animals of the same kind as you are taller than you?”

There is another important thing: each animal knows if another animal of the same kind is taller or not, in other words: there aren’t two cats of the same height and there aren’t two rabbits of the same height.

The problem also states the following:

“There are N animals numbered 0 to N-1″
“Each animal is a rabbit or a cat”
” The answer given by the i-th animal is answers[i]“

You may think that the little fox won’t be able to determine if cats are taller than rabbits just by knowing the answers from each animal, and that’s true, he will only know how many possible “configurations” are there. So we should provide him that; the number of possible configurations.

The full description of the problem is here.

So we are given an array of integers such that each index i of the array is the name of an animal and the value in that position is i’s answer. That said, if we have an input like [0,1] we can say that both animal 0 and 1 are rabbits or cats, because if animal 0 was a cat and animal 1 a rabbit, animal 1 would be lying  (saying that there is another cat taller than her).

So we have two obvious conditions:

  1. Both cats and rabbits answers, are sets formed by consecutive integers.
  2. Both sets, should have a tallest animal, so the number 0 should be present.

A “configuration” is a division of the answers indexes (since we can think of these as animal names) into TWO sets that satisfy the previous conditions.

Now let’s analyze  the example output number 3:

{1, 0, 2, 0, 1}
Returns: 8

Why 8? because that is the number of ways we can accommodate animal 0, animal 1, animal 2, animal 3, and animal 4 given their answers (I’ll call them simply a0, a1, a2, a3), the following table shows the 8 possible configurations for this input, each cell shows the answer of the animal and its name.

Rabbits Cats Rabbits Cats Rabbits Cats Rabbits Cats Rabbits Cats Rabbits Cats Rabbits Cats Rabbits Cats
0 a1 0 a3 0 a3 0 a1 0 a1 0 a3 0 a3 0 a1 0 a1 0 a3 0 a3 0 a1 0 a1 0 a3 0 a3 0 a1
1 a0 1 a4 1 a0 1 a4 1 a4 1 a0 1 a4 1 a0 1 a0 1 a4 1 a0 1 a4 1 a4 1 a0 1 a4 1 a0
2 a3 2 a3 2 a3 2 a3 2 a3 2 a3 2 a3 2 a3

 

For the couple of animals whose answers are 0 we have two possibilities, a1 is a cat and a3 is a rabbit or the opposite way. For the next couple of animals (the ones that answered 1), we have the same two possibilities, but the number of combinations satisfying the conditions between a1,a3,a4 and a0 is 4.
When we add the last animal a2 we duplicate the number of combinations again, staying with 8 possible combinations at the end. already seen a pattern? sure.

Lets make some code, first of all, we have to verify if animals are lying, or more exactly: if we can take the input and make two sets of consecutive integers starting with 0

function theCount(answers){
	
	answers.sort(function(a,b){ return a - b; });
	var l = answers.length;
	var s1 = 0, s2 = 0;
	
	for(var i = 0; i< l; i++){ 
		if (answers[i] == s1) 
			s1++; 
		else if (answers[i] == s2) 
			s2++; 
		else
			return 0;
	} 
	...
}

This way [1, 0, 2, 0, 1] turns into [0, 0, 1, 1, 2] and we can check if both sets are made of consecutive numbers by traversing the new array

The next thing to do is figure out the number of configurations, and if you noticed that the size of the sets determines the number of admissible combinations you are absolutely right, there is no need to generate any configuration; once we proved that animals are honest (got consecutive numbers), we just have to grab the size of both sets and return 2 to the power of the size of the sets. So if we have [0,1,0,1] as input, the generated sets size will be 2, and the number of configurations is 2^2 = 4.

There is one more thing we’re missing; if the sets are not of the same size, as it happens in [0, 0, 1, 1, 2] what do we do?
Note that the conditions to form the sets (consecutiveness and 0-starting) make the number of possible configurations between say [0,0,1,1]( 4 possibilities ) and [0,0,1,1,2,3,4,5] exactly the same. See below:

Rabbits Cats Rabbits Cats Rabbits Cats Rabbits Cats
0 a0 0 a1 0 a1 0 a0 0 a0 0 a1 0 a1 0 a0
1 a2 1 a3 1 a2 1 a3 1 a3 1 a2 1 a3 1 a2
2 a4 2 a4 2 a4 2 a4
3 a5 3 a5 3 a5 3 a5
4 a6 4 a6 4 a6 4 a6
5 a7 5 a7 5 a7 5 a7

 

No matter how different in size both sets are, the number of possibilities gets duplicated just once.

So finally our problem is solved: if both sets contain the same amount of elements, return 2^size, if not just return 2^(size_of_the_smallest_set + 1). So, for an input of [0,0,1,1,2] we have 2 rabbits and 3 cats or vice versa, so 2^(2+1) = 2^3 = 8 is the number of possible configurations. Let’s code it up:

function theCount(answers){
	
	answers.sort(function(a,b){ return a - b; });
	var l = answers.length;
	var s1 = 0, s2 = 0;
	
	for(var i = 0; i< l; i++){ 
		if (answers[i] == s1) 
			s1++; 
		else if (answers[i] == s2) 
			s2++; 
		else
			return 0;
	} 
	return (s1 == s2)? Math.pow( 2, s1) : Math.pow( 2, Math.min(s1,s2) + 1 );
}