Add a dynamic programming implementation of the Longest Repeating Subsequence (LRS) algorithm. This finds the longest subsequence that occurs at least twice in a string, using a variation of LCS where the string is compared with itself but characters at the same index cannot be reused. Includes comprehensive doctests and type hints.
Co-authored-by: Christian Clauss <cclauss@me.com>
Per discussion in #15418, these four files are not algorithms (they are
how-to-use scripts wrapping a deep-learning framework) and dragged in the
heavy keras/tensorflow dependency stack:
- computer_vision/cnn_classification.py
- dynamic_programming/k_means_clustering_tensorflow.py
- machine_learning/lstm/lstm_prediction.py
- neural_network/input_data.py (TF MNIST data loader; nothing imports it)
Also removes the now-orphaned machine_learning/lstm/ package (only
__init__.py + sample_data.csv, which served lstm_prediction.py).
Cleanups:
- Drop keras from pyproject.toml dependencies; regenerate uv.lock
(removes absl-py, h5py, keras, ml-dtypes, namex, optree).
- Remove the pre-release libhdf5-dev install step from build.yml and
sphinx.yml (it existed only because keras needs hdf5).
- Drop the four stale pytest --ignore entries in build.yml.
- Remove the four DIRECTORY.md entries and the empty Lstm heading.
* Add dynamic programming solution for Egg Dropping Problem
* Revert changes to .pre-commit-config.yaml
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: Christian Clauss <cclauss@me.com>
Co-authored-by: pre-commit-ci[bot] <66853113+pre-commit-ci[bot]@users.noreply.github.com>
* Update longest_common_substring.py
- Combined the ans_index and ans_length into a single tuple to track the best match (position + length) more cleanly.
- Early exit for empty strings.
* [pre-commit.ci] auto fixes from pre-commit.com hooks
for more information, see https://pre-commit.ci
* Update longest_common_substring.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>
Co-authored-by: Maxim Smolskiy <mithridatus@mail.ru>
* Create prefix_sum.py
* [pre-commit.ci] auto fixes from pre-commit.com hooks
for more information, see https://pre-commit.ci
* Fix pre-commit and ruff errors
* [pre-commit.ci] auto fixes from pre-commit.com hooks
for more information, see https://pre-commit.ci
* Rename prefix_sum.py to range_sum_query.py
* Refactor description
* Fix
* Refactor code
* [pre-commit.ci] auto fixes from pre-commit.com hooks
for more information, see https://pre-commit.ci
* Fix
---------
Co-authored-by: pre-commit-ci[bot] <66853113+pre-commit-ci[bot]@users.noreply.github.com>
Co-authored-by: Maxim Smolskiy <mithridatus@mail.ru>
* [pre-commit.ci] pre-commit autoupdate
updates:
- [github.com/astral-sh/ruff-pre-commit: v0.8.6 → v0.9.1](https://github.com/astral-sh/ruff-pre-commit/compare/v0.8.6...v0.9.1)
* [pre-commit.ci] auto fixes from pre-commit.com hooks
for more information, see https://pre-commit.ci
* Update maths/dual_number_automatic_differentiation.py
* Update maths/dual_number_automatic_differentiation.py
* [pre-commit.ci] auto fixes from pre-commit.com hooks
for more information, see https://pre-commit.ci
* Update dual_number_automatic_differentiation.py
* Update dual_number_automatic_differentiation.py
* No <fin-streamer> tag with the specified data-test attribute found.
---------
Co-authored-by: pre-commit-ci[bot] <66853113+pre-commit-ci[bot]@users.noreply.github.com>
Co-authored-by: Christian Clauss <cclauss@me.com>
* Ruff test resolution
* [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>
* Enable ruff E741 rule
* [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>
* Changing the code to return tuple
* Changing the code to return tuple
* [pre-commit.ci] auto fixes from pre-commit.com hooks
for more information, see https://pre-commit.ci
* Update dynamic_programming/subset_generation.py
Co-authored-by: Christian Clauss <cclauss@me.com>
* Adding doctests in subset_generation.py
* [pre-commit.ci] auto fixes from pre-commit.com hooks
for more information, see https://pre-commit.ci
* Update subset_generation.py
* Update subset_generation.py
* [pre-commit.ci] auto fixes from pre-commit.com hooks
for more information, see https://pre-commit.ci
* Update subset_generation.py
* Update subset_generation.py
* [pre-commit.ci] auto fixes from pre-commit.com hooks
for more information, see https://pre-commit.ci
* Update dynamic_programming/subset_generation.py
Co-authored-by: Christian Clauss <cclauss@me.com>
* Update stock_span_problem.py
* [pre-commit.ci] auto fixes from pre-commit.com hooks
for more information, see https://pre-commit.ci
* Update subset_generation.py
* [pre-commit.ci] auto fixes from pre-commit.com hooks
for more information, see https://pre-commit.ci
* Update subset_generation.py
* Update subset_generation.py
* Update subset_generation.py
* Update subset_generation.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>
2023-10-15 21:56:02 +02:00
Kosuri L Induandpre-commit-ci[bot] <66853113+pre-commit-ci[bot]@users.noreply.github.com>
* To add wildcard_matching.py
* [pre-commit.ci] auto fixes from pre-commit.com hooks
for more information, see https://pre-commit.ci
* changes for doctest errors
* [pre-commit.ci] auto fixes from pre-commit.com hooks
for more information, see https://pre-commit.ci
* code changes
* [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>
* added doctests
* added doctests
* [pre-commit.ci] auto fixes from pre-commit.com hooks
for more information, see https://pre-commit.ci
* Add doctests to integer_partition.py
* Update minimum_partition.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>
* Update minimum_steps_to_one.py
Made the problem explanation more clear and readable
* updating DIRECTORY.md
* Apply suggestions from code review
---------
Co-authored-by: github-actions <${GITHUB_ACTOR}@users.noreply.github.com>
Co-authored-by: Tianyi Zheng <tianyizheng02@gmail.com>
* Add doctests, type hints; fix bug
* [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>
* to add the trapped water program
* [pre-commit.ci] auto fixes from pre-commit.com hooks
for more information, see https://pre-commit.ci
* to make changes for error : B006
* [pre-commit.ci] auto fixes from pre-commit.com hooks
for more information, see https://pre-commit.ci
* to make changes for error : B006
* to make changes for error : B006
* [pre-commit.ci] auto fixes from pre-commit.com hooks
for more information, see https://pre-commit.ci
* to make changes in doctest
* to make changes in doctest
* [pre-commit.ci] auto fixes from pre-commit.com hooks
for more information, see https://pre-commit.ci
* Update dynamic_programming/trapped_water.py
Co-authored-by: Christian Clauss <cclauss@me.com>
* Update dynamic_programming/trapped_water.py
Co-authored-by: Christian Clauss <cclauss@me.com>
* to make changes in parameters
* [pre-commit.ci] auto fixes from pre-commit.com hooks
for more information, see https://pre-commit.ci
* to make changes in parameters
* [pre-commit.ci] auto fixes from pre-commit.com hooks
for more information, see https://pre-commit.ci
* Update dynamic_programming/trapped_water.py
Co-authored-by: Christian Clauss <cclauss@me.com>
* to make changes in parameters
* [pre-commit.ci] auto fixes from pre-commit.com hooks
for more information, see https://pre-commit.ci
* for negative heights
* Update dynamic_programming/trapped_water.py
Co-authored-by: Christian Clauss <cclauss@me.com>
* to remove falsy
* Final edits
* tuple[int, ...]
---------
Co-authored-by: pre-commit-ci[bot] <66853113+pre-commit-ci[bot]@users.noreply.github.com>
Co-authored-by: Christian Clauss <cclauss@me.com>
* largest divisible subset
* minor tweaks
* adding more test cases
Co-authored-by: Christian Clauss <cclauss@me.com>
* improving code for better readability
Co-authored-by: Christian Clauss <cclauss@me.com>
* update
Co-authored-by: Christian Clauss <cclauss@me.com>
* update
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
* suggested changes done, and further modfications
* final update
* [pre-commit.ci] auto fixes from pre-commit.com hooks
for more information, see https://pre-commit.ci
* Update largest_divisible_subset.py
* [pre-commit.ci] auto fixes from pre-commit.com hooks
for more information, see https://pre-commit.ci
* Update largest_divisible_subset.py
---------
Co-authored-by: Christian Clauss <cclauss@me.com>
Co-authored-by: pre-commit-ci[bot] <66853113+pre-commit-ci[bot]@users.noreply.github.com>
* DRAFT: GitHub Actions: Test on Python 3.12
Repeats #8777
* #8777
Some of our dependencies will not be ready yet.
* Python 3.12: Disable qiskit and tensorflow algorithms
* updating DIRECTORY.md
---------
Co-authored-by: github-actions <${GITHUB_ACTOR}@users.noreply.github.com>
* added smith waterman algorithm
* [pre-commit.ci] auto fixes from pre-commit.com hooks
for more information, see https://pre-commit.ci
* descriptive names for the parameters a and b
* doctesting lowercase upcase empty string cases
* updated block quot,fixed traceback and doctests
* shorter block quote
Co-authored-by: Tianyi Zheng <tianyizheng02@gmail.com>
* global vars to func params,more doctests
* updated doctests
* user access to SW params
* formating
---------
Co-authored-by: pre-commit-ci[bot] <66853113+pre-commit-ci[bot]@users.noreply.github.com>
Co-authored-by: Tianyi Zheng <tianyizheng02@gmail.com>
