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="")