Problem
There are N unique binary strings, all with the same length. Binary strings consist of only ‘1’s and ‘0’s, e.g. 10101, 00000, 10000. Let a string’s oneness be defined as the number of ‘1’s in the string minus the number of ‘0’s (e.g. 10101’s oneness is 3-2 = 1, 10000’s oneness is 1-4 = -3).
A string’s distance to another string is defined as the absolute value of the difference between their onenesses (e.g. 10101 and 10000 have distance |1-(-3)| = 4). The smaller the distance between two strings, the more similar they are. A string’s score is the sum of the distances between it and each of the other strings (e.g. among the 3 strings 10101, 00000, 10000, the string 10101 has score |1-1| + |1-(-5)| + |1-(-3)| = 10. The smaller a string’s score, the more representative it is. Find the most representative string among the N strings. Output the string and its score.
Input Format:
N
S1
S2
S3
...
SN-1
SN
Where Si denotes the ith binary string. It is guaranteed that no two binary strings are the same.
Output Format
R
P
Where R is a most representative string (there may be more than 1 most representative string, printing any one of them will do), and P is the score of that most representative string.
Sample Input:
3
10101
00000
10000
Sample Output:
10000
6
Approach
For this problem, we can apply the brute force algorithm design paradigm. The principle is an intuitive one - try all possible candidates. We can loop through all the strings, compute their score, and find the string with the minimum score. This is a straightforward application of the brute force paradigm - if you continue solving computing problems, you may find solutions requiring subtler applications of the same paradigm.
Strings
Let’s first try to figure out how to compute the oneness of a string. Take note that in other contexts, binary strings like 10101 can behave as numbers, but here we want to work with them as strings (i.e. “10101” is different from 10101).
Strings are sequences of characters, denoted by enclosing text in between quotes '' or double quotes "" in Python. You can click here for some basic string operations. To read input as strings, we can just use input(), since by default input() reads input as strings.To be able to type in input, please open the following code on the repl.it site by clicking “edit on repl.it” before running it.
We can index strings (i.e. access specific characters of strings) by using square brackets []. We can access the ith character of a string s using s[i]. In Python, like most programming languages, indexing starts from 0. So the first character of string s with n characters is s[0], while the last character is s[n-1] (or s[-1]). You can read more about string indexing and slicing here.
We can naturally loop through strings. This can be done either through looping directly through the string (for character in string:) or by looping through the indices of a string (for i in range(len(string)):).
Returning to our problem, we can compute the oneness of a string by looping through it, using a variable to keep track of the oneness and incrementing or decrementing the oneness depending on whether each character is a 1 or a 0. Click “edit on repl.it” to try and write some code to compute oneness, using what you now know about conditions, loops and strings!
Our solution: https://repl.it/BJdC/2
At this point, you can pause and head over to our practice site and try to solve Burgers - you have all the programming knowledge needed!
Functions and Modular Code
Before moving on, let’s define a function to compute oneness. Functions allows us to reuse code in a more organised manner. Python has some in-built functions, like print() and len(). We can also define our own functions. To define a function, we use the def keyword (e.g. def f():). A function block is demarcated using indentation, just like if/else statements and loops.
After defining a function, we can call it in our code via its name followed by ().
Notice how tedious and redundant it would be if we typed out the entire code block each time we had to print 1 to 10 (just replace each line which calls print1to10() with the code from the function body). Functions make our code modular. Modular code is neat and concise - especially useful when debugging. Programming in a modular fashion also helps us think in a clearer and more systematic way. A function can take in some arguments and return some value. Arguments in Python are placed between the parentheses. Return values are specified by the return keyword, at which point the function will exit.
Now, write the function compute_oneness(). What should the argument of this function be? What should it return? What needs to be in the function body to achieve the function’s specifications?
Our solution: https://repl.it/BJdX/3
Now that we have a function to compute oneness, we can write the function to compute distance. Two things to note before moving on.Firstly, functions can call other functions within their definitions, as long as the called function is defined before the one that calls it.
Secondly, to compute the absolute value of some number we can use the abs() function.
Now, you can write a function compute_distance() that takes as input two binary strings, and returns their distance. You can call compute_oneness() in your function body.
Our solution: https://repl.it/BJdX/5
Lists
We now know how to deal with strings, including reading input as strings, indexing them, and looping through them. We also know how to write functions to make our code more modular. We have functions to compute the oneness of a string, and the distance between two strings. What remains is to find a way to apply these functions over the strings to find the most representative string.Moving on, we need a way to deal with the fact that the input in the problem is not a single string, but a list of strings.To do so in Python, we can use (you guessed it!) lists. Just like a string is a sequence of characters, a list is a sequence of values (which can be of different types). Lists are declared using square brackets ([]). To initialise (i.e. fill up initial values) of a list, we can place values between the [], separated by commas.
Indexing and looping through lists can be done just like how indexing and looping through strings is done.
We can add objects to the end of a list by using the append() method.
Now, try to write some code reads the input for the problem as specified, and stores the list of strings in a Python list. You probably will need to use the append() method.
Our solution: https://repl.it/BJdj/10
Nested Loops
We have a way of storing the input as a list of strings now. How do we go about computing the score for a string? The score of a string can be computed by comparing that string with all the strings in the input (we don’t have to worry about whether we compare a string against itself, as the distance is 0, eg. distance between 10101 and 10101 is |1-1| = 0). We need to compute the score of each string this way. So, we need to loop through all the strings, and for each string, we need to loop through all the strings again.To do so, we can use nested loops (a loop within a loop). To a loop within another, we just need carefully take note of the indentation of each line - the level of indentation of a line of code decides whether it belongs to the inner loop or the outer loop.
Write some code below to print all pairs of strings from a list of strings.
Our solution: https://repl.it/BJdj/15
Now, given the functions compute_oneness and compute_distance, and a list of strings, compute the score of each string. Store the scores in a list.
Our solution: https://repl.it/BJdX/7
Solution
We can now combine all of the above to code up a solution. Write a program that solves Representative, reading input and printing the output as stated in the problem statement. To do so, compute the score of each string. Keep track of the lowest score so far, and a string that has that score.As far as possible, try not to directly copy and paste from the code snippets above. Instead, retrace the reasoning and conceptualising process that led us to this solution from the problem statement. Try to translate these concepts into code yourself.
Our solution: https://repl.it/BJdX/14