New Spotify Puzzles - Reversed Binary, Zipf's song, Cat vs. Dog - solutions

I discovered some months ago that Spotify has published some new puzzles. I love the puzzles, and was impossible to me resist the tentation to solve all of them :)

Reversed Binary Numbers

https://www.spotify.com/es/jobs/tech/reversed-binary/

Solution:
 - https://github.com/alonsovidales/spotify-puzzles-v2/blob/master/reversed_binary/reversed_binary.py

This is the simplest problem, I used less than ten minutes to solve it.
The steps to solve it are:

1. Get the string representation of the number in binary using the bin() Python function
2. Remove the first two characters, that Python adds to identify the string as a binary representation using the [:] notation
3. Using [::-1] Python will reverse the array (-1 is the step)
4. Convert the reversed array to an integer again using the int() call and specifying as second parameter the base 2

Zipf's song

http://www.spotify.com/es/jobs/tech/zipfsong/
Solution:
 - https://github.com/alonsovidales/spotify-puzzles-v2/blob/master/zipfsong/zipfsong.py

This puzzle was a little more complicated, not for the problem, is only to apply a simple formula, was because the team who did the puzzles made a little mistake and the platform always was returning a "Run Time Error" each time that I tried to send the answer, I wasted around two hours trying to found the error on my code, and when all the hope was left, one of the persons in charge of the puzzles sent me an e-mail:

Was really nice discover that was a concerned team behind the puzzles, and that I was not in a mistake :)

The steps to solve this puzzle are:

1. Calculate the quality of each song applying the formula: number of times plus the song position
2. Sort the array of tracks by quality
3. Split the array to get only the necessary song names
4. Return the list of tracks as a string

Cat vs. Dog

https://www.spotify.com/es/jobs/tech/catvsdog/
Solution:
 - https://github.com/alonsovidales/spotify-puzzles-v2/blob/master/catvsdog/catvsdog.py

This is the most complicated of the three problems, but if you remember the old puzzle "Bilateral":
 - http://alonso-vidales.blogspot.com.es/2012/03/spotify-bilateral-projects-puzzle.html
is much more simple :)
Reading the puzzle was easy to discover some clues:

1. Also, based on the universal fact that everyone is either a cat lover (i.e. a dog hater) or a dog lover (i.e. a cat hater), it has been decided that each vote must name exactly one cat and exactly one dog. -> Is a bipartite graph
2. procedure which guarantees that as many viewers as possible will continue watching the show -> Is a maximun cardinality problem :)

Then we have a bipartite graph:

 - http://en.wikipedia.org/wiki/Bipartite_graph

Now we have a reduced number of algorithms to apply with a small complexity. 

We have two options, study the compatible or the incompatible graphs of voters. If we build the bipartite graph of the incompatible voters, we can obtain the maximun matching on this graph, and a full coverage of all the vertex.

The minimun number of edges who cover all the vertexes of the incompatibles graph are equal to the minimun number of voters to be discarded in order to obtain the maximun number of happy voters :)

To obtain this we found an old friend, one of the most beautiful algorithms, the Hopcroft-Karp algorithm (the same to be used in order to solve the old puzzle):

 - http://en.wikipedia.org/wiki/Hopcroft%E2%80%93Karp_algorithm

The steps to solve the problem are:

1. Create the bipartite graph of incompatible voters, I used sets to do it as fast as possible
2. Apply the Hopcroft-Karp algorith to obtain the min number of edges who cover all the graph
3. Subtract the number of edges who cover the graph of the total number of voters, this will give us the max number of happy voters that we can obtain :)

Thanks Spotify for this puzzles :)