laurent_r

These are some answers to the Week 118 of the Perl Weekly Challenge organized by Mohammad S. Anwar.

Spoiler Alert: This weekly challenge deadline is due in a couple of days (June 27, 2021). This blog post offers some solutions to this challenge, please don’t read on if you intend to complete the challenge on your own.

Task 1: Binary Palindrome

You are given a positive integer $N.

Write a script to find out if the binary representation of the given integer is Palindrome. Print 1 if it is otherwise 0.

Example:

Input: $N = 5
Output: 1 as binary representation of 5 is 101 which is Palindrome.

Input: $N = 4
Output: 0 as binary representation of 4 is 100 which is NOT Palindrome.

Binary Palindrome in Raku

In Raku, the base method converts the invocant number to a string representation of the number in the given base. So we need to compare compare the binary representation of the number to its reverse string (using the flip routine). The code for doing that is a simple Raku one-liner. The + sign is used to numify Boolean values returned by the comparison (i.e. convert Trueand False values to 1 and 0, respectively).

use v6;

for 1..12 -> $test {
    say "$test -> ", + ($test.base(2) eq $test.base(2).flip);
}

This is the output with the 12 test cases:

$ raku ./bin-palindrome.raku
1 -> 1
2 -> 0
3 -> 1
4 -> 0
5 -> 1
6 -> 0
7 -> 1
8 -> 0
9 -> 1
10 -> 0
11 -> 0
12 -> 0

Binary Palindrome in Perl

The Perl implementation is quite similar to the Raku implementation, except that we use the sprintf built-in function to convert the number to a binary representation of the input number.

use strict;
use warnings;
use feature "say";

for my $test (1..12) {
    my $bin_num = sprintf "%b", $test;
    say "$test -> ", $bin_num eq reverse ($bin_num) ? 1 : 0;
}

This is the output with the 12 test cases:

$ perl ./bin-palindrome.pl
1 -> 1
2 -> 0
3 -> 1
4 -> 0
5 -> 1
6 -> 0
7 -> 1
8 -> 0
9 -> 1
10 -> 0
11 -> 0
12 -> 0

Task 2: Adventure of Knight

A knight is restricted to move on an 8×8 chessboard. The knight is denoted by N and its way of movement is the same as what it is defined in Chess.

* represents an empty square. x represents a square with treasure.

The Knight’s movement is unique. It may move two squares vertically and one square horizontally, or two squares horizontally and one square vertically (with both forming the shape of an L).

There are 6 squares with treasures.

Write a script to find the path such that Knight can capture all treasures. The Knight can start from the top-left square.

  a b c d e f g h
8 N * * * * * * * 8
7 * * * * * * * * 7
6 * * * * x * * * 6
5 * * * * * * * * 5
4 * * x * * * * * 4
3 * x * * * * * * 3
2 x x * * * * * * 2
1 * x * * * * * * 1
  a b c d e f g h

BONUS: If you believe that your algorithm can output one of the shortest possible path.

I have secured a Raku program solving the knight’s tour problem, using Warnsdorff’s rule. Since this program guarantees that the knight visits every square exactly once, we’re guaranteed to find all treasures in a relatively limited number of moves. But it is rather unlikely to find the shortest possible path. I’ll try to look for an optimal path, but this appears to require an entirely different algorithm. I’m very busy this week: I have meetings late on Thursday and Friday evenings and I have a fully booked weekend, with at best a couple of hours free on Saturday night. In short, I’m really not sure that I’ll be able to complete task 2 in time. This is the reason I decided to publish this blog post with solutions to only task 1. I’ll update this post if I succeed to complete task 2 in due time.

Wrapping up

The next week Perl Weekly Challenge will start soon. If you want to participate in this challenge, please check https://perlweeklychallenge.org/ and make sure you answer the challenge before 23:59 BST (British summer time) on Independence Day, i.e. July 4, 2021. And, please, also spread the word about the Perl Weekly Challenge if you can.