Project 4 for CS253 implemented in Raku Perl 6

ProjectFour.pm6

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