Perl Weekly Challenge: Week 121

Challenge 1:

Invert Bit

You are given integers 0 <= $m <= 255 and 1 <= $n <= 8.

Write a script to invert $n bit from the end of the binary representation of $m and print the decimal representation of the new binary number.

Example

Input: $m = 12, $n = 3
Output: 8

Binary representation of $m = 00001100
Invert 3rd bit from the end = 00001000
Decimal equivalent of 00001000 = 8

Input $m = 18, $n = 4
Output: 26

Binary representation of $m = 00010010
Invert 4th bit from the end = 00011010
Decimal equivalent of 00011010 = 26

This is very easy to do in Perl; a one liner even. We find the right bit to invert by left shifting 1, $n ($ARGV[1]) number of places minus 1 because we are starting from position 0. Then that is XOR'ed with $m ($ARGV[0]) to flip that bit.

say $ARGV[0] ^ (1 << $ARGV[1] - 1);

(Full code on Github.)

And it's a one-liner in Raku as well. Notice the extra pair of parentheses around @*ARGS[1] - 1. I was initially completely mystified by the wrong answers I was getting from a straight port of the Perl code until I realized that Raku had changed the order of precedence for left bit shift from what Perl had it as.

say @*ARGS[0] +^ (1 +< (@*ARGS[1] - 1));

(Full code on Github.)

Challenge 2:

The Travelling Salesman

You are given a NxN matrix containing the distances between N cities.

Write a script to find a round trip of minimum length visiting all N cities exactly once and returning to the start.

Example

Matrix: [0, 5, 2, 7]
        [5, 0, 5, 3]
        [3, 1, 0, 6]
        [4, 5, 4, 0]

Output:
        length = 10
        tour = (0 2 1 3 0)

BONUS 1: For a given number N, create a random NxN distance matrix and find a solution for this matrix.

BONUS 2: Find a solution for a random matrix of size 15x15 or 20x20

Unfortunately due to a severe lack of a time, I was not able to get this one done in time for submission though I will try to do it later.