Merge pull request #11496 from LubosKolouch/master

Challenge 306 LK Perl Python

4 files changed, 206 insertions, 0 deletions

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()