feat(challenge-118/lubos-kolouch/perl,python/): Challenge 118 LK Perl Python

4 files changed, 134 insertions, 0 deletions

diff --git a/challenge-118/lubos-kolouch/perl/ch-1.pl b/challenge-118/lubos-kolouch/perl/ch-1.pl
new file mode 100644
index 0000000000..f73acb3695
--- /dev/null
+++ b/challenge-118/lubos-kolouch/perl/ch-1.pl
@@ -0,0 +1,13 @@
+use strict;
+use warnings;
+
+sub is_binary_palindrome {
+    my ($N) = @_;
+    my $binary_rep = sprintf("%b", $N);
+    return $binary_rep eq reverse($binary_rep) ? 1 : 0;
+}
+
+# Tests
+print is_binary_palindrome(5);  # Output: 1
+print is_binary_palindrome(4);  # Output: 0
+
diff --git a/challenge-118/lubos-kolouch/perl/ch-2.pl b/challenge-118/lubos-kolouch/perl/ch-2.pl
new file mode 100644
index 0000000000..b251828bd8
--- /dev/null
+++ b/challenge-118/lubos-kolouch/perl/ch-2.pl
@@ -0,0 +1,64 @@
+use strict;
+use warnings;
+
+my @board = (
+    ['N', '*', '*', '*', '*', '*', '*', '*'],
+    ['*', '*', '*', '*', '*', '*', '*', '*'],
+    ['*', '*', '*', '*', 'x', '*', '*', '*'],
+    ['*', '*', '*', '*', '*', '*', '*', '*'], 
+    ['*', '*', 'x', '*', '*', '*', '*', '*'],
+    ['*', 'x', '*', '*', '*', '*', '*', '*'],
+    ['x', 'x', '*', '*', '*', '*', '*', '*'],
+    ['*', 'x', '*', '*', '*', '*', '*', '*']
+);
+
+my @moves = (
+    [-2, -1], [-2, 1], [2, -1], [2, 1],
+    [-1, -2], [1, -2], [-1, 2], [1, 2]
+);
+
+sub is_valid_move {
+    my ($x, $y) = @_;
+    return $x >= 0 && $x < 8 && $y >= 0 && $y < 8;
+}
+
+sub find_path {
+    my ($x, $y, $path, $treasures) = @_;
+
+    return $path if $treasures == 0;
+
+    my @new_path = (@$path, [$x, $y]);
+    my $new_treasures = $treasures - ($board[$x][$y] eq 'x' ? 1 : 0);
+
+    my @shortest_path;
+    my $shortest_length = 1e9;
+
+    for my $move (@moves) {
+        my ($dx, $dy) = @$move;
+        my $new_x = $x + $dx;
+        my $new_y = $y + $dy;
+
+        next unless is_valid_move($new_x, $new_y);
+        next if grep { $_->[0] == $new_x && $_->[1] == $new_y } @$path;
+
+        my $result = find_path($new_x, $new_y, \@new_path, $new_treasures);
+        my $result_length = scalar @$result;
+
+        if ($result_length < $shortest_length) {
+            @shortest_path = @$result;
+            $shortest_length = $result_length;
+        }
+    }
+
+    return \@shortest_path;
+}
+
+my $path = find_path(0, 0, [], 6);
+
+print "One of the shortest paths is:\n";
+for my $pos (@$path) {
+    my ($x, $y) = @$pos;
+    print "($x, $y) ";
+}
+print "\n";
+
diff --git a/challenge-118/lubos-kolouch/python/ch-1.py b/challenge-118/lubos-kolouch/python/ch-1.py
new file mode 100644
index 0000000000..e8fed3c656
--- /dev/null
+++ b/challenge-118/lubos-kolouch/python/ch-1.py
@@ -0,0 +1,11 @@
+#!/usr/bin/env python
+# -*- coding: utf-8 -*-
+
+def is_binary_palindrome(N):
+    binary_rep = bin(N)[2:]
+    return int(binary_rep == binary_rep[::-1])
+
+
+# Tests
+print(is_binary_palindrome(5))  # Output: 1
+print(is_binary_palindrome(4))  # Output: 0
diff --git a/challenge-118/lubos-kolouch/python/ch-2.py b/challenge-118/lubos-kolouch/python/ch-2.py
new file mode 100644
index 0000000000..37b976b3fb
--- /dev/null
+++ b/challenge-118/lubos-kolouch/python/ch-2.py
@@ -0,0 +1,46 @@
+#!/usr/bin/env python
+# -*- coding: utf-8 -*-
+
+from itertools import permutations
+from collections import deque
+
+
+def knight_moves(start, end):
+    # Calculate the knight distance between start and end using a breadth-first search
+    moves = [(2, 1), (1, 2), (-1, 2), (-2, 1),
+             (-2, -1), (-1, -2), (1, -2), (2, -1)]
+    visited = set()
+    queue = deque([(start, 0)])
+    while queue:
+        pos, dist = queue.popleft()
+        if pos == end:
+            return dist
+        if pos in visited:
+            continue
+        visited.add(pos)
+        for move in moves:
+            next_pos = (pos[0] + move[0], pos[1] + move[1])
+            if 0 <= next_pos[0] < 8 and 0 <= next_pos[1] < 8:
+                queue.append((next_pos, dist + 1))
+
+
+def shortest_path(treasures):
+    # Find the permutation of treasures with the shortest total distance
+    start = (0, 0)
+    shortest_dist = float('inf')
+    shortest_perm = None
+    for perm in permutations(treasures):
+        total_dist = sum(knight_moves(perm[i], perm[i+1])
+                         for i in range(len(perm) - 1))
+        total_dist += knight_moves(start,
+                                   perm[0]) + knight_moves(perm[-1], start)
+        if total_dist < shortest_dist:
+            shortest_dist = total_dist
+            shortest_perm = perm
+    return shortest_perm
+
+
+# The treasures' positions
+treasures = [(1, 1), (1, 0), (2, 0), (2, 1), (3, 1), (5, 3)]
+
+print(shortest_path(treasures))