Merge pull request #11496 from LubosKolouch/master

Challenge 306 LK Perl Python

8 files changed, 436 insertions, 0 deletions

diff --git a/challenge-304/lubos-kolouch/perl/ch-1.pl b/challenge-304/lubos-kolouch/perl/ch-1.pl
new file mode 100644
index 0000000000..ca1e29e2ff
--- /dev/null
+++ b/challenge-304/lubos-kolouch/perl/ch-1.pl
@@ -0,0 +1,42 @@
+#!/usr/bin/env perl
+use strict;
+use warnings;
+use Test::More;
+
+# Function to check if binary digits can be arranged
+sub can_arrange_binary {
+    my ( $digits_ref, $n ) = @_;
+
+    # Count existing ones
+    my $ones_count = grep { $_ == 1 } @$digits_ref;
+
+    # Calculate maximum possible ones that can be placed without being adjacent
+    my $max_possible_ones = int( ( scalar(@$digits_ref) + 1 ) / 2 );
+
+    # Calculate total ones after adding n more
+    my $total_ones = $ones_count + $n;
+
+    # Return true if total ones needed doesn't exceed maximum possible ones
+    return $total_ones <= $max_possible_ones;
+}
+
+# Tests
+subtest 'Example cases' => sub {
+    ok( can_arrange_binary( [ 1,  0, 0, 0, 1 ], 1 ), 'Example 1 returns true' );
+    ok( !can_arrange_binary( [ 1, 0, 0, 0, 1 ], 2 ),
+        'Example 2 returns false' );
+};
+
+subtest 'Edge cases' => sub {
+    ok( can_arrange_binary( [],  0 ), 'Empty array works' );
+    ok( can_arrange_binary( [0], 1 ), 'Single zero with n=1 works' );
+    ok( can_arrange_binary( [1], 0 ), 'Single one with n=0 works' );
+};
+
+subtest 'Additional cases' => sub {
+    ok( can_arrange_binary( [ 0,  0, 0, 0 ], 2 ), 'All zeros with n=2 works' );
+    ok( !can_arrange_binary( [ 0, 0, 0, 0 ], 3 ), 'All zeros with n=3 fails' );
+    ok( !can_arrange_binary( [ 1, 1, 1, 1 ], 0 ), 'All ones fails' );
+};
+
+done_testing();
diff --git a/challenge-304/lubos-kolouch/perl/ch-2.pl b/challenge-304/lubos-kolouch/perl/ch-2.pl
new file mode 100644
index 0000000000..46a8cac6f9
--- /dev/null
+++ b/challenge-304/lubos-kolouch/perl/ch-2.pl
@@ -0,0 +1,48 @@
+#!/usr/bin/env perl
+use strict;
+use warnings;
+use Test::More;
+
+# Function to find maximum average of contiguous subarray
+sub find_max_average {
+    my ( $nums_ref, $n ) = @_;
+
+    die "Invalid input: n must be <= length of nums and nums must not be empty"
+      if !@$nums_ref || $n > scalar(@$nums_ref);
+
+    # Calculate initial window sum
+    my $window_sum = 0;
+    $window_sum += $_ for @$nums_ref[ 0 .. ( $n - 1 ) ];
+    my $max_sum = $window_sum;
+
+    # Slide the window and update max_sum
+    for my $i ( $n .. scalar(@$nums_ref) - 1 ) {
+        $window_sum = $window_sum + $nums_ref->[$i] - $nums_ref->[ $i - $n ];
+        $max_sum    = $window_sum if $window_sum > $max_sum;
+    }
+
+    return $max_sum / $n;
+}
+
+# Tests
+subtest 'Example cases' => sub {
+    is( find_max_average( [ 1, 12, -5, -6, 50, 3 ], 4 ),
+        12.75, 'Example 1 works' );
+    is( find_max_average( [5], 1 ), 5, 'Example 2 works' );
+};
+
+subtest 'Edge cases' => sub {
+    is( find_max_average( [ 1, 2, 3 ], 3 ), 2, 'Full array works' );
+    eval { find_max_average( [], 1 ) };
+    like( $@, qr/Invalid input/, 'Empty array throws error' );
+    eval { find_max_average( [ 1, 2 ], 3 ) };
+    like( $@, qr/Invalid input/, 'n > length throws error' );
+};
+
+subtest 'Additional cases' => sub {
+    is( find_max_average( [ -1, -2, -3, -4 ], 2 ),
+        -1.5, 'Negative numbers work' );
+    is( find_max_average( [ 1, 2, 3, 4, 5 ], 2 ), 4.5, 'Decimal result works' );
+};
+
+done_testing();
diff --git a/challenge-304/lubos-kolouch/python/ch-1.py b/challenge-304/lubos-kolouch/python/ch-1.py
new file mode 100644
index 0000000000..6bee15a902
--- /dev/null
+++ b/challenge-304/lubos-kolouch/python/ch-1.py
@@ -0,0 +1,68 @@
+import unittest
+
+
+def can_arrange_binary(digits: list[int], n: int) -> bool:
+    """
+    Determine if a list of binary digits can be rearranged by replacing at least n 0s with 1s
+    such that no two consecutive digits are 1.
+
+    Args:
+        digits (List[int]): List of binary digits (0s and 1s)
+        n (int): Number of digits that must be replaced with 1
+
+    Returns:
+        bool: True if arrangement is possible, False otherwise
+
+    Examples:
+        >>> can_arrange_binary([1, 0, 0, 0, 1], 1)
+        True
+        >>> can_arrange_binary([1, 0, 0, 0, 1], 2)
+        False
+    """
+    # Count existing 1s
+    ones_count = sum(digits)
+
+    # Calculate maximum possible 1s that can be placed without being adjacent
+    max_possible_ones = (len(digits) + 1) // 2
+
+    # Calculate total 1s after adding n more
+    total_ones = ones_count + n
+
+    # If total ones needed exceeds maximum possible ones, return False
+    return total_ones <= max_possible_ones
+
+
+class TestArrangeBinary(unittest.TestCase):
+    """Test cases for the binary arrangement problem"""
+
+    def test_example_1(self):
+        """Test case from Example 1"""
+        self.assertTrue(can_arrange_binary([1, 0, 0, 0, 1], 1))
+
+    def test_example_2(self):
+        """Test case from Example 2"""
+        self.assertFalse(can_arrange_binary([1, 0, 0, 0, 1], 2))
+
+    def test_empty_list(self):
+        """Test with empty list"""
+        self.assertTrue(can_arrange_binary([], 0))
+
+    def test_single_element(self):
+        """Test with single element"""
+        self.assertTrue(can_arrange_binary([0], 1))
+        self.assertTrue(can_arrange_binary([1], 0))
+
+    def test_all_zeros(self):
+        """Test with all zeros"""
+        self.assertTrue(can_arrange_binary([0, 0, 0, 0], 2))
+        self.assertFalse(can_arrange_binary([0, 0, 0, 0], 3))
+
+    def test_all_ones(self):
+        """Test with all ones"""
+        self.assertFalse(can_arrange_binary([1, 1, 1, 1], 0))
+
+
+if __name__ == "__main__":
+    import doctest
+    doctest.testmod()
+    unittest.main(verbosity=2)
diff --git a/challenge-304/lubos-kolouch/python/ch-2.py b/challenge-304/lubos-kolouch/python/ch-2.py
new file mode 100644
index 0000000000..08b587621f
--- /dev/null
+++ b/challenge-304/lubos-kolouch/python/ch-2.py
@@ -0,0 +1,72 @@
+import unittest
+
+
+def find_max_average(nums: list[int], n: int) -> float:
+    """
+    Find the maximum average of a contiguous subarray of length n.
+
+    Args:
+        nums (List[int]): List of integers
+        n (int): Length of subarray to consider
+
+    Returns:
+        float: Maximum average of any contiguous subarray of length n
+
+    Raises:
+        ValueError: If n is greater than the length of nums or if nums is empty
+
+    Examples:
+        >>> find_max_average([1, 12, -5, -6, 50, 3], 4)
+        12.75
+        >>> find_max_average([5], 1)
+        5.0
+    """
+    if not nums or n > len(nums):
+        raise ValueError(
+            "Invalid input: n must be <= length of nums and nums must not be empty"
+        )
+
+    # Calculate initial window sum
+    window_sum = sum(nums[:n])
+    max_sum = window_sum
+
+    # Slide the window and update max_sum
+    for i in range(n, len(nums)):
+        window_sum = window_sum + nums[i] - nums[i - n]
+        max_sum = max(max_sum, window_sum)
+
+    return max_sum / n
+
+
+class TestMaxAverage(unittest.TestCase):
+    """Test cases for the maximum average problem"""
+
+    def test_example_1(self):
+        """Test case from Example 1"""
+        self.assertEqual(find_max_average([1, 12, -5, -6, 50, 3], 4), 12.75)
+
+    def test_example_2(self):
+        """Test case from Example 2"""
+        self.assertEqual(find_max_average([5], 1), 5.0)
+
+    def test_edge_cases(self):
+        """Test edge cases"""
+        self.assertEqual(find_max_average([1, 2, 3], 3), 2.0)
+        with self.assertRaises(ValueError):
+            find_max_average([], 1)
+        with self.assertRaises(ValueError):
+            find_max_average([1, 2], 3)
+
+    def test_negative_numbers(self):
+        """Test with negative numbers"""
+        self.assertEqual(find_max_average([-1, -2, -3, -4], 2), -1.5)
+
+    def test_decimal_result(self):
+        """Test case with decimal result"""
+        self.assertEqual(find_max_average([1, 2, 3, 4, 5], 2), 4.5)
+
+
+if __name__ == "__main__":
+    import doctest
+    doctest.testmod()
+    unittest.main(verbosity=2)
diff --git a/challenge-306/lubos-kolouch/perl/ch-1.pl b/challenge-306/lubos-kolouch/perl/ch-1.pl
new file mode 100644
index 0000000000..1b44cb2a21
--- /dev/null
+++ b/challenge-306/lubos-kolouch/perl/ch-1.pl
@@ -0,0 +1,42 @@
+use strict;
+use warnings;
+
+=head2 odd_sum
+
+Calculate the sum of all possible odd-length subarrays of the given array.
+
+A subarray is a contiguous subsequence of the array. This function computes the sum of each element of every possible subarray with odd length and returns the total sum.
+
+@param @ints Array of positive integers.
+
+@return The sum of all odd-length subarrays.
+
+=cut
+
+sub odd_sum {
+    my @ints   = @_;
+    my $n      = scalar @ints;
+    my @prefix = (0);
+    for my $i ( 0 .. $n - 1 ) {
+        $prefix[ $i + 1 ] = $prefix[$i] + $ints[$i];
+    }
+    my $total = 0;
+    for ( my $l = 1 ; $l <= $n ; $l += 2 ) {
+        my $max_start = $n - $l;
+        for ( my $start = 0 ; $start <= $max_start ; $start++ ) {
+            my $end = $start + $l;
+            $total += $prefix[$end] - $prefix[$start];
+        }
+    }
+    return $total;
+}
+
+# Tests
+use Test::More tests => 4;
+
+is( odd_sum( 2, 5, 3, 6, 4 ), 77,                    'Example 1' );
+is( odd_sum( 1, 3 ),          4,                     'Example 2' );
+is( odd_sum(5),               5,                     'Single element' );
+is( odd_sum( 1, 2, 3 ),       1 + 2 + 3 + 1 + 2 + 3, 'Length 3 array' );
+
+done_testing();
diff --git a/challenge-306/lubos-kolouch/perl/ch-2.pl b/challenge-306/lubos-kolouch/perl/ch-2.pl
new file mode 100644
index 0000000000..43ed8b49b7
--- /dev/null
+++ b/challenge-306/lubos-kolouch/perl/ch-2.pl
@@ -0,0 +1,45 @@
+use strict;
+use warnings;
+
+=head2 last_element
+
+Determine the last element left after repeatedly picking and processing the two largest elements.
+
+The process is:
+1. Pick the two largest elements (x and y).
+2. If x == y, remove both.
+3. If x != y, remove both and add (x - y) to the array.
+Repeat until at most one element remains.
+
+@param @ints Array of integers.
+
+@return The last remaining element, or 0 if none.
+
+=cut
+
+sub last_element {
+    my @ints = @_;
+    @ints = sort { $b <=> $a } @ints;    # Sort descending
+    while ( @ints >= 2 ) {
+        my $x = shift @ints;
+        my $y = shift @ints;
+        if ( $x != $y ) {
+            my $diff = $x - $y;
+            push @ints, $diff;
+            @ints = sort { $b <=> $a } @ints;    # Re-sort
+        }
+    }
+    return @ints ? $ints[0] : 0;
+}
+
+# Tests
+use Test::More tests => 6;
+
+is( last_element( 3, 8, 5, 2, 9, 2 ), 1,  'Example 1' );
+is( last_element( 3, 2, 5 ),          0,  'Example 2' );
+is( last_element(5),                  5,  'Single element' );
+is( last_element( 5, 5 ),             0,  'Two equal elements' );
+is( last_element( 10, 10, 10 ),       10, 'Three equal elements' );
+is( last_element( 7, 3, 7 ),          3,  'Diff after removal' );
+
+done_testing();
diff --git a/challenge-306/lubos-kolouch/python/ch-1.py b/challenge-306/lubos-kolouch/python/ch-1.py
new file mode 100644
index 0000000000..181dc81772
--- /dev/null
+++ b/challenge-306/lubos-kolouch/python/ch-1.py
@@ -0,0 +1,55 @@
+import unittest
+
+
+def odd_sum(arr: list[int]) -> int:
+    """
+    Calculate the sum of all possible odd-length subarrays of the given array.
+
+    A subarray is a contiguous subsequence of the array. This function computes the sum of each
+    element of every possible subarray with odd length and returns the total sum.
+
+    Args:
+        arr (list[int]): The array of positive integers.
+
+    Returns:
+        int: The sum of all odd-length subarrays.
+
+    Examples:
+        >>> odd_sum([2, 5, 3, 6, 4])
+        77
+        >>> odd_sum([1, 3])
+        4
+    """
+    n = len(arr)
+    prefix = [0] * (n + 1)
+    for i in range(n):
+        prefix[i + 1] = prefix[i] + arr[i]
+    total = 0
+    for length in range(1, n + 1, 2):
+        max_start = n - length
+        for start in range(max_start + 1):
+            end = start + length
+            total += prefix[end] - prefix[start]
+    return total
+
+
+# Unit tests
+
+
+class TestOddSum(unittest.TestCase):
+
+    def test_example1(self):
+        self.assertEqual(odd_sum([2, 5, 3, 6, 4]), 77)
+
+    def test_example2(self):
+        self.assertEqual(odd_sum([1, 3]), 4)
+
+    def test_single_element(self):
+        self.assertEqual(odd_sum([5]), 5)
+
+    def test_length3(self):
+        self.assertEqual(odd_sum([1, 2, 3]), 1 + 2 + 3 + (1 + 2 + 3))
+
+
+if __name__ == '__main__':
+    unittest.main()
diff --git a/challenge-306/lubos-kolouch/python/ch-2.py b/challenge-306/lubos-kolouch/python/ch-2.py
new file mode 100644
index 0000000000..4d5f9e5da4
--- /dev/null
+++ b/challenge-306/lubos-kolouch/python/ch-2.py
@@ -0,0 +1,64 @@
+import unittest
+
+
+def last_element(ints: list[int]) -> int:
+    """
+    Determine the last element left after repeatedly picking and processing the two largest elements.
+
+    The process is:
+    1. Pick the two largest elements (x and y).
+    2. If x == y, remove both.
+    3. If x != y, remove both and add (x - y) to the array.
+    Repeat until at most one element remains.
+
+    Args:
+        ints (list[int]): List of integers.
+
+    Returns:
+        int: The last remaining element, or 0 if none.
+
+    Examples:
+        >>> last_element([3, 8, 5, 2, 9, 2])
+        1
+        >>> last_element([3, 2, 5])
+        0
+    """
+    import heapq
+    # Use a max-heap by storing negatives
+    heap = [-x for x in ints]
+    heapq.heapify(heap)
+    while len(heap) >= 2:
+        x = -heapq.heappop(heap)
+        y = -heapq.heappop(heap)
+        if x != y:
+            diff = x - y
+            heapq.heappush(heap, -diff)
+    return -heap[0] if heap else 0
+
+
+# Unit tests
+
+
+class TestLastElement(unittest.TestCase):
+
+    def test_example1(self):
+        self.assertEqual(last_element([3, 8, 5, 2, 9, 2]), 1)
+
+    def test_example2(self):
+        self.assertEqual(last_element([3, 2, 5]), 0)
+
+    def test_single_element(self):
+        self.assertEqual(last_element([5]), 5)
+
+    def test_two_equal_elements(self):
+        self.assertEqual(last_element([5, 5]), 0)
+
+    def test_three_equal_elements(self):
+        self.assertEqual(last_element([10, 10, 10]), 10)
+
+    def test_diff_after_removal(self):
+        self.assertEqual(last_element([7, 3, 7]), 3)
+
+
+if __name__ == '__main__':
+    unittest.main()