Merge pull request #7910 from LubosKolouch/master

Challenge 057 059

12 files changed, 478 insertions, 0 deletions

diff --git a/challenge-057/lubos-kolouch/perl/ch-1.pl b/challenge-057/lubos-kolouch/perl/ch-1.pl
new file mode 100644
index 0000000000..8589164d70
--- /dev/null
+++ b/challenge-057/lubos-kolouch/perl/ch-1.pl
@@ -0,0 +1,58 @@
+#!/usr/bin/perl
+use strict;
+use warnings;
+
+package BinaryTree;
+
+sub new {
+    my ( $class, $value, $left, $right ) = @_;
+    my $self = {
+        value => $value,
+        left  => $left,
+        right => $right,
+    };
+    bless $self, $class;
+    return $self;
+}
+
+sub invert {
+    my $self = shift;
+
+    ( $self->{left}, $self->{right} ) = ( $self->{right}, $self->{left} );
+    $self->{left}->invert()  if defined $self->{left};
+    $self->{right}->invert() if defined $self->{right};
+}
+
+sub pretty_print {
+    my $self           = shift;
+    my $padding        = shift || '';
+    my $branch_padding = shift || '';
+
+    if ( defined $self->{right} ) {
+        $self->{right}->pretty_print( "$padding ", "$padding|" );
+    }
+
+    print $branch_padding;
+    print "--" if $branch_padding;
+    print $self->{value}, "\n";
+
+    if ( defined $self->{left} ) {
+        $self->{left}->pretty_print( "$padding ", "$padding|" );
+    }
+}
+
+package main;
+
+my $tree = BinaryTree->new(
+    1,
+    BinaryTree->new( 2, BinaryTree->new(4), BinaryTree->new(5) ),
+    BinaryTree->new( 3, BinaryTree->new(6), BinaryTree->new(7) )
+);
+
+print "Original tree:\n";
+$tree->pretty_print();
+
+$tree->invert();
+
+print "\nInverted tree:\n";
+$tree->pretty_print();
diff --git a/challenge-057/lubos-kolouch/perl/ch-2.pl b/challenge-057/lubos-kolouch/perl/ch-2.pl
new file mode 100644
index 0000000000..b8edac5a5a
--- /dev/null
+++ b/challenge-057/lubos-kolouch/perl/ch-2.pl
@@ -0,0 +1,26 @@
+#!/usr/bin/perl
+use strict;
+use warnings;
+
+sub shortest_unique_prefixes {
+    my @words = @_;
+    my @result;
+
+    for my $word (@words) {
+        my $prefix = "";
+        for my $char ( split //, $word ) {
+            $prefix .= $char;
+            if ( !grep { $_ =~ /^$prefix/ } @result ) {
+                push @result, $prefix;
+                last;
+            }
+        }
+    }
+
+    return \@result;
+}
+
+my @input  = ( "alphabet", "book", "carpet", "cadmium", "cadeau", "alpine" );
+my $result = shortest_unique_prefixes(@input);
+
+print "[", join( ", ", @{$result} ), "]\n";
diff --git a/challenge-057/lubos-kolouch/python/ch-1.py b/challenge-057/lubos-kolouch/python/ch-1.py
new file mode 100644
index 0000000000..e7dd3485db
--- /dev/null
+++ b/challenge-057/lubos-kolouch/python/ch-1.py
@@ -0,0 +1,51 @@
+#!/usr/bin/env python
+# -*- coding: utf-8 -*-
+
+class BinaryTree:
+    def __init__(self, value, left=None, right=None):
+        self.value = value
+        self.left = left
+        self.right = right
+
+    def invert(self):
+        self.left, self.right = self.right, self.left
+        if self.left:
+            self.left.invert()
+        if self.right:
+            self.right.invert()
+
+    def pretty_print(self, padding="", branch_padding=""):
+        if self.right:
+            self.right.pretty_print(padding + " ", padding + "|")
+
+        print(branch_padding, end="")
+        if branch_padding:
+            print("--", end="")
+        print(self.value)
+
+        if self.left:
+            self.left.pretty_print(padding + " ", padding + "|")
+
+
+if __name__ == "__main__":
+    tree = BinaryTree(
+        1,
+        BinaryTree(
+            2,
+            BinaryTree(4),
+            BinaryTree(5)
+        ),
+        BinaryTree(
+            3,
+            BinaryTree(6),
+            BinaryTree(7)
+        )
+    )
+
+    print("Original tree:")
+    tree.pretty_print()
+
+    tree.invert()
+
+    print("\nInverted tree:")
+    tree.pretty_print()
diff --git a/challenge-057/lubos-kolouch/python/ch-2.py b/challenge-057/lubos-kolouch/python/ch-2.py
new file mode 100644
index 0000000000..d8dd139311
--- /dev/null
+++ b/challenge-057/lubos-kolouch/python/ch-2.py
@@ -0,0 +1,24 @@
+#!/usr/bin/env python
+# -*- coding: utf-8 -*-
+
+from typing import List
+
+
+def shortest_unique_prefixes(words: List[str]) -> List[str]:
+    result = []
+
+    for word in words:
+        prefix = ""
+        for char in word:
+            prefix += char
+            if not any(res.startswith(prefix) for res in result):
+                result.append(prefix)
+                break
+
+    return result
+
+if __name__ == "__main__":
+    input_list = ["alphabet", "book", "carpet", "cadmium", "cadeau", "alpine"]
+    result = shortest_unique_prefixes(input_list)
+
+    print(result)
diff --git a/challenge-059/lubos-kolouch/perl/ch-1.pl b/challenge-059/lubos-kolouch/perl/ch-1.pl
new file mode 100644
index 0000000000..66d5a1b60d
--- /dev/null
+++ b/challenge-059/lubos-kolouch/perl/ch-1.pl
@@ -0,0 +1,94 @@
+#!/usr/bin/perl
+use strict;
+use warnings;
+
+package LinkedList;
+
+sub new {
+    my ( $class, $value ) = @_;
+    my $self = {
+        value => $value,
+        next  => undef,
+    };
+    bless $self, $class;
+    return $self;
+}
+
+sub append {
+    my ( $self, $value ) = @_;
+    my $current = $self;
+    while ( defined $current->{next} ) {
+        $current = $current->{next};
+    }
+    $current->{next} = LinkedList->new($value);
+}
+
+sub partition {
+    my ( $self, $k ) = @_;
+    my $less_head;
+    my $greater_head;
+    my $less_tail;
+    my $greater_tail;
+
+    my $current = $self;
+    while ( defined $current ) {
+        if ( $current->{value} < $k ) {
+            if ( defined $less_tail ) {
+                $less_tail->{next} = $current;
+            }
+            else {
+                $less_head = $current;
+            }
+            $less_tail = $current;
+        }
+        else {
+            if ( defined $greater_tail ) {
+                $greater_tail->{next} = $current;
+            }
+            else {
+                $greater_head = $current;
+            }
+            $greater_tail = $current;
+        }
+        $current = $current->{next};
+    }
+
+    if ( defined $less_tail ) {
+        $less_tail->{next} = $greater_head;
+    }
+    else {
+        $less_head = $greater_head;
+    }
+
+    if ( defined $greater_tail ) {
+        $greater_tail->{next} = undef;
+    }
+
+    return $less_head;
+}
+
+sub to_string {
+    my $self    = shift;
+    my $str     = '';
+    my $current = $self;
+    while ( defined $current ) {
+        $str .= $current->{value} . ' → ';
+        $current = $current->{next};
+    }
+    $str .= 'END';
+    return $str;
+}
+
+package main;
+
+my $list = LinkedList->new(1);
+$list->append(4);
+$list->append(3);
+$list->append(2);
+$list->append(5);
+$list->append(2);
+
+print "Original list: ", $list->to_string(), "\n";
+my $k                = 3;
+my $partitioned_list = $list->partition($k);
+print "Partitioned list with k=$k: ", $partitioned_list->to_string(), "\n";
diff --git a/challenge-059/lubos-kolouch/perl/ch-2.pl b/challenge-059/lubos-kolouch/perl/ch-2.pl
new file mode 100644
index 0000000000..70f82c4355
--- /dev/null
+++ b/challenge-059/lubos-kolouch/perl/ch-2.pl
@@ -0,0 +1,28 @@
+#!/usr/bin/perl
+use strict;
+use warnings;
+
+sub count_different_bits {
+    my ( $a, $b ) = @_;
+    my $count = 0;
+    while ( $a > 0 or $b > 0 ) {
+        $count += ( $a % 2 ) ^ ( $b % 2 );
+        $a >>= 1;
+        $b >>= 1;
+    }
+    return $count;
+}
+
+sub sum_different_bits {
+    my @numbers = @_;
+    my $sum     = 0;
+    for my $i ( 0 .. $#numbers ) {
+        for my $j ( $i + 1 .. $#numbers ) {
+            $sum += count_different_bits( $numbers[$i], $numbers[$j] );
+        }
+    }
+    return $sum;
+}
+
+my @input = ( 2, 3, 4 );
+print sum_different_bits(@input), "\n";
diff --git a/challenge-059/lubos-kolouch/python/ch-1.py b/challenge-059/lubos-kolouch/python/ch-1.py
new file mode 100644
index 0000000000..e463f94a8a
--- /dev/null
+++ b/challenge-059/lubos-kolouch/python/ch-1.py
@@ -0,0 +1,69 @@
+#!/usr/bin/env python
+# -*- coding: utf-8 -*-
+
+class LinkedList:
+    def __init__(self, value):
+        self.value = value
+        self.next = None
+
+    def append(self, value):
+        current = self
+        while current.next:
+            current = current.next
+        current.next = LinkedList(value)
+
+    def partition(self, k):
+        less_head = None
+        greater_head = None
+        less_tail = None
+        greater_tail = None
+
+        current = self
+        while current:
+            if current.value < k:
+                if less_tail:
+                    less_tail.next = current
+                else:
+                    less_head = current
+                less_tail = current
+            else:
+                if greater_tail:
+                    greater_tail.next = current
+                else:
+                    greater_head = current
+                greater_tail = current
+            current = current.next
+
+        if less_tail:
+            less_tail.next = greater_head
+        else:
+            less_head = greater_head
+
+        if greater_tail:
+            greater_tail.next = None
+
+        return less_head
+
+    def __str__(self):
+        current = self
+        result = []
+        while current:
+            result.append(str(current.value) + " → ")
+            current = current.next
+        result.append("END")
+        return "".join(result)
+
+
+if __name__ == "__main__":
+    linked_list = LinkedList(1)
+    linked_list.append(4)
+    linked_list.append(3)
+    linked_list.append(2)
+    linked_list.append(5)
+    linked_list.append(2)
+
+    print("Original list:", linked_list)
+    k_val = 3
+    partitioned_list = linked_list.partition(k_val)
+    print(f"Partitioned list with k={k_val}:", partitioned_list)
+       
diff --git a/challenge-059/lubos-kolouch/python/ch-2.py b/challenge-059/lubos-kolouch/python/ch-2.py
new file mode 100644
index 0000000000..f482a546d6
--- /dev/null
+++ b/challenge-059/lubos-kolouch/python/ch-2.py
@@ -0,0 +1,25 @@
+#!/usr/bin/env python
+# -*- coding: utf-8 -*-
+
+from typing import List
+
+
+def count_different_bits(a: int, b: int) -> int:
+    count = 0
+    while a > 0 or b > 0:
+        count += (a % 2) ^ (b % 2)
+        a >>= 1
+        b >>= 1
+    return count
+
+def sum_different_bits(numbers: List[int]) -> int:
+    total = 0
+    for i in range(len(numbers)):
+        for j in range(i+1, len(numbers)):
+            total += count_different_bits(numbers[i], numbers[j])
+    return total
+
+if __name__ == "__main__":
+    input_list = [2, 3, 4]
+    result = sum_different_bits(input_list)
+    print(result)
diff --git a/challenge-060/lubos-kolouch/perl/ch-1.pl b/challenge-060/lubos-kolouch/perl/ch-1.pl
new file mode 100644
index 0000000000..6a46d53308
--- /dev/null
+++ b/challenge-060/lubos-kolouch/perl/ch-1.pl
@@ -0,0 +1,33 @@
+#!/usr/bin/perl
+use strict;
+use warnings;
+
+sub number_to_excel_column {
+    my $num    = shift;
+    my $column = '';
+    while ( $num > 0 ) {
+        $num--;
+        $column = chr( ( $num % 26 ) + ord('A') ) . $column;
+        $num    = int( $num / 26 );
+    }
+    return $column;
+}
+
+sub excel_column_to_number {
+    my $column = shift;
+    my $num    = 0;
+    for my $char ( split //, $column ) {
+        $num = $num * 26 + ( ord($char) - ord('A') + 1 );
+    }
+    return $num;
+}
+
+my $input_number = 28;
+print "Input Number: $input_number\n";
+my $output_column = number_to_excel_column($input_number);
+print "Output: $output_column\n";
+
+my $input_column = "AD";
+print "Input Column Name: $input_column\n";
+my $output_number = excel_column_to_number($input_column);
+print "Output: $output_number\n";
diff --git a/challenge-060/lubos-kolouch/perl/ch-2.pl b/challenge-060/lubos-kolouch/perl/ch-2.pl
new file mode 100644
index 0000000000..8ac17e659d
--- /dev/null
+++ b/challenge-060/lubos-kolouch/perl/ch-2.pl
@@ -0,0 +1,22 @@
+#!/usr/bin/perl
+use strict;
+use warnings;
+
+sub generate_numbers {
+    my ( $list, $x, $y, $current ) = @_;
+    if ( $x == 0 ) {
+        return int($current) < $y ? ( int($current) ) : ();
+    }
+    my @result;
+    for my $num (@$list) {
+        push @result, generate_numbers( $list, $x - 1, $y, $current . $num );
+    }
+    return @result;
+}
+
+my @L = ( 0, 1, 2, 5 );
+my $X = 2;
+my $Y = 21;
+
+my @output = generate_numbers( \@L, $X, $Y, "" );
+print join( ", ", @output ), "\n";
diff --git a/challenge-060/lubos-kolouch/python/ch-1.py b/challenge-060/lubos-kolouch/python/ch-1.py
new file mode 100644
index 0000000000..24ddaa66b9
--- /dev/null
+++ b/challenge-060/lubos-kolouch/python/ch-1.py
@@ -0,0 +1,27 @@
+#!/usr/bin/env python
+# -*- coding: utf-8 -*-
+
+def number_to_excel_column(num: int) -> str:
+    column = ""
+    while num > 0:
+        num -= 1
+        column = chr((num % 26) + ord("A")) + column
+        num //= 26
+    return column
+
+def excel_column_to_number(column: str) -> int:
+    num = 0
+    for char in column:
+        num = num * 26 + (ord(char) - ord("A") + 1)
+    return num
+
+if __name__ == "__main__":
+    input_number = 28
+    print(f"Input Number: {input_number}")
+    output_column = number_to_excel_column(input_number)
+    print(f"Output: {output_column}")
+
+    input_column = "AD"
+    print(f"Input Column Name: {input_column}")
+    output_number = excel_column_to_number(input_column)
+    print(f"Output: {output_number}")
diff --git a/challenge-060/lubos-kolouch/python/ch-2.py b/challenge-060/lubos-kolouch/python/ch-2.py
new file mode 100644
index 0000000000..a6b872111d
--- /dev/null
+++ b/challenge-060/lubos-kolouch/python/ch-2.py
@@ -0,0 +1,21 @@
+#!/usr/bin/env python
+# -*- coding: utf-8 -*-
+
+from typing import List
+
+
+def generate_numbers(numbers: List[int], x: int, y: int, current: str) -> List[int]:
+    if x == 0:
+        return [int(current)] if int(current) < y else []
+    result = []
+    for num in numbers:
+        result.extend(generate_numbers(numbers, x - 1, y, current + str(num)))
+    return result
+
+if __name__ == "__main__":
+    L = [0, 1, 2, 5]
+    X = 2
+    Y = 21
+
+    output = generate_numbers(L, X, Y, "")
+    print(", ".join(map(str, output)))