Created
April 20, 2019 17:06
-
-
Save uzluisf/e5ac05a134b881ee140b8d02c50f1d25 to your computer and use it in GitHub Desktop.
Project 4 for CS253 implemented in Raku Perl 6
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
unit module ProjectFour; | |
=begin pod | |
=TITLE ProjectFour | |
=SUBTITLE Find a route in map by backtracking using a Stack | |
The module C<ProjectFour> implements two classes (C<City> and C<RouteMap>) | |
to find a route, if one exists, from an origin city to a destination city, | |
given a particular map. In a map, a city B is adjacent to a city A if there's | |
an arrow pointing from A to B. For example, in N->Q we say that Q is adjacent | |
to N. A route from an origin city to a destination city is a sequence of | |
cities such that each city in the sequence is adjacent to the previous one. | |
Both the cities and a map are provided in a file where: | |
=for item | |
Line 1 contains a comma-separated list of city names. | |
=for item | |
Remainder of file contains a comma-separated list of city pairs separated | |
separated by ‘-‘, where the second city in the pair is adjacent to the first. | |
=head2 Sample file | |
=begin code | |
P,Q,R,S,T,W,X,Y,Z | |
P-R,P-W,Q-X,R-X,S-T,T-W,W-S,W-Y,Y-R,Y-Z | |
=end code | |
=USAGE | |
=begin code | |
use lib '.'; | |
use ProjectFour; | |
# create a map and populate it | |
my RouteMap $x .= new; | |
$x.readMap("./data.csv"); | |
# create two cities | |
my $orig = $x.get-city(4); | |
my $dest = $x.get-city(8); | |
# print route if it exists | |
if $x.is-route($orig, $dest) { | |
print qq:to/END/; | |
ORIGIN: {$orig.name} | |
DESTINATION: {$dest.name} | |
ROUTE: {$x.get-route} | |
END | |
} | |
# clean up map | |
$x.untrace; | |
# print route if it exists | |
$orig = $x.get-city(3); | |
$dest = $x.get-city(6); | |
if $x.is-route($orig, $dest) { | |
print qq:to/END/; | |
ORIGIN: {$orig.name} | |
DESTINATION: {$dest.name} | |
ROUTE: {$x.get-route} | |
END | |
} | |
=end code | |
=METHODS | |
=end pod | |
#| Represents a city in the route map. | |
class City is export { | |
has Str $.name; #= name of the city | |
has Bool $.visited is rw = False; #= city's visit state | |
has City @!adjacent-cities; #= array of adjacent cities | |
#| Add city adjacent to invocant. | |
method add-adjacent( City:D $c --> True ) { | |
@!adjacent-cities.push: $c; | |
} | |
#| Return array of cities that are adjacent to invocant. | |
method get-adjacents( --> Array ) { | |
@!adjacent-cities; | |
} | |
#| Check if invocant has adjacent unvisited cities. | |
method has-unvisited( --> Bool ) { | |
for @!adjacent-cities -> $city { | |
return True unless $city.visited; | |
} | |
return False; | |
} | |
} | |
#| Represents the route map. | |
class RouteMap is export { | |
has City @!cities; #= array of cities | |
has Str $!route; #= route from origin to destination | |
#|«Read the map. Throw exception, catch it and return false if file is | |
empty.» | |
method readMap( Str:D $file_name --> Bool ) { | |
return False unless $file_name.IO.f; | |
try { | |
if $file_name.IO.s == 0 { | |
die "'$file_name' is either non-existent or empty" | |
} | |
CATCH { | |
default { | |
put "Catching"; | |
return False; | |
} | |
} | |
} | |
# get all lines from data file. | |
my Str @lines = $file_name.IO.lines; | |
# process first of data file. This line contains a | |
# comma-separated list of cities. | |
for @lines.first.split(',')».trim -> $city { | |
@!cities.push: City.new(:name($city)); | |
} | |
# process remainder of data file, which is a comma-separated list | |
# of city pairs separated by '-'. In each pair, the second city is | |
# adjacent to the second. | |
for @lines[1..*].split(',') -> $pair { | |
my ($city-name, $adj) = $pair.trim.split('-'); | |
for @!cities -> $city { | |
if $city.name eq $city-name { | |
for @!cities { | |
$city.add-adjacent($_) if $_.name eq $adj; | |
} | |
} | |
} | |
} | |
return True; | |
} | |
#|«Return True if there is a route from origin to destination. Otherwise, | |
False.» | |
method is-route( City:D $origin, City:D $destination --> Bool ) { | |
return False unless $origin.DEFINITE and $destination.DEFINITE; | |
my City @stack; | |
# start journey at origin 😃. | |
@stack.unshift($origin); | |
@stack.first.visited = True; | |
loop { | |
my $city-at-top = @stack.first; | |
# top has either no adjacent unvisited city or has no adjacent | |
# cities at all, in which case remove from top of stack. | |
if not $city-at-top.has-unvisited { | |
@stack.shift; | |
} | |
# top still has unvisited adjacent cities so visit them. | |
else { | |
for $city-at-top.get-adjacents -> $adj-city { | |
if not $adj-city.visited { | |
# push unvisited adjacent city to the stack | |
# and mark it as visited. | |
@stack.unshift($adj-city); | |
$adj-city.visited = True; | |
last; | |
} | |
} | |
} | |
# stop if stack is empty. | |
last if @stack.elems == 0; | |
# destination found! | |
if @stack.first.name eq $destination.name { | |
$!route = @stack.reverse».name.join(" -> "); | |
return True; | |
} | |
} | |
return False; | |
} | |
#|«Return city at 0 ≤ $position ≤ n - 1, where n is the number of cities. | |
City objects are stored in the same order they appear in the input file.» | |
method get-city( Int $position --> City ) { | |
my City $c; | |
try { | |
unless 0 ≤ $position ≤ @!cities.end { | |
die "Position out of range." | |
} | |
CATCH { | |
default { | |
put "Catching"; | |
return $c; | |
} | |
} | |
} | |
$c = @!cities[$position]; | |
return $c; | |
} | |
#|«If a route is found from $origin to $destination, it will | |
print it to STDOUT as $origin -> ... -> $destination.» | |
method get-route( City:D $origin, City:D $destination --> Str ) { | |
self.untrace; | |
if self.is-route($origin, $destination) { | |
return $!route | |
} | |
# empty string indicates no route | |
return ""; | |
} | |
#| Mark all cities in the map as unvisited. | |
method untrace { | |
@!cities.map({ .visited = False }); | |
} | |
} | |
=begin pod | |
=AUTHOR Luis F. Uceta | |
=PURPOSE Pedagogical | |
=DATE April 14, 2019 | |
=end pod |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment