Merge pull request #10788 from ppentchev/pp-285-python

Add Peter Pentchev's Python solution to 285.

4 files changed, 175 insertions, 0 deletions

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 <roam@ringlet.net>
+# 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 <roam@ringlet.net>
+# 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 <roam@ringlet.net>
+# 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 <roam@ringlet.net>
+# 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)