From 50445dbe3f83551244d858e5d2a0a0e1a90adf75 Mon Sep 17 00:00:00 2001 From: Peter Pentchev Date: Sat, 7 Sep 2024 13:23:38 +0300 Subject: Add Peter Pentchev's Python solution to 285. --- challenge-285/ppentchev/python/.gitignore | 7 ++ .../ppentchev/python/LICENSES/BSD-2-Clause.txt | 9 ++ challenge-285/ppentchev/python/README.md | 8 ++ challenge-285/ppentchev/python/pyproject.toml | 86 +++++++++++++ .../ppentchev/python/requirements/install.txt | 2 + .../ppentchev/python/requirements/ruff.txt | 4 + .../ppentchev/python/requirements/test.txt | 6 + challenge-285/ppentchev/python/ruff-base.toml | 39 ++++++ .../python/src/perl_weekly_285/__init__.py | 3 + .../ppentchev/python/src/perl_weekly_285/change.py | 88 ++++++++++++++ .../ppentchev/python/src/perl_weekly_285/defs.py | 34 ++++++ .../ppentchev/python/src/perl_weekly_285/routes.py | 50 ++++++++ .../ppentchev/python/tests/unit/__init__.py | 3 + .../ppentchev/python/tests/unit/test_change.py | 133 +++++++++++++++++++++ .../ppentchev/python/tests/unit/test_metadata.py | 21 ++++ .../ppentchev/python/tests/unit/test_routes.py | 73 +++++++++++ challenge-285/ppentchev/python/tox.ini | 106 ++++++++++++++++ 17 files changed, 672 insertions(+) create mode 100644 challenge-285/ppentchev/python/.gitignore create mode 100644 challenge-285/ppentchev/python/LICENSES/BSD-2-Clause.txt create mode 100644 challenge-285/ppentchev/python/README.md create mode 100644 challenge-285/ppentchev/python/pyproject.toml create mode 100644 challenge-285/ppentchev/python/requirements/install.txt create mode 100644 challenge-285/ppentchev/python/requirements/ruff.txt create mode 100644 challenge-285/ppentchev/python/requirements/test.txt create mode 100644 challenge-285/ppentchev/python/ruff-base.toml create mode 100644 challenge-285/ppentchev/python/src/perl_weekly_285/__init__.py create mode 100644 challenge-285/ppentchev/python/src/perl_weekly_285/change.py create mode 100644 challenge-285/ppentchev/python/src/perl_weekly_285/defs.py create mode 100644 challenge-285/ppentchev/python/src/perl_weekly_285/routes.py create mode 100644 challenge-285/ppentchev/python/tests/unit/__init__.py create mode 100644 challenge-285/ppentchev/python/tests/unit/test_change.py create mode 100644 challenge-285/ppentchev/python/tests/unit/test_metadata.py create mode 100644 challenge-285/ppentchev/python/tests/unit/test_routes.py create mode 100644 challenge-285/ppentchev/python/tox.ini (limited to 'challenge-285/ppentchev/python') diff --git a/challenge-285/ppentchev/python/.gitignore b/challenge-285/ppentchev/python/.gitignore new file mode 100644 index 0000000000..05f929a541 --- /dev/null +++ b/challenge-285/ppentchev/python/.gitignore @@ -0,0 +1,7 @@ +# SPDX-FileCopyrightText: Peter Pentchev +# SPDX-License-Identifier: BSD-2-Clause + +site/ +.tox/ + +**/__pycache__/ diff --git a/challenge-285/ppentchev/python/LICENSES/BSD-2-Clause.txt b/challenge-285/ppentchev/python/LICENSES/BSD-2-Clause.txt new file mode 100644 index 0000000000..5f662b354c --- /dev/null +++ b/challenge-285/ppentchev/python/LICENSES/BSD-2-Clause.txt @@ -0,0 +1,9 @@ +Copyright (c) + +Redistribution and use in source and binary forms, with or without modification, are permitted provided that the following conditions are met: + +1. Redistributions of source code must retain the above copyright notice, this list of conditions and the following disclaimer. + +2. Redistributions in binary form must reproduce the above copyright notice, this list of conditions and the following disclaimer in the documentation and/or other materials provided with the distribution. + +THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. diff --git a/challenge-285/ppentchev/python/README.md b/challenge-285/ppentchev/python/README.md new file mode 100644 index 0000000000..6ee66a9ba8 --- /dev/null +++ b/challenge-285/ppentchev/python/README.md @@ -0,0 +1,8 @@ + + +# perl-weekly-285 - task solutions + +These are Peter Pentchev's solutions to the Perl weekly challenge 285. diff --git a/challenge-285/ppentchev/python/pyproject.toml b/challenge-285/ppentchev/python/pyproject.toml new file mode 100644 index 0000000000..d09bf621ca --- /dev/null +++ b/challenge-285/ppentchev/python/pyproject.toml @@ -0,0 +1,86 @@ +# SPDX-FileCopyrightText: Peter Pentchev +# SPDX-License-Identifier: BSD-2-Clause + +[build-system] +requires = [ + "hatchling >= 1.8, < 2", + "hatch-requirements-txt >= 0.3, < 0.5", +] +build-backend = "hatchling.build" + +[project] +name = "perl-weekly-285" +description = "Parse an expression for selecting stages and tags" +readme = "README.md" +license = {text = "BSD-2-Clause"} +requires-python = ">= 3.11" +dynamic = ["dependencies", "version"] +classifiers = [ + "Development Status :: 5 - Production/Stable", + "Intended Audience :: Developers", + "License :: DFSG approved", + "License :: Freely Distributable", + "License :: OSI Approved :: BSD License", + "Operating System :: OS Independent", + "Programming Language :: Python", + "Programming Language :: Python :: 3", + "Programming Language :: Python :: 3 :: Only", + "Programming Language :: Python :: 3.11", + "Programming Language :: Python :: 3.12", + "Programming Language :: Python :: 3.13", + "Topic :: Software Development :: Libraries", + "Topic :: Software Development :: Libraries :: Python Modules", + "Topic :: Software Development :: Testing", + "Topic :: Software Development :: Testing :: Unit", + "Typing :: Typed", +] + +[[project.authors]] +name = "Peter Pentchev" +email = "roam@ringlet.net" + +[project.scripts] +"perl-weekly-285" = "perl_weekly_285.__main__:main" + +[project.urls] +Homepage = "https://devel.ringlet.net/misc/perl-weekly-285/" +Changes = "https://devel.ringlet.net/misc/perl-weekly-285/changes/" +"Issue Tracker" = "https://gitlab.com/ppentchev/perl-weekly-285/-/issues" +"Source Code" = "https://gitlab.com/ppentchev/perl-weekly-285" + +[tool.hatch.build.targets.wheel] +packages = ["src/perl_weekly_285"] + +[tool.hatch.metadata.hooks.requirements_txt] +files = ["requirements/install.txt"] + +[tool.hatch.version] +path = "src/perl_weekly_285/defs.py" +pattern = '(?x) ^ VERSION \s* (?: : \s* Final \s* )? = \s* " (?P [^\s"]+ ) " \s* $' + +[tool.mypy] +strict = true + +[tool.publync.format.version] +major = 0 +minor = 1 + +[tool.publync.build.tox] + +[tool.publync.sync.rsync] +remote = "marla.ludost.net:vhosts/devel.ringlet.net/public_html/misc/perl-weekly-285" + +[tool.ruff] +extend = "ruff-base.toml" +output-format = "concise" +preview = true + +[tool.ruff.lint] +select = ["ALL"] + +[tool.test-stages] +stages = [ + "(@check or @docs) and @quick and not @manual", + "(@check or @docs) and not @manual", + "@tests and not @manual", +] diff --git a/challenge-285/ppentchev/python/requirements/install.txt b/challenge-285/ppentchev/python/requirements/install.txt new file mode 100644 index 0000000000..eb4185e66d --- /dev/null +++ b/challenge-285/ppentchev/python/requirements/install.txt @@ -0,0 +1,2 @@ +# SPDX-FileCopyrightText: Peter Pentchev +# SPDX-License-Identifier: BSD-2-Clause diff --git a/challenge-285/ppentchev/python/requirements/ruff.txt b/challenge-285/ppentchev/python/requirements/ruff.txt new file mode 100644 index 0000000000..1c69e31418 --- /dev/null +++ b/challenge-285/ppentchev/python/requirements/ruff.txt @@ -0,0 +1,4 @@ +# SPDX-FileCopyrightText: Peter Pentchev +# SPDX-License-Identifier: BSD-2-Clause + +ruff == 0.6.4 diff --git a/challenge-285/ppentchev/python/requirements/test.txt b/challenge-285/ppentchev/python/requirements/test.txt new file mode 100644 index 0000000000..01f71935cf --- /dev/null +++ b/challenge-285/ppentchev/python/requirements/test.txt @@ -0,0 +1,6 @@ +# SPDX-FileCopyrightText: Peter Pentchev +# SPDX-License-Identifier: BSD-2-Clause + +packaging >= 21.3, < 24 +pygments >= 2.7, < 3 +pytest >= 7, < 9 diff --git a/challenge-285/ppentchev/python/ruff-base.toml b/challenge-285/ppentchev/python/ruff-base.toml new file mode 100644 index 0000000000..a76ef30a2e --- /dev/null +++ b/challenge-285/ppentchev/python/ruff-base.toml @@ -0,0 +1,39 @@ +# SPDX-FileCopyrightText: Peter Pentchev +# SPDX-License-Identifier: BSD-2-Clause + +target-version = "py311" +line-length = 100 + +[lint] +select = [] +ignore = [ + # No blank lines before the class docstring, TYVM + "D203", + + # The multi-line docstring summary starts on the same line + "D213", + + # We do not document everything in the docstring + "DOC201", + "DOC402", + "DOC501", + + # The /x regex modifier is common enough in many languages + "FURB167", +] + +[lint.flake8-copyright] +notice-rgx = "(?x) SPDX-FileCopyrightText: \\s \\S" + +[lint.isort] +force-single-line = true +known-first-party = ["perl_weekly_285"] +lines-after-imports = 2 +single-line-exclusions = ["collections.abc", "typing"] + +[lint.per-file-ignores] +# This is a command-line tool; console output is part of its job. +"src/perl_weekly_285/__main__.py" = ["T201"] + +# This is a test suite +"tests/unit/**.py" = ["S101", "T201"] diff --git a/challenge-285/ppentchev/python/src/perl_weekly_285/__init__.py b/challenge-285/ppentchev/python/src/perl_weekly_285/__init__.py new file mode 100644 index 0000000000..39cb6886dc --- /dev/null +++ b/challenge-285/ppentchev/python/src/perl_weekly_285/__init__.py @@ -0,0 +1,3 @@ +# SPDX-FileCopyrightText: Peter Pentchev +# SPDX-License-Identifier: BSD-2-Clause +"""Solve the tasks in Perl weekly challenge 285.""" diff --git a/challenge-285/ppentchev/python/src/perl_weekly_285/change.py b/challenge-285/ppentchev/python/src/perl_weekly_285/change.py new file mode 100644 index 0000000000..d2cc783794 --- /dev/null +++ b/challenge-285/ppentchev/python/src/perl_weekly_285/change.py @@ -0,0 +1,88 @@ +# SPDX-FileCopyrightText: Peter Pentchev +# SPDX-License-Identifier: BSD-2-Clause +"""Solve the second task in Perl weekly challenge 285, "Making Change".""" + +from __future__ import annotations + +import enum +import itertools +import typing + + +if typing.TYPE_CHECKING: + from typing import Final + + +class Coin(enum.IntEnum): + """A single denomination for breaking change down.""" + + PENNY = 1 + NICKEL = 5 + DIME = 10 + QUARTER = 25 + HALF_DOLLAR = 50 + + def lower(self) -> Coin: + """Return the next lower denomination.""" + match self: + case value if value == Coin.PENNY: + raise RuntimeError(repr(self)) + + case value if value == Coin.NICKEL: + return Coin.PENNY + + case value if value == Coin.DIME: + return Coin.NICKEL + + case value if value == Coin.QUARTER: + return Coin.DIME + + case value if value == Coin.HALF_DOLLAR: + return Coin.QUARTER + + +_ORDER_ABP: Final = [Coin.HALF_DOLLAR, Coin.QUARTER, Coin.DIME, Coin.NICKEL] +"""The denominations in descending order.""" + + +def break_down_ways(amount: int, highest: Coin) -> list[tuple[int, Coin]]: + """Make sure of things and stuff.""" + + def process_single(high: Coin) -> list[tuple[int, Coin]]: + """Get the candidates if we use this coin.""" + lower: Final = high.lower() + return [(amount - mult, lower) for mult in range(high, amount + 1, high)] + + return list(itertools.chain(*(process_single(high) for high in _ORDER_ABP if high <= highest))) + + +def make_change_rec(amount: int, highest: Coin, cache: dict[tuple[int, Coin], int]) -> int: + """Let me count the ways, recursively.""" + + def trivial(amt: int, high: Coin) -> bool: + """Sometimes there is only one.""" + return amt == 0 or high == Coin.PENNY + + if trivial(amount, highest): + return 1 + + cached: Final = cache.get((amount, highest)) + if cached is not None: + return cached + + def process_single(amt: int, high: Coin) -> int: + """Recursively count fewer ways.""" + if trivial(amt, high): + return 1 + + return make_change_rec(amt, high, cache) + + ways: Final = break_down_ways(amount, highest) + total: Final = 1 + sum(itertools.starmap(process_single, ways)) + cache[amount, highest] = total + return total + + +def solve_making_change(amount: int) -> int: + """Let me count the ways.""" + return make_change_rec(amount, Coin.HALF_DOLLAR, {}) diff --git a/challenge-285/ppentchev/python/src/perl_weekly_285/defs.py b/challenge-285/ppentchev/python/src/perl_weekly_285/defs.py new file mode 100644 index 0000000000..26d7ea59c6 --- /dev/null +++ b/challenge-285/ppentchev/python/src/perl_weekly_285/defs.py @@ -0,0 +1,34 @@ +# SPDX-FileCopyrightText: Peter Pentchev +# SPDX-License-Identifier: BSD-2-Clause +"""Common definitions for the perl-weekly-285 library.""" + +from __future__ import annotations + +import dataclasses +import typing + + +if typing.TYPE_CHECKING: + from typing import Final + + +VERSION: Final = "0.1.0" +"""The perl-weekly-285 library version, semver-like.""" + + +@dataclasses.dataclass +class Error(Exception): + """An error that occurred during the processing.""" + + def __str__(self) -> str: + """Provide a human-readable error message.""" + return f"{type(self).__str__} must be overridden for {self!r}" + + +@dataclasses.dataclass +class NoSolutionError(Error): + """No solution could be found.""" + + def __str__(self) -> str: + """Provide a human-readable error message.""" + return f"Could not find a solution: {self!r}" diff --git a/challenge-285/ppentchev/python/src/perl_weekly_285/routes.py b/challenge-285/ppentchev/python/src/perl_weekly_285/routes.py new file mode 100644 index 0000000000..51e19e556e --- /dev/null +++ b/challenge-285/ppentchev/python/src/perl_weekly_285/routes.py @@ -0,0 +1,50 @@ +# SPDX-FileCopyrightText: Peter Pentchev +# SPDX-License-Identifier: BSD-2-Clause +"""Solve the first task in Perl weekly challenge 285, "No Connection".""" + +from __future__ import annotations + +import dataclasses +import typing + +from . import defs + + +if typing.TYPE_CHECKING: + from typing import Final + + +@dataclasses.dataclass +class NoLeafError(defs.NoSolutionError): + """No leaf destinations at all.""" + + def __str__(self) -> str: + """Provide a human-readable error message.""" + return "No leaf destinations could be found" + + +@dataclasses.dataclass +class MultipleLeavesError(defs.NoSolutionError): + """More than one leaf destination.""" + + multiple: list[str] + """The leaf destinations found.""" + + def __str__(self) -> str: + """Provide a human-readable error message.""" + return f"Multiple leaf destinations found: {self.multiple!r}" + + +def solve_no_connection(routes: list[tuple[str, str]]) -> str: + """Solve the first task, "No Connection.""" + loc_from: Final = {item[0] for item in routes} + loc_to: Final = {item[1] for item in routes} + match sorted(loc_to - loc_from): + case []: + raise NoLeafError + + case [single]: + return single + + case multiple: + raise MultipleLeavesError(multiple) diff --git a/challenge-285/ppentchev/python/tests/unit/__init__.py b/challenge-285/ppentchev/python/tests/unit/__init__.py new file mode 100644 index 0000000000..2fcf8ce229 --- /dev/null +++ b/challenge-285/ppentchev/python/tests/unit/__init__.py @@ -0,0 +1,3 @@ +# SPDX-FileCopyrightText: Peter Pentchev +# SPDX-License-Identifier: BSD-2-Clause +"""Unit tests for the Perl weekly challenge 285 solutions.""" diff --git a/challenge-285/ppentchev/python/tests/unit/test_change.py b/challenge-285/ppentchev/python/tests/unit/test_change.py new file mode 100644 index 0000000000..e93bbe0286 --- /dev/null +++ b/challenge-285/ppentchev/python/tests/unit/test_change.py @@ -0,0 +1,133 @@ +# SPDX-FileCopyrightText: Peter Pentchev +# SPDX-License-Identifier: BSD-2-Clause +"""Test the second task in Perl weekly challenge 285, "Making Change".""" + +from __future__ import annotations + +import dataclasses + +import pytest + +from perl_weekly_285 import change + + +@dataclasses.dataclass(frozen=True) +class BreakDownWaysCase: + """A test case for the "No Connection" task.""" + + amount: int + """The amount to break down.""" + + highest: change.Coin + """The highest coin to use for this amount.""" + + expected: list[tuple[int, change.Coin]] + """The ways to break this amount down into smaller chunks.""" + + +@pytest.mark.parametrize( + "tcase", + [ + BreakDownWaysCase(amount=1, highest=change.Coin.HALF_DOLLAR, expected=[]), + BreakDownWaysCase(amount=2, highest=change.Coin.HALF_DOLLAR, expected=[]), + BreakDownWaysCase( + amount=6, + highest=change.Coin.HALF_DOLLAR, + expected=[(1, change.Coin.PENNY)], + ), + BreakDownWaysCase(amount=6, highest=change.Coin.NICKEL, expected=[(1, change.Coin.PENNY)]), + BreakDownWaysCase(amount=6, highest=change.Coin.PENNY, expected=[]), + BreakDownWaysCase( + amount=7, + highest=change.Coin.HALF_DOLLAR, + expected=[(2, change.Coin.PENNY)], + ), + BreakDownWaysCase(amount=7, highest=change.Coin.NICKEL, expected=[(2, change.Coin.PENNY)]), + BreakDownWaysCase(amount=7, highest=change.Coin.PENNY, expected=[]), + BreakDownWaysCase( + amount=10, + highest=change.Coin.HALF_DOLLAR, + expected=[(0, change.Coin.NICKEL), (5, change.Coin.PENNY), (0, change.Coin.PENNY)], + ), + BreakDownWaysCase( + amount=10, + highest=change.Coin.DIME, + expected=[(0, change.Coin.NICKEL), (5, change.Coin.PENNY), (0, change.Coin.PENNY)], + ), + BreakDownWaysCase( + amount=10, + highest=change.Coin.NICKEL, + expected=[(5, change.Coin.PENNY), (0, change.Coin.PENNY)], + ), + BreakDownWaysCase(amount=10, highest=change.Coin.PENNY, expected=[]), + BreakDownWaysCase( + amount=12, + highest=change.Coin.HALF_DOLLAR, + expected=[(2, change.Coin.NICKEL), (7, change.Coin.PENNY), (2, change.Coin.PENNY)], + ), + BreakDownWaysCase( + amount=12, + highest=change.Coin.DIME, + expected=[(2, change.Coin.NICKEL), (7, change.Coin.PENNY), (2, change.Coin.PENNY)], + ), + BreakDownWaysCase( + amount=12, + highest=change.Coin.NICKEL, + expected=[(7, change.Coin.PENNY), (2, change.Coin.PENNY)], + ), + BreakDownWaysCase(amount=12, highest=change.Coin.PENNY, expected=[]), + BreakDownWaysCase( + amount=15, + highest=change.Coin.HALF_DOLLAR, + expected=[ + (5, change.Coin.NICKEL), + (10, change.Coin.PENNY), + (5, change.Coin.PENNY), + (0, change.Coin.PENNY), + ], + ), + BreakDownWaysCase( + amount=15, + highest=change.Coin.DIME, + expected=[ + (5, change.Coin.NICKEL), + (10, change.Coin.PENNY), + (5, change.Coin.PENNY), + (0, change.Coin.PENNY), + ], + ), + BreakDownWaysCase( + amount=15, + highest=change.Coin.NICKEL, + expected=[(10, change.Coin.PENNY), (5, change.Coin.PENNY), (0, change.Coin.PENNY)], + ), + BreakDownWaysCase(amount=15, highest=change.Coin.PENNY, expected=[]), + ], +) +def test_break_down_ways(*, tcase: BreakDownWaysCase) -> None: + """Make sure we can find the leaf destination.""" + assert change.break_down_ways(tcase.amount, tcase.highest) == tcase.expected + + +@dataclasses.dataclass(frozen=True) +class MakeChangeCase: + """A test case for the actual "how many ways can we break this down" function.""" + + amount: int + """The amount to break down.""" + + expected: int + """The expected number of ways.""" + + +@pytest.mark.parametrize( + "tcase", + [ + MakeChangeCase(amount=9, expected=2), + MakeChangeCase(amount=15, expected=6), + MakeChangeCase(amount=100, expected=292), + ], +) +def test_make_change(tcase: MakeChangeCase) -> None: + """Make sure we can count the ways.""" + assert change.solve_making_change(tcase.amount) == tcase.expected diff --git a/challenge-285/ppentchev/python/tests/unit/test_metadata.py b/challenge-285/ppentchev/python/tests/unit/test_metadata.py new file mode 100644 index 0000000000..e957790fba --- /dev/null +++ b/challenge-285/ppentchev/python/tests/unit/test_metadata.py @@ -0,0 +1,21 @@ +# SPDX-FileCopyrightText: Peter Pentchev +# SPDX-License-Identifier: BSD-2-Clause +"""Basic test for file importing.""" + +from __future__ import annotations + +import typing + +from packaging import version as pkg_version + +from perl_weekly_285 import defs + + +if typing.TYPE_CHECKING: + from typing import Final + + +def test_version() -> None: + """Make sure the `VERSION` variable has a sane value.""" + version: Final = pkg_version.Version(defs.VERSION) + assert version > pkg_version.Version("0") diff --git a/challenge-285/ppentchev/python/tests/unit/test_routes.py b/challenge-285/ppentchev/python/tests/unit/test_routes.py new file mode 100644 index 0000000000..743e0d20d2 --- /dev/null +++ b/challenge-285/ppentchev/python/tests/unit/test_routes.py @@ -0,0 +1,73 @@ +# SPDX-FileCopyrightText: Peter Pentchev +# SPDX-License-Identifier: BSD-2-Clause +"""Test the first task in Perl weekly challenge 285, "No Connection".""" + +from __future__ import annotations + +import dataclasses + +import pytest + +from perl_weekly_285 import defs +from perl_weekly_285 import routes + + +@dataclasses.dataclass(frozen=True) +class RoutesCase: + """A test case for the "No Connection" task.""" + + routes: list[tuple[str, str]] + """The routes to examine.""" + + expected: str + """The leaf destination we expect to find.""" + + +@pytest.mark.parametrize( + "tcase", + [ + RoutesCase( + routes=[ + ("me", "you"), + ], + expected="you", + ), + RoutesCase( + routes=[ + ("here", "there"), + ("here", "everywhere"), + ("there", "everywhere"), + ], + expected="everywhere", + ), + RoutesCase( + routes=[("B", "C"), ("D", "B"), ("C", "A")], + expected="A", + ), + ], +) +def test_connection(*, tcase: RoutesCase) -> None: + """Make sure we can find the leaf destination.""" + assert routes.solve_no_connection(tcase.routes) == tcase.expected + + +@pytest.mark.parametrize( + "tcase", + [ + RoutesCase( + routes=[ + ("here", "there"), + ("here", "everywhere"), + ], + expected="not really", + ), + RoutesCase( + routes=[("me", "you"), ("you", "me")], + expected="not really", + ), + ], +) +def test_no_connection(*, tcase: RoutesCase) -> None: + """Make sure we cannot find any leaf destination.""" + with pytest.raises(defs.NoSolutionError): + routes.solve_no_connection(tcase.routes) diff --git a/challenge-285/ppentchev/python/tox.ini b/challenge-285/ppentchev/python/tox.ini new file mode 100644 index 0000000000..3c90abab52 --- /dev/null +++ b/challenge-285/ppentchev/python/tox.ini @@ -0,0 +1,106 @@ +# SPDX-FileCopyrightText: Peter Pentchev +# SPDX-License-Identifier: BSD-2-Clause + +[tox] +minversion = 4.1 +envlist = + ruff + format + reuse + mypy + unit-tests-pytest-7 + unit-tests-pytest-8 +isolated_build = True + +[defs] +pyfiles = + src/perl_weekly_285 \ + tests/unit + +[testenv:ruff] +skip_install = True +tags = + check + ruff + quick +deps = + -r requirements/ruff.txt +commands = + ruff check -- {[defs]pyfiles} + +[testenv:format] +skip_install = True +tags = + check + quick +deps = + -r requirements/ruff.txt +commands = + ruff check --config ruff-base.toml --select=D,I --diff -- {[defs]pyfiles} + ruff format --config ruff-base.toml --check --diff -- {[defs]pyfiles} + +[testenv:reformat] +skip_install = True +tags = + format + manual +deps = + -r requirements/ruff.txt +commands = + ruff check --config ruff-base.toml --select=D,I --fix -- {[defs]pyfiles} + ruff format --config ruff-base.toml -- {[defs]pyfiles} + +[testenv:mypy] +skip_install = True +tags = + check +deps = + -r requirements/install.txt + -r requirements/test.txt + mypy >= 1, < 2 +setenv = + MYPYPATH = {toxinidir}/stubs +commands = + mypy {[defs]pyfiles} + +[testenv:pyupgrade] +skip_install = True +tags = + check + manual +deps = + pyupgrade >= 3, < 4 +allowlist_externals = + sh +commands = + sh -c 'pyupgrade --py311-plus src/perl_weekly_285/*.py tests/unit/*.py' + +[testenv:unit-tests-pytest-7] +tags = + tests +deps = + -r requirements/install.txt + -r requirements/test.txt + pytest < 8 +commands = + pytest {posargs} tests/unit + +[testenv:unit-tests-pytest-8] +tags = + tests +deps = + -r requirements/install.txt + -r requirements/test.txt + pytest >= 8 +commands = + pytest {posargs} tests/unit + +[testenv:reuse] +skip_install = True +tags = + check + quick +deps = + reuse >= 4, < 5 +commands = + reuse --root . lint -- cgit From 2c5cab7c611241e0d85eebc4e5e6d89830b7c80b Mon Sep 17 00:00:00 2001 From: Mohammad Sajid Anwar Date: Sun, 8 Sep 2024 11:15:05 +0100 Subject: - Added solutions by Matthias Muth. - Added solutions by Peter Pentchev. --- .../ppentchev/python/src/perl_weekly_285/ch-1.py | 50 ++++++++++++ .../ppentchev/python/src/perl_weekly_285/ch-2.py | 88 ++++++++++++++++++++++ 2 files changed, 138 insertions(+) create mode 100644 challenge-285/ppentchev/python/src/perl_weekly_285/ch-1.py create mode 100644 challenge-285/ppentchev/python/src/perl_weekly_285/ch-2.py (limited to 'challenge-285/ppentchev/python') diff --git a/challenge-285/ppentchev/python/src/perl_weekly_285/ch-1.py b/challenge-285/ppentchev/python/src/perl_weekly_285/ch-1.py new file mode 100644 index 0000000000..51e19e556e --- /dev/null +++ b/challenge-285/ppentchev/python/src/perl_weekly_285/ch-1.py @@ -0,0 +1,50 @@ +# SPDX-FileCopyrightText: Peter Pentchev +# SPDX-License-Identifier: BSD-2-Clause +"""Solve the first task in Perl weekly challenge 285, "No Connection".""" + +from __future__ import annotations + +import dataclasses +import typing + +from . import defs + + +if typing.TYPE_CHECKING: + from typing import Final + + +@dataclasses.dataclass +class NoLeafError(defs.NoSolutionError): + """No leaf destinations at all.""" + + def __str__(self) -> str: + """Provide a human-readable error message.""" + return "No leaf destinations could be found" + + +@dataclasses.dataclass +class MultipleLeavesError(defs.NoSolutionError): + """More than one leaf destination.""" + + multiple: list[str] + """The leaf destinations found.""" + + def __str__(self) -> str: + """Provide a human-readable error message.""" + return f"Multiple leaf destinations found: {self.multiple!r}" + + +def solve_no_connection(routes: list[tuple[str, str]]) -> str: + """Solve the first task, "No Connection.""" + loc_from: Final = {item[0] for item in routes} + loc_to: Final = {item[1] for item in routes} + match sorted(loc_to - loc_from): + case []: + raise NoLeafError + + case [single]: + return single + + case multiple: + raise MultipleLeavesError(multiple) diff --git a/challenge-285/ppentchev/python/src/perl_weekly_285/ch-2.py b/challenge-285/ppentchev/python/src/perl_weekly_285/ch-2.py new file mode 100644 index 0000000000..d2cc783794 --- /dev/null +++ b/challenge-285/ppentchev/python/src/perl_weekly_285/ch-2.py @@ -0,0 +1,88 @@ +# SPDX-FileCopyrightText: Peter Pentchev +# SPDX-License-Identifier: BSD-2-Clause +"""Solve the second task in Perl weekly challenge 285, "Making Change".""" + +from __future__ import annotations + +import enum +import itertools +import typing + + +if typing.TYPE_CHECKING: + from typing import Final + + +class Coin(enum.IntEnum): + """A single denomination for breaking change down.""" + + PENNY = 1 + NICKEL = 5 + DIME = 10 + QUARTER = 25 + HALF_DOLLAR = 50 + + def lower(self) -> Coin: + """Return the next lower denomination.""" + match self: + case value if value == Coin.PENNY: + raise RuntimeError(repr(self)) + + case value if value == Coin.NICKEL: + return Coin.PENNY + + case value if value == Coin.DIME: + return Coin.NICKEL + + case value if value == Coin.QUARTER: + return Coin.DIME + + case value if value == Coin.HALF_DOLLAR: + return Coin.QUARTER + + +_ORDER_ABP: Final = [Coin.HALF_DOLLAR, Coin.QUARTER, Coin.DIME, Coin.NICKEL] +"""The denominations in descending order.""" + + +def break_down_ways(amount: int, highest: Coin) -> list[tuple[int, Coin]]: + """Make sure of things and stuff.""" + + def process_single(high: Coin) -> list[tuple[int, Coin]]: + """Get the candidates if we use this coin.""" + lower: Final = high.lower() + return [(amount - mult, lower) for mult in range(high, amount + 1, high)] + + return list(itertools.chain(*(process_single(high) for high in _ORDER_ABP if high <= highest))) + + +def make_change_rec(amount: int, highest: Coin, cache: dict[tuple[int, Coin], int]) -> int: + """Let me count the ways, recursively.""" + + def trivial(amt: int, high: Coin) -> bool: + """Sometimes there is only one.""" + return amt == 0 or high == Coin.PENNY + + if trivial(amount, highest): + return 1 + + cached: Final = cache.get((amount, highest)) + if cached is not None: + return cached + + def process_single(amt: int, high: Coin) -> int: + """Recursively count fewer ways.""" + if trivial(amt, high): + return 1 + + return make_change_rec(amt, high, cache) + + ways: Final = break_down_ways(amount, highest) + total: Final = 1 + sum(itertools.starmap(process_single, ways)) + cache[amount, highest] = total + return total + + +def solve_making_change(amount: int) -> int: + """Let me count the ways.""" + return make_change_rec(amount, Coin.HALF_DOLLAR, {}) -- cgit