Anonymous user
I'm a software engineer, get me out of here: Difference between revisions
I'm a software engineer, get me out of here (view source)
Revision as of 20:28, 9 December 2020
, 3 years ago→{{header|Phix}}
mNo edit summary |
|||
Line 777:
(11, 11) (11, 12) (14, 15) (16, 17) (17, 16) (18, 16) (20, 14)
(11, 11) (12, 12) (13, 11) (17, 15) (20, 12) (21, 11) (22, 12)
</pre>
=={{header|Perl}}==
<lang perl>#!/usr/bin/perl
use strict;
use warnings;
use List::Util qw( first );
my $d = join '', <DATA>, (" \n") x 4;
$d =~ s/.+/ sprintf "%-31s", $& /ge; # padding for single number addressing
#print $d;
my $w = $d =~ /\n/ ? $+[0] : die;
sub xy { "(@{[ int $_[0] / $w ]},@{[ $_[0] % $w ]})" }
sub fromxy { $_[0] * $w + $_[1] }
my @directions = ( 1, -1, -$w-1 .. -$w+1, $w-1 .. $w+1 );
my $startpos = fromxy 11, 11;
my @nodes;
push @nodes, $-[0] while $d =~ /\d/g;
my %dist = map { $_ => alldest($_) } @nodes; # all shortest from-to paths
my @best;
$best[ tr/ // ] .= "\t$_\n" for grep $_, map $dist{$startpos}{$_},
grep { '0' eq substr $d, $_, 1 } @nodes;
my $short = first { $best[$_] } 0 .. $#best;
my $n = $best[$short] =~ tr/\n//;
print "shortest escape routes ($n) of length $short:\n",
$best[$short] =~ s/\d+/ xy $& /ger;
print "\nshortest from (21,11) to (1,11):\n\t",
$dist{fromxy 21, 11}{fromxy 1, 11} =~ s/\d+/ xy $& /ger, "\n";
print "\nshortest from (1,11) to (21,11):\n\t",
$dist{fromxy 1, 11}{fromxy 21, 11} =~ s/\d+/ xy $& /ger, "\n";
@best = ();
$best[tr/ //] .= "\t$_\n" for map { values %$_ } values %dist;
print "\nlongestshortest paths (length $#best) :\n",
$best[-1] =~ s/\d+/ xy $& /ger;
my @notreach = grep !$dist{$startpos}{$_}, @nodes;
print "\nnot reached from HQ:\n\t@notreach\n" =~ s/\d+/ xy $& /ger;
@best = ();
$best[tr/ //] .= "\t$_\n" for values %{ $dist{$startpos} };
print "\nlongest reinforcement from HQ is $#best for:\n",
$best[-1] =~ s/\d+/ xy $& /ger;
sub alldest
{
my @queue = shift;
my $dd = $d;
my %to;
while( my $path = shift @queue )
{
my $from = (split ' ', $path)[-1];
my $steps = substr $dd, $from, 1;
' ' eq $steps and next;
$to{$from} //= $path;
$steps or next;
substr $dd, $from, 1, 0;
for my $dir ( @directions )
{
my $next = $from + $steps * $dir;
(substr $dd, $next, 1) =~ /\d/ and push @queue, "$path $next";
}
}
return \%to;
}
__DATA__
00000
00003130000
000321322221000
00231222432132200
0041433223233211100
0232231612142618530
003152122326114121200
031252235216111132210
022211246332311115210
00113232262121317213200
03152118212313211411110
03231234121132221411410
03513213411311414112320
00427534125412213211400
013322444412122123210
015132331312411123120
003333612214233913300
0219126511415312570
0021321524341325100
00211415413523200
000122111322000
00001120000
00000
</lang>
{{out}}
<pre>
shortest escape routes (40) of length 4:
(11,11) (11,12) (8,12) (6,12) (0,12)
(11,11) (10,11) (7,11) (7,12) (1,6)
(11,11) (11,12) (8,9) (2,9) (1,8)
(11,11) (11,12) (8,9) (2,9) (1,9)
(11,11) (10,10) (8,10) (5,13) (1,13)
(11,11) (11,12) (8,9) (2,15) (1,14)
(11,11) (11,12) (8,9) (2,15) (1,15)
(11,11) (11,12) (8,9) (2,15) (1,16)
(11,11) (10,10) (8,10) (5,7) (2,4)
(11,11) (10,11) (7,8) (7,5) (2,5)
(11,11) (11,12) (8,9) (2,15) (2,16)
(11,11) (11,12) (11,9) (9,9) (3,3)
(11,11) (10,11) (7,8) (4,5) (3,4)
(11,11) (12,11) (12,14) (8,18) (3,18)
(11,11) (12,11) (9,14) (6,17) (4,19)
(11,11) (11,12) (8,9) (8,3) (6,1)
(11,11) (10,10) (8,8) (8,4) (6,2)
(11,11) (11,12) (11,15) (11,17) (7,21)
(11,11) (11,12) (8,9) (8,3) (8,1)
(11,11) (10,10) (8,8) (12,4) (9,1)
(11,11) (11,12) (8,9) (14,3) (11,0)
(11,11) (10,11) (7,8) (7,5) (12,0)
(11,11) (12,10) (13,10) (13,5) (13,0)
(11,11) (10,10) (12,8) (16,4) (13,1)
(11,11) (12,11) (12,14) (16,18) (13,21)
(11,11) (10,10) (8,8) (12,4) (15,1)
(11,11) (11,12) (11,15) (11,17) (15,21)
(11,11) (10,10) (12,8) (16,4) (16,1)
(11,11) (10,11) (10,14) (12,16) (16,20)
(11,11) (12,11) (12,14) (16,18) (16,21)
(11,11) (12,11) (15,8) (15,5) (18,2)
(11,11) (10,11) (13,8) (14,7) (18,3)
(11,11) (11,12) (14,9) (18,5) (19,4)
(11,11) (11,12) (14,15) (16,15) (19,18)
(11,11) (11,12) (14,12) (16,12) (20,16)
(11,11) (10,11) (13,11) (17,15) (20,18)
(11,11) (12,10) (13,10) (18,15) (21,15)
(11,11) (11,12) (14,9) (18,13) (22,9)
(11,11) (12,11) (15,8) (18,11) (22,11)
(11,11) (11,12) (14,9) (18,13) (22,13)
shortest from (21,11) to (1,11):
(21,11) (21,12) (19,10) (14,10) (10,10) (8,8) (4,8) (1,11)
shortest from (1,11) to (21,11):
(1,11) (2,10) (5,13) (9,9) (15,3) (20,8) (20,10) (21,11)
longestshortest paths (length 9) :
(1,11) (1,12) (4,9) (6,9) (8,9) (14,15) (16,17) (17,16) (18,16) (20,14)
(2,9) (2,10) (5,7) (8,7) (8,9) (14,15) (16,17) (17,16) (18,16) (20,14)
(12,21) (12,19) (12,17) (12,16) (12,12) (12,11) (15,8) (15,5) (15,2) (14,2)
(7,3) (7,4) (5,4) (8,7) (8,9) (14,15) (16,17) (17,16) (18,16) (20,14)
(10,21) (10,20) (9,19) (9,16) (9,9) (15,3) (15,8) (15,5) (15,2) (14,2)
(2,13) (2,15) (3,15) (6,12) (12,18) (13,19) (13,20) (17,16) (18,16) (20,14)
(11,21) (11,20) (11,16) (11,17) (11,13) (13,11) (17,7) (15,5) (15,2) (14,2)
not reached from HQ:
(2,18) (4,3) (18,20)
longest reinforcement from HQ is 6 for:
(11,11) (11,12) (11,15) (13,17) (13,19) (13,20) (17,20)
(11,11) (11,12) (11,15) (11,17) (7,17) (7,20) (6,20)
(11,11) (12,11) (9,14) (6,17) (4,17) (4,18) (3,19)
(11,11) (11,12) (14,12) (16,12) (20,12) (21,11) (22,12)
(11,11) (11,12) (14,15) (16,17) (17,16) (18,16) (20,14)
</pre>
| |||