Merge remote-tracking branch 'upstream/master'

2 files changed, 82 insertions, 0 deletions

diff --git a/challenge-216/lubos-kolouch/python/ch-1.py b/challenge-216/lubos-kolouch/python/ch-1.py
new file mode 100644
index 0000000000..c52a4df31f
--- /dev/null
+++ b/challenge-216/lubos-kolouch/python/ch-1.py
@@ -0,0 +1,22 @@
+#!/usr/bin/env python
+# -*- coding: utf-8 -*-
+
+from typing import List
+
+
+def matching_words(words: List[str], reg: str) -> List[str]:
+    reg = reg.upper()
+    letters = set(letter for letter in reg if letter.isalpha())
+    matches = []
+    for word in words:
+        upper_word = word.upper()
+        matched = all(letter in upper_word for letter in letters)
+        if matched:
+            matches.append(word)
+    return matches
+
+
+words = ['job', 'james', 'bjorg']
+reg = '007 JB'
+matches_list = matching_words(words, reg)
+print("(", ", ".join(f"'{match}'" for match in matches_list), ")")
diff --git a/challenge-216/lubos-kolouch/python/ch-2.py b/challenge-216/lubos-kolouch/python/ch-2.py
new file mode 100644
index 0000000000..9cb331adf1
--- /dev/null
+++ b/challenge-216/lubos-kolouch/python/ch-2.py
@@ -0,0 +1,60 @@
+from collections import Counter
+import sys
+
+
+def min_stickers_needed(stickers, target):
+    target_counts = Counter(target)
+    stickers_counts = [Counter(sticker) for sticker in stickers]
+
+    # Filter out stickers that don't have any characters in common with the target word
+    filtered_stickers_counts = [
+        sticker
+        for sticker in stickers_counts
+        if any(sticker[char] > 0 for char in target_counts)
+    ]
+
+    return min_stickers_helper(filtered_stickers_counts, target_counts, 0)
+
+
+def min_stickers_helper(stickers_counts, target_counts, used_stickers):
+    if not target_counts:
+        return used_stickers
+
+    min_stickers = sys.maxsize
+    for sticker_counts in stickers_counts:
+        # Try to fulfill the remaining character requirements of the target word
+        new_target_counts = target_counts.copy()
+        used_current_sticker = False
+        for char, count in sticker_counts.items():
+            if new_target_counts[char] > 0:
+                new_target_counts[char] -= count
+                if new_target_counts[char] <= 0:
+                    del new_target_counts[char]
+                used_current_sticker = True
+
+        if used_current_sticker:
+            min_stickers = min(
+                min_stickers,
+                min_stickers_helper(
+                    stickers_counts, new_target_counts, used_stickers + 1
+                ),
+            )
+
+    return min_stickers if min_stickers != sys.maxsize else 0
+
+
+stickers = ["perl", "raku", "python"]
+word = "peon"
+print(min_stickers_needed(stickers, word))  # Output: 2
+
+stickers = ["love", "hate", "angry"]
+word = "goat"
+print(min_stickers_needed(stickers, word))  # Output: 3
+
+stickers = ["come", "nation", "delta"]
+word = "accommodation"
+print(min_stickers_needed(stickers, word))  # Output: 4
+
+stickers = ["come", "country", "delta"]
+word = "accommodation"
+print(min_stickers_needed(stickers, word))  # Output: -1