8000 Bucket sort Algorithm in Python by beingadityak · Pull Request #24 · AllAlgorithms/python · GitHub
[go: up one dir, main page]

Skip to content

Bucket sort Algorithm in Python #24

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Merged
merged 3 commits into from
Oct 4, 2018
Merged
Show file tree
Hide file tree
Changes from all commits
Commits
File filter

Filter by extension

Filter by extension

Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
27 changes: 27 additions & 0 deletions sorting/bucket_sort.py
Original file line number Diff line number Diff line change
@@ -0,0 +1,27 @@
#!/usr/bin/env python3

__author__ = "Aditya Krishnakumar"


def bucket_sort(A):
buckets = [[] for x in range(10)]
for i, x in enumerate(A):
buckets[int(x * len(buckets))].append(x)
out = []
for buck in buckets:
out += isort(buck)
return out


def isort(A):
if len(A) <= 1: return A
i = 1
while i < len(A):
k = A[i]
j = i - 1
while j >= 0 and A[j] > k:
A[j + 1] = A[j]
A[j] = k
j -= 1
i += 1
return A
44 changes: 44 additions & 0 deletions strings/anagram_search.py
Original file line number Diff line number Diff line change
@@ -0,0 +1,44 @@
#!/usr/bin/env python3

"""
Pythonic Implementation of Anagram search
"""

__author__ = "Aditya Krishnakumar"

import collections

# remove whitespaces
def remove_whitespace(string):
return ''.join(string.split())

"""
Checks if two strings are anagrams of each other, ignoring any whitespace.

First remove any whitespace and lower all characters of both strings.
Then create dictionaries of the counts of every character in each string.
As well as keep a set of all characters used in both strings.
Check to ensure every unique character are used in both strings the
same number of times.
"""

def is_anagram(string1, string2):
charCount1 = collections.Counter(remove_whitespace(string1.lower()))
charCount2 = collections.Counter(remove_whitespace(string2.lower()))

allChars = set(charCount1.keys())
allChars = allChars.union(charCount2.keys())

for c in allChars:
if (charCount1[c] != charCount2[c]):
return False

return True

# Dry runs

assert is_anagram("anagram", "not a gram") == False
assert is_anagram("anagram", "na a marg") == True
assert is_anagram("William Shakespeare", "I am \t a weakish speller") == True
assert is_anagram("Madam Curie", "Radium came") == True
assert is_anagramg("notagram", "notaflam") == False
69 changes: 69 additions & 0 deletions strings/morse_code.py
Original file line number Diff line number Diff line change
@@ -0,0 +1,69 @@
#!/usr/bin/env python
"""
Pythonic Implementation of Morse Code encoding
"""

__author__ = "Aditya Krishnakumar"


# The alphabet dictionary for morse codes
morseAlphabet = {
"A": ".-",
"B": "-...",
"C": "-.-.",
"D": "-..",
"E": ".",
"F": "..-.",
"G": "--.",
"H": "....",
"I": "..",
"J": ".---",
"K": "-.-",
"L": ".-..",
"M": "--",
"N": "-.",
"O": "---",
"P": ".--.",
"Q": "--.-",
"R": ".-.",
"S": "...",
"T": "-",
"U": "..-",
"V": "...-",
"W": ".--",
"X": "-..-",
"Y": "-.--",
"Z": "--..",
"1": ".----",
"2": "..---",
"3": "...--",
"4": "....-",
"5": ".....",
"6": "-....",
"7": "--...",
"8": "---..",
"9": "----.",
"0": "-----"
}

# Lambda function for decoding the code to alphabet
inverseAlphabet = reduce(lambda a, b: dict(a.items() + b.items()),
[{
morseAlphabet[k]: k
} for k in morseAlphabet.keys()], {})


def encode(_text):
return ' '.join([morseAlphabet[_c.upper()] for _c in _text[:]])


def decode(_text):
return ''.join([inverseAlphabet[_c] for _c in _text.split(' ')])

# Dry runner
def test():
print decode(encode("TEST")) == "TEST"


if __name__ == "__main__":
test()
29 changes: 29 additions & 0 deletions strings/password_checker.py
Original file line number Diff line number Diff line change
@@ -0,0 +1,29 @@
#!/usr/bin/env python3

import re, pyperclip

password = pyperclip.paste()

eightLettersRegex = re.compile(r'\S{8,}')
oneUppercaseRegex = re.compile(r'[A-Z]')
oneNumberRegex = re.compile(r'\d')

check = {
eightLettersRegex: 'Your password must be 8 letters',
oneUppercaseRegex: 'Your password must have at least one uppercase Letter.',
oneNumberRegex: 'Your password must have at least one number.'
}

print('Analyzing your password.') 8000

count = 1
for regex, msg in check.items():
mo = regex.search(password)
if mo == None:
print(msg)
break
if count == len(check):
print('Good! Your password is strong enough!')
count += 1

print('End.')
46 changes: 46 additions & 0 deletions strings/rabin_karp.py
Original file line number Diff line number Diff line change
@@ -0,0 +1,46 @@
#!/usr/local/bin/env python3

# Rabin Karp Algorithm in python using hash values
# d is the number of characters in input alphabet
d = 2560


def search(pat, txt, q):
M = len(pat)
N = len(txt)
i = 0
j = 0

p = 0
t = 0
h = 1

for i in range(M - 1):
h = (h * d) % q

for i in range(M):
p = (d * p + ord(pat[i])) % q
t = (d * t + ord(txt[i])) % q

for i in range(N - M + 1):
if p == t:
for j in range(M):
if txt[i + j] != pat[j]:
break

j += 1
if j == M:
print("Pattern found at index " + str(i))

if i < N - M:
t = (d * (t - ord(txt[i]) * h) + ord(txt[i + M])) % q
if t < 0:
t = t + q


# Driver program to test the above function
txt = "ALL WORLDS IS A STAGE AND ALL OF US ARE A PART OF THE PLAY"
pat = "ALL"

q = 101 # A prime number
search(pat, txt, q)
0