Visualisation with Pydot Part I

In this post, I'm going to talk about drawing trees and graphs programatically. I've written several answers on quora regarding recursion where I had to manually draw recursion tree as in Finding Subsets Solution I'll try to visulise this recursion tree programatically in the second part of this Visualisation with Pydot But before that, let's learn some basc concepts:
I'll be using pydot, which is a Python interface for Graphviz which is an awesome tool for Grah visualisation. So let's get started.
First thing first, we'll first setup the environment for graphviz. Let's download the graphviz binary from here. I'll be using a windows 10 64bit machine for this tutorial and install it. Now we have to add graphviz bin folder to the environment variable path. If you are having trouble here is the installation guide.
Let's install pydot by using:

pip install pydot

After installing the pydot package let's draw some simple graphs. Ill be using VS Code for the demo. Here is the minimalist example that draws a simple graph

# Import pydot
import pydot

# Make Dot graph object of type graph
graph = pydot.Dot(graph_type='graph')

# Make Edge from 1 -> 2
graph.add_edge(pydot.Edge("1", "2"))
# Make Edge from 1 -> 3
graph.add_edge(pydot.Edge("1", "3"))
# Save the graph as png
graph.write_png("out.png")

Here is how the output looks like. Cool, right?? We'll be exploring more options later on. Now let's say we want to change show a directed edge from node 1 to 2 and node 1 to 3. That's simple as changing the line
(

# Make Dot graph object of type graph
graph = pydot.Dot(graph_type='graph')

to

graph = pydot.Dot(graph_type='digraph')

Here is how the updated diagram looks like

Now let's say we allow multiple edges from one node to another. Say, we want an edge from 1 -> 2, 1 -> 3 and another edge from 1 -> 2. This is easy, we can add another line

graph.add_edge(pydot.Edge("1", "3"))

The output looks as follows.

But what if we want to prevent another edge from drawing if it is already present.

# Import pydot
import pydot

# Make Dot graph obect of type graph
graph = pydot.Dot(graph_type='digraph', strict=True)

# Make Edge from 1 -> 2
graph.add_edge(pydot.Edge("1", "2"))
graph.add_edge(pydot.Edge("1", "2"))
graph.add_edge(pydot.Edge("1", "3"))
# Save the graph as png
graph.write_png("4.png")

We simply supllied another option strict = True while making a dot graph object.
Now we have basic idea of drawing edges , let's eplore how we can add nodes on graph without any edges.

# Import pydot
import pydot

# Make Dot graph obect of type graph
graph = pydot.Dot(graph_type='digraph', strict=True)

# Make pydot Node obect with name 1
u = pydot.Node(name="1")
graph.add_node(u)

# Make pydot Node obect with name 2
v = pydot.Node(name="2")
graph.add_node(v)
# Save the graph as png
graph.write_png("out.png")

But what if you want 2 nodes with same name, Is it possible?

# Import pydot
import pydot

# Make Dot graph obect of type graph
graph = pydot.Dot(graph_type='digraph', strict=True)

# Make pydot Node obect with name 1
u = pydot.Node(name="1")
graph.add_node(u)

# Make pydot Node obect with name 2
v = pydot.Node(name="1")
graph.add_node(v)
# Save the graph as png
graph.write_png("out.png")

Here we can see, we are only able to get 1 node with the name "1", so what's the fix?
We'll see another property of pydot.Node called label. What exactly is a label? It is the value that appears on Node whereas the name is the actual value that identifies the node.

# Import pydot
import pydot

# Make Dot graph obect of type graph
graph = pydot.Dot(graph_type='digraph', strict=True)

u = pydot.Node(name="1", label="One")
graph.add_node(u)

v = pydot.Node(name="2", label="Two")
graph.add_node(v)
# Save the graph as png
graph.write_png("7.png")

Can we make the graphs more attractive using different colors for nodes and edges?

# Import pydot
import pydot

# Make Dot graph obect of type graph
graph = pydot.Dot(graph_type='digraph', strict=True)

u = pydot.Node(name="1", label="One", style="filled", fillcolor="gold")
graph.add_node(u)

v = pydot.Node(name="2", label="Two", style="filled", fillcolor="green")
graph.add_node(v)
# Save the graph as png
graph.write_png("8.png")

Now let's wrap up the tutorial by drawing some example graphs. First let's try drawing trees from google image results.

1. https://s3-ap-south-1.amazonaws.com/av-blog-media/wp-content/uploads/2018/09/Screenshot-from-2018-09-05-16-36-16.png

# Import pydot
import pydot

# Make Dot graph obect of type graph
graph = pydot.Dot(graph_type='graph', strict=True)

x = pydot.Node("A", style="filled", fillcolor="green")
graph.add_node(x)
x = pydot.Node("B", style="filled", fillcolor="green")
graph.add_node(x)
x = pydot.Node("C", style="filled", fillcolor="green")
graph.add_node(x)
x = pydot.Node("D", style="filled", fillcolor="green")
graph.add_node(x)
x = pydot.Node("E", style="filled", fillcolor="green")
graph.add_node(x)

edge = pydot.Edge("A", "B")
graph.add_edge(edge)
edge = pydot.Edge("A", "C")
graph.add_edge(edge)
edge = pydot.Edge("B", "D")
graph.add_edge(edge)
edge = pydot.Edge("B", "E")
graph.add_edge(edge)

# Save the graph as png
graph.write_png("9.png")

# Import pydot
import pydot

# Make Dot graph obect of type graph
graph = pydot.Dot(graph_type='graph', strict=True)

x = pydot.Node("A", style="filled", fillcolor="green")
graph.add_node(x)
x = pydot.Node("B", style="filled", fillcolor="green")
graph.add_node(x)
x = pydot.Node("C", style="filled", fillcolor="green")
graph.add_node(x)
x = pydot.Node("D", style="filled", fillcolor="green")
graph.add_node(x)
x = pydot.Node("E", style="filled", fillcolor="green")
graph.add_node(x)

edge = pydot.Edge("A", "B")
graph.add_edge(edge)
edge = pydot.Edge("A", "C")
graph.add_edge(edge)
edge = pydot.Edge("C", "E")
graph.add_edge(edge)
edge = pydot.Edge("B", "D")
graph.add_edge(edge)
edge = pydot.Edge("B", "E")
graph.add_edge(edge)

# Save the graph as png
graph.write_png("10.png")

Here is another question which asks to visualise recursion tree for nth fibonacci number.

def fib(n):

    if n <= 1:

        return n

    return fib(n - 1) + fib(n - 2)

Let's update the code :

import pydot 

i = 0
graph = pydot.Dot(graph_type="digraph")
parent = dict()

def fib(n, node_num):
    global i

    current_node = (n, node_num)
    if node_num == 0:
        u = pydot.Node(str((n, node_num)), label=f"fib({n})")
        graph.add_node(u)
    else:
	# Draw edge from parent of current node and current node
	
        u = pydot.Node(str(parent[current_node]), label=f"fib({parent[current_node ][0]})", style="filled", fillcolor="gold")
        graph.add_node(u)

        v = pydot.Node(str(current_node), label=f"fib({n})")
        graph.add_node(v)

        edge = pydot.Edge(str(parent[current_node]), str(current_node ))
        graph.add_edge(edge)


    if n <= 1:
	# Draw Node for base cases
        u = pydot.Node(str(current_node), label=f"fib({n})")
        graph.add_node(u)
        i += 1

        v = pydot.Node(str((n, i)), label=f"{n}", shape="plaintext")
        graph.add_node(v)

        edge = pydot.Edge(str(current_node), str((n, i)), dir="backward")
        graph.add_edge(edge)
        return n
    i += 1
    # Store current node as the parent of left child
    left_child =  (n - 1, i)
    parent[left_child] = current_node
    
	
    i += 1
    right_child = (n - 2, i)
    parent[right_child] = current_node
    
    #fib(n - 1) + fib(n - 2)
    return fib(*left_child) + fib(*right_child)

n = 6
memo = dict()
parent[(n, 0)] = None
fib(n, 0)
graph.write_png("out.png")

I'll be adding more on graphviz on Part II. Keep following... for more updates.

Read More

GCD of all of the subarrays

In this post, I'm going to explain about a question which I came across on quora. The question asks us to calculate gcd of all of the subarrays. If you don;t know what subarray is visit here.

Suppose A = [1, 2, 3, 4, 5] then subarrays are: [1], [2], [3], [4], [5], [1, 2], [2, 3], [3, 4], [4, 5], [1, 2, 3], [2, 3, 4], [3, 4, 5], [1, 2, 3, 4], [2, 3, 4, 5] [1, 2, 3, 4, 5].

Our objective is to find gcd of all of these subarrays. Assume gcd of subarray of length 1 as the element itself. I'll be implementing the solution in Python.

1. Bruteforce
The naive approach would be generating all the subarrays and then finding gcd for each subarray. This idea can be broken down into 2 parts:

• Finding subarrays
• Finding GCD of each subarray Let's see how we can find all the subarrays:

def generate_subarray(A):
 """
     function that  generate and returns all subarrays
 """
 ans = []
 # Starting from index i = 0
 # Find subarrays of length 1, 2, 3, ,4 ... starting from i
 for i in range(len(A)):
     for j in range(i + 1, len(A) + 1):
         ans.append(A[i:j])
 return ans

Let's implement a function to find gcd of 2 numbers:

def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)

Now, let's write a function to find gcd of each of the subarrays.

def find_gcd(sub_array):
    """
        Returns gcd of a sub_array
    """ 
    gcd_sub_array = sub_array[0]

    for i in range(1, len(sub_array)):
        gcd_sub_array = gcd(sub_array[i], gcd_sub_array) 

    return gcd_sub_array

Here is our complete code.

# Dictionary to store subarrays with their GCD
gcd_sub = dict()

def generate_subarray(A):
    """
        function that  generate and returns all subarrays
    """
    ans = []
    # Starting from index i = 0
    # Find subarrays of length 1, 2, 3, ,4 ... starting from i
    for i in range(len(A)):
        for j in range(i + 1, len(A) + 1):
            ans.append(A[i:j])
    return ans

def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)

def find_gcd(sub_array):
    """
        Returns gcd of a sub_array
    """ 
    gcd_sub_array = sub_array[0]

    for i in range(1, len(sub_array)):
        gcd_sub_array = gcd(sub_array[i], gcd_sub_array) 

    return gcd_sub_array

def main():
    A = [7, 3, 12, 7, 2]
    sub_arrays = generate_subarray(A)

    for sub_array in sub_arrays:
        # For every subarray of length greater than 1
        if len(sub_array) > 1:
            gcd_sub[tuple(sub_array)] = find_gcd(sub_array)
    # Prints
    # {(7, 3): 1, (7, 3, 12): 1, (7, 3, 12, 7): 1, (7, 3, 12, 7, 2): 1, (3, 12): 3, (3, 12, 7): 1, (3, 12, 7, 2): 1, (12, 7): 1, (12, 7, 2): 1, (7, 2): 1}
    print(gcd_sub)


if __name__ == "__main__":
    main()

Can we do better?

2. Tabulation
Let's recall

Suppose A = [1, 2, 3, 4, 5] then subarrays are: [1], [2], [3], [4], [5], [1, 2], [2, 3], [3, 4], [4, 5], [1, 2, 3], [2, 3, 4], [3, 4, 5], [1, 2, 3, 4], [2, 3, 4, 5] [1, 2, 3, 4, 5].

Let's take the subarray [1, 2]. We can see that it can be constructed from subarray [1] by appending 2. Similarly, let's take subarray [2, 3, 4]. We can see that it can be constructed from subarray [2, 3] by appending 4 to it(or [3, 4] by prepending 2 to it) An important observation we can see is that subarray of length j can be constructed simply by appending an element to it if we already have subarray of length j - 1. The same goes with the gcd for calculating subarray. For instance:
If A = [7, 3, 12, 7, 2] and if we have already calculated gcd for [7, 3] then we can calculate gcd for [7, 3, 12] as gcd( gcd(7, 3), 12). Let's try implementing the solution in the tabular approach:
Let dp[i][j] gives gcd for subarray A[i: j]. Then

 dp[i][j] = gcd(dp[i][j - 1], A[j]) if i != j
            A[i] if i == j

Let’s say we have A = [7, 3, 12, 7, 2]

• dp[0][0], then dp[0][0] = A[0] = 7 This implies that gcd for subarray [7] is 7
  
• dp[0][1], then dp[0][1] = gcd(dp[0][0], A[1]) = gcd(7, 3) = 1 which implies that gcd for subarray [7, 3] is 1
  
• dp[0][2], then dp[0][2] = gcd(dp[0][1], A[2]) = gcd(1, 12) = 1 which implies that gcd for subarray [7, 3, 12] is 1
  
• dp[0][3], then dp[0][3] = gcd(dp[0][2], A[3]) = gcd(1, 7) = 1 which implies that gcd for subarray [7, 3, 12, 7] is 1
  
• dp[0][4], then dp[0][4] = gcd(dp[0][3], A[4]) = gcd(1, 2) = 1 which implies that gcd for subarray [7, 3, 12, 7, 2] is 1
  
• dp[1][1], then dp[1][1] = A[1] = 3
  

and so on..
Here is the complete code.

gcd_sub = dict()

def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)


def main():
    A = [7, 3, 12, 7, 2]
    # Construct 2D array of size len(A) by len(A)
    # and initialize with -1
    dp = [[-1 for _ in range(len(A))] for _ in range(len(A))]

    # Set GCD of single element as the element itself
    for i in range(len(A)):
        dp[i][i] = A[i]

    # For every other subarrays of length l
    # Calculate gcd using  length l - 1
    for i in range(0, len(A)):
        for j in range(i + 1, len(A)):
            # print(A[i:j], A[j])
            dp[i][j] = gcd(dp[i][j - 1], A[j])
            gcd_sub[tuple(A[i: j + 1])] = dp[i][j]

    print(gcd_sub)

if __name__ == "__main__":
    main()

Read More

How to save offline documentation of language, framework or tools

Frequently, I have found myself going back and forth through the official documentation of language or frameworks.

This kind of gets annoying sometime when the internet is slow and I have to frequently go back to google and type "X documentation" and opening the links and searching for function or feature I'm looking for. That's a lot of work.

Recently, I found a great tool called Zeal which is completely free and offers offline documentations for about 194 great libraries, frameworks and languages like C++, Python, jQuery, React, Angualar, Laravel, Flask , Django and many more.

You can directly download this tool from the official link https://zealdocs.org/. This works on both linux and windows platform.

Read More

Project Euler 37: Truncatable Prime

I read the problem statements from both of the problems on hackerrank and project euler.
The problem at hackerrank is more general and has specific constraints. Here is the problem statement:

The number 3797 has an interesting property. Being prime itself, it is possible to continuously remove digits from left to right, and remain prime at each stage: 3797 , 797, 97, and 7. Similarly we can work from right to left: 3797 , 379, 37, and 3. Find the sum of primes that are both truncatable from left to right and right to left below N. NOTE: 2, 3, 5, and 7 are not considered to be truncatable primes.

The constraints for N is 100 <= N <= 10^6

Solution:
The problem statement is pretty clear about what we want to do. Basically, we call a number prime truncatable if

• The number is at least 2 digits
• we continuously remove digits from left to right and the results are prime
• we continuoulsy remove digits from right to left and the results are prime

We are asked to find the sum of truncatable prime numbers below any N?
The first idea that comes to find is to iterate every odd number (2 is the only prime even number) starting from 11 up to (N - 1) and checking if the number is truncatable.
This idea roughly translates to:

sum = 0
 for i in range(11, n, 2): 
     if all[i]:
         if is_truncatable(i):
             sum += i

Don’t worry about the function is_truncatable(). We’ll be implementing it in a while.
How efficient is the code? This naive code gets TLE. We’re simply bruteforcing for all the odd numbers. Do we actually need all these computations? Or, is there a better way to reduce computations?
Let’s think for a while… What if we can generate all the prime numbers below N beforehand and check for just the prime numbers as the number has to be prime first to be a truncatable prime number?
The best method to generate prime numbers is using the sieve. I'll be using Sieve of Eratosthenes .
Suppose, we have to generate all the prime from 1 to 120.
The basic idea of the sieve of erasthonses is:

• Make an array of size 121(0 Based Indexing).
• Mark all the numbers as prime initially.
• Strikeout all the multiples of 2 by marking them as non-prime.
• Similarly, strike out all the multiples of 3 and so on
• Finally, we’ll get an array of boolean value.

See the below visualization from Wikipedia.

Translating, the sieve of erasthonses is straightforward.

MAX = 1000000
prime = [True] * (MAX + 1)

def sieve():
    global prime
    prime[0] = prime[1] = False
    for i in range(2, MAX + 1):
        if i * i > MAX:
            break
        for j in range(i * i, MAX + 1, i):
             prime[j] = False

Let’s revisit the _istruncatable() function and try to implement the code.

• Start from a number N
• Remove digit from left one by one
• After removing, if the number is nonprime then immediately return false.
• Else continue removing digits until no digits are left.

Use the same logic for removing digit from right by one. This translates to:

def is_truncatable(n):
    quo = n
    rev = 0 
    while quo:
        rem = quo % 10;
        rev = rev * 10 + rem;
        # eg: For n = 3797
        # These pairs are checked 
        # 7 3797
        # 97 379
        # 797 37
        # 3797 3
        # print(reverse_digits(rev), quo)

        # If both of the pairs are prime continue
        if prime[reverse_digits(rev)] and prime[quo]:
            quo //= 10
            continue

        # Else immediately return false
        return False
    # If none of the pairs fails, it is a truncatable prime
    return True

If it doesn't make sense, you can 2 passes or use str() and int() builtins. We need to implement _reversedigits() function as:

def reverse_digits(n):
    quo = n 
    rem = 0 
    rev = 0
    while quo:
        rem = quo % 10;
        rev = rev * 10 + rem;
        quo //= 10;
    return rev

Here is our final code :

#Author: Bishal Sarang
 
MAX = 1000000
 
prime= [True] * (MAX + 1)
 
# Reverse a number 
# 123 -> 231
def reverse_digits(n):
    quo = n 
    rem = 0 
    rev = 0
    while quo:
        rem = quo % 10;
        rev = rev * 10 + rem;
        quo //= 10;
    return rev
 
 
def is_truncatable(n):
    quo = n
    rev = 0
    while quo:
        rem = quo % 10;
        rev = rev * 10 + rem;
        # eg: For n = 3797
        # These pairs are checked 
        # 7 3797
        # 97 379
        # 797 37
        # 3797 3
        # print(reverse_digits(rev), quo)
 
        # If both of the pairs are prime continue
        if prime[reverse_digits(rev)] and prime[quo]:
            quo //= 10
            continue
        
        # Else immediately return false
        return False
    
 
    # If none of the pairs fails, it is a truncatable prime
    return True
 
 
def sieve():
    global prime
    prime[0] = prime[1] = False
    for i in range(2, MAX + 1):
        if i * i > MAX:
            break
        for j in range(i * i, MAX + 1, i):
             prime[j] = False
        
 
def main():
    sieve()
    sum = 0;
    n = int(input())
    
    # For all the odd numbers starting from 11 to n - 1
    # If it is a prime, then check for truncatability
    for i in range(11, n, 2): 
        if prime[i]:
            # If truncatable prime
            # Increase the sum
            if is_truncatable(i):
                sum += i
    
    print(sum)
 
if __name__ == "__main__":
    main()

Here is the code that uses string to int and int to string conversion.

#Author: Bishal Sarang

MAX = 1000000
prime= [True] * (MAX + 1)

def is_truncatable(n):
    s = str(n)
    t = s[::-1]
    # If none of the pairs fail, it is a truncatable prime
    return all((prime[int(s[:j])] and  prime[int(t[:j][::-1])] for j in range(1, len(s) + 1)))
 

def sieve():
    global prime
    prime[0] = prime[1] = False
    for i in range(2, MAX + 1):
        if i * i > MAX:
            break
        for j in range(i * i, MAX + 1, i):
             prime[j] = False
        

def main():
    sieve()
    sum = 0;
    n = int(input())
    # For all thhe odd numbers starting from 11 to n - 1
    # If it is a prime, then check for truncatability
    for i in range(11, n, 2): 
        if prime[i]:
            # If truncatable prime
            # Increase the sum
            if is_truncatable(i):
                sum += i
    print(sum)

if __name__ == "__main__":
    main()

Read More

Yatra 3.0 Coding Competition

I recently participated in a coding competition organized by National College of Engineering(NCE) at Yatra 3.0. I'll be sharing my experience in this blog post.

Here is the info about the contest:

• There were 7 programming questions, out of which we were required to solve any 5.
• No internet was allowed.
• The only languages allowed were C and C++.
• Total time available was 1:30 mins.
• The evaluation was done on the basis of correctness and tie was broken by submission time.

The problems were not that hard if you have done some programming before.

1. WAP to find the sum of digits of a given number until you reach a single digit.
2. WAP to print a string N times without using any loop.
3. WAP to swap 2 variables without the use of any temporary variable.
4. WAP to check if a number is even or odd without the use of arithmetic and logical expression.
5. WAP to write "Hello World!" without using semicolon.
6. WAP to print print format specifiers "%s %d".
7. WAP to add 2 numbers without using + operator.

Note: I may have changed the wording or order of problems as I don't have access to the original question

When I first looked at the questions, I knew or had already seen most of the problems. As the questions were easy, in order to get a good rank, I had to solve the problems as quickly as possible. So, I solved the questions that required less thinking and less time to type. I chose: 2, 3, 4, 6, 7 The reason I didn't choose Q1 was that it needed more typing and Q5 because I couldn't think about the solution immediately at that time.

Solutions:

I decided to use C++ as the language of choice, as my knowledge of C has become somewhat rusty and I didn't want to spend a lot of time on debugging and thinking about language syntax. As I wasn't allowed to code on my own laptop, I have to make a template. The questions were basic so I used a simple template:

// Author: Bishal Sarang
#include<bits/stdc++.h>
using namespace std;

int main(){
    // Code
    return 0;
}

2. WAP to print string N times without using any loop.

Having solved several questions on recursion, this question was obvious. I could translate a loop using function call and passing counter variable i as a parameter.

for(int i = 0; i < n; i++){
    cout << s << "\n";
}

The above loop can be easily written as:

// Author: Bishal Sarang
#include<bits/stdc++.h>
using namespace std;

void solve(string s, int i){
    if(i == 0){
        return;
    }
    cout << s << "\n";
    // Recursively call with paramter (i - 1)
    solve(s, i - 1);
}

int main(){
    // Code
    string s; cin >> s;
    int n; cin >> n;

    // Call with parameter n. 
    solve(s, n);
    return 0;
}

4. WAP to check if a number is even or odd without the use of arithmetic and logical expression.

This question made me think for a while. If you are allowed to use arithmetic and logical expression, then the solution is straightforward

if(n % 2 == 0){
    cout << "Even";
}
else{
    cout << "Odd";
}

The closest operator, I could think of was bitwise operators, but I wasn't sure. With few trial and errors and observing some common bitwise property, I was able to simulate the above code using bitwise &

// Author: Bishal Sarang
#include<bits/stdc++.h>
using namespace std;

int main(){
    // Code
    int n; cin >> n;

    if(n & 1){
        cout << "Odd";
    }
    else{
        cout << "Even";
    }
    return 0;
}

6. WAP to print format specifiers "%s %d".

This question was kind of confusing at first sight. So, I asked the volunteer what was the question asking. The task was to simply print the string "%s %d". This question would have been a little bit tricky if I wasn't allowed to use C++, but since I was allowed I immediately solved it.

// Author: Bishal Sarang
#include<bits/stdc++.h>
using namespace std;

int main(){
    // Code
    cout << "%s %d";
    return 0;
}

Easy right :D ?? If I had to solve it using C, I would have done

// Author: Bishal Sarang
#include<stdio.h>
int main(){
    printf("%%s %%d");
    return 0;
}

7. WAP to add 2 numbers without using the + operator.

This question is a simple math question. My quick thought was, "If I ain't allowed to use plus, can I use minus?". Simple enough, I could write

a + b = -(-a - b)

// Author: Bishal Sarang
#include<bits/stdc++.h>
using namespace std;

int main(){
    // Code
    int a, b; cin >> a >> b;
    cout << -(-a - b);
    return 0;
}

3. WAP to swap 2 variables without the use of any temporary variable.

This question is one of the common questions which you can find on pretty much any CS related website. The question is simple, but it's kind of tricky as no temporary variable is allowed. I knew I had seen the question, but I didn't remember the exact solution. All I knew was a + b , a - b written in series of statementS. I did some paperwork and with few trials and errors, I was able to derive the relation:

a = a + b; b = a - b; a = a - b;

// Author: Bishal Sarang
 #include  <bits/stdc++.h>
 using namespace std;

int main(){ 
    // Code int a, b; cin >> a >> b; 
    a = a + b; 
    b = a - b; 
    a = a - b; 
    // After Swapping 
    cout << a << " " << b; 
    return 0; 
}

These were the 5 problems, I solved. I would also like to include solution to remaining problems:

1. WAP to find the sum of digits of a given number until you reach a single digit. This question is not that hard if you know how to extract each digit using modulus(%) operator.

// Author: Bishal Sarang
#include<bits/stdc++.h>
using namespace std;

int solve(int n){
    // Initialize sum with 0
    int sum = 0;
    // Extract each digit and add to sum
    while(n){
      sum += (n % 10);
      n /= 10;
    }
    // If the sum is single digit return sum
    if(sum < 10){
      return sum;
    }
    // Otherwise recursively find sum of digits of the current sum
    return solve(sum);
}

int main(){
    // Code
    int n; cin >> n;
    cout << solve(n);
    return 0;
}

5. WAP to write "Hello World!" without using semicolon.

// Author: Bishal Sarang
#include<bits/stdc++.h>
using namespace std;

int main(){
    // Code
    if(cout << "Hello"){

    }
    return 0;
    }

This works because the expression inside if is evaluated. Let's see another example to make it more clear

// Author: Bishal Sarang
#include<bits/stdc++.h>
using namespace std;

int main(){
    // Initially x is 0
    int x = 0;

    // Expression x = 2 + 2 is evaluated
    // So x becomes (2 + 2) = 4
    if(x = 2 + 2){
        // do nth
    }
    // Display 4
    cout << x;
    return 0;
    }

I managed to solve and submit all of the 5 problems correctly in about 15 mins and secure first position in the contest. The second position managed to solve 4 problems correctly who managed to solve the problem in about 45+ mins.

It was a pleasant experience.....

Read More

Writing Sum as Combinations and permutations from given array

Few days ago, I came across a question on quora which goes like this:

How do you solve this programming problem? Imagine you want to find all permutations of 2, 3, and 7 that can add up to make 10. (Ex: 2, 2, 2, 2, 2; or 3 , 7).

The question is basically asking us to represent sum using numbers from the array where a number can be used more than once.
Consider, the original example:

sum = 10
nums = [2, 3, 7]

We can use 2 five times to make sum 10. Also we consider 7 + 3 and 3 + 7 both as solution candidates.
At first glance, I thought the problem is related to subset sum. But no, we are allowed to use single number more than once and permutations is allowed. So, we’ll be using the recursion just like subset sum approach with slight modification i.e we are allowed to take same item again and again.

Solution:

The problem like this is easy to solve by recursion. Let’s try to visualize the solution recursively.
But, before that let’s talk about how would you solve it without code?
We have a list of numbers nums = [2, 3, 7] and we want to find all the combinations that make up the sum including the permutations.

eg: [3,7] and [7,3] to make 10

My approach would be like this:

1. Start with sum 10 and an empty list.
2. Include the first element 2 to the list. Solve for sum == 10 - 2 = 8 and [2].
3. Include the second element 3 to the list. Solve for sum == 10 - 3 = 7 and [3].
4. Include the third element 7 to the list. Solve for sum == 10 - 7 = 3 and [7].
5. Solve subproblems with sum = x and list ans recursively.

If it doesn’t make much sense don’t worry, here is the recursion tree recursion tree.

Here, we start with f(10, []) and at every states we take {2, 3, 7} and add to our answer list such that sum is greater than or equal to the number.
For every state f(sum, ans) we have 3 choices(if num is less than or equal to sum):

• Include 2 to the ans and solve for sum - 2
• Include 3 to the ans and solve for sum - 3
• Include 7 to the ans and solve for sum - 7

We can see at level 1, we have:

             — f(8, [2]) // Take 2
   f(10, []) — f(7, [3]) // Take 3
             — f(3, [7]) // Take 7

The nodes marked in gray in the recursion tree are the answers to the problem.
Here is the complete code in Python:

def solve(sum, ans):
    # If sum becoms 0 we have found the required list
    if sum == 0:
        print(ans)
    
    # Include every other element to make the sum
    # Number that is included also can be included
    for elem in nums:
        if sum - elem >= 0:
            solve(sum - elem, ans + [elem])
 
# We want to make the sum from list nums
nums = [2, 3, 7]
sum = 10
 
# Call solve with sum and an empty list 
solve(sum, [])

Output:

[2,  2,  2,  2,  2]
[2,  2,  3,  3]
[2,  3,  2,  3]
[2,  3,  3,  2]
[3,  2,  2,  3]
[3,  2,  3,  2]
[3,  3,  2,  2]
[3,  7]
[7,  3]

Read More

Leetcode 78: Subsets

In this post, I'm going to talk about a problem on leetcode which asks us to find all the possible subsets of given list of integers. This problem is the base to solving other problems like subset sum and subset partitioning which I'll be discussing in coming posts. Let's get started: I'll be solving this problem using 2 techniques:

1. Using Recursion
2. Using Bitset

I'll be using cpp for this task.
Problem Statement: Given a set of distinct integers, nums, return all possible subsets (the power set).
Note: The solution set must not contain duplicate subsets.
Example: Input:

nums = [1,2,3]

Output:

[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]

Solution

1. Using Recursion

Firstly, I'll be discussing recursive approach to subset finding problem. Recursive problem is easy to visualise. Consider the given testcase [1, 2, 3]. Let solve(nums, n, subset) be the function that find subsets for array nums and number of elements n, initially called with an empty subset. So our initial call is :

vector<int>subset;
solve(nums, nums.size(), subset);

Now lets try visualising how recursion tree looks like.
Recursive Cases: For every state i.e (n), i,e position n - 1 of

solve(nums, n, subset)

we can have 2 choices:(Try to visualise recursion for arr = {1, 2, 3} )

• Don’t include the current element in the subset i.e simply call

solve(nums, n - 1, subset);

• Include current element in the subset
  

  subset.push_back(arr[n -  1]);
  solve(nums, n -  1, subset);
  

Base Cases:
Let’s think of base cases. The base cases are:

• If n == 0 i.e no item left push the current subset to our subsets_ which is a vector of vector.
  

  if (n == 0){
  subsets_.push_back(subset);
  return;
  }
  

  Complete Code:
  

  class Solution {
  public:
  // Vector of vector of int to store all the subsets
  vector<vector<int>> subsets_;
  
  // Solve method that generates subset recursively
  void solve(vector<int> &nums, int n, vector<int> subset){
      // If size of array becomes 0, no elemnts are left
      // We push current subset to our subsets_ and return
      if (n == 0){
          subsets_.push_back(subset);
          return;
      }
      // Else we have 2 options:
  
      // Don't include the current element to subset
      solve(nums, n - 1, subset);
      // Incldue the current element in subset
      subset.push_back(nums[n - 1]);
      solve(nums, n - 1, subset);
  }
  
  // Solution method subsets
  vector<vector<int>> subsets(vector<int>& nums) {
      // Make an empty vector subset
      vector<int> subset;
      // Call solve function initially with an empty subset 
      solve(nums, nums.size(), subset);
      // Return subsets after calculation
      return subsets_;
  }
  };
  

2. Using Bitset

I have explained the bitset method on quora.

Read More

What are *args and **kwargs in Python

In this post, I'm going to talk about *args and **kwargs in Python which is a useful concept while handling multiple arguments.

They are called *args and **kwargs in Python which allows the function to accept optional arguments(positional and keyword).
Let’s see with an example.
At first, let’s make a simple function that accepts a single argument, first_name.

>>> def person(first_name):
...     print(first_name)
>>> person("Ram")
Ram
>>> person()
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: person() missing 1 required positional argument: 'first_name'

What we can see is first_name is a compulsory argument. So, it is not possible to call the function without arguments.
Now, what we are going to do is make a function that accepts first_name as compulsory arguments followed by last_name as an optional argument.
One way to do this would be

>>> def person(first_name, last_name=""):
...     print(first_name, last_name)
>>> person("Ram") # Called with 1 argument
Ram
>>> person("Ram", "Shrestha") # Called with 2 arguments
Ram Shrestha

So far everything is going well. But now we want to scale the same function to accept first_name(compulsory) and last_name and middle_name as positional arguments.
One simple trick is to add another argument middle_name.

>>> def person(first_name, last_name="", middle_name=""):
...     print(first_name, middle_name, last_name)

But there is a more concise way to scale the function to accept multiple optional arguments called *args in Python.

1. *args

*args collects extra positional arguments as a tuple

The idea is simple. We modify our function definition as:

>>> def person(first_name, *args):
...     print(first_name, end = " ")
...     for names in reversed(args):
...             print(names, end=" ")
...     print()
>>> # Accepts single argument
>>> person("Ram")
Ram
>>> # Accepts 2 arguments 
>>> person("Ram", "Chhetri")
Ram Chhetri
>>> # Accepts 3 arguments
>>> person("Ram", "Chhetri", "Lal")
Ram Lal Chhetri
>>> person("Ram", "Chhetri", "Lal", "Krishna")
Ram Krishna Lal Chhetri

We can see that now our function can accept first_name followed by last_name, middle_name as optional positional arguments. To see if args is indeed a tuple you can add

print(type(args))

inside of function definition
Let’s see another example:

Task 1: Write a function to add N integers which are passed as arguments ( N >= 1)
Let’s do it for 1 integer

>>> def add(a):
...     return a
>>> add(8)
8

Nothing complicated. Now do it for 2 integers

>>> def add(a, b):
...     return a + b
>>> add(8, 2)
10
>>> add(8)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: add() missing 1 required positional argument: 'b'

Notice?? We lost the compatibility for 1 argument.
This is where *args comes handy:

>>> def add(a, *args):
...     sum = a
...     print(type(args))
...     for num in args:
...         sum += num
...     return sum
>>> add(8)
8
>> add(8, 2)
10
>> add(8, 2, 5)
15

See how flexible it is using *args. Note it is not necessary to name *args as args . We can name it whatever we like. But it must be preceded with a *.

2. **kwargs

**kwargs collects extra positional arguments as a dictionary.

Let’s return to our previous examples of function person:

Task 2: Modify function person so that it accepts additional optional parameters phone_num, email and so on…as keywords.
We modify our original function definition to accept a new argument **kwargs which is a keyword argument as:

>>> def person(first_name, *args, **kwargs):
...     print(first_name, end=" ")
...     for names in reversed(args):
...             print(names, end=" ")
...     print()
...     # Since kwargs is a dictionary
...     # we can iterate using .items()
...     for key, value in kwargs.items():
...             print(key, value)
>>> person("Ram", "Chhetri", "Lal", phone_num="981128331", email="anon@testmail.com")

Ram Lal Chhetri
phone_num 981128331
email anon@testmail.com

Since kwargs is of dictionary type. we can iterate over key, value using .items()
Notes:

• *args and **kwargs are used to allow the function to accept a variable number of arguments
• *args collects positional arguments as a tuple whereas **kwargs as dictionary
• args and kwargs are just naming convention. You can name it whatever you like.
• * and ** are also used in value unpacking

Read More

What are map, filter and reduce in Python

I wrote a post about map, filter and reduce on Python a while ago on quora. In this post, I'm going to talk about map filter and reduce in detail with examples.
Let's get started: Basically map, filter and reduce gives functional programming features to Python. But before diving into these three functions let me talk briefly about lambda(Hopefully I'll be writing another post about lambdas)

Lambda

Let me introduce how to use lambda(nameless) function so that we dont have to define function by def keyword everytime. The syntax for lambda is as follows:

lambda *params: result

Doesn't make sense. Let's see some examples:
Q1. Write a lambda function to square a given number.

>>> func = lambda x: x * x
>>> func(3)
9

Here what lambda does is take a parameter x and then return its squarei i.e

x is the argument
x * x is the return value

Note, we don't need explicit return statement. Let's try a similar example that adds two given numbers.
Q2. Write a lambda function to add 2 numbers

>>> func = lambda x, y: x  + y
>>> func(5, 4)
9

This lambda function is simply taking two numbers x and y and simply returning it's result. Let's make it more interesting by writing a lambda function to square an even number but cube an odd number.
Q3. Write a lambda function that square if the number is even and cube if it is odd

>>> func = lambda x: x * x if x % 2 == 0 else x ** 3
>>> func(2)
4
>>> func(3)
27

We have used if..else in python to handle two cases You might be wondering why lambdas are called nameless or anonymous function, right? Let's get to that part. We don't necessarily need to give name to our lambda function. Let's see how it works

>>> (lambda x: x * x )(9)
81

Here we can directly invoke the lambda function. I hope you now know the basic working of lambdas to get started with map, filter and reduce.

1. Map:

Syntax:

map(funct, iterable)

Basically what map does is it take a function and an iterable(list, tuple, string, set) and applies function to each of the members in the iterable. Map returns a map object which is an iterable. Let's work on some of the examples on Python Console. A quick help on map shows following output

>>> help(map)
Help on class map in module builtins:

class map(object)
 |  map(func, *iterables) --> map object
 |
 |  Make an iterator that computes the function using arguments from
 |  each of the iterables.  Stops when the shortest iterable is exhausted.

I've included only few lines of the output but you can explore for more. Let's see some examples to understand more about map. I'll be working all the examples on console.
Task 1. Given a list of integer square each number in the list

>>> def func(x):
...     return x * x
>>> l = [1, 2, 3, 4, 5]

>>> map(func, l)

Remember lambdas from above ?? Instead of making function using def , I'll be using lambdas to make code more concise(Remember lambdas are handy in many cases like sorting). Let's replace the func with lambda function.

>>> map(lambda x: x * x, l)
<map object at 0x000001D59CDE3278>

Aren't we supposed to get output like ?

[1, 4, 9, 16, 25]

Don't worry we'll get there. As mentioned previoulsy map function returns a map object. Since, map returns an iterable, we can still access the elements using iter() and next() until StopIteration is raised i.e there are no more elements left.

>>> it = map(lambda x: x * x, l)
>>> next(it)
1
>>> next(it)
4
>>> next(it)
9
>>> next(it)
16
>>> next(it)
25
>>> next(it)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
StopIteration

We get the required results but this doesn't look quite interesting . An alternative way would be to loop across all the elements using a for loop.

>>> it = map(lambda x: x * x, l)
>>> for elem in it:
...     print(elem, end = " ")
...
1 4 9 16 25

This looks okayish. Can we do better like make a list out of the map object directly??

>>> l = list(map(lambda x: x * x, l))
>>> l
[1, 16, 81, 256, 625]

Okay it works as expected. Let's see an another example , maybe, square if the numbers are odd and cube if it is even.
Task 2. Given a list of integer square square if the numbers are odd and cube if it is even
I hope you know how to write lambda function that takes a number and does what the question is asking. If not read abut it in lambdas section. I'll be directly jumping to making a list out of map object. You may use loops or iter(), next() whenever necessary.

>>> l = list(map(lambda x: x * x if x % 2 == 0 else x ** 3, l))
>>> l
[1, 4, 27, 16, 125]

Task 3. Given a list of string integers like "1", "123", "5" write a function that convert the list of integer numbers.

>>> str_list = ["1", "2", "3"]
>>> l = list(map(lambda x: int(x), str_list))
>>> l
[1, 2, 3]

The above code works fine but there is some redundancy lambda x: int(x) . This is because there is already an inbuilt in Python named int that takes a paramer and return its integer equivalent.

>>> str_list = ["1", "2", "3"]
>>> l = list(map(int, str_list))
>>> l
[1, 2, 3]

Task 4. Given a list of string make a list of same size that gives the length of the string for every element

>>> str_list = ["Ram", "Hari"]
>>> l = list(map(len, str_list))
>>> l
[3, 4]

Task 5. Given a list of number separated by space as input . Write a function to make a list of the numbers using map This shorthand comes handy while reading inputs in competitive coding problems site.

>>> l = list(map(int, input().split()))
1 2 3 4 5
>>> l
[1, 2, 3, 4, 5]

Wondering what input().split() is doing? It simply splits a string by space while taking input and returns a list.

>>> l = input().split()
Ram Kumar
>>> l
['Ram', 'Kumar']

Compare it with

>>> l = input()
Ram Kumar
>>> l
'Ram Kumar'

See the difference? input().split() split the input string to make a list out of each strings other than space but if we dont use .split(), the input is taken as a single string no matter how many spaces are there.
Let's try working with multiple iterables. Task 6. Given two lists of strings one containing firstname and another containing last name of each i, write a function to make a single list with each firstname and lastname separated by space. Let's say we are given two lists

>>> first_name = ["Ram", "Sita", "Hari"]
>>> last_name = ["Pandey", "Chhetri", "Timalsina"]

What we want is output like

['Ram Pandey', 'Sita Chhetri', 'Hari Timalsina']

We can simply solve this problem using lambda function that takes 2 arguments and concatenate them with space in between.

lambda x, y: x + " " + y,

where x is the argument from first iterable and y is the argument from second.

>>> full_name = list(map(lambda x, y: x + " " + y, first_name, last_name))
>>> full_name
['Ram Pandey', 'Sita Chhetri', 'Hari Timalsina']

An alternative method to this would be using zip which is out of scope of this post.

>>> merged = list(zip(first_name, last_name))
>>> merged
[('Ram', 'Pandey'), ('Sita', 'Chhetri'), ('Hari', 'Timalsina')]
>>> full_name = list(map(lambda x: x[0] + " " + x[1], merged))
>>> full_name
['Ram Pandey', 'Sita Chhetri', 'Hari Timalsina']

2. Filter

Syntax:

filter(function, iterable)

Filter is similar to the map . The difference is that it returns a new filter object which is an iterable of the elements that satify the boolean function. As the name suggests, it is used to filter the elements based on a certain condition. Don't worry if it doesn't make sense right now. We'll get into more details with examples . Let's do some codes:

>>> help(filter)
Help on class filter in module builtins:

class filter(object)
 |  filter(function or None, iterable) --> filter object
 |
 |  Return an iterator yielding those items of iterable for which function(item)
 |  is true. If function is None, return the items that are true.

Task 1. Given a list of integer keep only the even numbers The lambda function that returns if a number is even easy to write. If you are having trouble writing it, revisit the lambda section above.

>>> (lambda x: x % 2 == 0)(1)
False
>>> (lambda x: x % 2 == 0)(2)
True

Now, we can use lambda and filter to perform the filter operation i.e separate only even numbers.

>>> l = [1, 2, 3, 4, 5]
>>> filter(lambda x: x % 2 == 0, l)
<filter object at 0x000001E60A8938D0>

Looks familiar? It is similar to the output of map .The only difference is we are getting a filter object insted of map. Since, it is also an iterable we can use iter(), nex() or a for loop to access the contents. But I would like to leave that as a exercise for you and directly dive into making a list out of filter object.

>>> l = [1, 2, 3, 4, 5]
>>> evens = list(filter(lambda x: x % 2 == 0, l))
>>> evens
[2, 4]

This works as expected.
Task 2. Given a list of passwords as string. Filter out all the weak passwords keeping only the vald passwords. For simplicity, a strong password is a password which is at least 8 characters long, contains at least one digit, at least one lowercase letter, at least one uppercase letter and at least 1 special symbols where special symbols are !@#$%^& Take your time to understand what question is asking. Basically, we are given a list of passwords and our task is to make list containing only the strong passwords. Sounds simple?

 >>> def is_strong(s):
...     return len(s) >= 8 and any([x.isupper() for x in s]) and any([x.islower() for x in s]) and any([x.isdigit() for x in s]) and any([(x in "!@#$%^&") for x in s])
>>> l = ["abcDEF1!", "abcdeF", "123456789", "aB1$", "123456789DDDDBBBaaa", "aaDDDD123$%"]
>>> strong = list(filter(is_strong, l))
>>> strong
['abcDEF1!', 'aaDDDD123$%']

Since , we are going to have a longer return statement, I've switched to normal functions instead of lambda . Remember readability matters. I could have written series of staements to check these 4 conditions but I choose to use a single statement . So what is_strong(s) does is take a string s and check if length of string is greater than or equal to 8 and contains any one of the uppercase letter, lowercase letter, digit and a special symbol characters. If you are seeing these string methods .isupper(), .islower(), .isdigit() for the first time here is how they work.

>>> "a".islower()
True
>>> "a".isupper()
False
>>> "A".isupper()
True
>>> "9".isdigit()
True
>>> "9".isupper()
False

Hope it clears your doubt. These are the string methods that returns a boolean value if the condition is satisfied(eg: isdigit() return true if the string is a digit). Let's see what any() is doing here.

>>> help(any)
Help on built-in function any in module builtins:

any(iterable, /)
    Return True if bool(x) is True for any x in the iterable.

    If the iterable is empty, return False.
>>> any([False, False])
False
>>> any([True, False, False])
True

What it is doing is is returns True if any one of the members in iterables is True , in our case if any one of the number is digit, uppercase, lowercase . Hope it clears your doubt.

3. Reduce

Syntax:

reduce(function, iterable, start)

Reduce applies a function of two arguments to items of sequence until it returns a single value. It takes a function that takes two arguments and an iterable and an start value. If start value is not specified explicitly it takes the first element as the start value.
Let's see what help has to offer.

>>> from functools import reduce
>>> help(reduce)
Help on built-in function reduce in module _functools:

reduce(...)
    reduce(function, sequence[, initial]) -> value

    Apply a function of two arguments cumulatively to the items of a sequence,
    from left to right, so as to reduce the sequence to a single value.
    For example, reduce(lambda x, y: x+y, [1, 2, 3, 4, 5]) calculates
    ((((1+2)+3)+4)+5).  If initial is present, it is placed before the items
    of the sequence in the calculation, and serves as a default when the
    sequence is empty.

Notice the first line? We are importing reduce from functools. We didn't need to import map and filter , right? This is because we don't need to import attributes that are in bultins.

>>> import builtins
>>> "map" in dir(builtins)
True
>>> "filter" in dir(builtins)
True
>>> "reduce" in dir(builtins)
False

Task 1: Given a list of integers, write a code that returns the total value obtained by multiplying the elements in the list.

>>> from functools import reduce
>>> l = [1, 2, 3, 4, 5, 6]
>>> mul = reduce(lambda x, y: x * y, l)
>>> mul
720

Task 2: Given a list of integers, write a code that returns the total value obtained by summing all the elements in the list.

>>> l = [1, 2, 3, 4, 5, 6]
>>> sm = reduce(lambda x, y: x + y, l, 0)
>>> sm
21

We can verify that it is indeed returning the sum by doing maths by hand or by using

>>> sum(l)
21

Task 3: Given a list of integers, write a code that returns the lcm of these values

>>> from functools import reduce
>>> from fractions import gcd
>>> l = [8, 19, 3, 5, 10, 2, 2, 4]
>>> lcm = reduce(lambda x, y: x * y // gcd(x, y), l)
>>> lcm
2280

Instead of implementing my own custom function to calculate LCM, I've used fractions module to calculate gcd and then find its lcm.
This kind of complete this post as of now. I'll be adding more examples.

Read More