Hexagons Turtle

import turtle

from random import randint

x = 20

y = 20

turtle.speed(100)

turtle.colormode(255)

def move(l, a):

                turtle.right(a)

                turtle.forward(l)

def hex():

        turtle.pendown()

        turtle.color( randint(0,255),randint(0,255),randint(0,255) )

        turtle.begin_fill()

        for i in range(6):

                move(x,-60)

        turtle.end_fill()

        turtle.penup()

turtle.penup()

for z in range (y):

        if z == 0:

                hex()

                move(x,-60)

                move(x,-60)

                move(x,-60)

                move(0,180)

        for i in range (6):

                move(0,60)

                for j in range (z+1):

                        hex()

                        move(x,-60)

                        move(x,60)

                move(-x,0)

        move(-x,60)

        move(x,-120)

        move(0,60)

turtle.exitonclick()

Dijkstra’s shortest path algorithm

import sys

class Graph():

def __init__(self, vertices):

self.V = vertices

self.graph = [[0 for column in range(vertices)]

for row in range(vertices)]

def printSolution(self, dist):

print("Vertex \tDistance from Source")

for node in range(self.V):

print(node, "\t", dist[node])

def minDistance(self, dist, sptSet):

min = sys.maxsize

for u in range(self.V):

if dist[u] < min and sptSet[u] == False:

min = dist[u]

min_index = u

return min_index

def dijkstra(self, src):

dist = [sys.maxsize] * self.V

dist[src] = 0

sptSet = [False] * self.V

for cout in range(self.V):

x = self.minDistance(dist, sptSet)

sptSet[x] = True

for y in range(self.V):

if self.graph[x][y] > 0 and sptSet[y] == False and \

dist[y] > dist[x] + self.graph[x][y]:

dist[y] = dist[x] + self.graph[x][y]

self.printSolution(dist)

g = Graph(9)

g.graph = [[0, 4, 0, 0, 0, 0, 0, 8, 0],

[4, 0, 8, 0, 0, 0, 0, 11, 0],

[0, 8, 0, 7, 0, 4, 0, 0, 2],

[0, 0, 7, 0, 9, 14, 0, 0, 0],

[0, 0, 0, 9, 0, 10, 0, 0, 0],

[0, 0, 4, 14, 10, 0, 2, 0, 0],

[0, 0, 0, 0, 0, 2, 0, 1, 6],

[8, 11, 0, 0, 0, 0, 1, 0, 7],

[0, 0, 2, 0, 0, 0, 6, 7, 0]

];

g.dijkstra(0);

Range Queries for Frequencies of array elements

def findFrequency(arr, n, left, right, element):

count = 0

for i in range(left - 1, right):

if (arr[i] == element):

count += 1

return count

arr = [2, 8, 6, 9, 8, 6, 8, 2, 11]

n = len(arr)

print("Frequency of 2 from 1 to 6 = ",

findFrequency(arr, n, 1, 6, 2))

print("Frequency of 8 from 4 to 9 = ",

findFrequency(arr, n, 4, 9, 8))

Optimum location of point to minimize total distance

import math

class Optimum_distance:

class Point:

def __init__(self, x, y):

self.x = x

self.y = y

class Line:

def __init__(self, a, b, c):

self.a = a

self.b = b

self.c = c

def dist(self, x, y, p):

return math.sqrt((x - p.x) ** 2 +

(y - p.y) ** 2)

def compute(self, p, n, l, x):

res = 0

y = -1 * (l.a*x + l.c) / l.b

for i in range(n):

res += self.dist(x, y, p[i])

return res

def find_Optimum_cost_untill(self, p, n, l):

low = -1e6

high = 1e6

eps = 1e-6 + 1

while((high - low) > eps):

mid1 = low + (high - low) / 3

mid2 = high - (high - low) / 3

dist1 = self.compute(p, n, l, mid1)

dist2 = self.compute(p, n, l, mid2)

if (dist1 < dist2):

high = mid2

else:

low = mid1

return self.compute(p, n, l, (low + high) / 2)

def find_Optimum_cost(self, p, l):

n = len(p)

p_arr = [None] * n

for i in range(n):

p_obj = self.Point(p[i][0], p[i][1])

p_arr[i] = p_obj

return self.find_Optimum_cost_untill(p_arr, n, l)

if __name__ == "__main__":

obj = Optimum_distance()

l = obj.Line(1, -1, -3)

p = [ [ -3, -2 ], [ -1, 0 ],

[ -1, 2 ], [ 1, 2 ],

[ 3, 4 ] ]

print(obj.find_Optimum_cost(p, l))

Euler’s Totient function for all numbers smaller than or equal to n

def computeTotient(n):

phi=[]

for i in range(n + 2):

phi.append(0)

for i in range(1, n+1):

phi[i] = i 

for p in range(2,n+1):

if (phi[p] == p):

phi[p] = p-1

for i in range(2*p,n+1,p):

phi[i] = (phi[i]//p) * (p-1)

for i in range(1,n+1):

print("Totient of ", i ," is ",

phi[i])

n = 12

computeTotient(n)

N Queen Problem

global N

N = 4

def printSolution(board):

for i in range(N):

for j in range(N):

print (board[i][j], end = " ")

print()

def isSafe(board, row, col):

for i in range(col):

if board[row][i] == 1:

return False

for i, j in zip(range(row, -1, -1),

range(col, -1, -1)):

if board[i][j] == 1:

return False

for i, j in zip(range(row, N, 1),

range(col, -1, -1)):

if board[i][j] == 1:

return False

return True

def solveNQUtil(board, col):

if col >= N:

return True

for i in range(N):

if isSafe(board, i, col):

board[i][col] = 1

if solveNQUtil(board, col + 1) == True:

return True

board[i][col] = 0

return False

def solveNQ():

board = [ [0, 0, 0, 0],

[0, 0, 0, 0],

[0, 0, 0, 0],

[0, 0, 0, 0] ]

if solveNQUtil(board, 0) == False:

print ("Solution does not exist")

return False

printSolution(board)

return True

solveNQ()

Interpolation Search

def interpolationSearch(arr, lo, hi, x):

if (lo <= hi and x >= arr[lo] and x <= arr[hi]):

pos = lo + ((hi - lo) // (arr[hi] - arr[lo]) *

(x - arr[lo]))

if arr[pos] == x:

return pos

if arr[pos] < x:

return interpolationSearch(arr, pos + 1,

hi, x)

if arr[pos] > x:

return interpolationSearch(arr, lo,

pos - 1, x)

return -1

arr = [10, 12, 13, 16, 18, 19, 20,

21, 22, 23, 24, 33, 35, 42, 47]

n = len(arr)

x = 18

index = interpolationSearch(arr, 0, n - 1, x)

if index != -1:

print("Element found at index", index)

else:

print("Element not found")

program to add two numbers in base 14

def getNumeralValue(num) :

if( num >= '0' and num <= '9') :

return ord(num) - ord('0')

if( num >= 'A' and num <= 'D') :

return ord(num ) - ord('A') + 10

def getNumeral(val):

if( val >= 0 and val <= 9):

return chr(val + ord('0'))

if( val >= 10 and val <= 14) :

return chr(val + ord('A') - 10)

def sumBase14(num1, num2):

l1 = len(num1)

l2 = len(num2)

carry = 0

if(l1 != l2) :

print("Function doesn't support numbers of different"

" lengths. If you want to add such numbers then"

" prefix smaller number with required no. of zeroes")

res = [0]*(l1 + 1)

for i in range(l1 - 1, -1, -1):

nml1 = getNumeralValue(num1[i])

nml2 = getNumeralValue(num2[i])

res_nml = carry + nml1 + nml2;

if(res_nml >= 14) :

carry = 1

res_nml -= 14

else:

carry = 0

res[i+1] = getNumeral(res_nml)

if(carry == 0):

return (res + 1)

res[0] = '1'

return res

if __name__ == "__main__":

num1 = "DC2"

num2 = "0A3"

print("Result is ",end="")

res = sumBase14(num1, num2)

for i in range(len(res)):

print(res[i],end="")

Stooge Sort

def stoogesort(arr, l, h):

if l >= h:

return

if arr[l]>arr[h]:

t = arr[l]

arr[l] = arr[h]

arr[h] = t

if h-l + 1 > 2:

t = (int)((h-l + 1)/3)

stoogesort(arr, l, (h-t))

stoogesort(arr, l + t, (h))

stoogesort(arr, l, (h-t))

arr = [2, 4, 5, 3, 1]

n = len(arr)

stoogesort(arr, 0, n-1)

for i in range(0, n):

print(arr[i], end = ' ')

checking the given number is Lucky or Not

import math

def isLucky(n):

ar = [0] * 10

while (n > 0):

digit = math.floor(n % 10)

if (ar[digit]):

return 0

ar[digit] = 1

n = n / 10

return 1

arr = [1291, 897, 4566, 1232, 80, 700]

n = len(arr)

for i in range(0, n):

k = arr[i]

if(isLucky(k)):

print(k, " is Lucky ")

else:

print(k, " is not Lucky ")