An Overview of competitivepython: A Python Library for Implementing Algorithms and Data Structures
Introduction:
As a software developer, we often come across situations where we need to implement algorithms or data structures to solve various programming problems. Competitive programming is one such area where developers need to implement various algorithms and data structures to solve a given problem within a specified time limit. To make this process easier, many libraries are available to provide implementations of common algorithms and data structures. In this blog, we will discuss one such library, competitivepython.
What is competitivepython?
competitivepython is an open-source library of algorithms and data structures implemented in Python. It offers a collection of frequently used algorithms and data structures that can be directly used in any Python-based project. The library provides implementations for several common algorithms and data structures, such as searching algorithms (Binary Search, Linear Search, KMP Pattern Search), graph algorithms (BFS, DFS, Dijkstra), sorting algorithms (Bubble Sort, Insertion Sort, Shell Sort, Selection Sort, Bucket Sort, Merge Sort, Tim Sort, Quick Sort, Heap Sort, Radix Sort), and Binary Search Trees.
Features:
competitivepython offers several useful features, including:
- Provides implementations for various commonly used algorithms and data structures.
- Codebase is easy to use, well-documented, and compatible with Python 3.
- Open source and available under the MIT license.
Implementation:
competitivepython is very easy to install and use. To install the library, simply run the following command: pip install competitivepython. Once installed, you can import any desired algorithm or data structure and use it as needed.
Usage:
Let’s take a look at some example use cases for competitivepython.
I͟m͟p͟l͟e͟m͟e͟n͟t͟i͟n͟g͟ S͟e͟a͟r͟c͟h͟e͟s͟:
Below are some example use cases for implementing searches using competitivepython.
a. Binary Search:
from competitivepython import searches
arr = [1, 2, 3, 4, 5]
target = 3
result = searches.binary_search(arr, target)
print("Binary Search:",result)b. Linear Search:
from competitivepython import searches
arr = [5, 7, 9, 2, 4, 10]
target = 4
result = searches.linear_search(arr, target)
print("Linear Search:",result)c. Knuth–Morris–Pratt string Search:
from competitivepython import searches
txt = "ABABDABACDABABCABAB"
pat = "ABABCABAB"
result = searches.kmp_search(pat,txt)
print("KMP Search:",result)I͟m͟p͟l͟e͟m͟e͟n͟t͟i͟n͟g͟ S͟o͟r͟t͟i͟n͟g͟:
Below are some example use cases for implementing sorting using competitivepython.
a. Bubble Sort:
from competitivepython import sorting
arr = [112, 6, 7, 12, 15]
result = sorting.bubble_sort(arr)
print('bubble sort:', result)b. Bucket Sort:
from competitivepython import sorting
arr = [112, 6, 7, 12, 15]
result = sorting.bucket_sort(arr)
print('bucket sort:', result)c. Heap Sort:
from competitivepython import sorting
arr = [112, 6, 7, 12, 15]
result = sorting.heap_sort(arr)
print('heap sort:', result)d. Insertion Sort:
from competitivepython import sorting
arr = [112, 6, 7, 12, 15]
result = sorting.insertion_sort(arr)
print('insertion sort:', result)e. Merge Sort:
from competitivepython import sorting
arr = [112, 6, 7, 12, 15]
result = sorting.merge_sort(arr)
print('merge sort:', result)
f. Quick Sort:
from competitivepython import sorting
arr = [112, 6, 7, 12, 15]
result = sorting.quick_sort(arr)
print('quick sort:', result)g. Radix Sort:
from competitivepython import sorting
arr = [112, 6, 7, 12, 15]
result = sorting.radix_sort(arr)
print('radix sort:', result)h. Selection Sort:
from competitivepython import sorting
arr = [112, 6, 7, 12, 15]
result = sorting.selection_sort(arr)
print('selection sort:', result)i. Shell Sort:
from competitivepython import sorting
arr = [112, 6, 7, 12, 15]
result = sorting.shell_sort(arr)
print('shell sort:', result)j. Tim Sort:
from competitivepython import sorting
arr = [112, 6, 7, 12, 15]
result = sorting.tim_sort(arr)
print('tim sort:', result)I͟m͟p͟l͟e͟m͟e͟n͟t͟i͟n͟g͟ G͟r͟a͟p͟h͟s͟:
Below are some example use cases for implementing graphs using competitivepython.
a. Breadth First Search (or Breadth First Traversal):
from competitivepython import graphs
graph = {
'A': {'B': 1, 'C': 4},
'B': {'A': 1, 'C': 2, 'D': 5},
'C': {'A': 4, 'B': 2, 'D': 1},
'D': {'B': 5, 'C': 1},
}
start = 'A'
end = 'D'
result = graphs.breadth_first_search(graph, 'C')
print("bfs:",result)b. Depth First Search(or Depth First Traversal):
from competitivepython import graphs
graph = {
'A': {'B': 1, 'C': 4},
'B': {'A': 1, 'C': 2, 'D': 5},
'C': {'A': 4, 'B': 2, 'D': 1},
'D': {'B': 5, 'C': 1},
}
start = 'A'
end = 'D'
result = graphs.depth_first_search(graph, 'C')
print("dfs:",result)c. Dijkstra’s Shortest Path:
from competitivepython import graphs
graph = {
'A': {'B': 1, 'C': 4},
'B': {'A': 1, 'C': 2, 'D': 5},
'C': {'A': 4, 'B': 2, 'D': 1},
'D': {'B': 5, 'C': 1},
}
start = 'A'
end = 'D'
result = graphs.dijkstra(graph, start, end)
print("dijikstra:",result)I͟m͟p͟l͟e͟m͟e͟n͟t͟i͟n͟g͟ T͟r͟e͟e͟s͟:
Below are some example use cases for implementing trees using competitivepython.
from competitivepython import trees
# Create an instance of the BinarySearchTree
bst = trees.BinarySearchTree()
# Insert some values into the tree
bst.insert(50)
bst.insert(30)
bst.insert(20)
bst.insert(40)
bst.insert(70)
bst.insert(60)
bst.insert(80)
# Check if a value is present in the tree
print(bst.search(50)) # Output: True
print(bst.search(35)) # Output: False
# Get the values in the tree in in-order traversal order
print(bst.get_in_order_traversal()) Benefits of Using competitivepython Library
The competitivepython library is a useful tool for anyone looking to improve their skills in competitive programming. Here are some benefits of using this library:
- Saves Time: The library provides a wide range of useful functions and algorithms that can be directly used in your code, saving you time in writing the code from scratch.
- Ease of Use: The library is designed to be easy to use, with simple and clear documentation that makes it easy to understand the functions and algorithms.
- Improved Performance: The algorithms provided in the library are optimized for performance, which means that they run faster and use less memory than less optimized algorithms.
- Reusable Code: The library provides a collection of functions that can be reused across multiple projects, saving you time and effort in writing similar functions for different projects.
- Open Source: The library is open source, which means that the code is available for anyone to use, modify, and distribute. This makes it a great resource for learning and contributing to the programming community.
Open Source and Collaboration
One of the main goals of competitivepythonis to provide the Python community with ready to use standard algorithms in their day to day task or coding contests (such as codeforces, codechef, leetcode etc.). As such, the library is hosted on GitHub, a popular platform for hosting open source projects.
You can access the Competitive Python repository at the following URL:
https://github.com/Shikha-code36/Competitive-Python
We welcome contributions from the community, whether that be bug fixes, feature requests, or other improvements. If you are interested in contributing to the project, please follow the guidelines outlined in the README file of the repository.
In addition to the repository, we have also made Competitive Python available on PyPI, the official Python Package Index. This means that you can easily install the library using pip, the Python package manager.
You can find Competitive Python on PyPI at the following URL:
https://pypi.org/project/competitivepython/
We encourage users to submit issues and feature requests through the GitHub repository, as this allows us to better track and prioritize requests. However, we also welcome feedback and questions through the PyPI page, so feel free to leave a review or comment there as well.
Thank you for your support of open source software development and collaboration within the Python community!
