Weekly Challenge 118

Challenge, My solutions

TASK #1 › Binary Palindrome

Task

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.

My solution

Compared to the second task, this is pretty straight forward. Convert the integer into a binary representation using sprintf '%b', and then compare this string to the reversed string.

The only thing up for debate is whether an even number (the last bit is 0) could be considered a palindrome if it was left padded by one or more zeros. For example, the binary value for 6 (110) could be written as 0110 which is palindromic. For the purpose of this task, I'm not doing that.

Examples

$ ./ch-1.pl 5
1

$ ./ch-1.pl 4

TASK #2 › Adventure of Knight

Task

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.

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

My solution

This is by far the most amount of code I've written for a challenge, beating my previous code for the word search task in week 076. I guess I'll find out once I've submitted my pull request if I'm on the mark or over engineered it. It would be a lot smaller if I wasn't trying to get the bonus points :)

The first thing what is the input. Rather than parsing a file for * and x, I specify the treasure spots in chess notation (a1 = bottom left, f8 = top right). While the task specifies six pieces of treasure, you can specify as many or as few as required.

Then the task is broken up into these sub tasks:

• The _input_to_targets subroutine converts the chess notation into cell positions (a1 = 0,0, a8 = 0,7). It also adds a8 as the starting position, and checks that there are no duplicates.
• The next thing to do is find all the intermediate moves (if any) between every two points. For six pieces of treasure (7 points including the knight's origin), there are 42 (6 × 7) combinations. Thankfully we only need to calculate half of them, as the other half are just the reverse order. This is done in the _get_intermediate_moves subroutine.
• The way this subroutine works is it starts with the starting point. It then adds a move in each of the eight directions the knight can move, providing the it is still within the bounds of the board and the cell it lands on has not already been seen. If none of these result in hitting the target, these moves have another move added to them. We continue this until we hit the target. We now know the shortest path between all points of interest on the board.
• The next task is to figure out all the permutations of the order to reach the treasure. I don't like using modules that aren't part of core Perl, so I rolled my own _get_permutation function that was copied from the second task of week 109. For six pieces of treasure, there are 720 (6!) possible permutations, since we must always start at the top left position.
• For each permutation of moves we need to find the number of moves required to collect all the treasure. This is done by using the intermediate moves between two pieces of treasure, and the cell itself. If this is the shortest path or the first permutation, we store the moves in the @least_moves array.
• Finally we display the results. For this I convert the grid position to chess notation with the _cn function. If the cell has a piece of treasure, then I put asterisks around the cell.

Examples

$ ./ch-2.pl e6 d4 c3 a2 b2 b1
The shortest path is 12 steps
*a8* » c7 » *e6* » *d4* » b5 » *c3* » *a2* » c3 » *b1* » c3 » d1 » *b2*