Skip to content

Commit 97b4a73

Browse files
NitzKashNitzKash
committed
Merge branch 'master' of https://github.com/TheAlgorithms/Python 
2 parents fab7683 + 57be21e commit 97b4a73

File tree

8 files changed

+179
-12
lines changed

8 files changed

+179
-12
lines changed

‎data_structures/Queue/QueueOnList.py

+43
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,43 @@
1+
"""Queue represented by a python list"""
2+
class Queue():
3+
def __init__(self):
4+
self.entries = []
5+
self.length = 0
6+
7+
def __str__(self):
8+
printed = '<' + str(self.entries)[1:-1] + '>'
9+
return printed
10+
11+
"""Enqueues {@code item}
12+
@param item
13+
item to enqueue"""
14+
def put(self, item):
15+
self.entries.append(item)
16+
self.length = self.length + 1
17+
18+
19+
"""Dequeues {@code item}
20+
@requirement: |self.length| > 0
21+
@return dequeued
22+
item that was dequeued"""
23+
def get(self):
24+
self.length = self.length - 1
25+
dequeued = self.entries[0]
26+
self.entries = self.entries[1:]
27+
return dequeued
28+
29+
"""Rotates the queue {@code rotation} times
30+
@param rotation
31+
number of times to rotate queue"""
32+
def rotate(self, rotation):
33+
for i in range(rotation):
34+
self.put(self.get())
35+
36+
"""Enqueues {@code item}
37+
@return item at front of self.entries"""
38+
def front(self):
39+
return self.entries[0]
40+
41+
"""Returns the length of this.entries"""
42+
def size(self):
43+
return self.length

‎data_structures/Queue/QueueOnPseudoStack.py

+50
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,50 @@
1+
"""Queue represented by a pseudo stack (represented by a list with pop and append)"""
2+
class Queue():
3+
def __init__(self):
4+
self.stack = []
5+
self.length = 0
6+
7+
def __str__(self):
8+
printed = '<' + str(self.stack)[1:-1] + '>'
9+
return printed
10+
11+
"""Enqueues {@code item}
12+
@param item
13+
item to enqueue"""
14+
def put(self, item):
15+
self.stack.append(item)
16+
self.length = self.length + 1
17+
18+
"""Dequeues {@code item}
19+
@requirement: |self.length| > 0
20+
@return dequeued
21+
item that was dequeued"""
22+
def get(self):
23+
self.rotate(1)
24+
dequeued = self.stack[self.length-1]
25+
self.stack = self.stack[:-1]
26+
self.rotate(self.length-1)
27+
self.length = self.length -1
28+
return dequeued
29+
30+
"""Rotates the queue {@code rotation} times
31+
@param rotation
32+
number of times to rotate queue"""
33+
def rotate(self, rotation):
34+
for i in range(rotation):
35+
temp = self.stack[0]
36+
self.stack = self.stack[1:]
37+
self.put(temp)
38+
self.length = self.length - 1
39+
40+
"""Reports item at the front of self
41+
@return item at front of self.stack"""
42+
def front(self):
43+
front = self.get()
44+
self.put(front)
45+
self.rotate(self.length-1)
46+
return front
47+
48+
"""Returns the length of this.stack"""
49+
def size(self):
50+
return self.length

‎data_structures/Queue/__init__.py

Whitespace-only changes.

‎data_structures/__init__.py

Whitespace-only changes.

‎dynamic_programming/edit_distance.py

+74
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,74 @@
1+
"""
2+
Author : Turfa Auliarachman
3+
Date : October 12, 2016
4+
5+
This is a pure Python implementation of Dynamic Programming solution to the edit distance problem.
6+
7+
The problem is :
8+
Given two strings A and B. Find the minimum number of operations to string B such that A = B. The permitted operations are removal, insertion, and substitution.
9+
"""
10+
11+
class EditDistance:
12+
"""
13+
Use :
14+
solver = EditDistance()
15+
editDistanceResult = solver.solve(firstString, secondString)
16+
"""
17+
18+
def __init__(self):
19+
self.__prepare__()
20+
21+
def __prepare__(self, N = 0, M = 0):
22+
self.dp = [[-1 for y in range(0,M)] for x in range(0,N)]
23+
24+
def __solveDP(self, x, y):
25+
if (x==-1):
26+
return y+1
27+
elif (y==-1):
28+
return x+1
29+
elif (self.dp[x][y]>-1):
30+
return self.dp[x][y]
31+
else:
32+
if (self.A[x]==self.B[y]):
33+
self.dp[x][y] = self.__solveDP(x-1,y-1)
34+
else:
35+
self.dp[x][y] = 1+min(self.__solveDP(x,y-1), self.__solveDP(x-1,y), self.__solveDP(x-1,y-1))
36+
37+
return self.dp[x][y]
38+
39+
def solve(self, A, B):
40+
if isinstance(A,bytes):
41+
A = A.decode('ascii')
42+
43+
if isinstance(B,bytes):
44+
B = B.decode('ascii')
45+
46+
self.A = str(A)
47+
self.B = str(B)
48+
49+
self.__prepare__(len(A), len(B))
50+
51+
return self.__solveDP(len(A)-1, len(B)-1)
52+
53+
if __name__ == '__main__':
54+
import sys
55+
if sys.version_info.major < 3:
56+
input_function = raw_input
57+
else:
58+
input_function = input
59+
60+
solver = EditDistance()
61+
62+
print("****************** Testing Edit Distance DP Algorithm ******************")
63+
print()
64+
65+
print("Enter the first string: ", end="")
66+
S1 = input_function()
67+
68+
print("Enter the second string: ", end="")
69+
S2 = input_function()
70+
71+
print()
72+
print("The minimum Edit Distance is: %d" % (solver.solve(S1, S2)))
73+
print()
74+
print("*************** End of Testing Edit Distance DP Algorithm ***************")

‎other/anagrams.txt

Whitespace-only changes.

‎other/password_generator.py

+7-6
Original file line numberDiff line numberDiff line change
@@ -1,13 +1,14 @@
11
import string
2-
from random import *
2+
import random
33

4-
letters = string.ascii_letters
5-
digits = string.digits
6-
symbols = string.punctuation
4+
letters = [letter for letter in string.ascii_letters]
5+
digits = [digit for digit in string.digits]
6+
symbols = [symbol for symbol in string.punctuation]
77
chars = letters + digits + symbols
8+
random.shuffle(chars)
89

910
min_length = 8
1011
max_length = 16
11-
password = ''.join(choice(chars) for x in range(randint(min_length, max_length)))
12-
print('Password: %s' % password)
12+
password = ''.join(random.choice(chars) for x in range(random.randint(min_length, max_length)))
13+
print('Password: ' + password)
1314
print('[ If you are thinking of using this passsword, You better save it. ]')

‎other/word_patterns.py

+5-6
Original file line numberDiff line numberDiff line change
@@ -17,9 +17,8 @@ def main():
1717
startTime = time.time()
1818
allPatterns = {}
1919

20-
fo = open('Dictionary.txt')
21-
wordList = fo.read().split('\n')
22-
fo.close()
20+
with open('Dictionary.txt') as fo:
21+
wordList = fo.read().split('\n')
2322

2423
for word in wordList:
2524
pattern = getWordPattern(word)
@@ -29,9 +28,9 @@ def main():
2928
else:
3029
allPatterns[pattern].append(word)
3130

32-
fo = open('Word Patterns.txt', 'w')
33-
fo.write(pprint.pformat(allPatterns))
34-
fo.close()
31+
with open('Word Patterns.txt', 'w') as fo:
32+
fo.write(pprint.pformat(allPatterns))
33+
3534
totalTime = round(time.time() - startTime, 2)
3635
print('Done! [', totalTime, 'seconds ]')
3736

0 commit comments

Comments
 (0)