Skip to content

Commit fd415bb

Browse files
wwjiang007wwjiang007
authored
Merge pull request #1 from TheAlgorithms/master
1
2 parents 1a434dd + 5955f98 commit fd415bb

File tree

153 files changed

+8057
-295
lines changed

Some content is hidden

Large Commits have some content hidden by default. Use the searchbox below for content that may be hidden.

153 files changed

+8057
-295
lines changed

‎.gitignore

+1
Original file line numberDiff line numberDiff line change
@@ -88,3 +88,4 @@ ENV/
8888
# Rope project settings
8989
.ropeproject
9090
.idea
91+
.DS_Store

‎.travis.yml

+24-9
Original file line numberDiff line numberDiff line change
@@ -1,11 +1,26 @@
11
language: python
2+
cache: pip
23
python:
3-
- "3.2"
4-
- "3.3"
5-
- "3.4"
6-
- "3.5"
7-
install:
8-
- if [ "$TRAVIS_PYTHON_VERSION" == "3.2" ]; then travis_retry pip install coverage==3.7.1; fi
9-
- if [ "$TRAVIS_PYTHON_VERSION" != "3.2" ]; then travis_retry pip install coverage; fi
10-
- "pip install pytest pytest-cov"
11-
script: py.test --doctest-modules --cov ./
4+
- 2.7
5+
- 3.6
6+
#- nightly
7+
#- pypy
8+
#- pypy3
9+
matrix:
10+
allow_failures:
11+
- python: nightly
12+
- python: pypy
13+
- python: pypy3
14+
install:
15+
#- pip install -r requirements.txt
16+
- pip install flake8 # pytest # add another testing frameworks later
17+
before_script:
18+
# stop the build if there are Python syntax errors or undefined names
19+
- flake8 . --count --select=E901,E999,F821,F822,F823 --show-source --statistics
20+
# exit-zero treats all errors as warnings. The GitHub editor is 127 chars wide
21+
- flake8 . --count --exit-zero --max-complexity=10 --max-line-length=127 --statistics
22+
script:
23+
- true # pytest --capture=sys # add other tests here
24+
notifications:
25+
on_success: change
26+
on_failure: change # `always` will be the setting once code changes slow down

‎ArithmeticAnalysis/Bisection.py

+33
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,33 @@
1+
import math
2+
3+
4+
def bisection(function, a, b): # finds where the function becomes 0 in [a,b] using bolzano
5+
6+
start = a
7+
end = b
8+
if function(a) == 0: # one of the a or b is a root for the function
9+
return a
10+
elif function(b) == 0:
11+
return b
12+
elif function(a) * function(b) > 0: # if none of these are root and they are both positive or negative,
13+
# then his algorithm can't find the root
14+
print("couldn't find root in [a,b]")
15+
return
16+
else:
17+
mid = (start + end) / 2
18+
while abs(start - mid) > 0.0000001: # until we achieve precise equals to 10^-7
19+
if function(mid) == 0:
20+
return mid
21+
elif function(mid) * function(start) < 0:
22+
end = mid
23+
else:
24+
start = mid
25+
mid = (start + end) / 2
26+
return mid
27+
28+
29+
def f(x):
30+
return math.pow(x, 3) - 2*x - 5
31+
32+
33+
print(bisection(f, 1, 1000))

‎ArithmeticAnalysis/Intersection.py

+16
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,16 @@
1+
import math
2+
3+
def intersection(function,x0,x1): #function is the f we want to find its root and x0 and x1 are two random starting points
4+
x_n = x0
5+
x_n1 = x1
6+
while True:
7+
x_n2 = x_n1-(function(x_n1)/((function(x_n1)-function(x_n))/(x_n1-x_n)))
8+
if abs(x_n2 - x_n1)<0.00001 :
9+
return x_n2
10+
x_n=x_n1
11+
x_n1=x_n2
12+
13+
def f(x):
14+
return math.pow(x,3)-2*x-5
15+
16+
print(intersection(f,3,3.5))

‎ArithmeticAnalysis/LUdecomposition.py

+34
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,34 @@
1+
import math
2+
import numpy
3+
4+
def LUDecompose (table): #table that contains our data
5+
#table has to be a square array so we need to check first
6+
rows,columns=numpy.shape(table)
7+
L=numpy.zeros((rows,columns))
8+
U=numpy.zeros((rows,columns))
9+
if rows!=columns:
10+
return
11+
for i in range (columns):
12+
for j in range(i-1):
13+
sum=0
14+
for k in range (j-1):
15+
sum+=L[i][k]*U[k][j]
16+
L[i][j]=(table[i][j]-sum)/U[j][j]
17+
L[i][i]=1
18+
for j in range(i-1,columns):
19+
sum1=0
20+
for k in range(i-1):
21+
sum1+=L[i][k]*U[k][j]
22+
U[i][j]=table[i][j]-sum1
23+
return L,U
24+
25+
26+
27+
28+
29+
30+
31+
matrix =numpy.array([[2,-2,1],[0,1,2],[5,3,1]])
32+
L,U = LUDecompose(matrix)
33+
print(L)
34+
print(U)

‎ArithmeticAnalysis/NeutonMethod.py

+15
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,15 @@
1+
def newton(function,function1,startingInt): #function is the f(x) and function1 is the f'(x)
2+
x_n=startingInt
3+
while True:
4+
x_n1=x_n-function(x_n)/function1(x_n)
5+
if abs(x_n-x_n1)<0.00001:
6+
return x_n1
7+
x_n=x_n1
8+
9+
def f(x):
10+
return (x**3)-2*x-5
11+
12+
def f1(x):
13+
return 3*(x**2)-2
14+
15+
print(newton(f,f1,3))

‎File_Transfer_Protocol/ftp_client_server.py

+58
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,58 @@
1+
# server
2+
3+
import socket # Import socket module
4+
5+
port = 60000 # Reserve a port for your service.
6+
s = socket.socket() # Create a socket object
7+
host = socket.gethostname() # Get local machine name
8+
s.bind((host, port)) # Bind to the port
9+
s.listen(5) # Now wait for client connection.
10+
11+
print('Server listening....')
12+
13+
while True:
14+
conn, addr = s.accept() # Establish connection with client.
15+
print('Got connection from', addr)
16+
data = conn.recv(1024)
17+
print('Server received', repr(data))
18+
19+
filename = 'mytext.txt'
20+
f = open(filename, 'rb')
21+
in_data = f.read(1024)
22+
while (in_data):
23+
conn.send(in_data)
24+
print('Sent ', repr(in_data))
25+
in_data = f.read(1024)
26+
f.close()
27+
28+
print('Done sending')
29+
conn.send('Thank you for connecting')
30+
conn.close()
31+
32+
33+
# client side server
34+
35+
import socket # Import socket module
36+
37+
s = socket.socket() # Create a socket object
38+
host = socket.gethostname() # Get local machine name
39+
port = 60000 # Reserve a port for your service.
40+
41+
s.connect((host, port))
42+
s.send("Hello server!")
43+
44+
with open('received_file', 'wb') as f:
45+
print('file opened')
46+
while True:
47+
print('receiving data...')
48+
data = s.recv(1024)
49+
print('data=%s', (data))
50+
if not data:
51+
break
52+
# write data to a file
53+
f.write(data)
54+
55+
f.close()
56+
print('Successfully get the file')
57+
s.close()
58+
print('connection closed')

‎File_Transfer_Protocol/ftp_send_receive.py

+36
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,36 @@
1+
"""
2+
File transfer protocol used to send and receive files using FTP server.
3+
Use credentials to provide access to the FTP client
4+
5+
Note: Do not use root username & password for security reasons
6+
Create a seperate user and provide access to a home directory of the user
7+
Use login id and password of the user created
8+
cwd here stands for current working directory
9+
"""
10+
11+
from ftplib import FTP
12+
ftp = FTP('xxx.xxx.x.x') # Enter the ip address or the domain name here
13+
ftp.login(user='username', passwd='password')
14+
ftp.cwd('/Enter the directory here/')
15+
16+
"""
17+
The file which will be received via the FTP server
18+
Enter the location of the file where the file is received
19+
"""
20+
21+
def ReceiveFile():
22+
FileName = 'example.txt' """ Enter the location of the file """
23+
LocalFile = open(FileName, 'wb')
24+
ftp.retrbinary('RETR ' + FileName, LocalFile.write, 1024)
25+
ftp.quit()
26+
LocalFile.close()
27+
28+
"""
29+
The file which will be sent via the FTP server
30+
The file send will be send to the current working directory
31+
"""
32+
33+
def SendFile():
34+
FileName = 'example.txt' """ Enter the name of the file """
35+
ftp.storbinary('STOR ' + FileName, open(FileName, 'rb'))
36+
ftp.quit()

‎Graphs/a_star.py

+102
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,102 @@
1+
from __future__ import print_function
2+
3+
grid = [[0, 1, 0, 0, 0, 0],
4+
[0, 1, 0, 0, 0, 0],#0 are free path whereas 1's are obstacles
5+
[0, 1, 0, 0, 0, 0],
6+
[0, 1, 0, 0, 1, 0],
7+
[0, 0, 0, 0, 1, 0]]
8+
9+
'''
10+
heuristic = [[9, 8, 7, 6, 5, 4],
11+
[8, 7, 6, 5, 4, 3],
12+
[7, 6, 5, 4, 3, 2],
13+
[6, 5, 4, 3, 2, 1],
14+
[5, 4, 3, 2, 1, 0]]'''
15+
16+
init = [0, 0]
17+
goal = [len(grid)-1, len(grid[0])-1] #all coordinates are given in format [y,x]
18+
cost = 1
19+
20+
#the cost map which pushes the path closer to the goal
21+
heuristic = [[0 for row in range(len(grid[0]))] for col in range(len(grid))]
22+
for i in range(len(grid)):
23+
for j in range(len(grid[0])):
24+
heuristic[i][j] = abs(i - goal[0]) + abs(j - goal[1])
25+
if grid[i][j] == 1:
26+
heuristic[i][j] = 99 #added extra penalty in the heuristic map
27+
28+
29+
#the actions we can take
30+
delta = [[-1, 0 ], # go up
31+
[ 0, -1], # go left
32+
[ 1, 0 ], # go down
33+
[ 0, 1 ]] # go right
34+
35+
36+
#function to search the path
37+
def search(grid,init,goal,cost,heuristic):
38+
39+
closed = [[0 for col in range(len(grid[0]))] for row in range(len(grid))]# the referrence grid
40+
closed[init[0]][init[1]] = 1
41+
action = [[0 for col in range(len(grid[0]))] for row in range(len(grid))]#the action grid
42+
43+
x = init[0]
44+
y = init[1]
45+
g = 0
46+
f = g + heuristic[init[0]][init[0]]
47+
cell = [[f, g, x, y]]
48+
49+
found = False # flag that is set when search is complete
50+
resign = False # flag set if we can't find expand
51+
52+
while not found and not resign:
53+
if len(cell) == 0:
54+
resign = True
55+
return "FAIL"
56+
else:
57+
cell.sort()#to choose the least costliest action so as to move closer to the goal
58+
cell.reverse()
59+
next = cell.pop()
60+
x = next[2]
61+
y = next[3]
62+
g = next[1]
63+
f = next[0]
64+
65+
66+
if x == goal[0] and y == goal[1]:
67+
found = True
68+
else:
69+
for i in range(len(delta)):#to try out different valid actions
70+
x2 = x + delta[i][0]
71+
y2 = y + delta[i][1]
72+
if x2 >= 0 and x2 < len(grid) and y2 >=0 and y2 < len(grid[0]):
73+
if closed[x2][y2] == 0 and grid[x2][y2] == 0:
74+
g2 = g + cost
75+
f2 = g2 + heuristic[x2][y2]
76+
cell.append([f2, g2, x2, y2])
77+
closed[x2][y2] = 1
78+
action[x2][y2] = i
79+
invpath = []
80+
x = goal[0]
81+
y = goal[1]
82+
invpath.append([x, y])#we get the reverse path from here
83+
while x != init[0] or y != init[1]:
84+
x2 = x - delta[action[x][y]][0]
85+
y2 = y - delta[action[x][y]][1]
86+
x = x2
87+
y = y2
88+
invpath.append([x, y])
89+
90+
path = []
91+
for i in range(len(invpath)):
92+
path.append(invpath[len(invpath) - 1 - i])
93+
print("ACTION MAP")
94+
for i in range(len(action)):
95+
print(action[i])
96+
97+
return path
98+
99+
a = search(grid,init,goal,cost,heuristic)
100+
for i in range(len(a)):
101+
print(a[i])
102+

0 commit comments

Comments
 (0)