CodeFights - Cat Walk - Solution

Problem
You've been working on a particularly difficult algorithm all day, and finally decided to take a break and drink some coffee. To your horror, when you returned you found out that your cat decided to take a walk on the keyboard in your absence, and pressed a key or two. Your computer doesn't react to letters being pressed when an unauthorized action appears, but allows typing whitespace characters and moving the arrow keys, so now your masterpiece contains way too many whitespace characters.
To repair the damage, you need to start with implementing a function that will replace all multiple space characters in the given line of your code with single ones. In addition, all leading and trailing whitespaces should be removed.
Example
For line = "def      m   e  gaDifficu     ltFun        ction(x):",
the output should be
catWalk(line) = "def m e gaDifficu ltFun ction(x):".
Input/Output
  • [execution time limit] 4 seconds (py)
  • [input] string line
    One line from your code containing way too many whitespace characters.
    Guaranteed constraints:
    5 ≤ line.length ≤ 125.
  • [output] string
    line with unnecessary whitespace characters removed.
Solution


def catWalk(code):
    return " ".join(code.strip().split())

CodeFights - Simple Sort - Solution

Problem
To understand how efficient the built-in Python sorting function is, you decided to implement your own simple sorting algorithm and compare its speed to the speed of the Python sorting. Write a function that, given an array of integers arr, sorts its elements in ascending order.
Hint: with Python it's possible to swap several elements in a single line. To solve the task, use this knowledge to fill in both of the blanks (...).
Example
For arr = [2, 4, 1, 5], the output should be
simpleSort(arr) = [1, 2, 4, 5].
Input/Output
  • [execution time limit] 4 seconds (py)
  • [input] array.integer arr
    Guaranteed constraints:
    1 ≤ arr.length ≤ 100,
    -105 ≤ arr[i] ≤ 105.
  • [output] array.integer
    The given array with elements sorted in ascending order.
Solution

We just have to swap the elements which are out of order. The line in bold does just that. Its called tuple unpacking.


def simpleSort(arr):

    n = len(arr)

    for i in range(n):
        j = 0
        stop = n - i
        while j < stop - 1:
            if arr[j] > arr[j + 1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
            j += 1
    return arr

CodeFights - Count Bits - Solution

Problem
Implement the missing code, denoted by ellipses. You may not modify the pre-existing code.
Implement a function that, given an integer n, uses a specific method on it and returns the number of bits in its binary representation.
Note: in this task and most of the following tasks you will be given a code snippet with some part of it replaced by the ellipsis (...). Only this part is allowed to be changed.
Example
For n = 50, the output should be
countBits(n) = 6.
5010 = 1100102, a number that consists of 6 digits. Thus, the output should be 6.
Input/Output
  • [execution time limit] 4 seconds (py)
  • [input] integer n
    A positive integer.
    Guaranteed constraints:
    1 ≤ n ≤ 109.
  • [output] integer
    The number of bits in binary representation of n.
Solution
It is expected to only replace the ellipsis with the code that would give you the bit length of the given integer. 

def countBits(n):
     return n.bit_length()

CodeFights - Comfortable Numbers - Solution

Problem

Let's say that number a feels comfortable with number b if a ≠ b and b lies in the segment [a - s(a), a + s(a)], where s(x) is the sum of x's digits.
How many pairs (a, b) are there, such that a < b, both a and b lie on the segment [L, R], and each number feels comfortable with the other?
Example
For L = 10 and R = 12, the output should be
comfortableNumbers(L, R) = 2.
Here are all values of s(x) to consider:
  • s(10) = 1, so 10 is comfortable with 9 and 11;
  • s(11) = 2, so 11 is comfortable with 91012 and 13;
  • s(12) = 3, so 12 is comfortable with 910111314 and 15.
Thus, there are 2 pairs of numbers comfortable with each other within the segment [10; 12](10, 11) and (11, 12).
Input/Output
  • [time limit] 500ms (cpp)
  • [input] integer L
    Guaranteed constraints:
    1 ≤ L ≤ R ≤ 1000.
  • [input] integer R
    Guaranteed constraints:
    1 ≤ L ≤ R ≤ 1000.
  • [output] integer
    The number of pairs satisfying all the above conditions.

Solution

The problem is pretty straightforward due to constraints of the problem. We need to look at 1000C2 pairs in the worst case. We look at all the pairs in the range [L, R] and check if the pair of integers in a given pair are comfortable to each other.

Code

int digitSum(int n){
    int _sum = 0;
    
    while (n){
        _sum += (n%10);
        n = n/10;
    }
    
    return _sum;
}

int comfortableNumbers(int L, int R) {
    int total_pairs = 0;
    
    for(int i=L; i<=R; i++){
        for(int j=i+1; j<=R; j++){
            int s_a = digitSum(i);
            int s_b = digitSum(j);
            if (j>= (i-s_a) and j<= (i+s_a) and 
                  i>= (j-s_b) and i<= (j+s_b)
               ) {
                total_pairs++;
            }
        }
    }
    return total_pairs;
}

CodeFights - Count Black Cells - Solution

Problem

Imagine a white rectangular grid of n rows and m columns divided into two parts by a diagonal line running from the upper left to the lower right corner. Now let's paint the grid in two colors according to the following rules:
  • A cell is painted black if it has at least one point in common with the diagonal;
  • Otherwise, a cell is painted white.
Count the number of cells painted black.

Solution

Here is the code that solves the problem:
 
int gcd(int n, int m){
    while (m) {
        int temp = n;
        n = m;
        m = temp%m;
    }
    
    return n;
}
int countBlackCells(int n, int m) {
    if (n == m) return (n + 2*(n-1));
    if (n == 1 or m==1 ) return n*m;
    return n + m -gcd(n, m) + (gcd(n, m)-1)*2;
}


Merge overlapping intervals in Python - Leetcode 56. Merge Intervals

Problem:
Given a set of intervals in arbitrary order, merge overlapping intervals to produce a list of intervals which are mutually exclusive.

Eg:
 [ [1,4], [1,5] ] --> [ [1,5] ]
[[6,8], [1,9], [2,4], [4,7]] -> [ [1, 9] ]

Approach:

This approach to solving the problem borrows the idea of how balanced parentheses are checked. We first flatten the given list of intervals into individual bounds and associate each of them with an integer which signifies whether that bound is lower or an upper bound. We then sort this list according to the starting/ending integer and then the bound i.e for the same starting/ending integer, lower bound should come before the upper bound. We use a stack and keep pushing items onto it as long as the integer represents a lower bound and pop items if it is an upper bound. If at any point of time, the stack gets empty, then we have found one merged interval.

Eg:

[ (6, 8), (1, 9), (2, 4), (4, 7) ]

Step 1: Flatten the list

[ (6, 8), (1, 9), (2, 4), (4, 7) ] -> [(6, 0), (8, 1), (1, 0), (9, 1), (2, 0), (4, 1), (4, 0), (7, 1)]

0/1 of a tuple in the resulting list tells whether it is a lower/upper bound respectively.

Step 2: Sort the flattened list

[(1, 0), (2, 0), (4, 0), (4, 1), (6, 0), (7, 1), (8, 1), (9, 1)]

Step 3: Go through the list item by item and merge as explained above.

Code:


Beautiful Python: Some Cool Language Constructs and Tricks for Beginners - Part 1


0. Pretty printing of a dictionary
Suppose you have a nested dictionary and you want a human readable view of it, you could use json module to accomplish this. json.dumps() takes an extra parameter 'indent' that formats the elements legibly.

>>> import json

>>> a = { 'a': {'b': {'c':'d', 'e':'f'}}}

>>> print json.dumps(a, indent=2)
{
  "a": {
    "b": {
      "c": "d",
      "e": "f"
    }
  }
}

You can also use the pprint python module for pretty print of python data structures.

1. Reverse an iterable in python

>>> a = [1, 2, 4]

>>> a[::-1]
[4, 2, 1]

>>> a
[1, 2, 4]

>>> b = (2, 3, 4)

>>> b[::-1]
(4, 3, 2)

>>> b
(2, 3, 4)

>>> c = "This is a string"

>>> c[::-1]
'gnirts a si sihT'

>>> c
'This is a string'
This method always returns a new instance of the iterable instead of an in-place reverse.

2. Swapping the values of two variables in python
>>> a = 1

>>> b=2

>>> a,b = b,a

>>> a
2

>>> b
1

How does this work?
Python separates the right-hand side expression from the left-hand side assignment. First the right-hand side is evaluated, and the result is stored on the stack, and then the left-hand side names are assigned using opcodes that take values from the stack again.
For tuple assignments with 2 or 3 items, Python just uses the stack directly:
>>> import dis
>>> def foo(a, b):
...     a, b = b, a
... 
>>> dis.dis(foo)
  2           0 LOAD_FAST                1 (b)
              3 LOAD_FAST                0 (a)
              6 ROT_TWO             
              7 STORE_FAST               0 (a)
             10 STORE_FAST               1 (b)
             13 LOAD_CONST               0 (None)
             16 RETURN_VALUE        
After the two LOAD_FAST opcodes (which push a value from a variable onto the stack), the top of stack holds [a, b]. The ROT_TWO opcode swaps the top two positions on the stack so the stack now has [b, a] at the top. The two STORE_FAST opcodes then takes those two values and store them in the names on the left-hand side of the assignment. The first STORE_FAST pops a value of the top of the stack and puts it into a, the next pops again, storing the value in b. The rotation is needed because Python guarantees that assignments in a target list on the left-hand side are done from left to right.
For rest of the answer refer: http://stackoverflow.com/questions/21047524/how-does-swapping-of-members-in-the-python-tuples-a-b-b-a-work-internally

3. Enumerate
When you loop through a sequence or an iterable, you can get the index and its corresponding value at the same time by wrapping the sequence in enumerate.

>>> for index, value in enumerate(['foo', 'bar', 'zoo']):
...     print index, value
...

0 foo
1 bar
2 zoo

4. Splitting a string into a list of words and join them back

To split a string by whitespace
>>> a = "This is a string"

>>> a.split()

['This', 'is', 'a', 'string']

To split a string by a character
>>> a = "This is a string"

>>> a.split('s')

['Thi', ' i', ' a ', 'tring']

To join a list of words by space
>>> b
['This', 'is', 'a', 'string']

>>> " ".join(b)
'This is a string'

To join a list of words by a character, comma for example

>>> b
['This', 'is', 'a', 'string']

>>> ",".join(b)
'This,is,a,string'


5. List Comprehensions
Suppose you have a list of elements and you need to do some operation on each of the element. For example, you have a list L consisting of words each of length greater than 5 and you have to create a new list consisting of first three letters of each word in L.
The common way to write code for this would be:

>>> L = ["Python", "makes", "people", "love her"]

>>> new_L = []

>>> for word in L:
...     new_L.append(word[0:3])
...

>>> new_L
['Pyt', 'mak', 'peo', 'lov']


This is where List comprehensions come to the rescue

>>> L = ["Python", "makes", "people", "love her"]

>>> new_L = [word[0:3] for word in L]

>>> new_L
['Pyt', 'mak', 'peo', 'lov']

This effectively reduced the number of lines from 3 in earlier approach to 1 using List comprehensions. Also, generally, List comprehensions are considered to be faster and efficient than creating an empty list and appending an element to that list one by one.

Now suppose you need only the words from L which have length>5.
>>> L = ["Python", "makes", "people", "love her"]

>>> new_L = [word for word in L if len(word)>5]

>>> new_L
['Python', 'people', 'love her']

Further reads on List Comprehensions:
[0] http://docs.python.org/2/tutorial/datastructures.html#list-comprehensions
[1] http://blog.cdleary.com/2010/04/efficiency-of-list-comprehensions/
[2] http://python-history.blogspot.in/2010/06/from-list-comprehensions-to-generator.html