The annual Hacktoberfest is around the corner! Register on Hacktoberfest's website and open 4 pull requests during October 2020 to receive the swags (if you're the first 70,000 participants)!

In our Python repository, there are currently several open issues:

• [ ] #2128
• [ ] #1901

What's more, you can also fix an existing bugs, improve any documentation and provide better implementations for certain algorithms! Feel free to inform the community by filling an issue and start hacking! If you're new to contributing code, please read our Contribution Guidelines for an overall understanding and ask questions on the internet - Google, StackOverflow or our Gitter.

TheAlgorithms has repositories in other programming languages, so find your language and start coding there!

What you can do to participate

1. Read our Contribution Guidelines
2. Comment below or open an issue (for big ideas you may want the community to know) on your new implementations, fixes or functionalities
3. Start hacking!
4. Open a pull request for your contribution
5. Label your pull requests with hacktoberfest
6. Wait until your pull requests get reviewed or merged! In the meantime, you can review someone else's pull requests too

Useful links

• Our Gitter channel
• The Contribution Guidelines of TheAlgorithms/Python
• Our Code of Conduct
• The Directory of TheAlgorithms/Python

Remarks

• Please observe Hacktoberfest's rules, terms and FAQ. If a pull request is marked invalid or spam it would not be counted and the person may be disqualified for the swags.
• Hacktoberfest 2020 is an event presented by DigitalOcean, Intel and DEV.

Hacktoberfest's update

PRs count if: Submitted in a repo with the hacktoberfest topic AND during the month of October AND ( The PR is merged OR The PR is labelled as hacktoberfest-accepted by a maintainer OR The PR has been approved ) https://hacktoberfest.digitalocean.com/hacktoberfest-update

The annual Hacktoberfest is underway! Register on Hacktoberfest's website and open 4 pull requests during October 2021 to plant a tree or receive the swags!

What's more, you can also fix any existing bugs, improve any documentation (open issues in TheAlgorithms/Python) and provide better implementations for certain algorithms! Feel free to inform the community by filling an issue and start hacking! If you're new to contributing code, please read our Contribution Guidelines for an overall understanding and ask questions on the internet - Google, StackOverflow or our Discord/Gitter.

TheAlgorithms has repositories for other programming languages, so find your language and start coding there!

What you can do to participate

1. Read our Contribution Guidelines
2. Comment below or open an issue (for big ideas you may want the community to know) on your new implementations, fixes or functionalities
3. Start hacking! 🐱‍💻👩🏾‍💻👩‍💻👨🏻‍💻👨🏽‍💻
4. Open a pull request for your contribution
5. Wait until your pull requests get reviewed or merged! In the meantime, you can review someone else's pull requests too

Useful links

• Our Discord and Gitter channels
• The Contribution Guidelines of TheAlgorithms/Python
• Our Code of Conduct
• The Directory of TheAlgorithms/Python

Remarks

• When in doubt, please refer to any of our Contribution Guidelines. As part of the event, we would like to invite everyone to adhere to Hacktoberfest's values and general internet etiquette.
• Please observe Hacktoberfest's rules, terms and FAQ. If a pull request is marked invalid or spam it would not be counted, and the person may be disqualified from the event.
• Hacktoberfest 2021 is an event presented by DigitalOcean, Intel, appwrite and deepsource.

We have a lot of is_prime (or similar) functions: https://github.com/TheAlgorithms/Python/search?p=4&q=is_prime, https://github.com/TheAlgorithms/Python/search?q=isPrime, data_structures/hashing/number_theory/prime_numbers, etc. Shall we use one common function for that exactly identical is_prime calculation (which takes O(sqrt(n)))?

Candidates include:

• maths/prime_check
• maths/primelib

I have added some interesting binary tree traversing methods.

Describe your change:

In data_structures/binary_tree repository I have added a new file that includes some interesting methods for traversing a binary tree.

• [x] Add an algorithm?
• [ ] Fix a bug or typo in an existing algorithm?
• [ ] Documentation change?

Checklist:

• [x] I have read CONTRIBUTING.md.
• [x] This pull request is all my own work -- I have not plagiarized.
• [x] I know that pull requests will not be merged if they fail the automated tests.
• [x] This PR only changes one algorithm file. To ease review, please open separate PRs for separate algorithms.
• [x] All new Python files are placed inside an existing directory.
• [x] All filenames are in all lowercase characters with no spaces or dashes.
• [x] All functions and variable names follow Python naming conventions.
• [x] All function parameters and return values are annotated with Python type hints.
• [x] All functions have doctests that pass the automated testing.
• [ ] All new algorithms have a URL in its comments that points to Wikipedia or other similar explanation.
• [ ] If this pull request resolves one or more open issues then the commit message contains Fixes: #{$ISSUE_NO}.

Just one left to fix...

https://github.com/TheAlgorithms/Python/blob/master/mypy.ini#L5

• [x] other/least_recently_used.py
• [x] other/lfu_cache.py #5755
• [x] other/lru_cache.py #5755

UPDATE: Our GitHub Actions now run mypy --ignore-missing-imports excluding those directories that fail that test.

• https://github.com/TheAlgorithms/Python/blob/master/mypy.ini#L5

Currently, we are not running mypy in our regular CI tests as there are a lot of errors in the entire codebase, which needs to be fixed. This won't be a one-person job, so we are asking for help from you. I cannot paste the entire message in here as there are around 600 of them, so here's just a gist of it:

$ mypy --ignore-missing-imports .
strings/word_occurrence.py:17: error: Need type annotation for 'occurrence'
strings/min_cost_string_conversion.py:36: error: No overload variant of "__setitem__" of "list" matches argument types "int", "str"
strings/min_cost_string_conversion.py:36: note: Possible overload variants:
strings/min_cost_string_conversion.py:36: note:     def __setitem__(self, int, int) -> None
strings/min_cost_string_conversion.py:36: note:     def __setitem__(self, slice, Iterable[int]) -> None
strings/min_cost_string_conversion.py:40: error: No overload variant of "__setitem__" of "list" matches argument types "int", "str"
strings/min_cost_string_conversion.py:40: note: Possible overload variants:
strings/min_cost_string_conversion.py:40: note:     def __setitem__(self, int, int) -> None
strings/min_cost_string_conversion.py:40: note:     def __setitem__(self, slice, Iterable[int]) -> None
...
backtracking/n_queens_math.py:109: error: List comprehension has incompatible type List[str]; expected List[int]
backtracking/n_queens_math.py:110: error: Argument 1 to "append" of "list" has incompatible type "List[int]"; expected "List[str]"
backtracking/n_queens_math.py:149: error: Need type annotation for 'boards' (hint: "boards: List[<type>] = ...")
backtracking/minimax.py:15: error: "list" is not subscriptable, use "typing.List" instead
backtracking/knight_tour.py:6: error: "tuple" is not subscriptable, use "typing.Tuple" instead
backtracking/knight_tour.py:6: error: "list" is not subscriptable, use "typing.List" instead
...

Guidelines to follow:

• Please make sure you read the Contributing Guidelines first.
• Please submit a fix for a maximum of 3 files at a time (1 file is also acceptable).
• As we are not running mypy in our CI tests, the user who is submitting a pull request should run it on their local machine and ensure there are no errors in their submission.
• Please ensure your pull request title contains the word mypy in it. If possible use this template for your pull request title:

[mypy] Fix type annotations for <filenames>

Which errors to fix?

Please follow the below steps to produce all the errors in this library:

• Fork this repository if you haven't already.
• Clone the forked repository on your local machine using the command:

git clone --depth 1 https://github.com/TheAlgorithms/Python.git

Then you need to install all the necessary requirements:

cd python/
python -m pip install --upgrade pip
python -m pip install -r requirements.txt
python -m pip install mypy

Then run either of the two commands:

• mypy --ignore-missing-imports . -> To produce all the error messages for the entire codebase.
• mypy --ignore-missing-imports <filepath1> <filepath2> ... -> To produce error messages for the mentioned file.

How to fix the errors?

• Make a separate branch for your fix with the command:

git checkout -b mypy-fix

• Make changes to the selected files.
• Push it to your forked copy and open a pull request with the appropriate title as mentioned above.

Focus on one directory at a time:

.
├── [x] arithmetic_analysis
├── [x] backtracking
├── [x] bit_manipulation
├── [x] blockchain
├── [x] boolean_algebra
├── [x] cellular_automata
├── [x] ciphers
├── [x] compression
├── [x] computer_vision
├── [x] conversions
├── [ ] data_structures
├── [x] digital_image_processing
├── [x] divide_and_conquer
├── [ ] dynamic_programming
├── [x] electronics
├── [x] file_transfer
├── [x] fractals
├── [x] fuzzy_logic
├── [x] genetic_algorithm
├── [x] geodesy
├── [x] graphics
├── [ ] graphs
├── [x] hashes
├── [x] knapsack
├── [x] linear_algebra
├── [x] machine_learning
├── [ ] maths
├── [ ] matrix
├── [x] networking_flow
├── [x] neural_network
├── [ ] other
├── [ ] project_euler
├── [x] quantum
├── [x] scheduling
├── [x] scripts
├── [ ] searches
├── [x] sorts
├── [ ] strings
└── [x] web_programming

Pre-requisites:

• You should be familiar with mypy: https://mypy.readthedocs.io
• You should be familiar with Python type hints: https://docs.python.org/3/library/typing.html

As described in https://github.com/TheAlgorithms/Python/pull/2463#issuecomment-698081363 Currently in beta

Adding solution_test.py file for testing all the submitted solutions for Project Euler. The file will not be picked up by Travis CI and we will have to manually call it, maybe we can call it in before_script section for Project Euler build.

The use case for imported modules:

• pathlib:
  • Path manipulation
  • Iterating over the solution files path
  • Excluding all non-solution files
• importlib.util
  • For importing the solution files directly using it's path
• logging
  • For logging errors like:
    • File doesn't contain solution() function
    • solution() function requires a positional argument
    • Incorrect answer for the problem

Currently all the logs goes into the filename described in LOG_FILENAME constant, we can change it to wherever we want it to go. The log looks like this (we can change it however we want):

ERROR: solution() missing 1 required positional argument: 'n' 
Source: Problem 1: sol7.py
...

ERROR: module 'sol3.py' has no attribute 'solution' 
Source: Problem 10: sol3.py
...

Describe your change:

• [x] Add an algorithm?

Checklist:

• [x] I have read CONTRIBUTING.md.
• [x] This pull request is all my own work -- I have not plagiarized.
• [x] I know that pull requests will not be merged if they fail the automated tests.
• [x] This PR only changes one algorithm file. To ease review, please open separate PRs for separate algorithms.
• [x] All new Python files are placed inside an existing directory.
• [x] All filenames are in all lowercase characters with no spaces or dashes.
• [x] All functions and variable names follow Python naming conventions.
• [ ] All function parameters and return values are annotated with Python type hints.
• [ ] All functions have doctests that pass the automated testing.
• [x] All new algorithms have a URL in its comments that points to Wikipedia or other similar explanation.
• [x] If this pull request resolves one or more open issues then the commit message contains Fixes: #{$ISSUE_NO}.

Project Euler has about 700 problems, but the current repository hosts solutions for only about 60-70 problems.
I'm willing to work on the issue and also if someone wants to help they can join in.
We can create guidelines on how many minimum solutions a PR should have to prevent spammy PRs with just one or two easy solutions. (open to discussion)

Describe your change:

• [ ] Add an algorithm?
• [x] Fix a bug or typo in an existing algorithm?
• [x] Documentation change?

Checklist:

• [x] I have read CONTRIBUTING.md.
• [x] This pull request is all my own work -- I have not plagiarized.
• [x] I know that pull requests will not be merged if they fail the automated tests.
• [x] This PR only changes one algorithm file. To ease review, please open separate PRs for separate algorithms.
• [x] All new Python files are placed inside an existing directory.
• [x] All filenames are in all lowercase characters with no spaces or dashes.
• [x] All functions and variable names follow Python naming conventions.
• [x] All function parameters and return values are annotated with Python type hints.
• [x] All functions have doctests that pass the automated testing.
• [x] All new algorithms have a URL in its comments that points to Wikipedia or other similar explanation.
• [x] If this pull request resolves one or more open issues then the commit message contains Fixes: #{$ISSUE_NO}.

Capitalization of the first character of a word or a sentence. It works like the capitalize() method of the strings in Python

Describe your change:

• [x] Add an algorithm?
• [ ] Fix a bug or typo in an existing algorithm?
• [ ] Documentation change?

Checklist:

• [x] I have read CONTRIBUTING.md.
• [x] This pull request is all my own work -- I have not plagiarized.
• [x] I know that pull requests will not be merged if they fail the automated tests.
• [x] This PR only changes one algorithm file. To ease review, please open separate PRs for separate algorithms.
• [x] All new Python files are placed inside an existing directory.
• [x] All filenames are in all lowercase characters with no spaces or dashes.
• [x] All functions and variable names follow Python naming conventions.
• [x] All function parameters and return values are annotated with Python type hints.
• [x] All functions have doctests that pass the automated testing.
• [x] All new algorithms have a URL in its comments that points to Wikipedia or other similar explanation.
• [x] If this pull request resolves one or more open issues then the commit message contains Fixes: #{$ISSUE_NO}.

I have a simple instruction which is good to be kept in CONTRIBUTION.md. Please add this wherever it looks good:

• clone your forked repository locally
• change directory to its root
• run pip install pre-commit
• run pre-commit run --all-files
• commit and push the changes to your fork.

My algorithm relates the application of the Fibonacci sequence (using Recursion) to the Memoization technique. Thus, it is possible to reach the complexity O (1), to calculate the Fibonacci value of very high numbers and in an incredibly shorter time interval than using only the common recursion.

• [x] Add an algorithm?
• [ ] Fix a bug or typo in an existing algorithm?
• [ ] Documentation change?

Checklist:

• [x] I have read CONTRIBUTING.md.
• [x] This pull request is all my own work -- I have not plagiarized.
• [x] I know that pull requests will not be merged if they fail the automated tests.
• [x] This PR only changes one algorithm file. To ease review, please open separate PRs for separate algorithms.
• [x] All new Python files are placed inside an existing directory.
• [x] All filenames are in all lowercase characters with no spaces or dashes.
• [x] All functions and variable names follow Python naming conventions.
• [x] All function parameters and return values are annotated with Python type hints.
• [x] All functions have doctests that pass the automated testing.
• [x] All new algorithms have a URL in its comments that points to Wikipedia or other similar explanation.
• [x] If this pull request resolves one or more open issues then the commit message contains Fixes: #{$ISSUE_NO}.

Feature description

greatest_common_divisor.py and euclidean_gcd.py both have basically the same two implementations of the Euclidean algorithm for calculating the GCD of 2 numbers. Thus, one of them should probably be removed as a duplicate.

Describe your change:

Change prime_sieve_eratosthenes.py to return a list of ints rather than print to avoid side effects Also added more doctests

• [ ] Add an algorithm?
• [x] Fix a bug or typo in an existing algorithm?
• [ ] Documentation change?

Checklist:

• [x] I have read CONTRIBUTING.md.
• [x] This pull request is all my own work -- I have not plagiarized.
• [x] I know that pull requests will not be merged if they fail the automated tests.
• [x] This PR only changes one algorithm file. To ease review, please open separate PRs for separate algorithms.
• [ ] All new Python files are placed inside an existing directory.
• [ ] All filenames are in all lowercase characters with no spaces or dashes.
• [ ] All functions and variable names follow Python naming conventions.
• [ ] All function parameters and return values are annotated with Python type hints.
• [x] All functions have doctests that pass the automated testing.
• [ ] All new algorithms include at least one URL that points to Wikipedia or another similar explanation.
• [ ] If this pull request resolves one or more open issues then the commit message contains Fixes: #{$ISSUE_NO}.

Feature description

I think one of 3n_plus_1.py and collatz_sequence.py should be removed, as they're nearly identical implementations of the same algorithm for computing Collatz sequences.

I'm not sure which of the two files should be deleted. I believe that "the Collatz conjecture" is the more well-known name for the problem, but it seems that 3n_plus_1.py is the older of the two files.

Describe your change:

Greatest common divisor for n numbers

• [x] Add an algorithm?
• [ ] Fix a bug or typo in an existing algorithm?
• [ ] Documentation change?

Checklist:

• [x] I have read CONTRIBUTING.md.
• [x] This pull request is all my own work -- I have not plagiarized.
• [x] I know that pull requests will not be merged if they fail the automated tests.
• [x] This PR only changes one algorithm file. To ease review, please open separate PRs for separate algorithms.
• [x] All new Python files are placed inside an existing directory.
• [x] All filenames are in all lowercase characters with no spaces or dashes.
• [x] All functions and variable names follow Python naming conventions.
• [x] All function parameters and return values are annotated with Python type hints.
• [x] All functions have doctests that pass the automated testing.
• [x] All new algorithms include at least one URL that points to Wikipedia or another similar explanation.
• [ ] If this pull request resolves one or more open issues then the commit message contains Fixes: #{$ISSUE_NO}.

Describe your change:

I create new RangeMinimumQuery class for RMQ problem using Spare Table algorithm.

• [x] Add an algorithm?
• [ ] Fix a bug or typo in an existing algorithm?
• [ ] Documentation change?

Checklist:

• [x] I have read CONTRIBUTING.md.
• [x] This pull request is all my own work -- I have not plagiarized.
• [x] I know that pull requests will not be merged if they fail the automated tests.
• [x] This PR only changes one algorithm file. To ease review, please open separate PRs for separate algorithms.
• [x] All new Python files are placed inside an existing directory.
• [x] All filenames are in all lowercase characters with no spaces or dashes.
• [x] All functions and variable names follow Python naming conventions.
• [x] All function parameters and return values are annotated with Python type hints.
• [x] All functions have doctests that pass the automated testing.
• [x] All new algorithms have a URL in its comments that points to Wikipedia or other similar explanation.
• [x] If this pull request resolves one or more open issues then the commit message contains Fixes: #{$ISSUE_NO}.

Describe your change:

• [ ] Add an algorithm?
• [x] Fix a bug or typo in an existing algorithm?
• [ ] Documentation change?

Checklist:

• [x] I have read CONTRIBUTING.md.
• [x] This pull request is all my own work -- I have not plagiarized.
• [x] I know that pull requests will not be merged if they fail the automated tests.
• [x] This PR only changes one algorithm file. To ease review, please open separate PRs for separate algorithms.
• [x] All new Python files are placed inside an existing directory.
• [x] All filenames are in all lowercase characters with no spaces or dashes.
• [x] All functions and variable names follow Python naming conventions.
• [x] All function parameters and return values are annotated with Python type hints.
• [x] All functions have doctests that pass the automated testing.
• [x] All new algorithms include at least one URL that points to Wikipedia or another similar explanation.
• [ ] If this pull request resolves one or more open issues then the commit message contains Fixes: #{$ISSUE_NO}.