sgreen solutions to challenge 346

3 files changed, 132 insertions, 0 deletions

diff --git a/challenge-346/sgreen/python/ch-1.py b/challenge-346/sgreen/python/ch-1.py
new file mode 100755
index 0000000000..c755993dbf
--- /dev/null
+++ b/challenge-346/sgreen/python/ch-1.py
@@ -0,0 +1,53 @@
+#!/usr/bin/env python3
+
+import re
+import sys
+
+
+def is_balanced(s: str) -> bool:
+    """Check if a string of parentheses is balanced.
+
+    Args:
+        s (str): A string consisting of '(' and ')'.
+
+    Returns:
+        bool: True if the string is balanced, False otherwise.
+    """
+    count = 0
+    for char in s:
+        if char == '(':
+            count += 1
+        elif char == ')':
+            if count == 0:
+                return False
+            count -= 1
+    return count == 0
+
+def longest_parenthesis(input_string: str) -> int:
+    """Return the length of the longest balanced parentheses substring.
+
+    Args:
+        input_string (str): A string consisting of '(' and ')'.
+
+    Returns:
+        int: Length of the longest balanced parentheses substring.
+    """
+    # Check the input string is only parentheses
+    if not re.search(r'^[()]+$', input_string):
+        raise ValueError("Input string must contain only parentheses")
+
+    for length in range(len(input_string), 1, -1):
+        for start in range(len(input_string) - length + 1):
+            substring = input_string[start:start + length]
+            if is_balanced(substring):
+                return length
+
+    return 0
+
+def main():
+    result = longest_parenthesis(sys.argv[1])
+    print(result)
+
+
+if __name__ == '__main__':
+    main()
diff --git a/challenge-346/sgreen/python/ch-2.py b/challenge-346/sgreen/python/ch-2.py
new file mode 100755
index 0000000000..802e538910
--- /dev/null
+++ b/challenge-346/sgreen/python/ch-2.py
@@ -0,0 +1,51 @@
+#!/usr/bin/env python3
+
+from itertools import product, zip_longest
+import re
+import sys
+
+
+def magic_expression(input_string: str | int, target: int) -> list[str]:
+    """Return all expressions formed by inserting +, -, * between digits
+    of input_string that evaluate to target.
+
+    Args:
+        input_string (str | int): A string or integer consisting of digits.
+        target (int): The target integer value.
+
+    Returns:
+        list[str]: A list of expressions that evaluate to target.
+    """
+    # Turn input into a string if it isn't already
+    input_string = str(input_string)
+    if not re.search(r'^[0-9]+$', input_string):
+        raise ValueError("Input string must contain only digits")
+
+    # Possible operators to insert between digits
+    operators = ['', '+', '-', '*']
+
+    magic_expressions = []
+
+    for ops in product(operators, repeat=len(input_string)-1):
+        expression = ''.join(
+            digit + op for digit, op in zip_longest(input_string, ops, fillvalue='')
+        )
+        if re.search(r'[\+\-\*]0\d', expression):
+            # Skip expressions with leading zeros
+            continue
+        if eval(expression) == target:
+            magic_expressions.append(expression)
+
+    return magic_expressions
+
+
+def main():
+    result = magic_expression(sys.argv[1], int(sys.argv[2]))
+    if not result:
+        print("No expressions found")
+    else:
+        print('("' + '", "'.join(result) + '")')
+
+
+if __name__ == '__main__':
+    main()
diff --git a/challenge-346/sgreen/python/test.py b/challenge-346/sgreen/python/test.py
new file mode 100755
index 0000000000..7651f10d7f
--- /dev/null
+++ b/challenge-346/sgreen/python/test.py
@@ -0,0 +1,28 @@
+#!/usr/bin/env python3
+
+import unittest
+ch_1 = __import__('ch-1')
+ch_2 = __import__('ch-2')
+
+
+class TestClass(unittest.TestCase):
+    def test_ch_1(self):
+        self.assertEqual(ch_1.longest_parenthesis('(()())'), 6)
+        self.assertEqual(ch_1.longest_parenthesis(')()())'), 4)
+        self.assertEqual(ch_1.longest_parenthesis('((()))()(((()'), 8)
+        self.assertEqual(ch_1.longest_parenthesis('))))((()('), 2)
+        self.assertEqual(ch_1.longest_parenthesis('()(()'), 2)
+
+    def test_ch_2(self):
+        self.assertEqual(ch_2.magic_expression(123, 6), ["1+2+3", "1*2*3"])
+        self.assertEqual(ch_2.magic_expression(105, 5), ["10-5", "1*0+5"])
+        self.assertEqual(ch_2.magic_expression(232, 8), ["2+3*2", "2*3+2"])
+        self.assertEqual(ch_2.magic_expression(1234, 10), ["1+2+3+4", "1*2*3+4"])
+        self.assertEqual(
+            ch_2.magic_expression(1001, 2),
+            ['1+0+0+1', '1+0-0+1', '1+0*0+1', '1-0+0+1', '1-0-0+1', '1-0*0+1']
+        )
+
+
+if __name__ == '__main__':
+    unittest.main()