Solving Spotify puzzles using Swift

You must have at some stage attempted to learn about algorithms and searched for puzzles to write algorithms for to solve. There are three interesting puzzles laid out by Spotify at https://labs.spotify.com/puzzles/. We shall have a look at solving those using Swift

1. [Easy] Reverse a Binary Number

The challenge involves a couple of things, it first expects you to convert an Integer into Binary, then reverse the string, and finally from that reversed string generate an Int and return this.

So for example, you are given the number 13 , which is Binary "1101" (2^3 + 2^2 + 0 + 2^0) .
Next we reverse this binary string to get "1011" which is (2^3 + 0 + 2^1 + 2^0) = 11
so if we reverse 13 in binary, we should get 11

Step 1

Let’s Convert the Integer into a binary string. There are plenty of articles that will walk you through converting an Int into a binary, the idea is simple, if the modulus of the Integer is 1, then prefix a 1 to the result string, otherwise prefix a 0. Divide the number by 2 and continue till the number is greater than zero. This is good, but …

WHY reinvent the wheel? If swift offers you an optimized way to deal with this, why do you want to do that yourself?
In swift it is one line of code, and it was covered earlier in this article http://swift.oz-apps.com/2015/09/convert-binary-string-to-integer/

So we can simply get a string by casting the number to a string as

next we can reverse a string by using the reversed() function on the string, however the function is now no longer available on the string, instead it is available on the characters collection, so it is as simple as String(String(num, radix:2).characters.reversed()) though it takes two String casting calls.

Now we have a string with the reversed of the binary representation of the number.

Finally we need to get the Integer from this, again either you can draw upon your uni days to know how to convert a binary string into a number, i.e. transverse through each character in the string and if it is 1, add the value of 2^index to the result, where index is a value from 0 to the number of characters in the string.

instead of all this, you can simply use a strtoul() function available to you as strtoul("1011", nil, 2) which is called in one line as

and there we have it, we have converted a number into binary, reversed it and converted it back into a number and returned the value.

2. [Medium] – Zipf’s Song

This is also quite simple when you consider the ease of use with Swift. The problem is defined as follows, you are given the number of plays of a particular song and the qi is calculated which determines the quality of the track. This is calculated as qi = fi / zi , where i is the track in discussion and fi determines the number of plays. It also predicts that the zi is proportional to the position of the track in the album, so it is 1/i . However, many of the things are not as clear in the description, this is the extract of what you need to know.
From here if you understand these basics, then the rest is quite simple and you can easily write code to solve Zipf’s Song problem.

Let’s look at the sample data
Sample input 1

Sample output 1

Solving Zipf’s song

1. The formula we are interested in is qi = fi / zi
2. Where zi = 1/i , so qi = fi / 1/i ==> q1 = fi * i
3. Once you get this, it gets easier to solve. This is that lightbulb moment

so if we were to solve this, we would first read the first line from the console. It would give us “4 2” this indicates to us that there are 4 records and the output expects the top 2 results.
Next we read the lines 4 times and we get the plays and the name of the song. We can calculate the qi from this by simply multiplying the plays ( fi ) by the index i .

If we were to load this in a memory model, we would have something like

next we sort these by the largest qi and then return the top 2 results. While it sounds so simple, it is a pain in many languages to sort an array and then to get slices. However this is where swift shines once again.

After sorting the array

The input suggested that it required the top two results, so we get

as the output.

a simple ARRAY.sort(<) function sorts the array and then simply referencing a slice as [0..<nOut] will return the first nOut slices of the array.

Code:

that’s all there is to it.

In Summary

I don’t feel that this was hard, however maybe it is because of the language and the features it offers, most of these quizzes were made for languages like C and Java. If you are a Ruby, Python or Lua user, you could find an equally simple way to deal with these puzzles.

It is the writing on the wall that the time for languages like Java are up. Do not dismiss Swift as a high level language, it can do some amazing things and most importantly, you can actually decouple your logic and UI and still read your code with Swift, which would have been a bit difficult with Java or C++. More on that later… till next time.

Views All Time
Views All Time
251
Views Today
Views Today
1
Posted in Algorithm, puzzle, Tutorial, Uncategorized.