FIND S

import csv
import random
a=[[]]
with open("finds.csv",'r') as CSVFile:
  reader=csv.reader(CSVFile)
  for row in reader:
    a.append(row)
print(a)
fs=['0']*(len(a[1])-1)
print(fs)

rlen=len(a)
for i in range(0,rlen):
  alen=len(a[i])
  if alen == 0:
    continue
  elif a[i][alen-1] == 'Yes':
    for j in range(0,alen-1):
      if fs[j]=='0':
        fs[j]=a[i][j]
      elif fs[j]=='?':
        continue
      elif fs[j] != a[i][j]:
        fs[j]='?'
      else:
        fs[j]=a[i][j]
    print(fs)
print(fs)

KNN

import csv
import math
A = []
with open('iris.csv','r') as csvfile:
  for row in csv.reader(csvfile):
    A.append(row)
ints = A[1:]
testSet = [7.2,3.6,5.1,2.5]
def ED(d1,d2,length):
  distance = 0
  for x in range(length):
    distance += (float(d1[x])-d2[x])*(float(d1[x])-d2[x])
  return math.sqrt(distance)

def KNN(trainSet, testset, k):
  ll = []
  for x in trainSet:
    ll.append([ED(x,testSet,len(testSet)),x[len(x)-1]])
  ll.sort(key=lambda x: int(x[0]))
  ss = ll[:k]
  se = list(set([x[1] for x in ss]))
  ss = [x[1] for x in ss]
  x = [0]*len(se)
  for i in range(len(se)):
    x[i] = ss.count(se[i])
  typ = se[x.index(max(x))]
  return typ


t = KNN(ints,testSet,13)
print('The estimated value of testSet is: ',t)

BFS,DFS,IDDFS,DLS
#BFS, DFS, DLS, IDDFS
graph={
    0:[1,2],
    1:[3,4],
    2:[5,6],
    3:[],
    4:[],
    5:[],
    6:[]
}
visited=[]
queue=[]
def bfs(visited,graph,node):
  visited.append(node)
  queue.append(node)
  while queue:
    s=queue.pop(0)
    print(s,end=' ')
    for neighbour in graph[s]:
      if neighbour not in visited:
        visited.append(neighbour)
        queue.append(neighbour)

print('BFS Traversal')
bfs(visited,graph,0)
print()

visited=set()
def DFS(visited,graph,node):
  if node not in visited:
    visited.add(node)
    print(node)
    for neighbour in graph[node]:
      dfs(visited,graph,neighbour)

print('DFS Traversal')
DFS(visited,graph,0)

visited=set()
limit=1
def DLS(visited,graph,node,k):
  if node not in visited:
    if(k<=l):
      visited.add(node)
      print(node)
      for neighbour in graph[node]:
        DLS(visited,graph,neighbour,k+1)

print('DLS Traversal')
DLS(visited,graph,0,0)

def IDDFS(visited,graph,node,k,l):
  if node not in visited:
    if(k<=l):
      visited.add(node)
      print(node)
      for neighbour in graph[node]:
        IDDFS(visited,graph,neighbour,k+1,l)

print('IDDFS Traversal')
for i in range(3):
  visited=set()
  IDDFS(visited,graph,0,0,i)


WATER JUG
from collections import defaultdict
jug1, jug2, aim = 4,2,1
visited = defaultdict(lambda: False)
def waterJugSolver(amt1, amt2):
   if (amt1 == aim and amt2 == 0) or (amt2 == aim and amt1 == 0):
      print(amt1, amt2)
      return True
   if visited[(amt1, amt2)] == False:
      print(amt1, amt2)
      visited[(amt1, amt2)] = True
      return (waterJugSolver(0, amt2) or
            waterJugSolver(amt1, 0) or
            waterJugSolver(jug1, amt2) or
            waterJugSolver(amt1, jug2) or
            waterJugSolver(amt1 + min(amt2, (jug1-amt1)), amt2 - min(amt2, (jug1-amt1))) or
            waterJugSolver(amt1 - min(amt1, (jug2-amt2)),amt2 + min(amt1, (jug2-amt2))))
   else:
      return False

print("Steps: ")

waterJugSolver(0, 0)

N QUEEN
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()

ALPHA BETAA

MAX, MIN = 1000, -1000

def minimax(depth, nodeIndex, maximizingPlayer, values, alpha, beta):
    if depth == 3:
        print(values[nodeIndex])
        return values[nodeIndex]
    if maximizingPlayer:
        best = MIN
        for i in range(0, 2):
            val = minimax(depth + 1, nodeIndex * 2 + i, False, values, alpha, beta)
            best = max(best, val)
            alpha = max(alpha, best)
            if beta <= alpha:
                break
        return best
    else:
        best = MAX
        for i in range(0, 2):
            val = minimax(depth + 1, nodeIndex * 2 + i, True, values, alpha, beta)
            best = min(best, val)
            beta = min(beta, best)
            if beta <= alpha:
                break
        return best

values = [3, 5, 6, 9, 1, 2, 0, -1]
print("The optimal value is :", minimax(0, 0, True, values, MIN, MAX))

TIC TAC TOE

player, opponent = 'x', 'o'


def isMovesLeft(board):
    for i in range(3):
        for j in range(3):
            if (board[i][j] == '_'):
                return True
    return False


def evaluate(b):
    for row in range(3):
        if (b[row][0] == b[row][1] and b[row][1] == b[row][2]):
            if (b[row][0] == player):
                return 10
            elif (b[row][0] == opponent):
                return -10
    for col in range(3):

        if (b[0][col] == b[1][col] and b[1][col] == b[2][col]):

            if (b[0][col] == player):
                return 10
            elif (b[0][col] == opponent):
                return -10
    if (b[0][0] == b[1][1] and b[1][1] == b[2][2]):

        if (b[0][0] == player):
            return 10
        elif (b[0][0] == opponent):
            return -10

    if (b[0][2] == b[1][1] and b[1][1] == b[2][0]):

        if (b[0][2] == player):
            return 10
        elif (b[0][2] == opponent):
            return -10
    return 0


def minimax(board, depth, isMax):
    score = evaluate(board)
    if (score == 10):
        return score
    if (score == -10):
        return score
    if (isMovesLeft(board) == False):
        return 0
    if (isMax):
        best = -1000
        for i in range(3):
            for j in range(3):
                if (board[i][j] == '_'):
                    board[i][j] = player
                    best = max(best, minimax(board,
                                             depth + 1,
                                             not isMax))
                    board[i][j] = '_'
        return best
    else:
        best = 1000
        for i in range(3):
            for j in range(3):
                if (board[i][j] == '_'):
                    board[i][j] = opponent
                    best = min(best, minimax(board, depth + 1, not isMax))
                    board[i][j] = '_'
        return best


def findBestMove(board):
    bestVal = -1000
    bestMove = (-1, -1)
    for i in range(3):
        for j in range(3):

            if (board[i][j] == '_'):
                board[i][j] = player
                moveVal = minimax(board, 0, False)

                # Undo the move
                board[i][j] = '_'
                if (moveVal > bestVal):
                    bestMove = (i, j)
                    bestVal = moveVal

    print("The value of the best Move is :", bestVal)
    print()
    return bestMove


board = [
    ['x', 'o', 'x'],
    ['o', 'o', 'x'],
    ['_', '_', '_']
]

bestMove = findBestMove(board)

print("The Optimal Move is :")
print("ROW:", bestMove[0], " COL:", bestMove[1])

K MEANS

from operator import itemgetter
import numpy
import random
from sklearn import datasets
import matplotlib.pyplot as plt

def newcent(clus):
    a=0
    b=0
    n=len(clus)
    for i in range(n):
        a=a+clus[i][0]
        b=b+clus[i][1]
    return [a/n,b/n]

def eucdist(p1,p2):
    return ((p2[0]-p1[0])**2+(p2[1]-p1[1])**2)**(0.5)

def getmin(a,b,c):
    if(a<=b and a<=c):
      return 1
    elif(b<=a and b<=c):
      return 2
    else:
      return 3

iris=datasets.load_iris()
data=list(iris.data)
target=list(iris.target)
n=len(target)

for i in range(n):
    data[i]=list(data[i])

newattr=[]
for i in range(n):
    newattr.append(data[i][0:2])

k1=random.choice(newattr)
k2=random.choice(newattr)
k3=random.choice(newattr)
# print(k1,k2,k3)
newattr.remove(k1)
newattr.remove(k2)
newattr.remove(k3)

n=len(newattr)
c1=[k1]
c2=[k2]
c3=[k3]
for i in range(n):
    clusno=getmin(eucdist(newattr[i],k1),eucdist(newattr[i],k2),eucdist(newattr[i],k3))
    if(clusno==1):
        c1.append(newattr[i])
        k1=newcent(c1)
    elif(clusno==2):
        c2.append(newattr[i])
        k2=newcent(c2)
    elif(clusno==3):
        c3.append(newattr[i])
        k3=newcent(c3)
# print(k1,k2,k3)
xcor=[]
ycor=[]
for i in range(len(c1)):
    xcor.append(c1[i][0])
    ycor.append(c1[i][1])
plt.scatter(xcor,ycor,c='g',marker='o')

xcor=[]
ycor=[]
for i in range(len(c2)):
    xcor.append(c2[i][0])
    ycor.append(c2[i][1])
plt.scatter(xcor,ycor,c='r',marker='o')

xcor=[]
ycor=[]
for i in range(len(c3)):
    xcor.append(c3[i][0])
    ycor.append(c3[i][1])
plt.scatter(xcor,ycor,c='y',marker='o')


EM

from sklearn import datasets
import pandas as pd
import numpy as np
import matplotlib.pyplot as plt

iris=datasets.load_iris()
X=pd.DataFrame(iris.data)
X.columns=['Sepal_Length','Sepal_Width','Petal_Length','Petal_Width']
Y=pd.DataFrame(iris.target)
Y.columns=['Targets']

colormap=np.array(['red','lime','blue'])
plt.figure(figsize=(7,10))
plt.subplot(2,1,1)
plt.scatter(X.Sepal_Length,X.Sepal_Width,c=colormap[Y.Targets],s=40)
plt.xlabel('Sepal Length')
plt.ylabel('Sepal Width')
plt.title('Real Clusters')

from sklearn import preprocessing
scaler=preprocessing.StandardScaler()
scaler.fit(X)
xsa=scaler.transform(X)
xs=pd.DataFrame(xsa,columns=X.columns)

from sklearn.mixture import GaussianMixture
gmm=GaussianMixture(n_components=3)
gmm.fit(xs)
gmm_y=gmm.predict(xs)

plt.subplot(2,1,2)
plt.scatter(X.Sepal_Length,X.Sepal_Width,c=colormap[gmm_y],s=40)
plt.title("GMM Clusters")
plt.xlabel('Sepal Length')
plt.ylabel('Sepal Width')


AND PERCEPTRON

import numpy as np
import random as r

inputs = np.array([[0,0,1,1],[0,1,0,1]])
preds = np.array([0,0,0,1])
weights = np.array([r.uniform(-0.5,0.5),r.uniform(-0.5,0.5)])

print(weights)

actual = []
errors = []
j = 0
threshold = 0
for i in range(len(preds)):
  k = inputs[0][j]*weights[0] +weights[1] *inputs[1][j]
  if  k > threshold:
     actual.append(1)
  else:
     actual.append(0)
  errors.append(preds[i]-actual[i])
  j+=1
print('Predicted',preds)
print('Actual',actual)
print('Errors',errors)


OR PERCEPTRON
 same as and

PERCEPTRON

import numpy as np
import random as r
import math

def af(x):
  return (1/(1+math.exp(-x)))

inputs = np.array([0,1,0])
preds = np.array([1])
weights = np.array([r.uniform(-0.5,0.5),r.uniform(-0.5,0.5),r.uniform(-0.5,0.5)])
print(weights)

actual = []
errors = []
bias = r.uniform(-0.5,0.5)

k =0
for i in range(len(inputs)):
  k += inputs[i] * weights[i]
k+= bias
print('Net = ',k)
k = af(k)
print('Actual (After Activation)  = ',k)
actual.append(k)
errors.append((preds[0] - actual[0]))

print('Predicted',preds)
print('Actual',actual)
print('Errors',errors)


a* algorithm

def aStarAlgo(start_node, stop_node):
    open_set = set(start_node)
    closed_set = set()

    g = {}
    parents = {}

    g[start_node] = 0
    parents[start_node] = start_node
    while len(open_set) > 0:
        n = None
        for v in open_set:
            if n == None or g[v] + heuristic(v) < g[n] + heuristic(n):
                n = v
        if n == stop_node or Graph_nodes[n] == None:
            pass
        else:
            for (m, weight) in get_neighbors(n):
                if m not in open_set and m not in closed_set:
                    open_set.add(m)
                    parents[m] = n
                    g[m] = g[n] + weight
                else:
                    if g[m] > g[n] + weight:
                        g[m] = g[n] + weight
                        parents[m] = n
                        if m in closed_set:
                            closed_set.remove(m)
                            open_set.add(m)
        if n == None:
            print('Path does not exist!')
            return None

        if n == stop_node:
            path = []
            while parents[n] != n:
                path.append(n)
                n = parents[n]
            path.append(start_node)
            path.reverse()
            print("Path found: " + str(path))
            return path
        open_set.remove(n)
        closed_set.add(n)
    print('Path does not exist!')
    return None

def get_neighbors(v):
    if v in Graph_nodes:
        return Graph_nodes[v]
    else:
        return None

def heuristic(n):
    H_dist = {
        'A': 11,
        'B': 6,
        'C': 5,
        'D': 7,
        'E': 3,
        'F': 6,
        'G': 5,
        'H': 3,
        'I': 1,
        'J': 0
    }
    return H_dist[n]

Graph_nodes = {
    'A': [('B', 6), ('F', 3)],
    'B': [('A', 6), ('C', 3), ('D', 2)],
    'C': [('B', 3), ('D', 1), ('E', 5)],
    'D': [('B', 2), ('C', 1), ('E', 8)],
    'E': [('C', 5), ('D', 8), ('I', 5), ('J', 5)],
    'F': [('A', 3), ('G', 1), ('H', 7)],
    'G': [('F', 1), ('I', 3)],
    'H': [('F', 7), ('I', 2)],
    'I': [('E', 5), ('G', 3), ('H', 2), ('J', 3)],
}

aStarAlgo('A', 'J')


BACK PROP

targets = [0.01,0.99]
inputs = [0.05,0.10]
weights = [[0.15,0.20],[0.25,0.30],[0.40,0.45],[0.50,0.55]]
biases = [0.35,0.60]
neth = [0,0]
outh = [0,0]
neto =[0,0]
outo = [0,0]
delta = [0,0]
whk = [0,0]
import math
learning_rate = 0.5
def forward():
  for i in range(0,2):
    netval = 0
    k = 0
    for j in weights[i]:
      netval += j*inputs[k]
      k+=1
    netval += biases[0]
    neth[i] = netval
    netval = 1/(1+math.exp(-netval))
    outh[i] = netval
  global ak
  ak =i
  i+=1
  m = 0
  while(i < ak+1+len(outh)):
    netval = 0
k = 0
    for j in weights[i]:
      netval +=j*outh[k]
      k+=1
    netval += biases[1]
    neto[m] = netval
    netval = 1/(1+math.exp(-netval))
    outo[m] = netval
    m+=1
    i+=1
  i= 0

def get_error():
  sum = 0
  for i in range(len(outo)):
    dif = targets[i] - outo[i]
    sum +=dif**2
  return sum/2

def outputlayer():
  for i in range(0,len(outo)):
    delt = -(targets[i] - outo[i])*(outo[i])*(1-outo[i])
    delta[i] = (delt)

  i = ak
  k = 0
  for i in range(ak+1,ak+1+len(outo)):
    for j in range(len(outo)):
      newval = weights[i][j] - learning_rate *(delta[k] * outh[k])
      weights[i][j] = newval
    k+=1


def hiddenlayers():
  for i in range(0,len(outh)):
    net = outh[i]*(1-outh[i])
    val = net

  for j in range(0,len(outh)):
    val = val * inputs[i] * whk[i]
    newval = weights[i][j] - learning_rate*val
    weights[i][j] = newval

print('Initially weights : ',weights)

for i in range(0,5):
  print('Epoch ',i+1)

forward()
outputlayer()
hiddenlayers()
print('Error :',get_error())
print('Weights: ',weights)


LOCALLY WEIGHTED
import csv,math,operator
A=[]
with open('tips (1).csv',newline='') as csvfile:
  next(csvfile)
  for row in csv.reader(csvfile):
    A.append(row)
import numpy as np
import pandas as pd
import matplotlib.pyplot as plt
def kernel(point, xmat, k):
  m,n = np.shape(xmat)
  weights = np.mat(np.eye((m)))
  for j in range(m):
    diff = point - X[j]
    weights[j, j] = np.exp(diff * diff.T / (-2.0 * k**2))
  return weights
def localWeight(point, xmat, ymat, k):
  wt = kernel(point, xmat, k)
  W = (X.T * (wt*X)).I * (X.T * wt * ymat.T)
  return W
def localWeightedRegression(xmat, ymat, k):
  m,n = np.shape(xmat)
  ypred = np.zeros(m)
  for i in range(m):
    ypred[i] = xmat[i] * localWeight(xmat[i], xmat, ymat, k)
  return ypred
df = pd.read_csv('tips (1).csv')
colA = np.array(df.total_bill)
colB = np.array(df.tip)
mcolA = np.mat(colA)
mcolB = np.mat(colB)
m = np.shape(mcolB)[1]
one = np.ones((1, m), dtype = int)
X = np.hstack((one.T, mcolA.T))
print(X.shape)
ypred = localWeightedRegression(X, mcolB, 0.8)
xsort = X.copy()
xsort.sort(axis = 0)
plt.scatter(colA, colB, color = 'blue')
plt.plot(xsort[:,1], ypred[X[:,1].argsort(0)], color = 'yellow', linewidth=5)
plt.xlabel('Total Bill')
plt.ylabel('Tip')
plt.show()