Month: June 2021

Wherein we dog-leg it around town, looking forwards and backwards for our buddy in all the usual haunts.

THE WEEKLY CHALLENGE – PERL & RAKU #118

---

episode one:
“Have You Looked In The Bin?”

---

Task 1

Binary Palindrome

Submitted by: Mohammad S Anwar

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.

Method

The first task this week is a rather perfunctory opening act for the main event, but serves as an introduction to a central character, the object our quest, who we shall call Bin.

Bin, you see, is a number, and hence a valued member of society, but Bin also a palindrome. Practically, this makes his front the same as his back, which causes him to sometimes head out in the wrong direction. Consequently he gets lost.

A lot.

Usually he wanders around until he finds somewhere familiar, some watering hole, and camps out there. Intermixed with an assortment of other numbers, he may be dressed as a decimal, and possibly hard to distinguish. We can find Bin amongst a collection of other numbers by first looking beneath the disguise to his underlying binary nature, and then seeing whether that looks the same from both sides.

PERL 5 SOLUTION

There are two steps to this problem: to first look at number as a binary representation, then to look at that representation and decide whether it is a palindrome.

In the first part, we can use the format specifier "%b" to convert the decimal integer in question into a binary string. Conceivably we could give this string a set size, say 8 or 16 or 32 bits, filling forward spaces with leading zeros, which would really change the dynamics of the problem: 28 in decimal, or 11100 in binary, would in a specified 8-bit width become 0011100 and hence a palindrome! Taken further, and given free rein in zero-padding the width, the number 4, or 100, could be viewed as 00100 and hence a palindrome as well. Allowing leading zeros, which we don’t normally consider good practice when expressing a number for its numerality, opens up the floodgates when we consider numbers as constructions of characters.

This is all very intriguing and thoughtful but I do believe does not apply here. So sprintf "%b" it is.

For the palindrome we’ll use a little regular expression I dreamed up a while back. This captures a group of characters, matches a possible central pivot point, then uses a cool little trick: within the latter complex construct the matched group, $1, is inserted and reverse is applied to it, and the result of this evaluation is then itself inserted into the expression and eval’ed into that. I find the ability to dynamically create strings with code blocks that are then used to complete an expression incredibly cool. So this places the matched group, reversed, into the expression to finish the match. If a match is made the string is a palindrome.

use warnings;
use strict;
use utf8;
use feature ":5.26";
use feature qw(signatures);
no warnings 'experimental::signatures';

my $num = shift @ARGV || 153;

$_ = sprintf "%b", $num;
 
m/^(.+).?(??{reverse($1)})$/ 
    ? say 1
    : say 0 ;

raku solution

In Raku the control flow is the same but the syntax is a little different: we cast a number to binary with a rather self-explanatory .base() method, and reverse a string using .flip. Code evaluation within a regex is a little different as well, and arguably cleaner. The extra code block used to “publish” the capture so it can be used immediately within the expression is a little weird to look at, though, so it’s a tradeoff.

unit sub MAIN (Int $num = 153) ;

say
$num.base(2) ~~ m:ex/^ (.*) {} .? "{$0.flip}" $/ 
    ?? 1
    !! 0 ;

---

episode two:
“Pithy Title”

---

task 2

Adventure of Knight

Submitted by: Cheok-Yin Fung

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

Method

Now that the principle characters have been introduced, we can plunge headlong into the story. Astute observers will at this point raise a hand and that we have not, in fact, introduced our knight, making our protagonist quite mysterious. In film, character is expressed through action, not dialog. Watch what he does, not what he says. For those who demand a name for him, because, you know, everybody has a name, let’s call him Toshiro Mifune.

Let’s begin at the beginning: I don’t really do chess. No disrespect to those who do, it’s just there’s only so much time and I was mostly doing other things with it along the way. I know how to play chess, of course, and have even held my own once or twice against people who express a love for the game. I have also been solidly dispatched with the the most basic tricks, which illustrates my situation: I know how to play, but lack the experience to have a good solid plan on what to play. In the context of this task then, I know how the knight moves, but am completely unfamiliar on how to run an endgame with one; thinking strategically, looking multiple moves in advance. I was just going to need to make something up.

So just went at it and started writing functions. I read the board in from __DATA__ into an 8×8 array of arrays, leaving the xs and undefining the stars. I established all 8 knight moves as coordinate deltas, such as “two squares back and one square up”, or [-2,1], then a function that, when given a square as a pair of coordinates, returns a list of valid positions for the knight to move next. Then we had a recursive function to start trying paths. Hmmm… Ok, not all paths as we don’t want to allow going back to the square we just left, as that would start a loop cycle… So unless there’s no other possible move, no takebacks. Oh wait again, that can’t happen it seems, there’s always another move, even along the edges or in a corner.

Like I said, no endgame chops.

But what about larger loops? I can visualize a four-parter right off the bat, making a squarish figure.

Well, to keep a long story short, I got the recursive solver sort of working, enough to figure out it was rapidly falling into a 6-part loop cycle. If we were to preserve a lookup table for moves made from one square to the next, and disallow, or at least avoid, repeating the last move previously made from any given position that just might work. But we’re rather far afield in our plan now and, frankly, that might not be enough. I mean, if you can call it a plan at all. Things are getting rather unpredictable. It might also eliminate proper best solutions; it’s hard to say and I don’t like that. And further, in the end we’re just sort of wandering around hoping to snatch up the treasures by luck and circumstance. It seems less like our knight is off to slay a dragon, with purpose and direction, and more like he’s drifting aimlessly looking for America. In the fourth act he’ll discover America was him, and all around him, the whole time.

I’m tempted to implement this no-repeating loop-breaker hash but I think the strategy is doomed from the outset. I wonder what it would look like? Do we exclude the last move or every move, somehow? The idea is simultaneously both intriguing and a total hack.

A New Development

Alternately, we could take a more directed approach. Instead of wandering aimlessly we could determine the closest treasure and home in on it, snatch it up and then move to the next, repeating until we run out of targets.

How could we go about this?

If we make some sort of distance algorithm we can find which of the available knight moves gets us closest to the target, then repeat. A little further analysis determines we can generally employ some stock patterns to move one square diagonally, or orthogonally. This sounds like a bother to configure but maybe not too bad.

On investigation I don’t seem to even have a chessboard in my house. I thought I did, somewhere, but it appears I do not. So after completing a side-quest to the internet to secure a pdf file for reference we’re back on track to pursue the analysis. Life is indirect sometimes. There’s a knight-move metaphor in there somewhere.

So on examination and a little tinkering it’s looking like we can do this with four basic actions. Breaking it down:

With each movement smaller than an individual knight move there is an accompanying sequence of moves to accomplish it, and these will need to be generalized. When a knight is finally able to land directly on a target square, the goal is noted and that square is removed from the list and the next target is selected.

On in other words, returning to our story: the knight picks the closest bar and goes there first, looking for his friend. Once searched, he moves on the next, from bar to bar. His friend, Bin, will be found in the last place he looks, because of course he’s there. After all, once he’s found, why would our knight need to keep looking?

Our hero rides off into the sunset, his quest complete.

THE END

Please take your trash with you as you exit the theater.

PERL 5 SOLUTION

There are a number of difficulties in implementing the strategy we’ve outlined. Notably, our unusual movement makes optimized distances tricky to decide: ideally placing our knight one move away from the target is better than placing him one square. That one, it turns out, is tough. Instead we’ll start with simple Euclidean distance and maybe refine that later. Closer should certainly be better, if not always best. Then, when we get close, we can optimize our specific endgame routines.

We end up with a driver, to run what amounts to a dispatch table, four assignable actions and a lot of little helper routines.

The result:

quest complete!

the knight's quest took 17 steps
quest path: 
	a8 - b6 - c4 - d2 - b3 - d2 - c4 - b2 - d1 - c3 - b1 - c3 - a2 - b4 - d5 - c7 - e6
loot piles found: 
	c4 - b3 - b2 - b1 - a2 - e6

It’s not bad. Not optimal, but not bad. The final endgame approaches from inside the single move radius all seemed to follow a basic pattern, to move halfway in with one move and then the other half with its mirror. Even for the one-square adjacent shift, which is too close for this technique, we wind up needing to first move farther away from the target, to where the strategy will work.

Defining the lateral positions for this split, giving us left and right options to choose from as an intermediate position, got a little complex, but the end results shared a bit of common structure. Even picking the intermediate position for the 1-square orthogonal move shared the same ideas. Essentially the coordinate deltas between the knight and the target determines a direction, with the values within some known constraints. These deltas are processed and combined with a pair of base values for the left and right splits, then mapped to the specific squares in question. If they are still on the board they are left in the list. As it doesn’t matter which symmetrical solution we pick we grab the first index position for our move.

In the end the closing routines did end up with a lot of common steps , suggesting a general refactoring could be made, with only the specific code to determine the intermediate positions varying. Further, as these are essentially hardwired lookahead combinations, we could expand the cases to, say, positions 4 squares orthogonally distant, or 4 squares diagonally; both of these cases would required trivial reworking. Then we could continue to generalize the lookahead to all patterns of squares that can be reached in two successive moves. This is noticeably more complex but would probably be the single best optimization we could do.

Chess has been a challenge tied to computer science since its inception, and success at the highest levels still seems to hinge on computationally intensive methods of exploring move combinations to ever-increasing depths. These schemes are all realized close to the iron, in some instances these days as demonstration pieces for custom hardware, and Perl, an interpreted language, is ill-suited to keep up. There is room for improvement on the strategy certainly, in both the target selection, which could be continuously reevaluated to accommodate targets of opportunity, and various lookahead strategies to optimize first more 2-move, then 3 and more move solutions. These would be fun to explore but I think we’ll stop here.

With that said I like what we’ve come up with here. It was a challenging puzzle, this quest for a quest.

use warnings;
use strict;
use utf8;
use feature ":5.26";
use feature qw(signatures);
no warnings 'experimental::signatures';

use constant { START     => 'a8' };

## we have four package variables:
## 1. the current location of the knight
## 2. the path of squares the knight has already travelled
## 3. the treasure map, a hash of treasure squares
## 4. a list of the loot spot we've collected
our $knight    = START;
our $quest     = [ START ];
our $treasures = get_treasure_map();
our $loot      = [ ];

search_for_treasure();

###
###     MAIN LOOP
###

sub search_for_treasure () {
## see note in the distance() sub on specific distance values
    QUEST: while ( 1 ) {
        my ($target, $dist) = select_treasure();
        last QUEST if not defined $target;
        while ( $dist > 0 ) {
            if    ($dist == 1)    { $dist = one_sq_ortho($target) }
            elsif ($dist == 2)    { $dist = one_sq_diag($target)  }
            elsif ($dist == 4)    { $dist = two_sq_ortho($target) }
            else                  { $dist = approach($target) }
        }

        ## take the treasure
        push $loot->@*, $target;
        delete $treasures->{ $target };
        undef $target;
    }
    
    say "quest complete!\n";
    say "the knight's quest took ", scalar $quest->@*, " steps";
    say "quest path: \n\t", join ' - ', $quest->@*;
    say "loot piles found: \n\t", join ' - ', $loot->@*;
}

####
####    DISPATCHES
####

sub approach ($target) {
## make the best move towards the target. All available moves from the current
## position are evaluated and the move resulting in the shortest remaining
## distance to the target is chosen.
    my @kpt   = chess2mat( $knight )->@*;
    my @moves = map  { mat2chess( $_ ) }
                grep { on_board( $_ ) }
                map  { add_pt( $_, chess2mat( $knight ) ) } 
                knight_move_deltas() ;
    my $dist;
    ($knight, $dist) = select_closest( $target, \@moves );
    push $quest->@*, $knight; 
    return $dist;
}

sub two_sq_ortho ($target) {
## to close two squares orthogonally we move one square, half-way, closer and
## dog-leg either left or right two squares. Then the mirror of this move will
## reverse the dog-leg and move forward the additional square. For every pair of
## squares on the board either the left or right movement will remain on the
## board.
    my $deltas   = point_pair_deltas( $target ) ;
    my @laterals = sub {    my @half = map { $_ / 2 } $_[0]->@*;
                            my @out  = ( [@half], [@half] );    
                            for ( (0,1) ) {
                            do { $out[0]->[$_] =  2; 
                                $out[1]->[$_] = -2 } if not $_[0]->[$_];
                            }
                            return @out;
                    } -> ($deltas);

    my @moves = map  { mat2chess( $_ ) }
                grep { on_board( $_ ) }
                map  { add_pt( $_, chess2mat( $knight ) ) } 
                @laterals;

    push $quest->@*, $moves[0], $target;  
    $knight = $target;
    return 0;
    
}

sub one_sq_diag ($target) {
## to close one square diagonally there are a pair of squares of the opposite
## color 0.5 square forward and 1.5 squares to the left or right, analogous to
## the "half-way closer and split left or right" algorithm to close two squares
## orthogonally. This works in all cases except the last two squares in the corners
## on the major and minor diagonals, which require special cases
    my $deltas = point_pair_deltas( $target ) ;
    
    my @moves = map  { mat2chess( $_ ) }
                grep { on_board( $_ ) }
                map  { add_pt( $_, chess2mat( $knight ) ) } 
                map  { mul_pt( $_, $deltas ) } 
                ( [-1,2], [2,-1] );

    if ( @moves ) {
        push $quest->@*, $moves[0], $target;  
        $knight = $target ;
        return 0;
    }
    ## if there are no viable half-way split positions on the board we're in a
    ## corner and will need to get out first before we can close.
    ## there are 2 cases:
    ## 1. moving diagonally out from a corner square
    ##      to move out we take either valid move to one square beyond 
    ##      the target. Then we are one square orthogonal to the target. 
    ## 2. moving diagonally into a corner square
    ##      to move into a corner we make one lateral diagonal step. Then 
    ##      we are a two-square orthogonal distance from the target
    if ($knight =~ /a8|a1|h8|h1/) {     ## case (1) moving out 
        approach( $target );
        one_sq_ortho( $target );
    }
    else {                              ## case (2) moving in 
        my @lateral_delta  = $deltas->@*;
        $lateral_delta[0] *= -1;            ## change direction 90°
        my $temp_target = mat2chess( add_pt( \@lateral_delta, chess2mat($knight) ) );

        one_sq_diag( $temp_target );
        two_sq_ortho( $target );
    
    }
    return 0;
                
}

sub one_sq_ortho ($target) {
## to close one square orthogonally, we first need to move forward into the
## target's rank, to either square two squares to the left or right as we fit on
## the board. The problem then becomes a two-square ortogonal close. Every pair
## of squares will have one of the two lateral position available, then the
## 2-ortho close works in all cases
  
    my $deltas = point_pair_deltas( $target ) ;

    my $laterals = sub { my @out  = ( [$_[0]->@*], [$_[0]->@*] );  
                         for ( (0,1) ) {
                         do { $out[0]->[$_] =  2; 
                              $out[1]->[$_] = -2 } if not $_[0]->[$_];
                         }
                         return @out;
                    };
    my @laterals = $laterals->($deltas);

    my @moves = map  { mat2chess( $_ ) }
                grep { on_board( $_ ) }
                map  { add_pt( $_, chess2mat( $knight ) ) } 
                @laterals;

    push $quest->@*, $moves[0]; 

    $knight = $moves[0] ;    
    two_sq_ortho ($target) ;      
    return 0;
}


###
###     HELPERS
###

sub add_pt ($pt1, $pt2) {
## sums point coordinates
    return [ $pt1->[0]+$pt2->[0], $pt1->[1]+$pt2->[1] ];
}

sub mul_pt ($pt1, $pt2) {
## multiplies point coordinates
    return [ $pt1->[0]*$pt2->[0], $pt1->[1]*$pt2->[1] ];
}

sub on_board( $pt ) {
## boolean for whether a point is on the chessboard
        return 0 <= $pt->[0] <= 7 && 0 <= $pt->[1] <= 7 ;
}

sub select_treasure ( ) {
## finds the closest treasure and 
## returns a tuple of chess position and distance
    return undef if scalar keys $treasures->%* == 0; 
    my @tr = keys $treasures->%*;
    return undef if @tr == 0;
    
    return select_closest( $knight, \@tr);
}

sub select_closest ( $sq, $arr ) {
## given a chess postion and an array of chess positions
## finds closest in array to square
## returns the closest square and distance
    my ($min, $sel) = ("Inf");
    for ( $arr->@* ) {
        my $dist = distance( $sq, $_ );
        if ($dist < $min) {
            $min = $dist;
            $sel = $_;
        }
    }
    return ($sel, $min);
}

sub distance ( $sq1, $sq2 ) {
## given 2 chess squares, returns sum of squares of sides of the cartesian
## deltas.  This maintains the relative relationships between distances without
## all those pesky floats and square roots. We never care too much about the
## quantity of the distance measured, only the comparative relationships between
## squares. This simplification is reflected in the dispatch table values. 
    my ($p1, $p2) = map { chess2mat( $_ ) } ( $sq1, $sq2 ) ;
    return ( ($p1->[0] - $p2->[0])**2 + ($p1->[1] - $p2->[1])**2 );
}

sub point_pair_deltas ( $target ) {
## return array tuple of point coordinate deltas
    my ($kpt, $tpt) = map {chess2mat( $_ )} ($knight, $target);
    return [ $tpt->[0] - $kpt->[0], $tpt->[1] - $kpt->[1] ]; 
}

sub knight_move_deltas {
## the eight possible knight movements, as tuples of deltas
    state @deltas = ( [1,2],    [2,1], 
                      [-1,2],   [-2,1], 
                      [1,-2],   [2,-1], 
                      [-1,-2],  [-2,-1] );
    return @deltas;
}

sub mat2chess ($tup) {
## given a 0-based 2-tuple [h,v]
## return string in chess notation [a-h][1-8]
## [2,3] -> c4
    my @alpha = qw( a b c d e f g h );
    return $alpha[$tup->[0]] . ($tup->[1]+1) ;
}

sub chess2mat ($str) {
## given chess notation string converts to point tuple reference
## c4 -> [2,3] 
    my $c = 0;
    my %alpha = map { $_ => $c++ } qw( a b c d e f g h );
    my @str = split //, $str;
    return [ $alpha{$str[0]}, $str[1]-1 ];
}

sub get_treasure_map {
## read in the board from DATA as an 8x8 matrix
## save treasure locations as hash keys in chess format
    my $row = 9;
    my %hash;
    my @lets = ("a".."h");
    while (<DATA>) {
        $row--;
        chomp;
        my @r = map  { $_ eq '*' ? undef : $_ } split / /;
        my @t = grep { defined $r[$_] } (0..7);
        $hash{ $lets[$_] . $row } = 1 for @t;
    }
    return \%hash;
}


__DATA__
* * * * * * * * 
* * * * * * * * 
* * * * x * * * 
* * * * * * * * 
* * x * * * * * 
* x * * * * * * 
x x * * * * * * 
* x * * * * * *