PPS 5

Join the FB group for all skillrack discussions.

Click here

******************************************************************************************

Practice Problems 5 Fall 17

1) CSE1701 Word histogram (Id-2103)

Histogram is a graphical representation drawn based on the frequency of occurrence of things. Histogram for a word is drawn based on the number of occurrences of each character in the word. An inverted dictionary is used to maintain the list of characters that has same frequency. Write an algorithm and the subsequent Python code to compute and print the frequency of occurrence of character as a dictionary (ch:count). Make the entire process to be case insensitive. For example, if the input word is ‘parrot’, then the dictionary with characters and frequency of occurrence is

{'a': 1, 'o': 1, 'p': 1, 'r': 2, 't': 1}

and the inverted dictionary is

{1: ['a', 'o', 'p', 't'], 2: ['r']}

Print dictionary in sorted order by key. Sort the values of each key in the inverted dictionary.

[Hint: use pprint function for printing dictionary in sorted order.

Syntax for pprint is

pprint(dictionary name)

Include the line “from pprint import pprint” in the top of your program

Check for boundary conditions and print 'Invalid input' if conditions are not met.

Input Format:

First line contains the input word

Output Format:

Dictionary of characters in the word as keys and count as values in sorted order by key.

Inverted dictionary in sorted order by key.

Boundary Conditions:

Given word should only contain alphabets

**********************************************************

CODE:(Verified👍)

word=input().rstrip().lower()
if(any(c.isnumeric() for c in word)==True):
    print('Invalid input')
    exit()
dic={}
for letter in word:
    if(letter not in dic):
        freq=word.count(letter)
        dic[letter]=freq

import pprint
#Finding the inverse dictionary:
inv_dic={}
for k,v in dic.items():
    inv_dic[v]=inv_dic.get(v,[])
    inv_dic[v].append(k)
    inv_dic[v]=sorted(inv_dic[v])

pprint.pprint(dic)
pprint.pprint(inv_dic)

2) CSE1701 Letter Identification (Id-2106)

Given three words, write an algorithm and the subsequent Python code to identify the following letters:

1. Letters common to all the three words
2. Letters in first two words but not in third word
3. Letters in first word but not in second and third word
4. Letters in all the three words

For example, if the words are apple, camel, element then letters in common to all the three words -  i, e

Letters in first two words but not in third word – a

Letters in first word but not in second and third word  - p

Letters in all the three words – a, p, p, l, e, c, m, n, t

Hint: Use sets in Python. While reading input, use rstrip() function to remove extra spaces 

Input Format

First line contains word1

Second line contains word2

Third line contains word3

Output Format

List of letters common to all the three words in lexicographical order

List of letters common to first two words but not in third word in lexicographical order

List of letters in first word but not in second or third word in lexicographical order

List of all letters in the three words in lexicographical order

**********************************************************

CODE:(Verified👍)

word1=input().rstrip().lower()
word2=input().rstrip().lower()
word3=input().rstrip().lower()
s1=set(word1)
s2=set(word2)
s3=set(word3)
L1=[]
L2=[]
L3=[]
L4=[]
for i in s1:
    if(i in s2 and i in s3):
        L1.append(i)
for i in s1:
    if(i in s2 and i not in s3):
        L2.append(i)
for i in s1:
    if(i not in s2 and i not in s3):
        L3.append(i)
s4=s1.union(s2).union(s3)
L4=list(s4)
print(sorted(L1))
print(sorted(L2))
print(sorted(L3))
print(sorted(L4))

3) CSE1701 Rook and a Queen (Id-2102)

Given the position of a Rook and a queen in a chess board (8X8 board),  write an algorithm and the subsequent Python code to determine the common positions where both rook and queen can be placed in the next move. Rook can move through any number of cells,  either horizontally or vertically. Queens can move through any number of cells,  either horizontally, vertically or diagonally.  Each cell in the chess board may be represented as a 2-tuple (row,col). For example, if the current position of the rook is (3,1) then the next possible position of the rook may be either in the same column {(2,1),(1,1),(4,1),(5,1),(6,1),(7,1),(8,1)} or in the same row {(3,2),(3,3),(3,4),(3,5),(3,6),(3,7),(3,8)}. If the queen is in the position (5,3) then it can be placed in the same row {(5,1),(5,2),(5,4),(5,5),(5,6),(5,7),(5,8)} or same column {(1,3),(2,3),(3,3),(4,3),(6,3),(7,3),(8,3)} or along the diagonal of the current position {(6,4),(7,5),(8,6),(4,2),(5,1),(6,2),(7,1),(4,4),(3,5),(2,6),(1,7)}. Then the common cells for next move are {(3,3), (5,1), (7,1)}.

The output is a set of common board positions where both queen and rook can be placed. The positions must be printed in sorted order, sort it by row. When rows are same,  sort it by column.

(Hint: Use built-in function to sort the values)

Input Format

Row position of rook

Column position of rook

Row position of queen

Column position of queen

Output Format

Common position1

Common position2

...

**********************************************************

CODE:(Verified👍)
File Attached for the same: (CLICK HERE) 

#Reading the inputs
r_rook=int(input())
c_rook=int(input())
r_queen=int(input())
c_queen=int(input())

#Finding the next positions for Rook
positions_rook=[]
for i in range(1,9):
 positions_rook.append((r_rook,i)) #same row
 positions_rook.append((i,c_rook)) #same column
for rc in positions_rook:
 if(rc==(r_rook,c_rook) or rc==(r_queen,c_queen)):
  positions_rook.remove(rc)

#Finding the next positions for Queen
positions_queen=[]
for i in range(1,9):
 positions_queen.append((r_queen,i)) #same row
 positions_queen.append((i,c_queen)) #same column

#For diagonals_Queen
c=c_queen
r=r_queen
while(c!=1 and r!=8):
 positions_queen.append((r+1,c-1))
 r=r+1
 c=c-1
c=c_queen
r=r_queen
while(c!=1 and r!=1):
 positions_queen.append((r-1,c-1))
 r=r-1
 c=c-1
c=c_queen
r=r_queen
while(c!=8 and r!=8):
 positions_queen.append((r+1,c+1))
 r=r+1
 c=c+1
c=c_queen
r=r_queen
while(c!=8 and r!=1):
 positions_queen.append((r-1,c+1))
 r=r-1
 c=c+1

for rc in positions_queen:
 if(rc==(r_rook,c_rook) or rc==(r_queen,c_queen)):
  positions_queen.remove(rc)

final_list=[]
for i in positions_rook:
 if(i in positions_queen):
  final_list.append(i)

x=sorted(final_list)
for i in x:
print(i)

4) CSE1701 Minimum distance points (Id-2105)

Given 'n' points in an X-Y plane , write an algorithm and the subsequent Python code to determine the pair of points that are closer. Distance between two points (x1, y1) and (x2, y2) is determined using the formula.

Consider only two decimal places of distance for comparison. When there are multiple points with the same minimum distance print all points.

Input Format

Number of points

x coordinate of point1

y coordinate of point1

x coordinate of point2

y coordinate of point2

...

Output format

Point1 and Point2 that have minimum distance between them

CODE:(Verified👍)

import math
dist = lambda a,b,x,y : format(math.sqrt((a-b)**2+(x-y)**2), '.2f')
n = int(input())
x,y,mixx,l,sl=0,0,0,[],[]
for i in range(n):
    x = int(input())
    y = int(input())
    l.append((x,y))
for i in range(n-1):
    x,y = l[i][0],l[i][1]
    for j in range(i+1,n):
        a,b = l[j][0],l[j][1]
        d = float(dist(x,a,y,b))
        if i == 0 and j == 1:
            mixx = d
        if d < mixx:
            sl = []
            sl.append((x,y))
            sl.append((a,b))
            mixx = d
        elif d == mixx:
            sl.append((x,y))
            sl.append((a,b))
            mixx = d
for i in sl:
    print(i)

5) CSE1701 Count Words (Id-2104)

Write an algorithm and write the Python code to count the number of unique words in a given passage. The paragraph may contain words with special characters such as '!', '?', '.', ',' , ':' and ';' and digits are not permitted. Special character must occur only at the end of a word in a passage that is Hello World! is valid but Hello !World or Hello Wor!ld is invalid. No two special character occur together. Print 'Invalid input' for such cases. Count words without special characters. Counting must be case insensitive. Print words in lower case and in sorted order. For example, given a passage 'Programming is a skill in demand! Your programming skills are bankable assets.' The output should be

{'a': 1,

'are': 1,

'assets': 1,

'bankable': 1,

'demand': 1,

'in': 1,

'is': 1,

'programming': 2,

'skill': 1,

'skills': 1,

'your': 1}

[Hint: use pprint function for printing dictionary in sorted order.

Syntax for pprint is

pprint(dictionary name)

Include the line “from pprint import pprint” in the top of your program]

Input format:

enter a paragraph

Output format:

Dictionary of words in the passage and their count

Boundary conditions:

One paragraph is entered at a strech

CODE:(Verified👍)

from pprint import pprint
s = input()+' '
s = s.replace('! ',' ').replace('? ',' ').replace('. ',' ').replace(', ',' ').replace(': ',' ').replace('; ',' ').lower()
if '!' in s or '?' in s or '.' in s or ',' in s or ':' in s or ';' in s:
    print('Invalid input')
    exit()
l = s.split()
dic = {}
for i in l:
    if i not in dic:
        dic[i] = 1
    else:
        dic[i] += 1
pprint(dic)

************************************

INLAB 4

Join the FB group for all skillrack discussions.

Click here

******************************************************************************************

Q.)

A team of experts formed by Govt. of India conducted a survey on colleges in India. Let us assume that the survey was conducted in ‘n’ number of institutes. The experts were asked to rank the institutes based on three different metrics. The metrics are facilities, academics and infrastructure. Maximum score in each category is as follows.

Facilities = 25

Academics = 50

Infrastructure = 25

At the end of the survey the scores of the individual metrics are added up to get the total score and the institutes are ranked based on the total score. The institute that scores the highest score is ranked 1st. Next highest score is given the rank 2 and so on. Write a program to read the scores of the three metrics for each institute, store the scores in a list. Make a list of individual score list for 10 institutes. Print only the Total score in the sorted (Descending) order. Use insertion sort for arranging the data in descending order.

Input:

Read 'n' - the number of institutes

For all institutes, :
1) Read Facilities  scores
2) Read Academics scores
3) Read Infrastructure scores

Output:
List of total scores in the descending order

Code:

**(The # ones are the comments __ No need to include those.)** 

n=int(input()) #number of institutes
score_fac=[] #list of scores for Facilities
score_acad=[] #list of scores for Academics
score_infra=[] #list of scores for Infrastructure
score_total=[] #list of total scores of an institute
for i in range(n):
a=int(input()) #score for Facilities
b=int(input()) #score for Academics
c=int(input()) #score for Infrastructure
if(0<a<=25 and 0<b<=50 and 0<c<=25): #checking for the boundary condition
score_fac.append(a)
score_acad.append(b)
score_infra.append(c)
score_total.append(a+b+c)
else:
print('Invalid input')


#Function for Inserion Sort:
def insertionSort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i-1
        while j >=0 and key < arr[j] :
                arr[j+1] = arr[j]
                j -= 1
        arr[j+1] = key
    return arr
    
            
score_total=insertionSort(score_total) #list of total scores in increasing order
score_total_final=[] #list of total scores in descending order
for i in range(n):
score_total_final.append(score_total[n-i-1])

print(score_total_final)

Procedure:
def insertionSort(arr):

    for i in range(1, len(arr)):

        key = arr[i]

        j = i-1

        while j >=0 and key < arr[j] :

                arr[j+1] = arr[j]

                j -= 1

        arr[j+1] = key

    return arr

Pseudo-Code:

1) Read 'n' - the number of institutes

2) For all institutes, :
        Read Facilities scores

       Read Academics scores

       Read Infrastructure scores

3) Insert the scores in separate lists

4) Make a list of total scores

5) Sort the list of total scores

6) Reverse the above list and print it.

******************************************************************************************
**(The # ones are the comments __ No need to include those.)**
******************************************************************************************

PPS 4

Join the FB group for all skillrack discussions.

Click here

******************************************************************************************

Practice Problems 4 Fall 17

1) CSE1701 Finding a Friend with Longest Name (Id-1994)
Write an algorithm and the subsequent Python program to store the names of your friends, count the number of friends, identify the longest name and the number of letters in the longest name. Get the names of friends till 'stop' is entered. For example, if the input sequence is Ravi, Raj, Puela, stop,  then the output is 3, Puela and 5.

When you are coding in the online judge (SkillRack), use rstrip() function to remove carriage return from the input string.

Input Format:

First line is the name of  the first friend

Second line is the  name of the second friend

Third line is the  name of the third friend

….

stop

Output Format:

Number of friends

Friend’s name with longest length

Number of characters in that longest name

Code:(Verified👍)
list_of_names=[]
name=input().rstrip()
while(name!="Stop"):
list_of_names.append(name)
name=input().rstrip()
print(len(list_of_names))
temp=""
m=0
for name in list_of_names:
if(len(name)>m):
m=(len(name))
temp=name
print(temp)
print(m)

******************************************************************************************

2) CSE1701 Polynomial Addition (Id-1993)
Write an algorithm and the subsequent Python program to add the two given polynomials. Assume that the coefficients of each polynomial are stored in a separate list.

Eg: 4x3 + 3x + 1 can be stored as [4,0,3,1]

2x2 - 3x - 4 can be stored as [2,-3,-4]

Output is [4, 2, 0, -3]

Input Format:

First line contains the degree of the first polynomial

Next line contains the coefficient of xn

Next line contains the coefficient of xn-1

...

Next line contains the coefficient of x0

Next line contains the degree of the second equation

Next line contains the coefficient of xn

Next line contains the coefficient of xn-1

...

Next line contains the coefficient of x0

Output Format:

Coefficients as a list from the highest degree to the lowest degree

Code:(Verified👍)
d=int(input())
p1=[]
p2=[]
for i in range(d+1):
c=int(input())
p1=[c]+p1    #first element is the coefficient of x^0
d=int(input())
for i in range(d+1):
c=int(input())
p2=[c]+p2    #first element is the coefficient of x^0
l1=len(p1)
l2=len(p2)
greater_degree=l2;  #let
pf=[]  #final list with the sum of coefficients


#Reversing the list
p1.reverse()   #first element is the coefficient of x^n
p2.reverse()   #first element is the coefficient of x^n


if(l1>l2):
greater_degree=l1;
for i in range(l1-l2):
p2=[0]+p2
else:
for i in range(l2-l1):
p1=[0]+p1
for i in range(greater_degree):
pf.append(p1[i]+p2[i])
print(pf)

3) CSE1701 Creating Unique List and Searching (Id-1996)

A login register is maintained in the library of VITCC in which, the register number of students are recorded when they enter the library. Sometimes it happens that the students visit the library more than once in a day and hence duplicate entries occur so frequently in the register. The librarian wants to have a report of all students who have visited on a particular day, ‘x’. Given the list  of students who visited the library on the day ‘x’, write an algorithm and the subsequent Python program to prepare a report with unique register number of students. Also read a register number ‘r’ and search for it in the list. Print ‘Found’ if ‘r’ is in the list and print ‘Not found’ otherwise.

Input Format:

First line contains the number of students visited, ‘n’

Second line contains the register number of first entry

Third line contains the register number of second entry

. . .

N+1th line contains the register number of n-th entry

Next line contains the register number  ‘r’ that has to be searched

Output Format:

A list without duplicate entries

Print either ‘Found’ or ‘Not found’

Boundary Conditions:

Number of students visited >=0

Code:(Verified👍)
n=int(input())
p=[]
for i in range(n):
    reg=input().rstrip().upper()
    if(reg not in p):
        p.append(reg)
r=input().rstrip().upper()
print(p)
if(r in p):
 print('Found')
else:
 print('Not found')

4) CSE1701 Arrangement of Plants (Id-1997)

A gardener has the practice of assigning ID to the plants during plantation. One day, he makes a note of the heights of plants in his garden. He writes the height of the plant against the ID of the plant. He then instructs his employee to keep the plants, in ascending order of its height. Design an algorithm and write the Python code to display the list of ID numbers of plants in ascending order of their height. IDs are also numbers. Check for boundary conditions and print 'Invalid input' for wrong input. For example, if there are three trees with IDs as 175, 160, 120 and height as 47, 73 and 23 then the output should be [120, 175, 160].

Input Format:

First line contains the number of plants, n

Next line contains the ID of the plant-1

Next line contains the height of plant-1

. . .

Next line contains the ID of the plant-n

Next line contains the height of plantn

Output Format:

IDs sorted according to height. Print one id in one line

Boundary Conditions:

All inputs >=0

Code:(Verified👍)
n=int(input())
ids=[]
heights=[]
for i in range(n):
ids.append(int(input()))
heights.append(int(input()))
sorted_ids=[x for (y,x) in sorted(zip(heights,ids))]
#The zip() function returns an iterator of tuples based on the iterable object.
for i in sorted_ids:
print(i)

5) CSE1701 Sparse Matrix (Id-1995)

Write an algorithm and the subsequent Python program to check whether the given matrix is sparse or not. A matrix is said to be a “Sparse” if the number  of zero entries  in the matrix,  is greater than or equal to the number  of non-zero entries. Otherwise it is  “Not sparse”. Check for boundary conditions and print 'Invalid input' when not satisfied.

Input Format:

The first line will contain the number of rows in the matrix, rows

The Second line will contain the number of columns in the matrix, cols

The next (rows * cols) lines will contain the elements of the matrix, entered row wise

Output Format:

Print either Sparse or Not sparse

Boundary Conditions:

Number of rows and columns > 0

Code:(Verified👍)

r=int(input())  #number of rows in matrix
c=int(input())  #number of columns in matrix
if(r<=0 or c<=0):
print('Invalid input')
exit
else:
vals=[]
flag=0
for i in range(r*c):
vals.append(int(input()))
zero_entries=vals.count(0)
if(zero_entries>=r*c-zero_entries):
print('Sparse')
else:
print('Not sparse')

******************************************************************************************

THANK YOU FOR VISITING...

Best of luck. 👍

******************************************************************************************