* Improve crossword puzzle solver implementation
The original `is_valid` returned `False` for any non-empty cell, which meant two words sharing a letter could never be placed together. Since crossword grids are built on exactly those intersections, this broke the core use case. Related to that, `remove_word` during backtracking blindly blanked every cell of the removed word, wiping out letters that belonged to already-placed crossing words. The fix snapshots the grid before placement and only clears cells that were empty beforehand. There was also a mutation bug: `words.remove(word)` does an O(n) scan and modifies state shared across the call stack, replaced here with a local slice per frame. On top of the fixes, the solver now tries the longest word first at each level, a standard "most-constrained variable" heuristic that cuts down backtracks significantly on larger inputs.
* [pre-commit.ci] auto fixes from pre-commit.com hooks
for more information, see https://pre-commit.ci
* Refactor character check in crossword solver
---------
Co-authored-by: pre-commit-ci[bot] <66853113+pre-commit-ci[bot]@users.noreply.github.com>
Co-authored-by: Christian Clauss <cclauss@me.com>
* Create Calc.py
* Rename Calc.py to calc.py
* [pre-commit.ci] auto fixes from pre-commit.com hooks
for more information, see https://pre-commit.ci
* Create rat_in_a_maze.py
* Delete dynamic_programming/rat_in_a_maze.py
* Create m-coloring-problem.py
* [pre-commit.ci] auto fixes from pre-commit.com hooks
for more information, see https://pre-commit.ci
* Rename m-coloring-problem.py to m_coloring_problem.py
* Delete other/calc.py
* Update m_coloring_problem.py
* Update m_coloring_problem.py
* [pre-commit.ci] auto fixes from pre-commit.com hooks
for more information, see https://pre-commit.ci
* Update m_coloring_problem.py
* [pre-commit.ci] auto fixes from pre-commit.com hooks
for more information, see https://pre-commit.ci
* Update m_coloring_problem.py
* [pre-commit.ci] auto fixes from pre-commit.com hooks
for more information, see https://pre-commit.ci
* Update m_coloring_problem.py
* Update m_coloring_problem.py
* Update m_coloring_problem.py
* Update m_coloring_problem.py
* Update m_coloring_problem.py
* [pre-commit.ci] auto fixes from pre-commit.com hooks
for more information, see https://pre-commit.ci
* Update m_coloring_problem.py
* [pre-commit.ci] auto fixes from pre-commit.com hooks
for more information, see https://pre-commit.ci
* Update m_coloring_problem.py
* Update m_coloring_problem.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>
* Added get_word_path function
* [pre-commit.ci] auto fixes from pre-commit.com hooks
for more information, see https://pre-commit.ci
* updating DIRECTORY.md
* Implement board and word validation function
Added a new validation function to check the board and word parameters, ensuring proper input types and values. Updated existing function docstrings for clarity and consistency.
* [pre-commit.ci] auto fixes from pre-commit.com hooks
for more information, see https://pre-commit.ci
* Improve readability of validate_board_and_word call
Refactor the validate_board_and_word function call for better readability.
---------
Co-authored-by: Kadambari <kadambari179@gmail.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>
Co-authored-by: cclauss <cclauss@users.noreply.github.com>
* add some doctests to algos in backtracking
* [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>
* Add type hints and improve code quality for generate_parentheses_iterative
* [pre-commit.ci] auto fixes from pre-commit.com hooks
for more information, see https://pre-commit.ci
* Fix line length issue
* Update generate_parentheses_iterative.py
* Update generate_parentheses_iterative.py
---------
Co-authored-by: pre-commit-ci[bot] <66853113+pre-commit-ci[bot]@users.noreply.github.com>
Co-authored-by: Maxim Smolskiy <mithridatus@mail.ru>
* Fix n-queens problem
* [pre-commit.ci] auto fixes from pre-commit.com hooks
for more information, see https://pre-commit.ci
* Update n_queens.py
* [pre-commit.ci] auto fixes from pre-commit.com hooks
for more information, see https://pre-commit.ci
* Update n_queens.py
* Update n_queens.py
---------
Co-authored-by: pre-commit-ci[bot] <66853113+pre-commit-ci[bot]@users.noreply.github.com>
Co-authored-by: Maxim Smolskiy <mithridatus@mail.ru>
* Add Word Break algorithm
* Add Word Break algorithm
* [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 word ladder algorithm in backtracking
* Improve comments and implement ruff checks
* updating DIRECTORY.md
* [pre-commit.ci] auto fixes from pre-commit.com hooks
for more information, see https://pre-commit.ci
* Change BFS to Backtracking
* [pre-commit.ci] auto fixes from pre-commit.com hooks
for more information, see https://pre-commit.ci
* Incorporate PR Changes
* [pre-commit.ci] auto fixes from pre-commit.com hooks
for more information, see https://pre-commit.ci
* Add type hints for backtrack function
* [pre-commit.ci] auto fixes from pre-commit.com hooks
for more information, see https://pre-commit.ci
---------
Co-authored-by: Hardvan <Hardvan@users.noreply.github.com>
Co-authored-by: pre-commit-ci[bot] <66853113+pre-commit-ci[bot]@users.noreply.github.com>
* Enable ruff PLR5501 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>
* Update all_combinations.py
The original implementation had limitations in handling edge cases and certain input parameters, leading to potential RecursionError.
* Update all_combinations.py
Added checks to handle cases where n or k are negative or where k is greater than n. In such scenarios, the function now returns an empty list, avoiding invalid recursive calls.
* Update error handling
Added checks to handle cases where `n` or `k` are negative or where `k` is greater than `n`. In such scenarios, the function now returns an empty list, avoiding invalid recursive calls.
* Update backtracking/all_combinations.py
* Update all_combinations.py
---------
Co-authored-by: Christian Clauss <cclauss@me.com>
* Add: Matrix Prefix Sum
* [pre-commit.ci] auto fixes from pre-commit.com hooks
for more information, see https://pre-commit.ci
* Changes made in Matrix Prefix Sum
* [pre-commit.ci] auto fixes from pre-commit.com hooks
for more information, see https://pre-commit.ci
* Changes made in Matrix Prefix Sum
* [pre-commit.ci] auto fixes from pre-commit.com hooks
for more information, see https://pre-commit.ci
* Changes made in Matrix Prefix Sum
* [pre-commit.ci] auto fixes from pre-commit.com hooks
for more information, see https://pre-commit.ci
* Changes made in Matrix Prefix Sum
* Changes made in Matrix Prefix Sum
* [pre-commit.ci] auto fixes from pre-commit.com hooks
for more information, see https://pre-commit.ci
* Changes made in Matrix Prefix Sum
* [pre-commit.ci] auto fixes from pre-commit.com hooks
for more information, see https://pre-commit.ci
* Changes made in Matrix Prefix Sum
* [pre-commit.ci] auto fixes from pre-commit.com hooks
for more information, see https://pre-commit.ci
* Changes made in Matrix Prefix Sum
* Changes made in Matrix Prefix Sum
* [pre-commit.ci] auto fixes from pre-commit.com hooks
for more information, see https://pre-commit.ci
* Changes made in Matrix Prefix Sum
* [pre-commit.ci] auto fixes from pre-commit.com hooks
for more information, see https://pre-commit.ci
* Changes made in Matrix Prefix Sum
* [pre-commit.ci] auto fixes from pre-commit.com hooks
for more information, see https://pre-commit.ci
* Changes made in Matrix Prefix Sum
* Changes made in Matrix Prefix Sum
* [pre-commit.ci] auto fixes from pre-commit.com hooks
for more information, see https://pre-commit.ci
* Changes made in Matrix Prefix Sum
* Changes made in Matrix Prefix Sum
* [pre-commit.ci] auto fixes from pre-commit.com hooks
for more information, see https://pre-commit.ci
* Changes made in Matrix Prefix Sum
* [pre-commit.ci] auto fixes from pre-commit.com hooks
for more information, see https://pre-commit.ci
* Changes made in Matrix Prefix Sum
* Add: Distinct Subsequences
* [pre-commit.ci] auto fixes from pre-commit.com hooks
for more information, see https://pre-commit.ci
* Changes made in Distinct Subsequences
* [pre-commit.ci] auto fixes from pre-commit.com hooks
for more information, see https://pre-commit.ci
* Changes made in Distinct Subsequences
* Changes made in Distinct Subsequences
* Changes made in Distinct Subsequences
* [pre-commit.ci] auto fixes from pre-commit.com hooks
for more information, see https://pre-commit.ci
* Removed Distinct Subsequences
* Add: Generate Parentheses
* Add: Generate Parentheses
* [pre-commit.ci] auto fixes from pre-commit.com hooks
for more information, see https://pre-commit.ci
* Add: Generate Parentheses
* Add: Generate Parentheses
* [pre-commit.ci] auto fixes from pre-commit.com hooks
for more information, see https://pre-commit.ci
* Add: Generate Parentheses
* Add: Generate Parentheses
* [pre-commit.ci] auto fixes from pre-commit.com hooks
for more information, see https://pre-commit.ci
* Update backtracking/generate_parentheses.py
* Delete matrix/matrix_prefix_sum.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>
* Create crossword_puzzle_solver.py
* Update crossword_puzzle_solver.py
* [pre-commit.ci] auto fixes from pre-commit.com hooks
for more information, see https://pre-commit.ci
* Update crossword_puzzle_solver.py
* [pre-commit.ci] auto fixes from pre-commit.com hooks
for more information, see https://pre-commit.ci
* Update crossword_puzzle_solver.py
* [pre-commit.ci] auto fixes from pre-commit.com hooks
for more information, see https://pre-commit.ci
* Update crossword_puzzle_solver.py
* [pre-commit.ci] auto fixes from pre-commit.com hooks
for more information, see https://pre-commit.ci
* Update crossword_puzzle_solver.py
* [pre-commit.ci] auto fixes from pre-commit.com hooks
for more information, see https://pre-commit.ci
* Update crossword_puzzle_solver.py
* [pre-commit.ci] auto fixes from pre-commit.com hooks
for more information, see https://pre-commit.ci
* Update crossword_puzzle_solver.py
* [pre-commit.ci] auto fixes from pre-commit.com hooks
for more information, see https://pre-commit.ci
* Update crossword_puzzle_solver.py
* [pre-commit.ci] auto fixes from pre-commit.com hooks
for more information, see https://pre-commit.ci
* Update crossword_puzzle_solver.py
* Update backtracking/crossword_puzzle_solver.py
* Update crossword_puzzle_solver.py
* [pre-commit.ci] auto fixes from pre-commit.com hooks
for more information, see https://pre-commit.ci
* Update crossword_puzzle_solver.py
* [pre-commit.ci] auto fixes from pre-commit.com hooks
for more information, see https://pre-commit.ci
* Update crossword_puzzle_solver.py
* Apply suggestions from code review
* Update crossword_puzzle_solver.py
* Update crossword_puzzle_solver.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>
* Enhance readability of N Queens
* Simplify is_safe code
* [pre-commit.ci] auto fixes from pre-commit.com hooks
for more information, see https://pre-commit.ci
* Apply suggestions from code review
---------
Co-authored-by: pre-commit-ci[bot] <66853113+pre-commit-ci[bot]@users.noreply.github.com>
Co-authored-by: Tianyi Zheng <tianyizheng02@gmail.com>
* Updated test cases of power_sum.py
* updated
* updated.
* remove extra comment and used ** instead of pow
* [pre-commit.ci] auto fixes from pre-commit.com hooks
for more information, see https://pre-commit.ci
* Update backtracking/power_sum.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: Tianyi Zheng <tianyizheng02@gmail.com>
* Replacing the generator with numpy vector operations from lu_decomposition.
* Revert "Replacing the generator with numpy vector operations from lu_decomposition."
This reverts commit ad217c6616.
* Replacing the example in doctest with a less resource-intensive example.
2023-10-10 00:16:02 -04:00
Abul Hasanandpre-commit-ci[bot] <66853113+pre-commit-ci[bot]@users.noreply.github.com>
* Fix: Issue 9588
* Fix: Issue 9588
* [pre-commit.ci] auto fixes from pre-commit.com hooks
for more information, see https://pre-commit.ci
* Fix: Issue 9588
* Fix: Issue #9588
* [pre-commit.ci] auto fixes from pre-commit.com hooks
for more information, see https://pre-commit.ci
* Fix: Issue #9588
* [pre-commit.ci] auto fixes from pre-commit.com hooks
for more information, see https://pre-commit.ci
* Fix: Issue #9588
* [pre-commit.ci] auto fixes from pre-commit.com hooks
for more information, see https://pre-commit.ci
* fix: issue #9793
* fix: issue #9793
* fix: issue #9588
* [pre-commit.ci] auto fixes from pre-commit.com hooks
for more information, see https://pre-commit.ci
* fix: issue #9844
* [pre-commit.ci] auto fixes from pre-commit.com hooks
for more information, see https://pre-commit.ci
* fix: issue #9844
* [pre-commit.ci] auto fixes from pre-commit.com hooks
for more information, see https://pre-commit.ci
* fix: issue #9844
* [pre-commit.ci] auto fixes from pre-commit.com hooks
for more information, see https://pre-commit.ci
* fix: issue #9844
* [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>
* UPDATED rat_in_maze.py
* Update reddit.py in Webprogramming b/c it was causing error in pre-commit tests while raising PR.
* UPDATED rat_in_maze.py
* fixed return type to only maze,otherwise raise valueError.
* fixed whitespaces error,improved matrix visual.
* [pre-commit.ci] auto fixes from pre-commit.com hooks
for more information, see https://pre-commit.ci
* updated.
* Try
* updated
* updated
* Apply suggestions from code review
---------
Co-authored-by: pre-commit-ci[bot] <66853113+pre-commit-ci[bot]@users.noreply.github.com>
Co-authored-by: Christian Clauss <cclauss@me.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>
* Add powersum problem
* Add doctest
* [pre-commit.ci] auto fixes from pre-commit.com hooks
for more information, see https://pre-commit.ci
* Add more doctests
* [pre-commit.ci] auto fixes from pre-commit.com hooks
for more information, see https://pre-commit.ci
* Add more doctests
* Improve paramater name
* Fix line too long
* Remove global variables
* Apply suggestions from code review
* Apply suggestions from code review
---------
Co-authored-by: pre-commit-ci[bot] <66853113+pre-commit-ci[bot]@users.noreply.github.com>
Co-authored-by: Christian Clauss <cclauss@me.com>
* pre-commit: Upgrade psf/black for stable style 2023
Updating https://github.com/psf/black ... updating 22.12.0 -> 23.1.0 for their `2023 stable style`.
* https://github.com/psf/black/blob/main/CHANGES.md#2310
> This is the first [psf/black] release of 2023, and following our stability policy, it comes with a number of improvements to our stable style…
Also, add https://github.com/tox-dev/pyproject-fmt and https://github.com/abravalheri/validate-pyproject to pre-commit.
I only modified `.pre-commit-config.yaml` and all other files were modified by pre-commit.ci and psf/black.
* [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 backtracking word search
* updating DIRECTORY.md
* [pre-commit.ci] auto fixes from pre-commit.com hooks
for more information, see https://pre-commit.ci
* review notes fixes
* additional fixes
* add tests
* small cleanup
* [pre-commit.ci] auto fixes from pre-commit.com hooks
for more information, see https://pre-commit.ci
* small cleanup 2
* [pre-commit.ci] auto fixes from pre-commit.com hooks
for more information, see https://pre-commit.ci
* Update backtracking/word_search.py
Co-authored-by: Christian Clauss <cclauss@me.com>
* Update backtracking/word_search.py
Co-authored-by: Christian Clauss <cclauss@me.com>
* Update backtracking/word_search.py
Co-authored-by: Christian Clauss <cclauss@me.com>
* Update backtracking/word_search.py
Co-authored-by: Christian Clauss <cclauss@me.com>
Co-authored-by: github-actions <${GITHUB_ACTOR}@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>
* Create minmax.py
* Update minmax.py
* [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>
