Merge pull request #10857 from LubosKolouch/master

Challenge 284 285 LK Perl Python

8 files changed, 480 insertions, 0 deletions

diff --git a/challenge-284/lubos-kolouch/perl/ch-1.pl b/challenge-284/lubos-kolouch/perl/ch-1.pl
new file mode 100644
index 0000000000..17a5769fe9
--- /dev/null
+++ b/challenge-284/lubos-kolouch/perl/ch-1.pl
@@ -0,0 +1,59 @@
+#!/usr/bin/perl
+use strict;
+use warnings;
+use Test::More tests => 3;
+
+=pod
+
+=head1 DESCRIPTION
+
+This script finds the lucky integer in a given array of integers.
+
+A lucky integer is defined as an integer whose frequency in the array is equal to its value.
+
+If there are multiple lucky integers, the largest one is returned. If no lucky integers are found, -1 is returned.
+
+=head1 FUNCTIONS
+
+=head2 find_lucky_integer(\@ints)
+
+Given an array reference of integers, returns the lucky integer as per the problem definition.
+
+=over 4
+
+=item * C<\@ints> - Reference to an array of integers.
+
+=back
+
+Returns the lucky integer if found, otherwise -1.
+
+=cut
+
+sub find_lucky_integer {
+    my ($ints_ref) = @_;
+    my %freq;
+
+    foreach my $num (@$ints_ref) {
+        $freq{$num}++;
+    }
+
+    my @lucky_integers;
+    foreach my $num (keys %freq) {
+        if ($num == $freq{$num}) {
+            push @lucky_integers, $num;
+        }
+    }
+
+    if (@lucky_integers) {
+        return (sort { $b <=> $a } @lucky_integers)[0];
+    } else {
+        return -1;
+    }
+}
+
+# Unit Tests
+is(find_lucky_integer([2, 2, 3, 4]), 2, 'Example 1');
+is(find_lucky_integer([1, 2, 2, 3, 3, 3]), 3, 'Example 2');
+is(find_lucky_integer([1, 1, 1, 3]), -1, 'Example 3');
+
+done_testing();
diff --git a/challenge-284/lubos-kolouch/perl/ch-2.pl b/challenge-284/lubos-kolouch/perl/ch-2.pl
new file mode 100644
index 0000000000..2579cd474e
--- /dev/null
+++ b/challenge-284/lubos-kolouch/perl/ch-2.pl
@@ -0,0 +1,88 @@
+#!/usr/bin/perl
+use strict;
+use warnings;
+use Test::More tests => 3;
+
+=pod
+
+=head1 DESCRIPTION
+
+This script sorts the elements of @list1 based on the relative order defined in @list2. Elements in @list1 that are not in @list2 are placed at the end in ascending order.
+
+=head1 FUNCTIONS
+
+=head2 relative_sort(\@list1, \@list2)
+
+Sorts @list1 based on the order of elements in @list2.
+
+=over 4
+
+=item * C<\@list1> - Reference to the first list of integers.
+
+=item * C<\@list2> - Reference to the second list of integers defining the relative order.
+
+=back
+
+Returns a sorted array.
+
+=cut
+
+sub relative_sort {
+    my ($list1_ref, $list2_ref) = @_;
+    my %order;
+    my @result;
+
+    # Assign order to elements in @list2
+    my $idx = 0;
+    foreach my $num (@$list2_ref) {
+        $order{$num} = $idx++;
+    }
+
+    # Separate elements that are in @list2 and not in @list2
+    my @in_list2;
+    my @not_in_list2;
+
+    foreach my $num (@$list1_ref) {
+        if (exists $order{$num}) {
+            push @in_list2, $num;
+        } else {
+            push @not_in_list2, $num;
+        }
+    }
+
+    # Sort elements in @list1 that are in @list2 based on the order in @list2
+    @in_list2 = sort {
+        $order{$a} <=> $order{$b}
+            ||
+        $a <=> $b  # To handle duplicates
+    } @in_list2;
+
+    # Sort elements not in @list2 in ascending order
+    @not_in_list2 = sort { $a <=> $b } @not_in_list2;
+
+    # Combine the two lists
+    @result = (@in_list2, @not_in_list2);
+
+    return @result;
+}
+
+# Unit Tests
+is_deeply(
+    [relative_sort([2, 3, 9, 3, 1, 4, 6, 7, 2, 8, 5], [2, 1, 4, 3, 5, 6])],
+    [2, 2, 1, 4, 3, 3, 5, 6, 7, 8, 9],
+    'Example 1'
+);
+
+is_deeply(
+    [relative_sort([3, 3, 4, 6, 2, 4, 2, 1, 3], [1, 3, 2])],
+    [1, 3, 3, 3, 2, 2, 4, 4, 6],
+    'Example 2'
+);
+
+is_deeply(
+    [relative_sort([3, 0, 5, 0, 2, 1, 4, 1, 1], [1, 0, 3, 2])],
+    [1, 1, 1, 0, 0, 3, 2, 4, 5],
+    'Example 3'
+);
+
+done_testing();
diff --git a/challenge-284/lubos-kolouch/python/ch-1.py b/challenge-284/lubos-kolouch/python/ch-1.py
new file mode 100644
index 0000000000..2f817578f1
--- /dev/null
+++ b/challenge-284/lubos-kolouch/python/ch-1.py
@@ -0,0 +1,51 @@
+from typing import List
+import unittest
+
+
+def find_lucky_integer(ints: List[int]) -> int:
+    """
+    Finds the lucky integer in the given list of integers.
+
+    A lucky integer is an integer whose frequency in the array is equal to its value.
+
+    If there are multiple lucky integers, returns the largest one.
+    If no lucky integers are found, returns -1.
+
+    Args:
+        ints (List[int]): A list of integers.
+
+    Returns:
+        int: The lucky integer if found, otherwise -1.
+    """
+    from collections import Counter
+    freq = Counter(ints)
+    lucky_integers = [num for num, count in freq.items() if num == count]
+    if lucky_integers:
+        return max(lucky_integers)
+    else:
+        return -1
+
+
+# Unit Tests
+class TestFindLuckyInteger(unittest.TestCase):
+
+    def test_example1(self):
+        self.assertEqual(find_lucky_integer([2, 2, 3, 4]), 2, 'Example 1')
+
+    def test_example2(self):
+        self.assertEqual(find_lucky_integer([1, 2, 2, 3, 3, 3]), 3,
+                         'Example 2')
+
+    def test_example3(self):
+        self.assertEqual(find_lucky_integer([1, 1, 1, 3]), -1, 'Example 3')
+
+    def test_additional(self):
+        self.assertEqual(find_lucky_integer([5, 5, 5, 5, 5]), 5,
+                         'All same number')
+        self.assertEqual(find_lucky_integer([2, 2, 2, 3, 3]), -1,
+                         'No lucky integer')
+        self.assertEqual(find_lucky_integer([]), -1, 'Empty list')
+
+
+if __name__ == "__main__":
+    unittest.main()
diff --git a/challenge-284/lubos-kolouch/python/ch-2.py b/challenge-284/lubos-kolouch/python/ch-2.py
new file mode 100644
index 0000000000..c0fb8a888b
--- /dev/null
+++ b/challenge-284/lubos-kolouch/python/ch-2.py
@@ -0,0 +1,66 @@
+from typing import List
+import unittest
+
+
+def relative_sort(list1: List[int], list2: List[int]) -> List[int]:
+    """
+    Sorts the elements of list1 based on the relative order defined in list2.
+    Elements not in list2 are placed at the end in ascending order.
+
+    Args:
+        list1 (List[int]): The list of integers to sort.
+        list2 (List[int]): The list defining the relative order.
+
+    Returns:
+        List[int]: The sorted list.
+    """
+    order = {num: idx for idx, num in enumerate(list2)}
+    in_list2 = []
+    not_in_list2 = []
+
+    for num in list1:
+        if num in order:
+            in_list2.append(num)
+        else:
+            not_in_list2.append(num)
+
+    # Sort elements in list1 that are in list2 based on the order in list2
+    in_list2.sort(key=lambda x: (order[x], x))
+
+    # Sort elements not in list2 in ascending order
+    not_in_list2.sort()
+
+    return in_list2 + not_in_list2
+
+
+# Unit Tests
+class TestRelativeSort(unittest.TestCase):
+
+    def test_example1(self):
+        list1 = [2, 3, 9, 3, 1, 4, 6, 7, 2, 8, 5]
+        list2 = [2, 1, 4, 3, 5, 6]
+        expected = [2, 2, 1, 4, 3, 3, 5, 6, 7, 8, 9]
+        self.assertEqual(relative_sort(list1, list2), expected, 'Example 1')
+
+    def test_example2(self):
+        list1 = [3, 3, 4, 6, 2, 4, 2, 1, 3]
+        list2 = [1, 3, 2]
+        expected = [1, 3, 3, 3, 2, 2, 4, 4, 6]
+        self.assertEqual(relative_sort(list1, list2), expected, 'Example 2')
+
+    def test_example3(self):
+        list1 = [3, 0, 5, 0, 2, 1, 4, 1, 1]
+        list2 = [1, 0, 3, 2]
+        expected = [1, 1, 1, 0, 0, 3, 2, 4, 5]
+        self.assertEqual(relative_sort(list1, list2), expected, 'Example 3')
+
+    def test_additional(self):
+        list1 = [7, 5, 9, 4, 8, 6]
+        list2 = [5, 7, 6]
+        expected = [5, 7, 6, 4, 8, 9]
+        self.assertEqual(relative_sort(list1, list2), expected,
+                         'Additional Test')
+
+
+if __name__ == "__main__":
+    unittest.main()
diff --git a/challenge-285/lubos-kolouch/perl/ch-1.pl b/challenge-285/lubos-kolouch/perl/ch-1.pl
new file mode 100644
index 0000000000..63d294742a
--- /dev/null
+++ b/challenge-285/lubos-kolouch/perl/ch-1.pl
@@ -0,0 +1,51 @@
+#!/usr/bin/perl
+use strict;
+use warnings;
+use Test::More tests => 2;
+
+=pod
+
+=head1 DESCRIPTION
+
+This script finds the destination with no further outgoing connection from a given list of routes.
+
+=head1 FUNCTIONS
+
+=head2 find_destination(\@routes)
+
+Given an array reference of routes, where each route is an array reference containing a source and a destination city, this function returns the city that is a destination but not a source in any route.
+
+=over 4
+
+=item * C<\@routes> - Reference to an array of routes (array references of source and destination cities).
+
+=back
+
+Returns the destination city with no outgoing connections.
+
+=cut
+
+sub find_destination {
+    my ($routes_ref) = @_;
+    my %sources;
+    my %destinations;
+
+    foreach my $route (@$routes_ref) {
+        my ($source, $destination) = @$route;
+        $sources{$source} = 1;
+        $destinations{$destination} = 1;
+    }
+
+    foreach my $city (keys %destinations) {
+        unless (exists $sources{$city}) {
+            return $city;
+        }
+    }
+    return undef;  # In case there is no such city
+}
+
+# Unit Tests
+is(find_destination([["B","C"], ["D","B"], ["C","A"]]), "A", 'Example 1');
+is(find_destination([["A","Z"]]), "Z", 'Example 2');
+
+done_testing();
diff --git a/challenge-285/lubos-kolouch/perl/ch-2.pl b/challenge-285/lubos-kolouch/perl/ch-2.pl
new file mode 100644
index 0000000000..4ca1821de2
--- /dev/null
+++ b/challenge-285/lubos-kolouch/perl/ch-2.pl
@@ -0,0 +1,57 @@
+#!/usr/bin/perl
+use strict;
+use warnings;
+use Test::More tests => 3;
+
+=pod
+
+=head1 DESCRIPTION
+
+This script computes the number of distinct ways to make change for a given amount in cents using US coins.
+
+Coins available:
+- Penny (P): 1 cent
+- Nickel (N): 5 cents
+- Dime (D): 10 cents
+- Quarter (Q): 25 cents
+- Half-dollar (HD): 50 cents
+
+Order of coin selection does not matter.
+
+=head1 FUNCTIONS
+
+=head2 making_change($amount)
+
+Computes the number of ways to make change for the given amount.
+
+=over 4
+
+=item * C<$amount> - The amount in cents (non-negative integer).
+
+=back
+
+Returns the number of distinct ways to make change.
+
+=cut
+
+sub making_change {
+    my ($amount) = @_;
+    my @coins = (1, 5, 10, 25, 50);
+    my @dp = (0) x ($amount + 1);
+    $dp[0] = 1;
+
+    foreach my $coin (@coins) {
+        for my $i ($coin .. $amount) {
+            $dp[$i] += $dp[$i - $coin];
+        }
+    }
+
+    return $dp[$amount];
+}
+
+# Unit Tests
+is(making_change(9),   2,   'Example 1');
+is(making_change(15),  6,   'Example 2');
+is(making_change(100), 292, 'Example 3');
+
+done_testing();
diff --git a/challenge-285/lubos-kolouch/python/ch-1.py b/challenge-285/lubos-kolouch/python/ch-1.py
new file mode 100644
index 0000000000..be24d53a49
--- /dev/null
+++ b/challenge-285/lubos-kolouch/python/ch-1.py
@@ -0,0 +1,52 @@
+from typing import List
+import unittest
+
+
+def find_destination(routes: List[List[str]]) -> str:
+    """
+    Finds the destination with no further outgoing connection from a given list of routes.
+
+    Each route is represented as a list containing a source and a destination city.
+
+    Args:
+        routes (List[List[str]]): A list of routes.
+
+    Returns:
+        str: The destination city with no outgoing connections.
+
+    """
+    sources = set()
+    destinations = set()
+
+    for route in routes:
+        source, destination = route
+        sources.add(source)
+        destinations.add(destination)
+
+    no_outgoing = destinations - sources
+
+    if no_outgoing:
+        # Assuming there is only one such city
+        return no_outgoing.pop()
+    else:
+        return None  # In case there is no such city
+
+
+# Unit Tests
+class TestNoConnection(unittest.TestCase):
+
+    def test_example1(self):
+        routes = [["B", "C"], ["D", "B"], ["C", "A"]]
+        self.assertEqual(find_destination(routes), "A", 'Example 1')
+
+    def test_example2(self):
+        routes = [["A", "Z"]]
+        self.assertEqual(find_destination(routes), "Z", 'Example 2')
+
+    def test_no_destination(self):
+        routes = [["A", "B"], ["B", "A"]]
+        self.assertIsNone(find_destination(routes), 'No unique destination')
+
+
+if __name__ == "__main__":
+    unittest.main()
diff --git a/challenge-285/lubos-kolouch/python/ch-2.py b/challenge-285/lubos-kolouch/python/ch-2.py
new file mode 100644
index 0000000000..60182732c2
--- /dev/null
+++ b/challenge-285/lubos-kolouch/python/ch-2.py
@@ -0,0 +1,56 @@
+from typing import List
+import unittest
+
+
+def making_change(amount: int) -> int:
+    """
+    Compute the number of ways to make change for the given amount in cents using US coins.
+
+    Coins available:
+    - Penny (P): 1 cent
+    - Nickel (N): 5 cents
+    - Dime (D): 10 cents
+    - Quarter (Q): 25 cents
+    - Half-dollar (HD): 50 cents
+
+    Order of coin selection does not matter.
+
+    Args:
+        amount (int): The amount in cents (non-negative integer).
+
+    Returns:
+        int: The number of distinct ways to make change.
+    """
+    coins = [1, 5, 10, 25, 50]
+    dp = [0] * (amount + 1)
+    dp[0] = 1  # There is one way to make 0 cents
+
+    for coin in coins:
+        for i in range(coin, amount + 1):
+            dp[i] += dp[i - coin]
+
+    return dp[amount]
+
+
+# Unit Tests
+class TestMakingChange(unittest.TestCase):
+
+    def test_example1(self):
+        self.assertEqual(making_change(9), 2, 'Example 1')
+
+    def test_example2(self):
+        self.assertEqual(making_change(15), 6, 'Example 2')
+
+    def test_example3(self):
+        self.assertEqual(making_change(100), 292, 'Example 3')
+
+    def test_zero_amount(self):
+        self.assertEqual(making_change(0), 1, 'Zero amount')
+
+    def test_negative_amount(self):
+        with self.assertRaises(IndexError):
+            making_change(-1)
+
+
+if __name__ == "__main__":
+    unittest.main()