Bacon-Zahl in Perl
-
18-09-2019 - |
Frage
Zuerst ja, das ist ein Hausaufgaben-Projekt für meine Perl-Klasse. Ich bin nicht auf der Suche nach der Antwort (obwohl das wäre süß). Wie ich es verstehe ich brauche einen BFS und einen regulären Ausdruck verwenden, um meine Daten zur Verwendung zu organisieren. Ich brauche Richtung auf diese. Wie verwende ich ein BFS? Muß ich einen massiven Stapel verwenden und in dem Stapel durch jeden Punkt gehen? Soll ich eine riesige Hash-Tabelle verwenden? Hat jemand auf dieses Problem gearbeitet? Wie haben Sie es zu tun? Ich brauche nur einige Richtung ist alles. Ist das ähnlich einem BST? Ist dies möglich, ohne das Diagramm-Modul? Ist dies möglich, unter Verwendung von Hash-Werten?
Lösung
Dies ist keine Antwort , aber es ist Hinweise auf Ihre Antwort.
Sie sind am besten gedient, indem man zuerst schauen, was eine Breitensuche in einem Graphen ist.
Auch wenn Sie nicht einen regulären Ausdruck gegeben worden sind, können Sie prüfen, die Tokenisieren Problem und suchen Sie das wieder wett. Möglicherweise, das wird nicht nötig sein. Überprüfen Sie die Zuordnung und sehen, ob Sie können schlürfen in einigen Informationen.
Andere Tipps
Siehe Graph .
#!/usr/bin/perl
use autodie;
use strict; use warnings;
use Graph;
use Graph::TransitiveClosure::Matrix;
my $dat = 'kevin-bacon.dat';
my $kbg = Graph->new(undirected => 1);
open my $kbf, '<', $dat;
my %movies;
while ( my $line = <$kbf> ) {
last unless $line =~ /\S/;
chomp $line;
my ($u, $m, $v) = split /;/, $line;
$kbg->add_edge($u, $v);
$movies{"$u|$v"} = $movies{"$v|$u"} = $m;
}
my $tcm = Graph::TransitiveClosure::Matrix->new($kbg,
path_length => 1,
path_vertices => 1,
);
my ($u, $v) = ('Kevin Bacon', 'Yelena Maksimova');
if ( my $n = $tcm->path_length($u, $v) ) {
printf "%d degrees of separation between %s and %s\n", $n, $u, $v;
}
my @path = $tcm->path_vertices($u, $v);
for my $i ( 0 .. @path - 2 ) {
my ($u, $v) = @path[$i, $i + 1];
print qq{$u - $v: $movies{"$u|$v"}\n};
}
Mit kevin-bacon.dat
aus dem Boost-Projekt:
3 degrees of separation between Kevin Bacon and Yelena Maksimova Kevin Bacon - Elisabeth Shue: Hollow Man (2000) Elisabeth Shue - Lev Prygunov: Saint, The (1997) Lev Prygunov - Yelena Maksimova: Bezottsovshchina (1976)