Base Conversions
- Decimal to Binary
# convert decimal numbers to binary numbers
def decimal_to_binary(decimal_number):
binary_number = ''
while decimal_number > 0:
binary_number = str(decimal_number % 2) + binary_number
decimal_number = decimal_number // 2
return binary_number
# Alternative method - built-in function
bin(decimal_number)
- Decimal to Octal
# convert decimal numbers to octal numbers
def decimal_to_octal(decimal_number):
octal_number = ''
while decimal_number > 0:
octal_number = str(decimal_number % 8) + octal_number
octal_number = decimal_number // 8
return octal_number
# Alternative method - built-in function
oct(decimal_number)
- Decimal to Hexadecimal
# convert decimal numbers to hexadecimal numbers
def decimal_to_hexadecimal(decimal_number):
hexadecimal_number = ''
hexadecimal_number_list = ['0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'A', 'B', 'C', 'D', 'E', 'F']
while decimal_number > 0:
hexadecimal_number = hexadecimal_number_list[decimal_number % 16] + hexadecimal_number
decimal_number = decimal_number // 16
return hexadecimal_number
# Alternative method - built-in function
hex(decimal_number)
- Binary to Decimal
# convert binary numbers to decimal numbers
def binary_to_decimal(binary_number):
decimal_number = 0
power = 0
for i in range(len(binary_number) - 1, -1, -1):
decimal_number += int(binary_number[i]) * (2 ** power)
power += 1
return decimal_number
# Alternative method - built-in function
int(binary_number, 2)
- Octal to Decimal
# convert octal numbers to decimal numbers
def octal_to_decimal(octal_number):
decimal_number = 0
power = 0
for i in range(len(octal_number) - 1, -1, -1):
decimal_number += int(octal_number[i]) * (8 ** power)
power += 1
return decimal_number
# Alternative method - built-in function
int(octal_number, 8)
- Hexadecimal to Decimal
# convert hexadecimal numbers to decimal numbers
def hexadecimal_to_decimal(hexadecimal_number):
decimal_number = 0
hexadecimal_number_list = ['0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'A', 'B', 'C', 'D', 'E', 'F']
power = 0
for i in range(len(hexadecimal_number) - 1, -1, -1):
decimal_number += hexadecimal_number_list.index(hexadecimal_number[i]) * (16 ** power)
power += 1
return decimal_number
# Alternative method - built-in function
int(hexadecimal_number, 16)
Data Structures
- Binary tree
class Node:
def __init__(self, data):
self.data = data
self.left: Node | None = None
self.right: Node | None = None
def __str__(self):
value = str(self.value) + " "
left = str(self.left or "")
right = str(self.right or "")
return value + left + right
def insert(self, data):
if self.data:
if data < self.data:
if self.left is None:
self.left = Node(data)
else:
self.left.insert(data)
elif data > self.data:
if self.right is None:
self.right = Node(data)
else:
self.right.insert(data)
else:
self.data = data
def inorder_traversal(self, root):
res = []
if root:
res = self.inorderTraversal(root.left)
res.append(root.data)
res = res + self.inorderTraversal(root.right)
return res
- Linked list
class Node:
def __init__(self, data):
self.data = data
self.next = None
def __repr__(self):
return self.data
class LinkedList:
def __init__(self, nodes=None):
self.head = None
if nodes is not None:
node = Node(data=nodes.pop(0))
self.head = node
for elem in nodes:
node.next = Node(data=elem)
node = node.next
def __repr__(self):
node = self.head
nodes = []
while node is not None:
nodes.append(node.data)
node = node.next
nodes.append("None")
return " -> ".join(nodes)
def __iter__(self):
node = self.head
while node is not None:
yield node
node = node.next
def add_first(self, node):
node.next = self.head
self.head = node
def add_last(self, node):
if self.head is None:
self.head = node
return
for current_node in self:
pass
current_node.next = node
def remove_node(self, target_node_data):
if self.head is None:
raise Exception("List is empty")
if self.head.data == target_node_data:
self.head = self.head.next
return
previous_node = self.head
for node in self:
if node.data == target_node_data:
previous_node.next = node.next
return
previous_node = node
raise Exception(f"Node with data '{target_node_data}' not found")
- Queue
class Queue:
def __init__(self):
self.items = []
def __repr__(self):
return str(self.items)
def __getitem__(self, key):
return self.items[key]
def __len__(self):
return len(self.items)
def __eq__(self, other):
return self.items == other
def __contains__(self, item):
"""Checks if an item is in the queue"""
return item in self.items
def is_empty(self):
"""Checks if a Queue is empty"""
return self.items == []
def enqueue(self, item):
"""Adds an element at the end of the Queue"""
self.items.append(item)
def dequeue(self):
"""Removes the element at the beginning of the queue"""
self.items = self.items[1:]
return self.items
def peek(self):
"""Returns the element at the beginning of the queue"""
return self.items[-1]
def reverse(self):
"""Reverses the order of the elements in the queue"""
self.items.reverse()
return self.items
- Stack
class Stack:
def __init__(self, size):
self.size = size
self.stack = []
def __str__(self):
return str(self.stack)
def __repr__(self):
return str(self.stack)
def __getitems__(self, key):
return self.stack[key]
def __len__(self):
return len(self.stack)
def __eq__(self, other):
return self.stack == other
def __contains__(self, item):
return item in self.stack
def push(self, item):
"""Adds an item to the top of the stack"""
if len(self.stack) == self.size:
raise IndexError("Stack is full")
else:
self.stack.append(item)
def pop(self):
"""Removes and returns the top item of the stack"""
if len(self.stack) == 0:
raise IndexError("Stack is empty")
else:
return self.stack.pop()
def peek(self):
"""Returns the top item of the stack without removing it"""
if len(self.stack) == 0:
raise IndexError("Stack is empty")
else:
return self.stack[-1]
def is_empty(self):
"""Returns True if the stack is empty, False otherwise"""
return len(self.stack) == 0
def is_full(self):
"""Returns True if the stack is full, False otherwise"""
return len(self.stack) == self.size
def clear(self):
"""Removes all items from the stack"""
self.stack = []
Math
- Calculating the value of e
# Brother's formula of calculating e
def e_value():
"""Calculates the value of e"""
e0, e, n, fact = 0, 2, 0, 1
while e != e0:
e0 = e
n += 1
fact *= 2 * n * (2 * n + 1)
e += (2 * n + 2) / fact
return e
#print("Computed e = ", e_value())
#from math import e
#print("Math library e = ", e)
- Calculating the value of pi
from math import sin
# Newtons method of calculating pi
def pi_value():
"""Calculates the value of pi"""
pi = 3
while True:
pi += sin(pi) # The value of this variable 'tends' to pi
if sin(pi) < 10 ** -15: # reduce limit for accuracy
break
return pi
#print("Computed pi = ", pi_value())
#from math import pi
#print("Math library pi = ", pi)
- Calculating the value of sin(x)
from math import factorial
# Taylor series of sin(x)
def sin_value(x):
"""Calculates the value of sine of a given number."""
s = 0
for k in range(10): # 10 is arbitrary. increase to get more accuracy
s += ((-1) ** k) * (x ** (1 + 2 * k)) / factorial(2 * k + 1)
return round(s, 8) # 8 is arbitrary. increase to get more accuracy
#sin_value(0)
#from math import sin
#sin(0)
- Calculating the value of cos(x)
from math import factorial
def cos_value(x):
"""Calculates the value of cosine of a given number."""
cosine = 0
for i in range(0, 10):
cosine += (-1) ** i * (x ** (2 * i)) / factorial(2 * i)
return round(cosine, 8)
#cos_value(0)
#from math import cos
#cos(0)
- Euclid's Division Lemma
def euclid_division_lemma(a, b):
if b > a:
a, b = b, a
r = a % b
if r == 0:
return b
else:
return euclid_division_lemma(b, r)
- Explicit Euler method for EDO
import numpy as np
def euler_ode(a, b, u0, n_step, f):
"""
solve the ODE given by :
u'(x) = f(x, u(x)) with a <= x <= b
u(a) = u0
Parameters
==========
a [float] : starting x value.
b [float] : ending x value.
u0 [float] : initial condition.
n_step : number of step used to compute the result.
f [function of 2 parameters] : function describing the ODE as given above.
u [function of 1 parameter]
Returns
=======
np.ndarray : an array of size n_step describing the solution of the ODE in the range [a, b].
Example
=======
If we have the simple equation : u'(x) = - u(x) with u(a) = u0,
and we want to know the value of u in the range [a,b]
We just have to call : euler_edo(a, b, u0, (b-a)*10, lambda x, u : -u)
"""
x, step = np.linspace(a, b, n_step + 1, retstep = True)
u = np.zeros(len(x))
u[0] = u0
for i in range(len(x) - 1):
u[i+1] = u[i] + step*f(x, u[i])
return u
- Factorial
def factorial(n):
fact = 1
for i in range(2, n + 1):
fact = fact * i
return fact
#factorial(n)
#import math
#math.factorial(n)
- Fibonacci
def fibonacci(n):
"""returns n terms from the series of Fibonacci numbers"""
a, b = 0, 1
arr = []
for i in range(n):
arr.append(a)
a, b = b, a + b
return arr
- Greatest Common Divisor / Highest Common Factor
def gcd(a, b):
"""returns the Greatest Common Divisor (GCD) of 2 numbers."""
while b:
a, b = b, a % b
return a
#gcd(a, b)
#import math
#math.gcd(a, b)
- Least Common Multiple
def lcm(a, b):
"""Returns the Lowest Common Multiple (LCM) of 2 numbers."""
return (a * b // gcd(a, b))
- Pascal's Triangle
# returns nth row of Pascal's triangle
def pascals_triangle(n):
if n == 0:
return [1]
elif n == 1:
return [1, 1]
else:
prev = pascals_triangle(n - 1)
return [1] + [prev[i] + prev[i + 1] for i in range(len(prev) - 1)] + [1]
One Liners
- Converting Decimal code (R, G, B) to hex code
rgb_to_hex = lambda rgb: '%02x%02x%02x' % rgb
- Converting Hex code to Decimal code (R, G, B)
hex_to_rgb = lambda h: tuple(int(h[i: i+2], 16) for i in (0, 2, 4))
- Current date (DD-MM-YY) and time
import datetime from datetime
now = lambda: datetime.now().strftime('%d-%m-%y %H:%M:%S')
- Fibonacci
fibonacci = lambda x: x if x<=1 else fibonacci(x-1) + fibonacci(x-2)
# >>> fibonacci(10)
# 55
- Find if string is a palindrome
is_palindrome = lambda s: s == s[::-1]
# >>> is_palindrome("abdba")
# True
- Flatten a list
See here for better solution
[i for sublist in lst for i in sublist]
#works only if all elements are iterables
# works with [[1], [2, 3], [4, 5, 6]]
# but not [1, [2, 3], [4, 5, 6]]
- Input space seperated integers
list(map(int, input().split()))
- Sum of all the numbers in a list
from functools import reduce
list_sum = lambda arr: reduce(lambda x, y: x + y, arr)
# >>> list_sum([2, 38, 267, 82])
# 389
- Read a file, line by line
print([line.strip() for line in open("readFile.py")])
- Reverse a string/list
reverse = lambda s: s[::-1]
#reverse("Hello, world!")
Primes
- Fermat's prime
# A prime number of the form (2^2^n) + 1 for some non-negative integer n.
# The first few fermat numbers are 3, 5, 17, 257, 65537, 4294967297, 18446744073709551617
def factors(x):
factors = []
i = 2
s = int(x ** 0.5)
while i < s:
if x % i == 0:
factors.append(i)
x = int(x / i)
s = int(x ** 0.5)
i += 1
factors.append(x)
return factors
print("First 10 Fermat numbers:")
for i in range(10):
fermat = 2 ** 2 ** i + 1
print(f"F{chr(i + 0x2080)} = {fermat}")
print("\nFactors of first few Fermat numbers:")
for i in range(10):
fermat = 2 ** 2 ** i + 1
fac = factors(fermat)
if len(fac) == 1:
print(f"F{chr(i + 0x2080)} -> IS PRIME")
else:
print(f"F{chr(i + 0x2080)} -> FACTORS: {fac}")
- Mersene Primes
def is_prime(num: int):
i = 2
while i ** 2 <= num:
if num % i == 0:
return False
i += 1
return True
def mersenne_prime(num):
"""Returns mersenne prime number less than or equal to the given number.
mersenne primes are prime numbers of the form 2^n - 1.
>>> mersene_prime(10)
[3, 7]
>>> mersene_prime(100)
[3, 7, 31]
"""
arr = []
power = 1
value = 2 ** power - 1
while value < num:
if is_prime(value):
arr.append(value)
power += 1
value = 2 ** power - 1
return arr
- Palindrome Primes
def is_palindrome(num):
num = str(num)
return num == num[::-1]
def palindrome_prime(num):
"""Returns the prime numbers less than or equal to the given number which are palindromes.
Plaindromes are numbers/strings that are the same when read from left to right and right to left.
>>> palindrome_prime(10)
[2, 3, 5, 7]
>>> palindrome_prime(20)
[2, 3, 5, 7, 11]
"""
prime = [True] * (num + 1)
p = 2
while (p ** 2 <= num):
if prime[p]:
for i in range(p * 2, num + 1, p):
prime[i] = False
p += 1
arr = []
for p in range(2, num + 1):
if (prime[p] and is_palindrome(p)):
arr.append(p)
return arr
- Sieve of Eratosthenes
def sieve_of_eratosthenese(num):
"""Returns a list of prime numbers less than or equal to the given number."""
sieve = [i for i in range(2, num + 1)]
key = 0
while key < len(sieve):
prime = sieve[key]
for i in range(prime * prime, num + 1, prime):
if i in sieve:
sieve.remove(i)
key += 1
return sieve
# The following code is faster than the above array version using only odd composite operations
# (for a factor of over two) and because it has been optimized to use slice operations for
# composite number culling to avoid extra work by the interpreter:
def primes2(limit):
if limit < 2:
return []
if limit < 3:
return [2]
lmtbf = (limit - 3) // 2
buf = [True] * (lmtbf + 1)
for i in range((int(limit ** 0.5) - 3) // 2 + 1):
if buf[i]:
p = i + i + 3
s = p * (i + 1) + i
buf[s::p] = [False] * ((lmtbf - s) // p + 1)
return [2] + [2 * i + 3 for i, v in enumerate(buf) if v] # return only odd numbers
# This uses a 235 factorial wheel for further reductions in operations
# the same techniques can be applied to the array version as well
# it runs slightly faster and uses slightly less memory as compared to the odds-only algorithms:
def primes235(limit):
yield 2
yield 3
yield 5
if limit < 7:
return
modPrms = [7,11,13,17,19,23,29,31]
gaps = [4,2,4,2,4,6,2,6,4,2,4,2,4,6,2,6] # 2 loops for overflow
ndxs = [0,0,0,0,1,1,2,2,2,2,3,3,4,4,4,4,5,5,5,5,5,5,6,6,7,7,7,7,7,7] # 2 loops for overflow
lmtbf = (limit + 23) // 30 * 8 - 1 # integral number of wheels rounded up
lmtsqrt = (int(limit ** 0.5) - 7)
lmtsqrt = lmtsqrt // 30 * 8 + ndxs[lmtsqrt % 30] # round down on the wheel
buf = [True] * (lmtbf + 1)
for i in range(lmtsqrt + 1):
if buf[i]:
ci = i & 7
p = 30 * (i >> 3) + modPrms[ci]
s = p * p - 7
p8 = p << 3
for _ in range(8):
c = s // 30 * 8 + ndxs[s % 30]
buf[c::p8] = [False] * ((lmtbf - c) // p8 + 1)
s += p * gaps[ci]
ci += 1
for i in range(lmtbf - 6 + (ndxs[(limit - 7) % 30])): # adjust for extras
if buf[i]: yield (30 * (i >> 3) + modPrms[i & 7])
- Sophie Germain Primes
def sophie_germain_prime(num):
"""Returns all Sophie Germain Prime numbers less than or equal to the given number.
A prime number p is called Sophie Germain Prime number if (2*p + 1) is also prime.
>>> sophie_germain_prime(25)
[2, 3, 5, 11, 23]
>>> sophie_germain_prime(50)
[2, 3, 5, 11, 23, 29, 41]
"""
prime = sieve_of_eratosthenese(2 * num + 1)
arr = []
for i in range(2, n + 1) :
if i in prime and (2 * i + 1) in prime:
arr.append(i)
return arr
Regex
- Address Validation
import regex as re
# regex for address validation
def address_validation(address):
regex = r'^[a-zA-Z0-9\s,.-]{2,}$'
return bool(re.search(regex, address))
- Credit Card Validation
See here for better solution
import regex as re
# regex for credit card validation - American Express
def credit_card_validation_american_express(credit_card):
regex = r'^3[47][0-9]{13}$'
return bool(re.fullmatch(regex, credit_card))
# regex for credit card validation - BCGlobal
def credit_card_validation_BCGlobal(credit_card):
regex = r'^(6541|6556)[0-9]{12}$'
return bool(re.fullmatch(regex, credit_card))
# regex for credit card validation - Carte Blanche
def credit_card_validation_carte_blanche(credit_card):
regex = r'^389[0-9]{11}$'
return bool(re.fullmatch(regex, credit_card))
# regex for credit card validation - Dankort
def credit_card_validation_dankort(credit_card):
regex = r'^(5019|4175|4571|4)\d{12}|^(5019|4175|4571|4)\d{14}|^(5019|4175|4571|4)\d{16}|^(5019|4175|4571|4)\d{18}$'
return bool(re.fullmatch(regex, credit_card))
# regex for credit card validation - Diners Club
def credit_card_validation_diners_club(credit_card):
regex = r'^3(?:0[0-5]|[68][0-9])[0-9]{11}$'
return bool(re.fullmatch(regex, credit_card))
# regex for credit card validation - Discover
def credit_card_validation_discover(credit_card):
regex = r'^65[4-9][0-9]{13}|64[4-9][0-9]{13}|6011[0-9]{12}|(622(?:12[6-9]|1[3-9][0-9]|[2-8][0-9][0-9]|9[01][0-9]|92[0-5])[0-9]{10})$'
return bool(re.fullmatch(regex, credit_card))
# regex for credit card validation - Insta Payment
def credit_card_validation_insta_payment(credit_card):
regex = r'^63[7-9][0-9]{13}$'
return bool(re.fullmatch(regex, credit_card))
# regex for credit card validation - JCB
def credit_card_validation_JCB(credit_card):
regex = r'^(?:2131|1800|35\d{3})\d{11}$'
return bool(re.fullmatch(regex, credit_card))
# regex for credit card validation - Korean Local
def credit_card_validation_korean_local(credit_card):
regex = r'^9[0-9]{15}$'
return bool(re.fullmatch(regex, credit_card))
# regex for credit card validation - Laser
def credit_card_validation_laser(credit_card):
regex = r'^(6304|6706|6709|6771)[0-9]{12,15}$'
return bool(re.fullmatch(regex, credit_card))
# regex for credit card validation - Maestro
def credit_card_validation_maestro(credit_card):
regex = r'^(5018|5020|5038|6304|6759|6761|6763)[0-9]{8,15}$'
return bool(re.fullmatch(regex, credit_card))
# regex for credit card validation - Mastercard
def credit_card_validation_mastercard(credit_card):
regex = r'^5[1-5][0-9]{14}$'
return bool(re.fullmatch(regex, credit_card))
# regex for credit card validation - Solo
def credit_card_validation_solo(credit_card):
regex = r'^(6334|6767)[0-9]{12}|(6334|6767)[0-9]{14}|(6334|6767)[0-9]{15}$'
return bool(re.fullmatch(regex, credit_card))
# regex for credit card validation - UnionPay
def credit_card_validation_unionPay(credit_card):
regex = r'^(62[0-9]{14,17})$'
return bool(re.fullmatch(regex, credit_card))
# regex for credit card validation - Visa
def credit_card_validation_visa(credit_card):
regex = r'^(?:4[0-9]{12}(?:[0-9]{3})?$'
return bool(re.fullmatch(regex, credit_card))
# regex for credit card validation - Visa Mastercard
def credit_card_validation_visa_mastercard(credit_card):
regex = r'^(?:4[0-9]{12}(?:[0-9]{3})?|5[1-5][0-9]{14})$'
return bool(re.fullmatch(regex, credit_card))
# driver function for credit card validation
def credit_card_validation(credit_card):
credit_card_validation_dict = {
'american_express': credit_card_validation_american_express,
'BCGlobal': credit_card_validation_BCGlobal,
'carte_blanche': credit_card_validation_carte_blanche,
'dankort': credit_card_validation_dankort,
'diners_club': credit_card_validation_diners_club,
'discover': credit_card_validation_discover,
'insta_payment': credit_card_validation_insta_payment,
'JCB': credit_card_validation_JCB,
'korean_local': credit_card_validation_korean_local,
'laser': credit_card_validation_laser,
'maestro': credit_card_validation_maestro,
'mastercard': credit_card_validation_mastercard,
'solo': credit_card_validation_solo,
'unionPay': credit_card_validation_unionPay,
'visa': credit_card_validation_visa,
'visa_mastercard': credit_card_validation_visa_mastercard
}
for key, value in credit_card_validation_dict.items():
if value(credit_card):
return key
else:
return 'Unknown'
- Date Validation
import regex as re
# regex for date validation (DD/MM/YYYY)
def date_validation(date):
regex = r'^(1[0-2]|0[1-9])/(3[01]|[12][0-9]|0[1-9])/[0-9]{4}$'
return bool(re.fullmatch(regex, date))
- Email Validation
import regex as re
# regex for email validation
def email_validation(email):
regex = r"^[a-zA-Z0-9_.+-]+@[a-zA-Z0-9-]+\.[a-zA-Z0-9-.]+$"
return bool(re.fullmatch(regex, email))
- Password Validation
import regex as re
# regex for password validation
def password_validation(password):
regex = r'^(?=.*[a-z])(?=.*[A-Z])(?=.*\d)(?=.*[@$!%*?&])[A-Za-z\d@$!%*?&]{8,}$'
return bool(re.fullmatch(regex, password))
- Phone Number Validation
import regex as re
# regex for phone number validation
def phone_validation(phone):
regex = r'^[0-9]{10}$'
return bool(re.fullmatch(regex, phone))
- Time Validation
import regex as re
# regex for time validation HH:MM:SS
def time_validation(time):
regex = r'^([0-1]?[0-9]|2[0-3]):[0-5][0-9]:[0-5][0-9]$'
return bool(re.fullmatch(regex, time))
- URL Validation
import regex as re
# regex for url validation
def URL_validation(url):
regex = r'^(?:http(s)?:\/\/)?[\w.-]+(?:\.[\w\.-]+)+[\w\-\._~:/?#[\]@!\$&\'\(\)\*\+,;=.]+$'
return bool(re.fullmatch(regex, url))
- IP Address Validation
import regex as re
# regex for IP address validation IPv4
def IP_validation(IP):
regex = r'(\b25[0-5]|\b2[0-4][0-9]|\b[01]?[0-9][0-9]?)(\.(25[0-5]|2[0-4][0-9]|[01]?[0-9][0-9]?)){3}'
return bool(re.fullmatch(regex, IP))
Searching Techniques
- Binary search
# Binary Search - time complexity: O(log(n))
# NOTE: This works only for sorted arrays
# Iterative method
def binary_search(l, value):
LOW = 0
TOP = len(l)-1
while LOW <= TOP:
MID = (LOW + TOP) // 2
if l[MID] > value:
TOP = MID-1
elif l[MID] < value:
LOW = MID+1
else:
return MID
return -1
# Recursive method
def binary_search(l, value, LOW = 0, TOP = -1):
if not l:
return -1
if TOP == -1:
TOP = len(l)-1
if LOW >= TOP:
if l[LOW] == value:
return LOW
else:
return -1
MID = (LOW + TOP) // 2
if l[MID] > value:
return binary_search(l, value, LOW, MID-1)
elif l[MID] < value:
return binary_search(l, value, MID+1, TOP)
else:
return MID
- Jump search
# Jump Search - time complexity: O(n^1/2)
def jump_search(arr, element):
n = len(arr)
step = int(math.floor(math.sqrt(n)))
prev = 0
while arr[min(step, n) - 1] < element:
prev = step
step += int(math.floor(math.sqrt(n)))
if prev >= n:
return -1
while arr[prev] < element:
prev = prev + 1
if prev == min(step, n):
return -1
if arr[prev] == element:
return prev
return -1
- Linear search
# Linear Search - time complexity: O(n)
def linear_search(arr, element):
for i in range(len(arr)):
if arr[i] == element:
return i
return -1
Sorting Techniques
- Bead sort
def bead_sort(arr):
if any(not isinstance(x, int) or x < 0 for x in arr):
raise TypeError("Sequence must be list of non-negative integers")
for _ in range(len(arr)):
for i, (rod_upper, rod_lower) in enumerate(zip(arr, arr[1:])):
if rod_upper > rod_lower:
arr[i] -= rod_upper - rod_lower
arr[i + 1] += rod_upper - rod_lower
return arr
- Bubble sort
def bubble_sort(arr):
for iter_num in range(len(arr) - 1, 0, -1):
for i in range(iter_num):
if arr[i] > arr[i + 1]:
arr[i], arr[i + 1] = arr[i + 1], arr[i]
return arr
- Cocktail sort
def cocktailSort(A):
up = range(len(A)-1)
while True:
for indices in (up, reversed(up)):
swapped = False
for i in indices:
if A[i] > A[i+1]:
A[i], A[i+1] = A[i+1], A[i]
swapped = True
if not swapped:
return
- Counting sort
def counting_sort(arr):
maxEl = max(arr)
countArrayLength = maxEl+1
countArray = [0] * countArrayLength
for el in arr:
countArray[el] += 1
for i in range(1, countArrayLength):
countArray[i] += countArray[i-1]
outputArray = [0] * len(arr)
i = len(arr) - 1
while i >= 0:
currentEl = arr[i]
countArray[currentEl] -= 1
newPosition = countArray[currentEl]
outputArray[newPosition] = currentEl
i -= 1
return outputArray
- Heap sort
def siftdown(arr, start, end):
root = start
while True:
child = root * 2 + 1
if child > end:
break
if child + 1 <= end and arr[child] < arr[child + 1]:
child += 1
if arr[root] < arr[child]:
arr[root], arr[child] = arr[child], arr[root]
root = child
else:
break
def heapsort(arr):
# in pseudo-code, heapify only called once, so inline it here
for start in range((len(arr)-2)/2, -1, -1):
siftdown(arr, start, len(arr)-1)
for end in range(len(arr)-1, 0, -1):
arr[end], arr[0] = arr[0], arr[end]
siftdown(arr, 0, end - 1)
return arr
- Insertion sort
def insertion_sort(arr):
for i in range(1, len(arr)):
key = arr[i]
j = i - 1
while j >= 0 and key < arr[j] :
arr[j + 1] = arr[j]
j -= 1
arr[j + 1] = key
return arr
- Merge sort
def merge_sort(arr):
def merge(left, right):
def _merge():
while left and right:
yield (left if left[0] <= right[0] else right).pop(0)
yield from left
yield from right
return list(_merge())
if len(arr) <= 1:
return arr
mid = len(arr) // 2
return merge(merge_sort(arr[:mid]), merge_sort(arr[mid:]))
- Selection sort
def selection_sort(arr):
for i in range(len(arr)):
min_idx = i
for j in range(i+1, len(arr)):
if arr[min_idx] > arr[j]:
min_idx = j
arr[i], arr[min_idx] = arr[min_idx], arr[i]
return arr
- Shell sort
def shell_sort(arr):
gap = len(arr) // 2
while gap > 0:
for i in range(gap, len(arr)):
temp = arr[i]
j = i
while j >= gap and arr[j - gap] > temp:
arr[j] = arr[j - gap]
j -= gap
arr[j] = temp
gap = gap//2
return arr
- Quick sort
def quick_sort(arr):
if len(arr) < 2:
return arr
pivot = arr.pop()
greater: list[int] = []
lesser: list[int] = []
for element in arr:
(greater if element > pivot else lesser).append(element)
return quick_sort(lesser) + [pivot] + quick_sort(greater)
Statistics
- Absolute value
def abs(x):
if isinstance(x, [int, float]):
return x if x >= 0 else -x
else:
raise TypeError(f"x must be an integer or float not {type(x)}")
# abs() is also an in-built function in Python
- Arithmetic Mean
def arithmetic_mean(arr):
"""Returns the Arithmetic mean of a list of numbers"""
mu = sum(arr) / len(arr)
return mu
- Geometric Mean
def geometric_mean(arr):
"""Returns the geometric mean of a list of numbers"""
return reduce(mul, num, 1) ** (1 / len(num))
- Harmonic Mean
def harmonic_mean(arr):
"""Returns the harmonic mean of a list of numbers"""
return len(arr) / sum(1 / x for x in arr)
- Quadratic mean / Root mean square
from math import sqrt
def quadratic_mean(array):
"""calculate the root mean square of an array."""
sum = 0
length = 0
for i in range(len(array)):
sum += array[i] ** 2
length += 1
return sqrt(sum / length)
- Circular mean
def circular_mean(arr):
"""Calculate the circular mean of a list of numbers."""
total = 0
for i in arr:
total += i
total %= 360
return total / len(arr)
- Median
def median(arr):
"""Returns the median of a list of numbers"""
arr.sort()
if len(arr) % 2 == 0:
return (arr[len(arr) // 2] + arr[len(arr) // 2 - 1]) / 2
else:
return arr[len(arr) // 2]
- Mode
def mode(arr):
"""Returns the mode of a list of numbers"""
arr.sort()
mode = arr[0]
frequency = 1
count = 1
for i in range(1, len(arr)):
if arr[i] == arr[i - 1]:
count += 1
else:
count = 1
if count > frequency:
mode = arr[i]
frequency = count
return mode
- Range
def range(arr):
"""Returns the range of a list of numbers"""
arr.sort()
return arr[-1] - arr[0]
- Variance
def variance(arr):
"""Returns the variance of a list of numbers"""
mean = mean(arr)
total = 0
length = 0
for i in arr:
total += (i - mean) ** 2
length += 1
return total / length
- Standard deviation
def standard_deviation(arr, mu=None):
"""Returns the standard deviation of a list of numbers"""
if not mu:
mu = mean(arr)
return sum((x-mu) ** 2 for x in arr) ** 0.5
- Probability Distribution Function
from math import pi, e
def PDF(x, mean=0, std_dev=1):
p = 1.0 / (std_dev * ((2 * pi) ** 0.5))
p *= e ** (-0.5 * ((x - mean)/std_dev)**2)
return p
- Cummulative Distribution Function
def CDF(mean=0, std_dev=1, x_left=-5, x_right=5, width=0.0001):
CDF = 0
x = x_left + width / 2
while x < x_right:
panel = PDF(x, mean, std_dev) * width
CDF += panel
x += width
return CDF
- Second smallest
def second_smallest(numbers):
"""Find the second smallest number in a list of numbers"""
smallest = None
second_smallest = None
for number in numbers:
if smallest is None or number < smallest:
second_smallest, smallest = smallest, number
elif second_smallest is None or number < second_smallest:
second_smallest = number
return second_smallest
- Second largest
def second_largest(numbers):
"""Find the second largest number in a list of numbers."""
largest = None
second_largest = None
for number in numbers:
if largest is None or number > largest:
second_largest, largest = largest, number
elif second_largest is None or number > second_largest:
second_largest = number
return second_largest
Miscellaneous
- Caesar cipher
import string
def caesar(s, k, decode = False):
if decode:
k = 26 - k
return s.translate(
str.maketrans(string.ascii_uppercase + string.ascii_lowercase,
string.ascii_uppercase[k:] + string.ascii_uppercase[:k] +
string.ascii_lowercase[k:] + string.ascii_lowercase[:k]))
#msg = "The quick brown fox jumped over the lazy dogs"
#print(msg)
#enc = caesar(msg, 11)
#print(enc)
#print(caesar(enc, 11, decode = True))
- Flatten a list
# flatten a list
def flatten(arr):
try:
result = []
for item in arr:
result.extend(flatten(item))
except TypeError: # if nested element is not a list
result = [arr]
return result
- Luhn's Algorithm
def luhns_algorithm(credit_card_number):
"""Checks if a credit card number is valid"""
# convert the credit card number to a list of ints
credit_card_number_list = [int(x) for x in str(credit_card_number)]
# reverse the list
credit_card_number_list.reverse()
# initialize the total
total = 0
for i in range(len(credit_card_number_list)):
# every other element
if i % 2 == 0:
# double the value
credit_card_number_list[i] = credit_card_number_list[i] * 2
# add the digits if > 9
if credit_card_number_list[i] > 9:
credit_card_number_list[i] = credit_card_number_list[i] - 9
# add to the total
total = total + credit_card_number_list[i]
# if the total is a multiple of 10 the number is valid
return True if total % 10 == 0 else False
