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 https://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
String(num, radix: 2)
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
strtoul(String(String(num, radix: 2).characters.reversed()), nil, 2)
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
4 2 30 one 30 two 15 three 25 four
Sample output 1
four two
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
fi name index qi --------------------- 30 one 1 30 30 two 2 60 15 three 3 45 25 four 4 100
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
fi name index qi --------------------- 25 four 4 100 30 two 2 60 15 three 3 45 30 one 1 30
The input suggested that it required the top two results, so we get
four two
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:
// For now we are creating an array of the input
let data = [
"15 3",
"197812 re_hash",
"78906 5_4",
"189518 tomorrow_comes_today",
"39453 new_genious",
"210492 clint_eastwood",
"26302 man_research",
"22544 punk",
"19727 sound_check",
"17535 double_bass",
"18782 rock_the_house",
"198189 19_2000",
"13151 latin_simone",
"12139 starshine",
"11272 slow_country",
"10521 m1_a1"
]
// Next we parse the first line
let line1 = data[0].components(separatedBy: " ")
let nRecs = Int(line1[0])! // Number of records
let nOut = Int(line1[1])! // Number of Output lines
// Next we create a structure that will hold the data
struct List {
var plays : Double
var name : String
var qi : Double
init(plays: Int, name:String, index: Int) {
self.plays = Double(plays)
self.name = name
self.qi = Double(plays * index)
}
}
// We hold an array of List in here
var lists:[List] = []
// Now let us parse the rest of the data
for i in 1...nRecs {
let lineN = data[i].components(separatedBy: " ")
let _list = List(plays: Int(lineN[0])!, name: lineN[1], index: i)
lists.append(_list)
}
//Now we have a memory representation of the list, let us sort and return the top nOut
lists.sorted(by: {$0.qi > $1.qi})[0..<nOut].forEach {
print($0.name)
}
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.
