The weekly challenge 281 - Task 2: Knight’s Move

  1 #!/usr/bin/env perl
  2 # https://theweeklychallenge.org/blog/perl-weekly-challenge-281/#TASK2
  3 #
  4 # A Knight in chess can move from its current position to any square two rows
  5 # or columns plus one column or row away. So in the diagram below, if it starts
  6 # a S, it can move to any of the squares marked E.
  7 #
  8 # Write a script which takes a starting position and an ending position and
  9 # calculates the least number of moves required.
 10 #
 11 # https://theweeklychallenge.org/images/blog/week_281_task_2.png
 12 #
 13 ## Example 1
 14 ##
 15 ## Input: $start = 'g2', $end = 'a8'
 16 ## Ouput: 4
 17 ##
 18 ## g2 -> e3 -> d5 -> c7 -> a8
 19 #
 20 ## Example 2
 21 ##
 22 ## Input: $start = 'g2', $end = 'h2'
 23 ## Ouput: 3
 24 ##
 25 ## g2 -> e3 -> f1 -> h2
 26 #
 27 ############################################################
 28 ##
 29 ## discussion
 30 ##
 31 ############################################################
 32 #
 33 # Some observations:
 34 # 1. The shortest path from one square to the directly neighboring
 35 #    square has length 5
 36 #    Example: a8->c7->e6->d8->c6->b8 (for all other combinations
 37 #    it's just shifted around, mirrored, or rotated by 90°)
 38 # 2. The shortest path from one square to its diagonal neighboar has
 39 #    length 2, except if it's in the corner (a8->b7 is one move to
 40 #    b6 or c7, then it's a case of walking to the directly neighboring
 41 #    square, so the length is 1+5=6 in this case)
 42 # 3. The shortest path to cover most of the distance on the board from
 43 #    one end to the next (or the opposing corner) is basically 4, plus
 44 #    some more steps to jump to the exact square you want to end up in
 45 # From this, we can assume there is an upper limit of how many steps are
 46 # required to go from any square to any other square: 4+6=10 steps
 47 # should be enough in any case.
 48 # So we can brute-force this with a max-depth of 10.
 49 
 50 use strict;
 51 use warnings;
 52 use List::Util qw(min any);
 53 
 54 knights_move("g2", "a8");
 55 knights_move("g2", "h2");
 56 
 57 sub knights_move {
 58    my ($start, $end) = @_;
 59    print "Input: $start -> $end\n";
 60    my $l = min_length($start, $end, 1, []);
 61    print "Output: $l\n";
 62 }
 63 
 64 sub min_length {
 65    my ($start, $end, $step, $seen) = @_;
 66    # print "=> [" . join(",", @$seen) . "] $start, $end, $step\n";
 67    if($start eq $end) {
 68       return 0;
 69    }
 70    if($step > 10 || any { $_ eq $start} @$seen) {
 71       return 1000;
 72    }
 73    my $map = { "a" => 1, "b" => 2, "c" => 3, "d" => 4,
 74       "e" => 5, "f" => 6, "g" => 7, "h" => 8 };
 75    my $reverse_map = { 1 => "a", 2 => "b", 3 => "c", 4 => "d",
 76       5 => "e", 6 => "f", 7 => "g", 8 => "h" };
 77    my ($char1, $digit1) = split //, $start;
 78    my ($char2, $digit2) = split //, $end;
 79    my @lengths = ();
 80    foreach my $direction ( ([-2, 1], [-2,-1], [-1,-2], [-1,2],
 81       [2,1], [2,-1], [1,2], [1,-2]) ) {
 82         my $c = $map->{$char1} + $direction->[0];
 83         my $d = $digit1 + $direction->[1];
 84         if(legal( $c, $d)) {
 85            next if any  { $_ eq $start} @$seen;
 86            my $l = 1 + min_length($reverse_map->{$c} . $d, $end, $step+1, [@$seen, $start] );
 87            next unless $l;
 88            push @lengths, $l if $l < 1000;
 89         }
 90    }
 91    return min(@lengths, 1000);
 92 }
 93 
 94 sub legal {
 95    my ($mapped_digit, $digit) = @_;
 96    if($mapped_digit < 1 || $digit < 1) {
 97       return 0;
 98    }
 99    if($mapped_digit > 8 || $digit > 8) {
100       return 0;
101    }
102    return 1;
103 }