8000 Merge pull request #34 from gleydson/master · AllAlgorithms/python@a469aab · GitHub
[go: up one dir, main page]
Skip to content
8000

Commit a469aab

Browse files
abranheabranhe
authored
Merge pull request #34 from gleydson/master
some algorithms in python
2 parents d8de721 + 44ddbc3 commit a469aab

File tree

9 files changed

+901
-0
lines changed

9 files changed

+901
-0
lines changed

‎ciphers/caesar_cipher.py

Lines changed: 68 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,68 @@
1+
import sys
2+
def encrypt(strng, key):
3+
encrypted = ''
4+
for x in strng:
5+
indx = (ord(x) + key) % 256
6+
if indx > 126:
7+
indx = indx - 95
8+
encrypted = encrypted + chr(indx)
9+
return encrypted
10+
11+
12+
def decrypt(strng, key):
13+
decrypted = ''
14+
for x in strng:
15+
indx = (ord(x) - key) % 256
16+
if indx < 32:
17+
indx = indx + 95
18+
decrypted = decrypted + chr(indx)
19+
return decrypted
20+
21+
def brute_force(strng):
22+
key = 1
23+
decrypted = ''
24+
while key <= 94:
25+
for x in strng:
26+
indx = (ord(x) - key) % 256
27+
if indx < 32:
28+
indx = indx + 95
29+
decrypted = decrypted + chr(indx)
30+
print("Key: {}\t| Message: {}".format(key, decrypted))
31+
decrypted = ''
32+
key += 1
33+
return None
34+
35+
36+
def main():
37+
print('-' * 10 + "\n**Menu**\n" + '-' * 10)
38+
print("1.Encrpyt")
39+
print("2.Decrypt")
40+
print("3.BruteForce")
41+
print("4.Quit")
42+
while True:
43+
choice = input("What would you like to do?: ")
44+
if choice not in ['1', '2', '3', '4']:
45+
print ("Invalid choice")
46+
elif choice == '1':
47+
strng = input("Please enter the string to be ecrypted: ")
48+
while True:
49+
key = int(input("Please enter off-set between 1-94: "))
50+
if key in range(1, 95):
51+
print (encrypt(strng, key))
52+
main()
53+
elif choice == '2':
54+
strng = input("Please enter the string to be decrypted: ")
55+
while True:
56+
key = int(input("Please enter off-set between 1-94: "))
57+
if key > 0 and key <= 94:
58+
print(decrypt(strng, key))
59+
main()
60+
elif choice == '3':
61+
strng = input("Please enter the string to be decrypted: ")
62+
brute_force(strng)
63+
main()
64+
elif choice == '4':
65+
print ("Goodbye.")
66+
sys.exit()
67+
68+
main()

‎ciphers/playfair.py

Lines changed: 146 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,146 @@
1+
#!/usr/bin/env python
2+
# -*- coding: utf-8 -*-
3+
4+
import sys
5+
6+
# @Author: Gleydson Rodrigues
7+
8+
# ./playfair.py [encrypt/decrypt] key message
9+
10+
11+
alphabet = "abcdefghijlmnopqrstuvwxyz".upper()
12+
13+
def vetorize(text):
14+
listText = []
15+
for letter in text:
16+
listText.append(letter)
17+
return listText
18+
19+
def normalizeMessage(text):
20+
newText = []
21+
text = text.upper()
22+
text = text.replace(" ", "")
23+
text = text.replace(".", "")
24+
text = text.replace(",", "")
25+
pos = 0
26+
while pos < len(text) - 1:
27+
firstLetter = text[pos]
28+
secondLetter = text[pos + 1]
29+
if firstLetter == secondLetter:
30+
if firstLetter == "X":
31+
newText.append(firstLetter)
32+
newText.append("Z")
33+
pos += 1
34+
else:
35+
newText.append(firstLetter)
36+
newText.append("X")
37+
pos += 1
38+
else:
39+
newText.append(firstLetter)
40+
newText.append(secondLetter)
41+
pos += 2
42+
if pos < len(text):
43+
if text[-1] == "X":
44+
newText.append(text[pos])
45+
newText.append("Z")
46+
else:
47+
newText.append(text[pos])
48+
newText.append("X")
49+
return newText
50+
51+
def createMatrix():
52+
matrix = []
53+
for i in range(5):
54+
matrix.append([])
55+
for j in range(5):
56+
matrix[i].append("")
57+
return matrix
58+
59+
def mountGrid(matrix, key, alphabet):
60+
alphabet = vetorize(alphabet)
61+
line, column, pos = 0, 0, 0
62+
for letter in key:
63+
line = pos / 5
64+
column = pos % 5
65+
if letter in alphabet:
66+
alphabet.remove(letter)
67+
matrix[line][column] = letter
68+
pos += 1
69+
while len(alphabet) > 0:
70+
line = pos / 5
71+
column = pos % 5
72+
matrix[line][column] = alphabet.pop(0)
73+
pos += 1
74+
return matrix
75+
76+
def getIndex(letter, matrix):
77+
for i in range(5):
78+
for j in range(5):
79+
if matrix[i][j] == letter:
80+
return [i, j]
81+
82+
def encrypt(message, key):
83+
matrix = mountGrid(createMatrix(), key, alphabet)
84+
message = normalizeMessage(message)
85+
messageEncrypted = ""
86+
pos, line, column = 0, 0, 1
87+
while pos < len(message) - 1:
88+
firstLetter = message[pos]
89+
secondLetter = message[pos + 1]
90+
indexFirstLetter = getIndex(firstLetter, matrix)
91+
indexSecondLetter = getIndex(secondLetter, matrix)
92+
if indexFirstLetter[line] == indexSecondLetter[line]:
93+
messageEncrypted += matrix[indexFirstLetter[line]][(indexFirstLetter[column] + 1) % 5]
94+
messageEncrypted += matrix[indexSecondLetter[line]][(indexSecondLetter[column] + 1) % 5]
95+
elif indexFirstLetter[column] == indexSecondLetter[column]:
96+
messageEncrypted += matrix[(indexFirstLetter[line] + 1) % 5][indexFirstLetter[column]]
97+
messageEncrypted += matrix[(indexSecondLetter[line] + 1) % 5][indexSecondLetter[column]]
98+
else:
99+
messageEncrypted += matrix[indexFirstLetter[line]][indexSecondLetter[column]]
100+
messageEncrypted += matrix[indexSecondLetter[line]][indexFirstLetter[column]]
101+
pos += 2
102+
return messageEncrypted
103+
104+
def decrypt(messageEncrypted, key):
105+
matrix = mountGrid(createMatrix(), key, alphabet)
106+
messageDecrypted = ""
107+
pos, line, column = 0, 0, 1
108+
while pos < len(messageEncrypted):
109+
firstLetter = messageEncrypted[pos]
110+
secondLetter = messageEncrypted[pos + 1]
111+
indexFirstLetter = getIndex(firstLetter, matrix)
112+
indexSecondLetter = getIndex(secondLetter, matrix)
113+
if indexFirstLetter[line] == indexSecondLetter[line]:
114+
messageDecrypted += matrix[indexFirstLetter[line]][(indexFirstLetter[column] - 1) % 5]
115+
messageDecrypted += matrix[indexSecondLetter[line]][(indexSecondLetter[column] - 1) % 5]
116+
elif indexFirstLetter[column] == indexSecondLetter[column]:
117+
messageDecrypted += matrix[(indexFirstLetter[line] - 1) % 5][indexFirstLetter[column]]
118+
messageDecrypted += matrix[(indexSecondLetter[line] - 1) % 5][indexSecondLetter[column]]
119+
else:
120+
messageDecrypted += matrix[indexFirstLetter[line]][indexSecondLetter[column]]
121+
messageDecrypted += matrix[indexSecondLetter[line]][indexFirstLetter[column]]
122+
pos += 2
123+
return messageDecrypted
124+
125+
def help():
126+
print(
127+
"./playfair.py [encrypt/decrypt] key message"
128+
)
129+
130+
def main():
131+
params = sys.argv[1:]
132+
if len(params) == 0:
133+
help()
134+
elif params[0] == "encrypt":
135+
key = params[1].upper()
136+
message = params[2:]
137+
print(encrypt("".join(x for x in message).upper(), key))
138+
elif params[0] == "decrypt":
139+
key = params[1].upper()
140+
message = params[2:]
141+
print(decrypt("".join(x for x in message).upper(), key))
142+
else:
143+
help()
144+
145+
if __name__ == "__main__":
146+
main()

‎data-structures/AVL.py

Lines changed: 178 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,178 @@
1+
from __future__ import print_function
2+
3+
4+
class Node:
5+
6+
def __init__(self, label):
7+
self.label = label
8+
self._parent = None
9+
self._left = None
10+
self._right = None
11+
self.height = 0
12+
13+
@property
14+
def right(self):
15+
return self._right
16+
17+
@right.setter
18+
def right(self, node):
19+
if node is not None:
20+
node._parent = self
21+
self._right = node
22+
23+
@property
24+
def left(self):
25+
return self._left
26+
27+
@left.setter
28+
def left(self, node):
29+
if node is not None:
30+
node._parent = self
31+
self._left = node
32+
33+
@property
34+
def parent(self):
35+
return self._parent
36+
37+
@parent.setter
38+
def parent(self, node):
39+
if node is not None:
40+
self._parent = node
41+
self.height = self.parent.height + 1
42+
else:
43+
self.height = 0
44+
45+
46+
class AVL:
47+
48+
def __init__(self):
49+
self.root = None
50+
self.size = 0
51+
52+
def insert(self, value):
53+
node = Node(value)
54+
55+
if self.root is None:
56+
self.root = node
57+
self.root.height = 0
58+
self.size = 1
59+
else:
60+
# Same as Binary Tree
61+
dad_node = None
62+
curr_node = self.root
63+
64+
while True:
65+
if curr_node is not None:
66+
67+
dad_node = curr_node
68+
69+
if node.label < curr_node.label:
70+
curr_node = curr_node.left
71+
else:
72+
curr_node = curr_node.right
73+
else:
74+
node.height = dad_node.height
75+
dad_node.height += 1
76+
if node.label < dad_node.label:
77+
dad_node.left = node
78+
else:
79+
dad_node.right = node
80+
self.rebalance(node)
81+
self.size += 1
82+
break
83+
84+
def rebalance(self, node):
85+
n = node
86+
87+
while n is not None:
88+
height_right = n.height
89+
height_left = n.height
90+
91+
if n.right is not None:
92+
height_right = n.right.height
93+
94+
if n.left is not None:
95+
height_left = n.left.height
96+
97+
if abs(height_left - height_right) > 1:
98+
if height_left > height_right:
99+
left_child = n.left
100+
if left_child is not None:
101+
h_right = (left_child.right.height
102+
if (left_child.right is not None) else 0)
103+
h_left = (left_child.left.height
104+
if (left_child.left is not None) else 0)
105+
if (h_left > h_right):
106+
self.rotate_left(n)
107+
break
108+
else:
109+
self.double_rotate_right(n)
110+
break
111+
else:
112+
right_child = n.right
113+
if right_child is not None:
114+
h_right = (right_child.right.height
115+
if (right_child.right is not None) else 0)
116+
h_left = (right_child.left.height
117+
if (right_child.left is not None) else 0)
118+
if (h_left > h_right):
119+
self.double_rotate_left(n)
120+
break
121+
else:
122+
self.rotate_right(n)
123+
break
124+
n = n.parent
125+
126+
def rotate_left(self, node):
127+
aux = node.parent.label
128+
node.parent.label = node.label
129+
node.parent.right = Node(aux)
130+
node.parent.right.height = node.parent.height + 1
131+
node.parent.left = node.right
132+
133+
134+
def rotate_right(self, node):
135+
aux = node.parent.label
136+
node.parent.label = node.label
137+
node.parent.left = Node(aux)
138+
node.parent.left.height = node.parent.height + 1
139+
node.parent.right = node.right
140+
141+
def double_rotate_left(self, node):
142+
self.rotate_right(node.getRight().getRight())
143+
self.rotate_left(node)
144+
145+
def double_rotate_right(self, node):
146+
self.rotate_left(node.getLeft().getLeft())
147+
self.rotate_right(node)
148+
149+
def empty(self):
150+
if self.root is None:
151+
return True
152+
return False
153+
154+
def preShow(self, curr_node):
155+
if curr_node is not None:
156+
self.preShow(curr_node.left)
157+
print(curr_node.label, end=" ")
158+
self.preShow(curr_node.right)
159+
160+
def preorder(self, curr_node):
161+
if curr_node is not None:
162+
self.preShow(curr_node.left)
163+
self.preShow(curr_node.right)
164+
print(curr_node.label, end=" ")
165+
166+
def getRoot(self):
167+
return self.root
168+
169+
t = AVL()
170+
t.insert(1)
171+
t.insert(2)
172+
t.insert(3)
173+
# t.preShow(t.root)
174+
# print("\n")
175+
# t.insert(4)
176+
# t.insert(5)
177+
# t.preShow(t.root)
178+
# t.preorden(t.root)

0 commit comments

Comments
 (0)
0