Wednesday, December 28, 2016

Learning Python

Python is a general-purpose interpreted, interactive, object-oriented, and high-level programming language.Python was developed by Guido van Rossum in the late eighties and early nineties at the National Research Institute for Mathematics and Computer Science in the Netherlands

Python is processed at runtime by the interpreter.
Python is interactive shows prompt and interact with the interpreter directly to write your programs.
Python supports Object-Oriented style or technique of programming that encapsulates code within objects.


>>> print ("Hello, World!") 
#!/usr/bin/python3

counter = 100          # An integer assignment
miles   = 1000.0       # A floating point
name    = "John"       # A string

print (counter)
print (miles)
print (name)

Python has five standard data types − Numbers, String, List, Tuple, Dictionary
Numbers :
var1 = 1
var2 = 10
del var
del var_a, var_b
Python supports four different numerical types −
  • int (signed integers)
  • float (floating point real values)
  • complex (complex numbers)
string :
str = 'Hello World!'

print (str)          # Prints complete string
print (str[0])       # Prints first character of the string
print (str[2:5])     # Prints characters starting from 3rd to 5th
print (str[2:])      # Prints string starting from 3rd character
print (str * 2)      # Prints string two times
print (str + "TEST") # Prints concatenated string
list :
list = [ 'abcd', 786 , 2.23, 'john', 70.2 ]
tinylist = [123, 'john']

print (list)          # Prints complete list
print (list[0])       # Prints first element of the list
print (list[1:3])     # Prints elements starting from 2nd till 3rd 
print (list[2:])      # Prints elements starting from 3rd element
print (tinylist * 2)  # Prints list two times
print (list + tinylist) # Prints concatenated lists
Tuples
The main differences between lists and tuples are: Lists are enclosed in brackets ( [ ] ) and their elements and size can be changed, while tuples are enclosed in parentheses ( ( ) ) and cannot be updated. Tuples can be thought of as read-only lists. For example −
#!/usr/bin/python3

tuple = ( 'abcd', 786 , 2.23, 'john', 70.2  )
tinytuple = (123, 'john')

print (tuple)           # Prints complete tuple
print (tuple[0])        # Prints first element of the tuple
print (tuple[1:3])      # Prints elements starting from 2nd till 3rd 
print (tuple[2:])       # Prints elements starting from 3rd element
print (tinytuple * 2)   # Prints tuple two times
print (tuple + tinytuple) # Prints concatenated tuple
Dictionary :
Python's dictionaries are kind of hash table type. A dictionary key can be almost any Python type, but are usually numbers or strings. Values, on the other hand, can be any arbitrary Python object. Dictionaries are enclosed by curly braces ({ }) and values can be assigned and accessed using square braces ([]). For example −
#!/usr/bin/python3

dict = {}
dict['one'] = "This is one"
dict[2]     = "This is two"

tinydict = {'name': 'john','code':6734, 'dept': 'sales'}


print (dict['one'])       # Prints value for 'one' key
print (dict[2])           # Prints value for 2 key
print (tinydict)          # Prints complete dictionary
print (tinydict.keys())   # Prints all the keys
print (tinydict.values()) # Prints all the values
This produce the following result −
This is one
This is two
{'code': 6734, 'name': 'john', 'dept': 'sales'}
dict_keys(['code', 'name', 'dept'])
dict_values([6734, 'john', 'sales'])
Dictionaries have no concept of order among elements. It is incorrect to say that the elements are "out of order"; they are simply unordered.

Introductory Program showing function , loop, condition and printing :

Example 1 : given an input integer N, print output as 123.....N without using any special data types

from __future__ import print_function
if __name__ == '__main__':
    n = int(raw_input())
    i = 0
    j = 0
    result = 0
    num = 0
    while i <= n :
        num = i
        while num :
            j+=1
            num/=10
        result = result *(10**j) + i
        i+=1
        j = 0
    print (result)



Example 2 :  bear, honey and gold game :

from sys import exit

def gold_room():
print "This room is full of gold. How much do you take?"
next = raw_input("> ")
if "0" in next or "1" in next:
how_much = int(next)
else:
dead("Man, learn to type a number.")
if how_much < 50:
print "Nice, you are not greedy, you win!"
exit(0)
else:
dead("You are greedy bastard!")

def bear_room():
print "There is a bear here."
print "The bear has a bunch of honey."
print "The fat bear is in front of another door."
print "How are you going to move the bear?"
bear_moved = False

while True:
next = raw_input("> ")

if next == "take honey":
dead("The bear looks at you then slaps your face off.")
elif next == "taunt bear" and not bear_moved:
print "The bear has moved from the door. You can go through it now."
bear_moved = True
elif next == "taunt bear" and bear_moved:
dead("The bear gets pissed off and chews your leg off.")
elif next == "open door" and bear_moved:
gold_room()
else:
print "I got no idea what that means."

def cthulhu_room():
print "Here you see the great evil Cthulhu."
print "He, it, whatever stares at you and you go insane."
print "Do you flee for your life or eat your head?"

next = raw_input("> ")

if "flee" in next:
start()
elif "head" in next:
dead("Well that was tasty!")
else:
cthulhu_room()

def dead(why):
print why, "Good job!"
exit(0)

def start():
print "You are in a dark room."
print "There is a door to your right and left."
print "Which one do you take?"

next = raw_input("> ")

if next == "left":
bear_room()
elif next == "right":
cthulhu_room()
else:
dead("You stumble around the room untill you starve.")

start()

Tuesday, November 1, 2016

Regular Expression




Regular expression is a sequence of characters that defines search pattern.
starts as /abc/


There are four matching modes :
a) Global match (g)
b) Case insensitive (i)
c) Multiline anchors (m)
d) Dot matches all (s)

Literal character matching :
non global matching : matches earliest / left most set is going to match.
global matching : matches all matching set.

Meta Character :
These are the characters with special meaning like mathematical operators. It transforms
literal character to powerful expressions.

 \ . * +  -  { } [ ]  ^  $ |  ?  ( )  : ! =


Wildcard meta character :

 " . "

for example -  c.r  will match car , cor , cbr , cxr etc
                        resume.\.txt  will match resume1.txt , resume2.txt resume3.txt etc


spaces : c a t  matches c a t
tab (\t)  : a\tb matches a    b
new line (\n) :  a\nd  matches a
                                                d

line return (\r)

character set  [ ]   :

/g[aeiuo]t/  matches gat , get , git , gut, got


Character range :

Represents all the character between two characters  ex - [0-9]
[A-Za-z] , [a-zA-Z] , [0-9A-Z] , [A-Z0-9]

Negative character set :  /[^abcdefg]/
                                       see[^abcd]  matches  sees , seen but not matches seed
                                       see[^a-d]  matches sees seen but not seed or seea seeb seec

metacharacter inside the character set  is considered as literal , except ] , - , ^ , \

Repetition Expressions : 

repetition metacharacters : 

*  -   /apples*/  matches apple , apples , applessssssss        :   0 or more repetition

+  -  /apples+/  matches apples , applessss , but not apple   :  1 or more repetition

?  -  /apples?/   matches apple , apples but not applessss     :   no repetition


Quantified repetition :

{min, max}

min and max are positive number defining the repetition range. minimum must be always there , least value can be 0 , if max is not included then max range will be infinity.

for ex :
/\d{5}/  matches 5 digit number
/\d{5,}/  matches 5 digit number or more
/\d{2,5}/ matches number having number of digits from 2 to 5

Lazy expressions :

*?
+?
{min,max}?
??

/apples??/   first ? makes it greedy and second one lazy , apples? matches apple or apples but go greedy and matches apples but another ? puts it to apple

Capturing groups and Back referencing :

( ) captures the things need to be put together . grouping metacharacter.
/(abc)+/  matches abcabcabc
abc+ matches abcccccc

/(in)?dependent/ matches both independent and dependent

Anchored expressions :

^  : caret sign means start of string/line
$  :  dollar sign means end of string/line
\A : start of string, never end of line  : same as ^
\Z : End of string , never end of line : same as $

single line mode , ^ , \A and $ , \Z do not match line break , they match in Multiline mode
(except \A and \Z) .  re.MULTILINE

word boundaries :  \b word boundary , \B not a word boundary
very first and last word , between a word character and non-word character
 This helps skipping backtracking while  matching
space is not word boundary , boundary is at end position and start position of any word

apples and oranges
matches , /bapples/b and /boranges/b  however not matches with  /bapples/band/boranges/b

Alteration metacharacter ->   |   pipe character

here its an OR operator.

regular expressions are eager to return and greedy , so put the best search first

Back referencing : stores the matched data , not the expression. it allows to access the captured data
by \1 through \9   back reference positions

/(A?)B\1/ matches "ABA" and "B"
/(A?)B\1C/ matches "ABAC" and "BC"   , back reference gets zero or more

find and replace using back reference :

for ex
^(\d{1,2}),([\w.]+?) ([\w]+?),(\d[4])}   -> find

matches :
1, Leonardo Dicaprio, 2016

replace with
$1,$3,$2,$4

result : 1, Dicaprio, Leonardo, 2016

Non capturing group expression : turn off grouping  ?:  specify a non-capturing group

/(?:\w+)/  -> increases speed , more spaces for capture.
ex: (oranges) and (apples) to \1
oranges and apples to oranges 

(?:oranges) and (apples) to \1

oranges and apples to apples
 ? -> give this group different meaning
: -> non capturing 

LookAround Assertions :
two types : LookAhead and LookBehind assertions

positive lookahead :  looks what should be ahead ,  /(?=regex)/
/(?=seashore)sea/ matches sea from seashore not from seaside  ?= says looks ahead if its present but dont match whatever followed after it

Negative lookahead : /(?!regex)/

/(?!seashore)sea/ matches seaside not seashore

Lookbehind Assertion :
/(?<=regex)/  positive look behind assertion
/(?!regex)/     negative look behind assertion

/(?<=base)ball/ matches ball in baseball not football   efficiently


position :

This costs 54.00 or $54.00.

(?<![$\d])\d+\.\d\d   matches 54.00
(?<![$\d])(?=\d+\.\d\d)  gets the regular expression pointer jumps to front of 53 , helps in inserting

Unicode and Multibyte Characters :

single byte  , uses 8 bits to repesent a character  , allows for 256 characters
A-Z , a-z , 0-9 , punctuation , common symbols

Double byte :  16 bits ; 2 to power of 16 , 65,536 characters

Unicode is varibale byte size : 1 , 2 or more byte , it allows over 1 million characters
its mapping between character and number
"U+" followed by a four digit hexadecimal number
infinity is written as U+221E

"cafe","café"

café can be encoded as four or five characters

unicode indicator : \u
\u followed by hexadecimal number (0000-FFFF)
/caf\u00E9/  matches café not cafe

unicode wildcard and properties :
Unicode wildcard : \X  matches any single character , always matches line breaks like /./s
/cafe\X/ matches café  and cafe

Unicode property : \p
/\p{Mark}/ or /\p{M}/ matches any mark  (just accents)

Letter L
Mark M
Separator Z
Punctuation P
Number N
Symbol S
Other C

unicode not-property : \P

/caf\P{M}\p{M}/ matches café

The unicode property  is widely supported

Now Practice!

Monday, August 1, 2016

2D Image Convolution in C or C++

How to get the convolution output of an Image with the given filter/Kernel 

// in, out are m x n images (integer data)
// K is the kernel size (KxK) - currently needs to be an odd number, e.g. 3
// coeffs[K][K] is a 2D array of integer coefficients
// scale is a scaling factor to normalise the filter gain

for (i = K / 2; i < m - K / 2; ++i) // iterate through image
{
  for (j = K / 2; j < n - K / 2; ++j)
  {
    int sum = 0; // sum will be the sum of input data * coeff terms

    for (ii = - K / 2; ii <= K / 2; ++ii) // iterate over kernel
    {
      for (jj = - K / 2; jj <= K / 2; ++jj)
      {
        int data = in[i + ii][j +jj];
        int coeff = coeffs[ii + K / 2][jj + K / 2];

        sum += data * coeff;
      }
    }
    out[i][j] = sum;  //if normalization needed then divide sum by N or factor.
  }
}

Wednesday, June 29, 2016

C++ Exception Handling

Exception handling in C++ helps to prevent the unexpected problems which can happen while executing the program and if there is any error like invalid data, out of bound, overflow or any other
exceptional circumstances so that rest of the program and system in general does not get screwed up.

It mainly involves the idea:
1) Hit the exception at problem code.
2) Throw the exception
3) Catch/Receive the error info
4) handle the error or exception

Above steps gets wrapped under different block using keywords like try - to wrap the code where an exception needs to be detected & thrown.
catch - receives the exception  via exception object and handle the error.
finally -  {Not present in C++} block of code needs to be executed even if exception occurred on try block exit, used mostly to put clean up code , C++ can put those code in deconstructor.


sample code:


submitted solution from hackerrank

#include <cmath>
#include <iostream>
#include <exception>
#include <stdexcept>
using namespace std;

//Write your code here
class myException : public std::exception {
  virtual const char *what() const throw() {
    return "n and p should be non-negative";
  }
};

class Calculator {
   public:
    int power(int n, int p) {
        int result = 1;
        if(n <0 || p < 0)
            throw myException();
        for(int i=0; i<p;i++)
            result*=n;
        return result;
    }
};

int main()
{
    Calculator myCalculator=Calculator();
    int T,n,p;
    cin>>T;
    while(T-->0){
      if(scanf("%d %d",&n,&p)==2){
         try{
               int ans=myCalculator.power(n,p);
               cout<<ans<<endl;
         }
         catch(exception& e){
             cout<<e.what()<<endl;
         }
      }
    }   
}





Friday, May 27, 2016

C++ solved inheritance problem from hackerrank

C++ solved inheritance problem from hackerrank:

#include <iostream>
#include <vector>

using namespace std;


class Person{
    protected:
        string firstName;
        string lastName;
        int id;
    public:
        Person(string firstName, string lastName, int identification){
            this->firstName = firstName;
            this->lastName = lastName;
            this->id = identification;
        }
        void printPerson(){
            cout<< "Name: "<< lastName << ", "<< firstName <<"\nID: "<< id << "\n";
        }
   
};

class Student :  public Person{
    private:
        vector<int> testScores; 
    public:
          // Write your constructor
        Student(string firstName, string lastName, int identification, vector<int> scores): Person(firstName, lastName, identification), testScores(scores) {
        }
          // Write char calculate()
        char calculate() {
            int sum = 0;
            int count = 0;
            vector<int>::iterator it;
            for(it = testScores.begin(); it != testScores.end(); ++it) {
                sum+= *it;
                count++;
            }
            int avg = sum/count;
            if (90 <= avg && avg <=100)
                return 'O';
            else if(80<= avg && avg < 90)
                return 'E';
            else if(70<= avg && avg < 80)
                return 'A';
            else if(55<= avg && avg < 70)
                return 'P';
            else if(40 <= avg && avg < 55)
                return 'D';
             else
                return 'T';
        }
};

int main() {
    string firstName;
      string lastName;
    int id;
      int numScores;
    cin >> firstName >> lastName >> id >> numScores;
      vector<int> scores;
      for(int i = 0; i < numScores; i++){
          int tmpScore;
          cin >> tmpScore;
        scores.push_back(tmpScore);
    }
    Student* s = new Student(firstName, lastName, id, scores);
    s->printPerson();
    cout << "Grade: " << s->calculate() << "\n";
    return 0;
}

Sunday, May 8, 2016

progrom for converting time from 12 hr format to 24 hr format


#include <math.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>
#include <limits.h>
#include <stdbool.h>

int main(){
    char* time = (char *)malloc(10240 * sizeof(char));
    scanf("%s",time);
    int count = 0;
   
    int hh = (time[0] - '0') * 10 + (time[1] - '0');
    for(int i=0;i < 10240;i++) {
        if ((time[i] == 'P' || time[i] == 'p') && (time[i+1] == 'M' || time[i+1] =='m')) {
            if (hh > 11) break;
            if (hh == 24 )
                hh = 0;
            else
                hh+=12;
            break;
        }
        if ((time[i] == 'A'  || time[i+1] =='a') && (time[i+1] == 'M' || time[i+1] =='m')) {
            if (hh > 11) hh = 0;
            break;
        }
        if (time[i] == '\0') {
            break;
        }
        count++;
    }

    time[0] = hh/10 + '0';
    time[1] = hh%10 + '0';

    char* newTime = (char*) malloc(count* sizeof (char));
    strncpy(newTime, time, count);
        printf("%s", newTime);
    return 0;
}

Saturday, May 7, 2016

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
void exchange(int *a, int* b) {
    int temp;
    temp = *a;
    *a = *b;
    *b = temp;
}
int partition (int* arr, int si, int ei) {
    int x = arr[ei];
    int i = si-1;
    int j;
    for (j = si; j < ei; j++) {
        if (arr[j] <= x) {
            i++;
            exchange(&arr[j], &arr[i]);
        }
    }
    exchange (&arr[i+1], &arr[ei]);
    return i+1;
}
void quickSort (int* arr, int si, int ei) {
    int pi;
    if (si < ei) {
        pi = partition(arr, si, ei);
        quickSort(arr, si, pi -1);
        quickSort(arr, pi+1, ei);
    }
}
int* twoSum(int* nums, int numsSize, int target) {
      int start = 0, end = numsSize-1, sum,a, b;
      int *temp = malloc(numsSize*sizeof(int));
      int k;
      for (k=0; k <= end; k++) {
          temp[k] = nums[k];
      }
     
      int* index = malloc(2*sizeof(int));
     
      quickSort(temp, start, end);
      int l;
      while (start < end) {
          sum = temp[start] + temp[end];
          if (sum == target) {
              a = temp[start];
              b = temp[end];
              break;
          } else if (sum > target)
            end--;
          else
            start++;
      }
      int z, y;
     
      for(z = 0; z < numsSize; z++) {
          if (nums[z] == a) {
             
              break;
          }
      }
      for (y = 0; y < numsSize; y++) {
          if(nums[y] == b && y!=z) {
             
              break;
          }
      }
      if (z < y) {
          index[0] = z;
          index[1] = y;
      }else {
          index[0] = y;
          index[1] = z;
      }

     
      return index;
}

Wednesday, January 13, 2016

Heap Introduction

Heap :

A Heap is a binary tree where all the leaves are either present at depth d or d-1 same as complete binary tree.
for every node n, the value in n is greater than or equal to the values in its children, thus also greater or equal
to all of the values in its subtrees.

Conditions for Heap: 
1) All leaves are either at depth d or d-1 for same d value
2) All of the leaves at depth d-1 are to the right of the leaves at d depth.
3) There is at most 1 node with just 1 child, that child is the left of its parent and it is the rightmost leaf at depth d.

examples  from http://pages.cs.wisc.edu/~vernon/cs367/notes/11.PRIORITY-Q.html