## Nodes and Trees

0 likes • Nov 18, 2022
Python

## More Python Posts

```from functools import partial
```from itertools import productV='∀'E='∃'

def tt(f,n) :  xss=product((0,1),repeat=n)  print('function:',f.__name__)  for xs in xss : print(*xs,':',int(f(*xs)))  print('')
# p \/ (q /\ r) = (p \/ q) /\ (p \/ r)
def prob1(p,q,r) :  x=p or (q and r)  y= (p or q) and (p or r)  return x==y
tt(prob1,3)
# p/\(q\/r)=(p/\q)\/(p/\r)
def prob2(p,q,r) :  x=p and ( q or r )  y=(p and q) or (p and r)  return x==y
tt(prob2,3)
#~(p/\q)=(~p\/~q)
def prob3(p,q) :  x=not (p and q)  y=(not p) or (not q)  return x==ytt(prob3,2)
#(~(p\/q))=((~p)/\~q)
def prob4(p, q):   x = not(p or q)   y = not p and not q   return x == y
tt(prob4, 2)
#(p/\(p=>q)=>q)
def prob5(p,q):  x= p and ( not p or q)  return not x or q    tt(prob5,2)
# (p=>q)=((p\/q)=q)
def prob6(p,q) :  x = (not p or q)  y=((p or q) == q)  return x==y tt(prob6,2)

#((p=>q)=(p\/q))=qdef prob7(p,q):  if ((not p or q)==(p or q))==q:    return 1 tt(prob7,2)

#(p=>q)=((p/\q)=p)def prob8(p,q):  if (not p or q)==((p and q)==p):    return 1 tt(prob8,2)

#((p=>q)=(p/\q))=p
def prob9(p,q):  if ((not p or q)==(p and q))==p:    return '1'
tt(prob9,2)

#(p=>q)/\(q=>r)=>(p=>r)def prob10(p,q,r) :  x = not ((not p or q) and (not q or r)) or (not p or r)  return x tt(prob10, 3)

# (p = q) /\ (q => r)  => (p => r)#answer 1def prob11(p,q,r) :  x = not((p is q) and (not q or r)) or (not p or r)  return x tt(prob11, 3)
#(p=q)/\(q=>r)=>(p=>r)#answer 2def prob11(p,q,r):  x=(p==q) and (not q or r)  y=not p or r  return not x or y
tt(prob11,3)
#((p=>q)/\(q=r))=>(p=>r)
def prob12(p,q,r):  x=(not p or q) and ( q==r )  y=not p or r  return not x or y
tt(prob12,3)
#(p=>q)=>((p/\r)=>(q/\r))
def prob13(p,q,r):  x=not p or q  y=(not(p and r) or ( q and r))  return not x or y
tt(prob13,3)
#Question#2----------------------------------------
#(p=>q)=>r=p=>(q=>r)
def prob14(p,q,r):  x=(not(not p or q) or r)  y=(not p or (not q or r))  return x==y
tt(prob14,3)

def prob15(p, q):    x = not(p and q)    y = not p and not q    return x == y
tt(prob15, 2)

def prob16(p, q):    x = not(p or q)    y = not p or not q    return x == y
tt(prob16, 2)

def prob17(p):    x = p    y = not p    return x == y
tt(prob17, 1)```
`""" Rock Paper Scissors----------------------------------------"""import randomimport osimport reos.system('cls' if os.name=='nt' else 'clear')while (1 < 2):    print "\n"    print "Rock, Paper, Scissors - Shoot!"    userChoice = raw_input("Choose your weapon [R]ock], [P]aper, or [S]cissors: ")    if not re.match("[SsRrPp]", userChoice):        print "Please choose a letter:"        print "[R]ock, [S]cissors or [P]aper."        continue    // Echo the user's choice    print "You chose: " + userChoice    choices = ['R', 'P', 'S']    opponenetChoice = random.choice(choices)    print "I chose: " + opponenetChoice    if opponenetChoice == str.upper(userChoice):        print "Tie! "    #if opponenetChoice == str("R") and str.upper(userChoice) == "P"    elif opponenetChoice == 'R' and userChoice.upper() == 'S':              print "Scissors beats rock, I win! "        continue    elif opponenetChoice == 'S' and userChoice.upper() == 'P':              print "Scissors beats paper! I win! "        continue    elif opponenetChoice == 'P' and userChoice.upper() == 'R':              print "Paper beat rock, I win! "        continue    else:               print "You win!"`
`#Python program to print topological sorting of a DAGfrom collections import defaultdict  #Class to represent a graphclass Graph:    def __init__(self,vertices):        self.graph = defaultdict(list) #dictionary containing adjacency List        self.V = vertices #No. of vertices      # function to add an edge to graph    def addEdge(self,u,v):        self.graph[u].append(v)      # A recursive function used by topologicalSort    def topologicalSortUtil(self,v,visited,stack):          # Mark the current node as visited.        visited[v] = True          # Recur for all the vertices adjacent to this vertex        for i in self.graph[v]:            if visited[i] == False:                self.topologicalSortUtil(i,visited,stack)          # Push current vertex to stack which stores result        stack.insert(0,v)      # The function to do Topological Sort. It uses recursive     # topologicalSortUtil()    def topologicalSort(self):        # Mark all the vertices as not visited        visited = [False]*self.V        stack =[]          # Call the recursive helper function to store Topological        # Sort starting from all vertices one by one        for i in range(self.V):            if visited[i] == False:                self.topologicalSortUtil(i,visited,stack)          # Print contents of stack        print(stack)  g= Graph(6)g.addEdge(5, 2);g.addEdge(5, 0);g.addEdge(4, 0);g.addEdge(4, 1);g.addEdge(2, 3);g.addEdge(3, 1);  print("Following is a Topological Sort of the given graph")g.topologicalSort()`
```# question3.pyfrom itertools import productV='âˆ€'E='âˆƒ'
def tt(f,n) :  xss=product((0,1),repeat=n)  print('function:',f.__name__)  for xs in xss : print(*xs,':',int(f(*xs)))  print('')
# this is the logic for part A (p\/q\/r) /\ (p\/q\/~r) /\ (p\/~q\/r) /\ (p\/~q\/~r) /\ (~p\/q\/r) /\ (~p\/q\/~r) /\ (~p\/~q\/r) /\ (~p\/~q\/~r)
def parta(p,q,r) :    a=(p or q or r) and (p or q or not r) and (p or not q or r)and (p or not q or  not r)  b=(not p or q or r ) and (not p or q or not r) and (not p or not q or r) and (not p or not q or not r)  c= a and b  return c
def partb(p,q,r) :  a=(p or q and r) and (p or not q or not r) and (p or not q or not  r)and (p or q or  not r)  b=(not p or q or r ) and (not p or q or not r) and (not p or not q or r) and (not p or not q or not r)  c= a and b  return c
print("part A:")tt(parta,3)
print("part B:")tt(partb,3)```

### Bitonic sort

CodeCatch
0 likes • Nov 19, 2022
Python
```# Python program for Bitonic Sort. Note that this program# works only when size of input is a power of 2.
# The parameter dir indicates the sorting direction, ASCENDING# or DESCENDING; if (a[i] > a[j]) agrees with the direction,# then a[i] and a[j] are interchanged.*/def compAndSwap(a, i, j, dire):	if (dire==1 and a[i] > a[j]) or (dire==0 and a[i] > a[j]):		a[i],a[j] = a[j],a[i]
# It recursively sorts a bitonic sequence in ascending order,# if dir = 1, and in descending order otherwise (means dir=0).# The sequence to be sorted starts at index position low,# the parameter cnt is the number of elements to be sorted.def bitonicMerge(a, low, cnt, dire):	if cnt > 1:		k = cnt/2		for i in range(low , low+k):			compAndSwap(a, i, i+k, dire)		bitonicMerge(a, low, k, dire)		bitonicMerge(a, low+k, k, dire)
# This funcion first produces a bitonic sequence by recursively# sorting its two halves in opposite sorting orders, and then# calls bitonicMerge to make them in the same orderdef bitonicSort(a, low, cnt,dire):	if cnt > 1:		k = cnt/2		bitonicSort(a, low, k, 1)		bitonicSort(a, low+k, k, 0)		bitonicMerge(a, low, cnt, dire)
# Caller of bitonicSort for sorting the entire array of length N# in ASCENDING orderdef sort(a,N, up):	bitonicSort(a,0, N, up)
# Driver code to test abovea = [3, 7, 4, 8, 6, 2, 1, 5]n = len(a)up = 1
sort(a, n, up)print ("\n\nSorted array is")for i in range(n):	print("%d" %a[i]),```