Re: [code challenge] knights move

#!/usr/bin/perl

# http://perlmonks.org/?node_id=1131329 [code challenge] knights move

use strict;
use warnings;

my @queue = my $start = <<endofdata; # find backwards
OOO
...
...
XXX
endofdata

tr/XO/OX/ for my $end = $start;
my %from;
my $count = 0;
my @moves = qw(0-5 0-8 1-6 1-8 2-1 2-6 4-5 4-8 5-6 5-8 6-1 6-6 8-5 10-
+1);

while( $_ = shift @queue and $_ ne $end ) # breadth first search
  {
  for my $move ( @moves )
    {
    my ($skip, $gap) = split /-/, $move;
    for my $new (
      s/^.{$skip}\K(\w)(.{$gap})\./.$2$1/sr,
      s/^.{$skip}\K\.(.{$gap})(\w)/$2$1./sr,
      )
      {
      if( $new ne $_ && !$from{$new} )
        {
        $from{$new} = $_; # keep backtrace
        push @queue, $new;
        }
      }
    }
  }

while( $from{$end} ) # prints in reverse order of found
  {
  $count++;
  print "     $count\n", $end;
  $end eq $start and last;
  $end = $from{$end}; # go back a step
  }
[download]

Comment on Re: [code challenge] knights move Download Code

Replies are listed 'Best First'.
Re^2: [code challenge] knights move by LanX (Saint) on Jun 21, 2015 at 22:30 UTC
Well you provided code but no output. And at least one of your allowed moves looks wrong (0-8) or I'm not understanding you're coding system. How long does your code run? Cheers Rolf _{(addicted to the Perl Programming Language and ☆☆☆☆ :) Je suis Charlie!}	[reply]
Re^3: [code challenge] knights move by Anonymous Monk on Jun 21, 2015 at 22:47 UTC
Just run it. :) 0-8 means start in upper left corner and go down two and right one. Double check the code, The 0 is the skip from the start of string, and the 8 is the gap (in bytes) between the squares to be swapped. This program runs in just under seven seconds on my machine, an AMD Athlon(tm) Dual Core Processor 5050e running at 2.8GHz.	[reply]
Re^4: [code challenge] knights move by LanX (Saint) on Jun 21, 2015 at 23:04 UTC
> Just run it. :) my mobile has no Perl installed (yet) ...but my Netbook does and I'm back home now. Congrats it's the best known solution, almost exactly the sequence given in the book. (found manually though) Cheers Rolf _{(addicted to the Perl Programming Language and ☆☆☆☆ :) Je suis Charlie!}	[reply]
Re^3: [code challenge] knights move by Anonymous Monk on Jun 21, 2015 at 23:15 UTC
A knight has eight moves, but only four are "forward", which is desired for the regexes. `move gap S E.. 1 S.. E 5 S . E. 6 S . .E 8` [download]	[reply] [d/l]