[pull] master from TheAlgorithms:master - #114

* Fix binary search to return leftmost occurrence for duplicates

Signed-off-by: SoulSniper1212 <warush23@gmail.com>

* [pre-commit.ci] auto fixes from pre-commit.com hooks

for more information, see https://pre-commit.ci

---------

Signed-off-by: SoulSniper1212 <warush23@gmail.com>
Co-authored-by: SoulSniper1212 <warush23@gmail.com>
Co-authored-by: pre-commit-ci[bot] <66853113+pre-commit-ci[bot]@users.noreply.github.com>

* Add connectionist temporal classification (CTC) loss algorithm

* Update loss_functions.py

---------

Co-authored-by: Tianyi Zheng <tianyizheng02@gmail.com>
Co-authored-by: Christian Clauss <cclauss@me.com>

* Add sparse categorical cross entropy loss algorithm

* Update loss_functions.py

---------

Co-authored-by: Christian Clauss <cclauss@me.com>

* Add Gaussian negative log likelihood loss algorithm

* Fix boolean conversion in Gaussian NLL loss example

---------

Co-authored-by: Christian Clauss <cclauss@me.com>

* feat: ✨ calculating the resitance of resistor using color codes

* feat: ✨ implementation of boyle's law

* docs: 📝 removed redundant information in description

* docs: 📝 updated description of boyle's law as suggested

* refactor: ♻️ refactored code as suggested in review

* fix: 🩹 added return type for check_validity function

* test: ✅ handled input validation for values less than 0

* updating DIRECTORY.md

* fix: 🚨 resolve remaining ruff dictionary error

---------

Co-authored-by: Akshay B Shetty <107768228+NinjaSoulPirate@users.noreply.github.com>
Co-authored-by: akshaybsh <akshaybsh@users.noreply.github.com>
Co-authored-by: Akshay B Shetty <akshay.b@tenxerlabs.com>

* adding negative binary base conversion algorithms

* [pre-commit.ci] auto fixes from pre-commit.com hooks

for more information, see https://pre-commit.ci

* fixing bugs

* [pre-commit.ci] auto fixes from pre-commit.com hooks

for more information, see https://pre-commit.ci

---------

Co-authored-by: pre-commit-ci[bot] <66853113+pre-commit-ci[bot]@users.noreply.github.com>

* Add visualization support for linear regression

* [pre-commit.ci] auto fixes from pre-commit.com hooks

for more information, see https://pre-commit.ci

* Fix linting and plotting issues

* Apply ruff auto fixes

* Fix spelling issue

* Update linear_regression.py

---------

Co-authored-by: pre-commit-ci[bot] <66853113+pre-commit-ci[bot]@users.noreply.github.com>
Co-authored-by: Christian Clauss <cclauss@me.com>

* Added Shor Algorithm for RSA n factorization

* updating DIRECTORY.md

* [pre-commit.ci] auto fixes from pre-commit.com hooks

for more information, see https://pre-commit.ci

* Added referred website and handle type hints

* [pre-commit.ci] auto fixes from pre-commit.com hooks

for more information, see https://pre-commit.ci

* Developed the Logical implementation of Shor Algo #12318

* Apply suggestion from @cclauss

---------

Co-authored-by: joelkurien <joelkurien@users.noreply.github.com>
Co-authored-by: pre-commit-ci[bot] <66853113+pre-commit-ci[bot]@users.noreply.github.com>
Co-authored-by: Christian Clauss <cclauss@me.com>

* add basic crypto price converter in accordance with #13008

* [pre-commit.ci] auto fixes from pre-commit.com hooks

for more information, see https://pre-commit.ci

* Switch from httpx to httpx2 for API requests

Updated the import statement and modified the get_eth_price_usd function to use httpx2 instead of httpx.

* [pre-commit.ci] auto fixes from pre-commit.com hooks

for more information, see https://pre-commit.ci

* Refactor ETH price fetching to use direct import

---------

Co-authored-by: pre-commit-ci[bot] <66853113+pre-commit-ci[bot]@users.noreply.github.com>
Co-authored-by: Christian Clauss <cclauss@me.com>

* Add crypto_price_tracker.py to fetch live crypto prices

* Update crypto_price_tracker to use httpx2

* [pre-commit.ci] auto fixes from pre-commit.com hooks

for more information, see https://pre-commit.ci

* updating DIRECTORY.md

* Correct JSON response handling in price tracker

Fix incorrect variable reference for JSON response.

---------

Co-authored-by: Christian Clauss <cclauss@me.com>
Co-authored-by: pre-commit-ci[bot] <66853113+pre-commit-ci[bot]@users.noreply.github.com>
Co-authored-by: cclauss <cclauss@users.noreply.github.com>

* Create largest_smallest_words.py

* [pre-commit.ci] auto fixes from pre-commit.com hooks

for more information, see https://pre-commit.ci

* Update largest_smallest_words.py

* [pre-commit.ci] auto fixes from pre-commit.com hooks

for more information, see https://pre-commit.ci

* Update largest_smallest_words.py

* [pre-commit.ci] auto fixes from pre-commit.com hooks

for more information, see https://pre-commit.ci

* Update largest_smallest_words.py

* [pre-commit.ci] auto fixes from pre-commit.com hooks

for more information, see https://pre-commit.ci

* Update largest_smallest_words.py

* Update largest_smallest_words.py

* [pre-commit.ci] auto fixes from pre-commit.com hooks

for more information, see https://pre-commit.ci

---------

Co-authored-by: pre-commit-ci[bot] <66853113+pre-commit-ci[bot]@users.noreply.github.com>

* pr_file_map.py: Use a human-readable date format

Use a human-readable date format.

* [pre-commit.ci] auto fixes from pre-commit.com hooks

for more information, see https://pre-commit.ci

---------

Co-authored-by: pre-commit-ci[bot] <66853113+pre-commit-ci[bot]@users.noreply.github.com>

* [Add] Kronecker Product

* [pre-commit.ci] auto fixes from pre-commit.com hooks

for more information, see https://pre-commit.ci

* fix: failed tests

* [pre-commit.ci] auto fixes from pre-commit.com hooks

for more information, see https://pre-commit.ci

* updating DIRECTORY.md

---------

Co-authored-by: Jay Prajapati <jay.prajapati@upsquare.in>
Co-authored-by: pre-commit-ci[bot] <66853113+pre-commit-ci[bot]@users.noreply.github.com>
Co-authored-by: Christian Clauss <cclauss@me.com>
Co-authored-by: cclauss <cclauss@users.noreply.github.com>

* Created proof_of_stake.py

* Updated proof_of_stake.py

* [pre-commit.ci] auto fixes from pre-commit.com hooks

for more information, see https://pre-commit.ci

* Changes to proof_of_stake.py

* [pre-commit.ci] auto fixes from pre-commit.com hooks

for more information, see https://pre-commit.ci

* Delete blockchain/proof_of_stake.py

* Created and updated proof_of_stake.py

* [pre-commit.ci] auto fixes from pre-commit.com hooks

for more information, see https://pre-commit.ci

* Updated proof_of_stake.py

* Created proof_of_work.py

* [pre-commit.ci] auto fixes from pre-commit.com hooks

for more information, see https://pre-commit.ci

* Updated proof_of_work.py

* [pre-commit.ci] auto fixes from pre-commit.com hooks

for more information, see https://pre-commit.ci

* Updated proof_of_work.py

* Updated proof_of_work.py

* Updated proof_of_work.py

* [pre-commit.ci] auto fixes from pre-commit.com hooks

for more information, see https://pre-commit.ci

* Delete blockchain/proof_of_work.py

* Added proof_of_work.py

* [pre-commit.ci] auto fixes from pre-commit.com hooks

for more information, see https://pre-commit.ci

* Updated proof_of_work.py

* [pre-commit.ci] auto fixes from pre-commit.com hooks

for more information, see https://pre-commit.ci

* Update proof_of_work.py

* Update proof_of_work.py

* [pre-commit.ci] auto fixes from pre-commit.com hooks

for more information, see https://pre-commit.ci

* Update proof_of_work.py

* [pre-commit.ci] auto fixes from pre-commit.com hooks

for more information, see https://pre-commit.ci

* updating DIRECTORY.md

---------

Co-authored-by: pre-commit-ci[bot] <66853113+pre-commit-ci[bot]@users.noreply.github.com>
Co-authored-by: Christian Clauss <cclauss@me.com>
Co-authored-by: cclauss <cclauss@users.noreply.github.com>

Co-authored-by: Christian Clauss <cclauss@me.com>

* unit test for graphs_floyd_warshall

* cleaning up

* capturing print output

* editing doctest

* editing doctest

* editing doctest

* editing doctest

* removing blank lines from print statement

* removing tabs from print statement

* commenting out print statement

* changing pytest

* fixing doctest

* including print statement and output in doctest

* editing doctest

* changing tab to double spaces to capture in doctest

* changing end character in print statement

* fixing doctests

* chagning tab to double space for doctest

* updating DIRECTORY.md

* Improve output formatting in Floyd Warshall example

Added a blank line for better readability in the output.

---------

Co-authored-by: Ajmera, Mahita  SI/HZR-IDSA <ajmermhi@schaeffler.com>
Co-authored-by: Christian Clauss <cclauss@me.com>
Co-authored-by: cclauss <cclauss@users.noreply.github.com>

* Added the doctests - Contributes to #9943

* move work to new branch

* [pre-commit.ci] auto fixes from pre-commit.com hooks

for more information, see https://pre-commit.ci

* Resolved the error Added the doctests - Contributes to #9943

* Added the doctests - Contributes to #9943

* [pre-commit.ci] auto fixes from pre-commit.com hooks

for more information, see https://pre-commit.ci

---------

Co-authored-by: Priyal595 <231030016@juitsolan.in>
Co-authored-by: pre-commit-ci[bot] <66853113+pre-commit-ci[bot]@users.noreply.github.com>
Co-authored-by: Christian Clauss <cclauss@me.com>

* corrected the typos

* added the docstrings in the functions

* [pre-commit.ci] auto fixes from pre-commit.com hooks

for more information, see https://pre-commit.ci

* Update camel_case_to_snake_case.py

* Improve docstring clarity in frequency_finder.py

Updated docstrings for get_letter_count and get_item_at_index_zero functions for clarity.

---------

Co-authored-by: pre-commit-ci[bot] <66853113+pre-commit-ci[bot]@users.noreply.github.com>
Co-authored-by: Christian Clauss <cclauss@me.com>

* Updated the error handling in and_gate.py

* Apply batched suggestions from code review

Co-authored-by: Christian Clauss <cclauss@me.com>

---------

Co-authored-by: Christian Clauss <cclauss@me.com>

Added comprehensive doctests for find_mod_inverse function.

Contributes to #9943

Co-authored-by: Christian Clauss <cclauss@me.com>

- Added detailed docstring explaining modular multiplicative inverse
- Included 10 valid test cases with verification calculations
- Added 3 error cases testing ValueError for non-coprime inputs
- Added Wikipedia reference for educational value
- All doctests pass locally (python -m doctest -v)
- Passes ruff, mypy, and pre-commit hooks

Contributes to #9943

Co-authored-by: Christian Clauss <cclauss@me.com>

#14635)

* fix: int_to_roman silently returns wrong values for out-of-range input

Added input validation for int_to_roman function.

* fix: EM102 assign f-strings to msg before raising exceptions

* Update conversions/roman_numerals.py

* Bool don't work

* Apply suggestion from @cclauss

---------

Co-authored-by: Christian Clauss <cclauss@me.com>

* fix: Boyer-Moore bad character shift was dead code in for-loop

The bad_character_heuristic() method used a for-loop with an
assignment to the loop variable i, which was immediately
overwritten by the next iteration. This caused the algorithm
to degrade from O(n/m) to O(n*m) naive search.

Changed to a while-loop so the shift actually takes effect.
Added max(i+1, shift) guard to prevent backward skips when
the mismatched character appears to the right of the mismatch
in the pattern. Added edge case doctests.

* [pre-commit.ci] auto fixes from pre-commit.com hooks

for more information, see https://pre-commit.ci

* Update boyer_moore_search.py

* Correct documentation for positions in BoyerMooreSearch

Fixes the documentation to clarify that 'positions' contains the locations where the pattern was matched.

* Fix grammatical issues in Boyer-Moore search comments

Corrected grammatical errors in comments and docstrings.

---------

Co-authored-by: Christian Clauss <cclauss@me.com>
Co-authored-by: pre-commit-ci[bot] <66853113+pre-commit-ci[bot]@users.noreply.github.com>

* Refine Wheatstone Bridge explanation

Updated docstring to provide a clearer explanation of the Wheatstone Bridge, its balance condition, and applications.

* Update wheatstone_bridge.py

* Correct docstring formatting in wheatstone_bridge.py

Fix formatting in docstring for clarity.

* [pre-commit.ci] auto fixes from pre-commit.com hooks

for more information, see https://pre-commit.ci

* Fix docstring capitalization and simplify return statement

Corrected capitalization of 'Wheatstone' in the docstring and improved code structure by removing unnecessary else statement.

---------

Co-authored-by: pre-commit-ci[bot] <66853113+pre-commit-ci[bot]@users.noreply.github.com>
Co-authored-by: Christian Clauss <cclauss@me.com>

* docs: Add circuit diagram and improve Wheatstone bridge documentation

* [pre-commit.ci] auto fixes from pre-commit.com hooks

for more information, see https://pre-commit.ci

* Fix docstring in wheatstone_solver function

Corrected docstring formatting in wheatstone_solver function.

* Add reference link for Wheatstone bridge

Added a comment to reference the Wheatstone bridge Wikipedia page.

---------

Co-authored-by: pre-commit-ci[bot] <66853113+pre-commit-ci[bot]@users.noreply.github.com>
Co-authored-by: Christian Clauss <cclauss@me.com>

* Stop bidirectional A* when either frontier is empty

* Add bidirectional A* regressions and a grid benchmark

Preserve all 18 existing doctest examples and append frontier exhaustion regressions and controls. Add an optional 2,025-cell benchmark with a documented 89-cell reachable corridor, leaving the production fix unchanged.

* test: cover insertion sort stability with equal-priority items

* test: simplify insertion sort stability doctest output

* test: verify insertion sort ignores labels when ordering

* Fix maximum Fenwick tree range values after updates

* Add Fenwick regression doctests and 2000-item benchmark

Preserve all existing doctests while covering lost range maxima and decreases. Add an optional timeit benchmark for update and query workloads, as requested in #15485.

* Avoid unnecessary maximum Fenwick recomputation

Propagate only changed maxima and rebuild necessary buckets directly from disjoint child buckets. Preserve arbitrary overwrites, regression doctests and the benchmark.

---------

Co-authored-by: Christian Clauss <cclauss@me.com>

* Fix consumed character tracking in Jaro-Winkler matching

* Add Jaro-Winkler regression tests and a large-input benchmark

Preserve all eight existing examples and append three regressions that fail before the fix. Add an optional 2,000-character timing comparison without changing the production implementation.

* Optimize Jaro-Winkler matching with occurrence queues

Preserve earliest unused matches while avoiding repeated window scans. Retain all existing regression doctests and the benchmark.

* code: add modern list type hint and annotations to double_linear_search_recursion

* code: update list type hints to generic Any per code review

* code: Add comparable type and person doctests per maintainer review

* [pre-commit.ci] auto fixes from pre-commit.com hooks

for more information, see https://pre-commit.ci

* Apply batched suggestions from code review

Co-authored-by: Christian Clauss <cclauss@me.com>

* [pre-commit.ci] auto fixes from pre-commit.com hooks

for more information, see https://pre-commit.ci

---------

Co-authored-by: pre-commit-ci[bot] <66853113+pre-commit-ci[bot]@users.noreply.github.com>
Co-authored-by: Christian Clauss <cclauss@me.com>

The PEP 695 type parameters already bound T to Comparable, so the module-level TypeVar was unused. Matches the cleanup requested in #15234.

* Type recursive quick sort for any comparable items

Part of #15234

* Cover recursive quick sort in the comparison-sort battery

Part of #15234

* Replace placeholder test file with comparison-sort coverage

Part of #15234

* Document the comparison operators recursive quick sort actually uses

The partition uses <= and >, so the Comparable protocol should declare __le__ and __gt__ as well as __lt__.

* Apply batched suggestions from code review

Co-authored-by: Christian Clauss <cclauss@me.com>

* Update recursive_quick_sort.py

---------

Co-authored-by: Christian Clauss <cclauss@me.com>

* fix: handle EMA window size of one

* fix: satisfy ruff check

* Update exponential_moving_average.py

---------

Co-authored-by: Christian Clauss <cclauss@me.com>

* types(power_sort): preserve input item type

* Enhance power_sort docstring with more examples

Added examples for using power_sort with tuples and lists.

* Update power_sort.py

* [pre-commit.ci] auto fixes from pre-commit.com hooks

for more information, see https://pre-commit.ci

---------

Co-authored-by: nightcityblade <nightcityblade@gmail.com>
Co-authored-by: Christian Clauss <cclauss@me.com>
Co-authored-by: pre-commit-ci[bot] <66853113+pre-commit-ci[bot]@users.noreply.github.com>

…15502)

updates:
- [github.com/tox-dev/pyproject-fmt: v2.29.4 → v2.30.1](tox-dev/pyproject-fmt@v2.29.4...v2.30.1)
- [github.com/astral-sh/ruff-pre-commit: v0.16.7 → v0.16.10](astral-sh/ruff-pre-commit@v0.16.7...v0.16.10)
- [github.com/rvben/rumdl-pre-commit: v0.2.73 → v0.2.78](rvben/rumdl-pre-commit@v0.2.73...v0.2.78)
- [github.com/astral-sh/uv-pre-commit: 0.12.13 → 0.12.23](astral-sh/uv-pre-commit@0.12.13...0.12.23)
- [github.com/15r10nk/matchify: v0.2.0 → v0.3.0](15r10nk/matchify@v0.2.0...v0.3.0)

Co-authored-by: pre-commit-ci[bot] <66853113+pre-commit-ci[bot]@users.noreply.github.com>

* fix(maths): use conventional datetime alias in Zeller's congruence

* from datetime import date

Replaced datetime module alias with direct import for clarity.

---------

Co-authored-by: Christian Clauss <cclauss@me.com>

* refactor(heap): remove redundant TypeVar in Heap

* refactor(heap): revert Comparable.__gt__ signature to self: T, other: T

* Clean up imports in heap.py

Removed unused TypeVar import from heap.py

* Update __gt__ method signature in Comparable class

---------

Co-authored-by: Christian Clauss <cclauss@me.com>

* feat(dynamic_programming): add weighted interval scheduling algorithm

* test(dynamic_programming): add doctest to __post_init__ and add test function

* Move weighted interval scheduling to scheduling directory

---------

Co-authored-by: Christian Clauss <cclauss@me.com>

…15551)

* fix: parenthesize multi-catch that only parses on 3.14

PEP 758 syntax requires Python 3.14, but the script metadata declares
requires-python >= 3.13. Reported by ty check run per #15187.

* [pre-commit.ci] auto fixes from pre-commit.com hooks

for more information, see https://pre-commit.ci

* Update required Python version in instagram_crawler.py

---------

Co-authored-by: pre-commit-ci[bot] <66853113+pre-commit-ci[bot]@users.noreply.github.com>
Co-authored-by: Christian Clauss <cclauss@me.com>

#15550)

* fix: parenthesize multi-catch that only parses on 3.14

PEP 758 syntax requires Python 3.14, but the script metadata declares
requires-python >= 3.11. Reported by ty check run per #15187.

* [pre-commit.ci] auto fixes from pre-commit.com hooks

for more information, see https://pre-commit.ci

* fix: declare 3.14 in crypto_price_tracker PEP 723 metadata

The unparenthesized multi-catch (PEP 758) only parses on 3.14+.
Parenthesizing is not an option: ruff-format 0.16.10 with the repo's
py315 target re-emits the parenthesized form, so pre-commit.ci reverts
it on every push. Align the declared minimum instead.

* fix: alias datetime import to dt in maths/zellers_congruence

Clears ICN001, which fails on master and blocks every PR ruff check.

* Refactor datetime import in zellers_congruence.py

Replaced 'datetime as dt' with 'datetime' for clarity.

* Update required Python version to 3.15

---------

Co-authored-by: pre-commit-ci[bot] <66853113+pre-commit-ci[bot]@users.noreply.github.com>
Co-authored-by: Christian Clauss <cclauss@me.com>

- Implement is_keith_number(number: int) -> bool with rolling sum optimization
- Implement find_keith_numbers(limit: int) -> list[int]
- Add Wikipedia and OEIS reference links
- Comprehensive doctests covering normal, edge, and error cases

make_linked_list declared the input as Iterable[int] but tested emptiness
with truthiness, so an empty generator silently produced an empty
LinkedList instead of raising. Materialize the iterable first and cover
generator input with doctests.

Co-authored-by: Christian Clauss <cclauss@me.com>

…ies (#15570)

Co-authored-by: Copilot <223556219+Copilot@users.noreply.github.com>

* Add scripts/find_and_fix_pep798.py to find and fix PEP 798 opportunities

Co-authored-by: Copilot <223556219+Copilot@users.noreply.github.com>

* Python PEP 798 compression fixes

* updating DIRECTORY.md

---------

Co-authored-by: Copilot <223556219+Copilot@users.noreply.github.com>
Co-authored-by: cclauss <cclauss@users.noreply.github.com>

…e rule (#15568)

Annotating @contextmanager functions as -> Iterator is deprecated in Python 3.15 typeshed stubs; updated to -> Generator[None]. Un-ignores rules.deprecated in pyproject.toml.

Contributes to #15187.

* Initial plan

* Filter PEP 798 scan paths

Co-authored-by: cclauss <3709715+cclauss@users.noreply.github.com>

---------

Co-authored-by: copilot-swe-agent[bot] <198982749+Copilot@users.noreply.github.com>
Co-authored-by: cclauss <3709715+cclauss@users.noreply.github.com>

…lysis (#15606)

In linear_discriminant_analysis, line 146 wrote if features.any: instead of calling if features.any():. Because the method object is always truthy, the else branch handling empty datasets was unreachable dead code, triggering ty warning[redundant-condition].

Call eatures.any() (matching line 107 in principal_component_analysis) and add a test case in test_linear_discriminant_analysis verifying that an empty dataset properly enters the else branch.

Validation:
- uvx ty check machine_learning/dimensionality_reduction.py -> All checks passed (0 diagnostics)
- uvx --with scipy --with scikit-learn --with numpy pytest machine_learning/dimensionality_reduction.py --doctest-modules -> 9 passed
- uvx ruff check / format -> clean

updates:
- [github.com/tox-dev/pyproject-fmt: v2.30.1 → v2.30.3](tox-dev/pyproject-fmt@v2.30.1...v2.30.3)
- [github.com/astral-sh/ruff-pre-commit: v0.16.10 → v0.17.3](astral-sh/ruff-pre-commit@v0.16.10...v0.17.3)
- [github.com/rvben/rumdl-pre-commit: v0.2.78 → v0.3.2](rvben/rumdl-pre-commit@v0.2.78...v0.3.2)
- [github.com/astral-sh/uv-pre-commit: 0.12.23 → 0.13.6](astral-sh/uv-pre-commit@0.12.23...0.13.6)
- [github.com/abravalheri/validate-pyproject: 0.26 → v0.27](abravalheri/validate-pyproject@0.26...v0.27)

Co-authored-by: pre-commit-ci[bot] <66853113+pre-commit-ci[bot]@users.noreply.github.com>