Bit Stuffing in Computer Network Using Python

Bit Stuffing Mechanism

Here, the delimiting flag sequence generally contains six or more consecutive 1s. Most protocols use the 8-bit pattern 01111110 as flag. In order to differentiate the message from the flag in case of same sequence, a single bit is stuffed in the message. Whenever a 0 bit is followed by five consecutive 1bits in the message, an extra 0 bit is stuffed at the end of the five 1s. When the receiver receives the message, it removes the stuffed 0s after each sequence of five 1s. The un-stuffed message is then sent to the upper layers.

 

Code :

#Stuffing the original signal def stuff(sig): onec = 0 # one counter c = 0 # index counter one = [] # one indexes s = list(sig) for i in s: c += 1 if i == '0': onec = 0 else: onec += 1 if onec == 5: one.append(c) onec = 0 k = 0 # count extra index number for i in one: # print(i) s.insert(i+k,'0') k+=1 return s # destuffing the stuffed signal def destuff(sig): onec = 0 # one counter c = 0 # index counter one = [] # one indexes sig = list(sig) for i in sig: c += 1 if i == '0': onec = 0 else: onec += 1 if onec == 5: one.append(c) onec = 0 k = 0 # count extra index number for i in one: # print(i) sig.pop(i+k) k-=1 return sig # Driver Code sig = input("Enter the signal: ") print("Original Signal : ",sig) stf = stuff(sig) print("Stuffed Signal : ",end ="") print("".join([ x for x in stf])) dstf = destuff(stf) print("Destuffed Signal : ",end ="") print("".join([ x for x in dstf]))

Byte Stuffing in Computer Network Using Python

Byte Stuffing Mechanism

If the pattern of the flag byte is present in the message byte sequence, there should be a strategy so that the receiver does not consider the pattern as the end of the frame. Here, a special byte called the escape character (ESC) is stuffed before every byte in the message with the same pattern as the flag byte. If the ESC sequence is found in the message byte, then another ESC byte is stuffed before it.

Code :

st=input('Enter the Data :') flag=input('Flag :') esc=input('Esc :') def Sender(st,flag,esc): a=st.replace(esc,esc*2) y=a.replace(flag,esc+flag) return y print("Stuffed : "+Sender(st,flag,esc))

The Flight Plan - Hackerearth Problem Solution Using Python

Here , To solve this problem we have use the BFS algorithm using python in which we just add a "dist" list in which we store distance of every node from its parent node. And we have use dictionary named "dd" in which we store its parent node if we print that dictionary we get the path for for each node from source given node.

For the Problem goto below link and search for problem: The Flight Plan

Code :

from collections import defaultdict class Graph: def __init__(self): self.graph = defaultdict(list) def addEdge(self,u,v): self.graph[u].append(v) def BFS(self, s,l): dist=[0]*100 dd=defaultdict(list) dd[s].append(0) visited = [False] * 100#(len(self.graph)+1) queue = [] queue.append(s) visited[s] = True while queue: s = queue.pop(0) for i in self.graph[s]: if visited[i] == False: dist[i]=dist[s]+1 dd[i].append(s) for j in dd[s]: dd[i].append(j) queue.append(i) visited[i] = True print(dist[l]+1) return dd[l] def main(): l=list(map(int,input().split())) g=Graph() for i in range(l[1]): l2=list(map(int,input().split())) g.addEdge(l2[0],l2[1]) g.addEdge(l2[1],l2[0]) l3=list(map(int,input().split())) ans=g.BFS(l3[0],l3[1]) ans.reverse() for i in ans: if i==0: continue print(i,end=' ') print(l3[1],end=' ') main()

Social Networking Graph - Hackerearth Problem Solution Using Python

Here , To solve this problem we have use the BFS algorithm using python in which we just add a "dist" list in which we store distance of every node from its parent node. And then we see count nodes which are at a given distance from given source node.

For the Problem goto below link and search for problem: Social Networking Graph

Code :

from collections import defaultdict from collections import defaultdict class Graph: def __init__(self): self.graph = defaultdict(list) def addEdge(self,u,v): self.graph[u].append(v) def BFS(self, s,a): dist=[0]*100 visited = [False] * 100#(len(self.graph)+1) queue = [] queue.append(s) visited[s] = True while queue: s = queue.pop(0) for i in self.graph[s]: if visited[i] == False: dist[i]=dist[s]+1 #this is the dist list queue.append(i) visited[i] = True return dist.count(a) def main(): ml=[] l=list(map(int,input().split())) g=Graph() for i in range(l[1]): l2=list(map(int,input().split())) g.addEdge(l2[0],l2[1]) g.addEdge(l2[1],l2[0]) #graph is bidirectional n=int(input()) for j in range(n): ll=list(map(int,input().split())) ans=g.BFS(ll[0],ll[1]) ml.append(ans) for i in ml: print(i) main()

Monk and the Islands - Hackerearth Problem Solution Using Python

Here , To solve this problem we have use the BFS algorithm using python in which we just add a "dist" list in which we store distance of every node from its parent node.

For the Problem goto below link and search for problem: Monk and Islands

Code :

from collections import defaultdict from collections import defaultdict class Graph: def __init__(self): self.graph = defaultdict(list) def addEdge(self,u,v): self.graph[u].append(v) def BFS(self, s,l): dist=[0]*10000000 visited = [False] * 10000000#(len(self.graph)+1) queue = [] queue.append(s) visited[s] = True while queue: s = queue.pop(0) for i in self.graph[s]: if visited[i] == False: dist[i]=dist[s]+1 #this is the dist list queue.append(i) visited[i] = True return dist[l[0]] def main(): t=int(input()) ml=[] for i in range(t): l=list(map(int,input().split())) g=Graph() for i in range(l[1]): l2=list(map(int,input().split())) g.addEdge(l2[0],l2[1]) g.addEdge(l2[1],l2[0]) #graph is bidirectional ans=g.BFS(1,l) ml.append(ans) for i in ml: print(i) main()

Shortest Path Using Breadth First Search (BFS)

Shortest Path Using Breadth First Search (BFS)

Here , To find the shortest path using BFS first we have to know that the graph should always be unweighted graph .

If you know about the BFS algorithm then to find shortest path we have to add only one thing that is a dictionary named "dist" which records the distance of every node from given node As shown in below code.

Code :

from collections import defaultdict # This class represents a directed graph # using adjacency list representation class Graph: # Constructor def __init__(self): # default dictionary to store graph self.graph = defaultdict(list) # function to add an edge to graph def addEdge(self,u,v): self.graph[u].append(v) # Function to print a BFS of graph def BFS(self, s): dist=[0]*10 # Mark all the vertices as not visited visited = [False] * (len(self.graph)) # Create a queue for BFS queue = [] # Mark the source node as # visited and enqueue it queue.append(s) visited[s] = True while queue: # Dequeue a vertex from # queue and print it s = queue.pop(0) print (s, end = " ") # Get all adjacent vertices of the # dequeued vertex s. If a adjacent # has not been visited, then mark it # visited and enqueue it for i in self.graph[s]: if visited[i] == False: dist[i]=dist[s]+1 queue.append(i) visited[i] = True print(dist) # Driver code # Create a graph given in # the above diagram g = Graph() g.addEdge(0, 1) g.addEdge(1,0) g.addEdge(0, 3) g.addEdge(3,0) g.addEdge(1, 2) g.addEdge(2,1) g.addEdge(3, 7) g.addEdge(7,3) g.addEdge(3, 4) g.addEdge(4,3) g.addEdge(4, 7) g.addEdge(7,4) g.addEdge(4, 6) g.addEdge(6,4) g.addEdge(7, 6) g.addEdge(6,7) g.addEdge(6, 5) g.addEdge(5,6) print ("Following is Breadth First Traversal" " (starting from vertex 2)") g.BFS(2)