Skip to content

Commit 7d9dc70

Browse files
MatthewG25MatthewG25
committed
Merge branch 'TheAlgorithms:master' into master
2 parents 65c2d50 + 368ce7a commit 7d9dc70

File tree

159 files changed

+3069
-1511
lines changed

Some content is hidden

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

159 files changed

+3069
-1511
lines changed

‎.github/workflows/build.yml

Lines changed: 2 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -20,7 +20,8 @@ jobs:
2020
- name: Install dependencies
2121
run: |
2222
python -m pip install --upgrade pip setuptools six wheel
23-
python -m pip install pytest-cov -r requirements.txt
23+
python -m pip install mypy pytest-cov -r requirements.txt
24+
- run: mypy .
2425
- name: Run tests
2526
run: pytest --doctest-modules --ignore=project_euler/ --ignore=scripts/ --cov-report=term-missing:skip-covered --cov=. .
2627
- if: ${{ success() }}

‎.github/workflows/pre-commit.yml

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -14,6 +14,7 @@ jobs:
1414
~/.cache/pip
1515
key: ${{ runner.os }}-pre-commit-${{ hashFiles('.pre-commit-config.yaml') }}
1616
- uses: actions/setup-python@v2
17+
- uses: psf/black@21.4b0
1718
- name: Install pre-commit
1819
run: |
1920
python -m pip install --upgrade pip

‎.pre-commit-config.yaml

Lines changed: 9 additions & 9 deletions
Original file line numberDiff line numberDiff line change
@@ -1,6 +1,6 @@
11
repos:
22
- repo: https://github.com/pre-commit/pre-commit-hooks
3-
rev: v3.2.0
3+
rev: v3.4.0
44
hooks:
55
- id: check-executables-have-shebangs
66
- id: check-yaml
@@ -13,17 +13,17 @@ repos:
1313
)$
1414
- id: requirements-txt-fixer
1515
- repo: https://github.com/psf/black
16-
rev: stable
16+
rev: 21.4b0
1717
hooks:
1818
- id: black
1919
- repo: https://github.com/PyCQA/isort
20-
rev: 5.5.3
20+
rev: 5.8.0
2121
hooks:
2222
- id: isort
2323
args:
2424
- --profile=black
2525
- repo: https://gitlab.com/pycqa/flake8
26-
rev: 3.8.3
26+
rev: 3.9.1
2727
hooks:
2828
- id: flake8
2929
args:
@@ -38,17 +38,17 @@ repos:
3838
# args:
3939
# - --ignore-missing-imports
4040
- repo: https://github.com/codespell-project/codespell
41-
rev: v1.17.1
41+
rev: v2.0.0
4242
hooks:
4343
- id: codespell
4444
args:
45-
- --ignore-words-list=ans,fo,followings,hist,iff,mater,secant,som,tim
46-
- --skip="./.*,./other/dictionary.txt,./other/words,./project_euler/problem_022/p022_names.txt"
45+
- --ignore-words-list=ans,crate,fo,followings,hist,iff,mater,secant,som,tim
46+
- --skip="./.*,./strings/dictionary.txt,./strings/words.txt,./project_euler/problem_022/p022_names.txt"
4747
- --quiet-level=2
4848
exclude: |
4949
(?x)^(
50-
other/dictionary.txt |
51-
other/words |
50+
strings/dictionary.txt |
51+
strings/words.txt |
5252
project_euler/problem_022/p022_names.txt
5353
)$
5454
- repo: local

‎CONTRIBUTING.md

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -155,6 +155,8 @@ We want your work to be readable by others; therefore, we encourage you to note
155155
return a + b
156156
```
157157

158+
Instructions on how to install mypy can be found [here](https://github.com/python/mypy). Please use the command `mypy --ignore-missing-imports .` to test all files or `mypy --ignore-missing-imports path/to/file.py` to test a specific file.
159+
158160
- [__List comprehensions and generators__](https://docs.python.org/3/tutorial/datastructures.html#list-comprehensions) are preferred over the use of `lambda`, `map`, `filter`, `reduce` but the important thing is to demonstrate the power of Python in code that is easy to read and maintain.
159161

160162
- Avoid importing external libraries for basic algorithms. Only use those libraries for complicated algorithms.

‎DIRECTORY.md

Lines changed: 45 additions & 24 deletions
Large diffs are not rendered by default.

‎README.md

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1,5 +1,6 @@
11
# The Algorithms - Python
22
[![Gitpod Ready-to-Code](https://img.shields.io/badge/Gitpod-Ready--to--Code-blue?logo=gitpod&style=flat-square)](https://gitpod.io/#https://github.com/TheAlgorithms/Python) 
3+
[![Discord chat](https://img.shields.io/discord/808045925556682782.svg?logo=discord&colorB=7289DA&style=flat-square)](https://discord.gg/c7MnfGFGa6) 
34
[![Gitter chat](https://img.shields.io/badge/Chat-Gitter-ff69b4.svg?label=Chat&logo=gitter&style=flat-square)](https://gitter.im/TheAlgorithms) 
45
[![GitHub Workflow Status](https://img.shields.io/github/workflow/status/TheAlgorithms/Python/build?label=CI&logo=github&style=flat-square)](https://github.com/TheAlgorithms/Python/actions) 
56
[![LGTM](https://img.shields.io/lgtm/alerts/github/TheAlgorithms/Python.svg?label=LGTM&logo=LGTM&style=flat-square)](https://lgtm.com/projects/g/TheAlgorithms/Python/alerts) 

‎arithmetic_analysis/gaussian_elimination.py

Lines changed: 3 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -7,7 +7,7 @@
77
import numpy as np
88

99

10-
def retroactive_resolution(coefficients: np.matrix, vector: np.array) -> np.array:
10+
def retroactive_resolution(coefficients: np.matrix, vector: np.ndarray) -> np.ndarray:
1111
"""
1212
This function performs a retroactive linear system resolution
1313
for triangular matrix
@@ -38,7 +38,7 @@ def retroactive_resolution(coefficients: np.matrix, vector: np.array) -> np.arra
3838
return x
3939

4040

41-
def gaussian_elimination(coefficients: np.matrix, vector: np.array) -> np.array:
41+
def gaussian_elimination(coefficients: np.matrix, vector: np.ndarray) -> np.ndarray:
4242
"""
4343
This function performs Gaussian elimination method
4444
@@ -57,7 +57,7 @@ def gaussian_elimination(coefficients: np.matrix, vector: np.array) -> np.array:
5757
# coefficients must to be a square matrix so we need to check first
5858
rows, columns = np.shape(coefficients)
5959
if rows != columns:
60-
return []
60+
return np.array((), dtype=float)
6161

6262
# augmented matrix
6363
augmented_mat = np.concatenate((coefficients, vector), axis=1)

‎arithmetic_analysis/in_static_equilibrium.py

Lines changed: 3 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -3,7 +3,7 @@
33
"""
44
from typing import List
55

6-
from numpy import array, cos, cross, radians, sin
6+
from numpy import array, cos, cross, ndarray, radians, sin
77

88

99
def polar_force(
@@ -23,7 +23,7 @@ def polar_force(
2323

2424

2525
def in_static_equilibrium(
26-
forces: array, location: array, eps: float = 10 ** -1
26+
forces: ndarray, location: ndarray, eps: float = 10 ** -1
2727
) -> bool:
2828
"""
2929
Check if a system is in equilibrium.
@@ -42,7 +42,7 @@ def in_static_equilibrium(
4242
False
4343
"""
4444
# summation of moments is zero
45-
moments: array = cross(location, forces)
45+
moments: ndarray = cross(location, forces)
4646
sum_moments: float = sum(moments)
4747
return abs(sum_moments) < eps
4848

‎bit_manipulation/binary_shifts.py

Lines changed: 109 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,109 @@
1+
# Information on binary shifts:
2+
# https://docs.python.org/3/library/stdtypes.html#bitwise-operations-on-integer-types
3+
# https://www.interviewcake.com/concept/java/bit-shift
4+
5+
6+
def logical_left_shift(number: int, shift_amount: int) -> str:
7+
"""
8+
Take in 2 positive integers.
9+
'number' is the integer to be logically left shifted 'shift_amount' times.
10+
i.e. (number << shift_amount)
11+
Return the shifted binary representation.
12+
13+
>>> logical_left_shift(0, 1)
14+
'0b00'
15+
>>> logical_left_shift(1, 1)
16+
'0b10'
17+
>>> logical_left_shift(1, 5)
18+
'0b100000'
19+
>>> logical_left_shift(17, 2)
20+
'0b1000100'
21+
>>> logical_left_shift(1983, 4)
22+
'0b111101111110000'
23+
>>> logical_left_shift(1, -1)
24+
Traceback (most recent call last):
25+
...
26+
ValueError: both inputs must be positive integers
27+
"""
28+
if number < 0 or shift_amount < 0:
29+
raise ValueError("both inputs must be positive integers")
30+
31+
binary_number = str(bin(number))
32+
binary_number += "0" * shift_amount
33+
return binary_number
34+
35+
36+
def logical_right_shift(number: int, shift_amount: int) -> str:
37+
"""
38+
Take in positive 2 integers.
39+
'number' is the integer to be logically right shifted 'shift_amount' times.
40+
i.e. (number >>> shift_amount)
41+
Return the shifted binary representation.
42+
43+
>>> logical_right_shift(0, 1)
44+
'0b0'
45+
>>> logical_right_shift(1, 1)
46+
'0b0'
47+
>>> logical_right_shift(1, 5)
48+
'0b0'
49+
>>> logical_right_shift(17, 2)
50+
'0b100'
51+
>>> logical_right_shift(1983, 4)
52+
'0b1111011'
53+
>>> logical_right_shift(1, -1)
54+
Traceback (most recent call last):
55+
...
56+
ValueError: both inputs must be positive integers
57+
"""
58+
if number < 0 or shift_amount < 0:
59+
raise ValueError("both inputs must be positive integers")
60+
61+
binary_number = str(bin(number))[2:]
62+
if shift_amount >= len(binary_number):
63+
return "0b0"
64+
shifted_binary_number = binary_number[: len(binary_number) - shift_amount]
65+
return "0b" + shifted_binary_number
66+
67+
68+
def arithmetic_right_shift(number: int, shift_amount: int) -> str:
69+
"""
70+
Take in 2 integers.
71+
'number' is the integer to be arithmetically right shifted 'shift_amount' times.
72+
i.e. (number >> shift_amount)
73+
Return the shifted binary representation.
74+
75+
>>> arithmetic_right_shift(0, 1)
76+
'0b00'
77+
>>> arithmetic_right_shift(1, 1)
78+
'0b00'
79+
>>> arithmetic_right_shift(-1, 1)
80+
'0b11'
81+
>>> arithmetic_right_shift(17, 2)
82+
'0b000100'
83+
>>> arithmetic_right_shift(-17, 2)
84+
'0b111011'
85+
>>> arithmetic_right_shift(-1983, 4)
86+
'0b111110000100'
87+
"""
88+
if number >= 0: # Get binary representation of positive number
89+
binary_number = "0" + str(bin(number)).strip("-")[2:]
90+
else: # Get binary (2's complement) representation of negative number
91+
binary_number_length = len(bin(number)[3:]) # Find 2's complement of number
92+
binary_number = bin(abs(number) - (1 << binary_number_length))[3:]
93+
binary_number = (
94+
"1" + "0" * (binary_number_length - len(binary_number)) + binary_number
95+
)
96+
97+
if shift_amount >= len(binary_number):
98+
return "0b" + binary_number[0] * len(binary_number)
99+
return (
100+
"0b"
101+
+ binary_number[0] * shift_amount
102+
+ binary_number[: len(binary_number) - shift_amount]
103+
)
104+
105+
106+
if __name__ == "__main__":
107+
import doctest
108+
109+
doctest.testmod()

‎bit_manipulation/binary_twos_complement.py

Lines changed: 43 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,43 @@
1+
# Information on 2's complement: https://en.wikipedia.org/wiki/Two%27s_complement
2+
3+
4+
def twos_complement(number: int) -> str:
5+
"""
6+
Take in a negative integer 'number'.
7+
Return the two's complement representation of 'number'.
8+
9+
>>> twos_complement(0)
10+
'0b0'
11+
>>> twos_complement(-1)
12+
'0b11'
13+
>>> twos_complement(-5)
14+
'0b1011'
15+
>>> twos_complement(-17)
16+
'0b101111'
17+
>>> twos_complement(-207)
18+
'0b100110001'
19+
>>> twos_complement(1)
20+
Traceback (most recent call last):
21+
...
22+
ValueError: input must be a negative integer
23+
"""
24+
if number > 0:
25+
raise ValueError("input must be a negative integer")
26+
binary_number_length = len(bin(number)[3:])
27+
twos_complement_number = bin(abs(number) - (1 << binary_number_length))[3:]
28+
twos_complement_number = (
29+
(
30+
"1"
31+
+ "0" * (binary_number_length - len(twos_complement_number))
32+
+ twos_complement_number
33+
)
34+
if number < 0
35+
else "0"
36+
)
37+
return "0b" + twos_complement_number
38+
39+
40+
if __name__ == "__main__":
41+
import doctest
42+
43+
doctest.testmod()

‎bit_manipulation/single_bit_manipulation_operations.py

Lines changed: 20 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -74,6 +74,26 @@ def is_bit_set(number: int, position: int) -> bool:
7474
return ((number >> position) & 1) == 1
7575

7676

77+
def get_bit(number: int, position: int) -> int:
78+
"""
79+
Get the bit at the given position
80+
81+
Details: perform bitwise and for the given number and X,
82+
Where X is a number with all the bits – zeroes and bit on given position – one.
83+
If the result is not equal to 0, then the bit on the given position is 1, else 0.
84+
85+
>>> get_bit(0b1010, 0)
86+
0
87+
>>> get_bit(0b1010, 1)
88+
1
89+
>>> get_bit(0b1010, 2)
90+
0
91+
>>> get_bit(0b1010, 3)
92+
1
93+
"""
94+
return int((number & (1 << position)) != 0)
95+
96+
7797
if __name__ == "__main__":
7898
import doctest
7999

‎other/game_of_life.py renamed to ‎cellular_automata/game_of_life.py

File renamed without changes.

‎ciphers/a1z26.py

Lines changed: 4 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -7,24 +7,24 @@
77
"""
88

99

10-
def encode(plain: str) -> list:
10+
def encode(plain: str) -> list[int]:
1111
"""
1212
>>> encode("myname")
1313
[13, 25, 14, 1, 13, 5]
1414
"""
1515
return [ord(elem) - 96 for elem in plain]
1616

1717

18-
def decode(encoded: list) -> str:
18+
def decode(encoded: list[int]) -> str:
1919
"""
2020
>>> decode([13, 25, 14, 1, 13, 5])
2121
'myname'
2222
"""
2323
return "".join(chr(elem + 96) for elem in encoded)
2424

2525

26-
def main():
27-
encoded = encode(input("->").strip().lower())
26+
def main() -> None:
27+
encoded = encode(input("-> ").strip().lower())
2828
print("Encoded: ", encoded)
2929
print("Decoded:", decode(encoded))
3030

0 commit comments

Comments
 (0)