% the DCG (definite clause grammar) for the given input specification
%
% You will need to make one change to this grammar to correctly read all test
%  cases that I run your programs against (one of the test cases will fail with
%  this grammar). It is up to you to determine what change that is (it should
%  be a fairly simple change).
%
s((G,Q))              --> graph(G), delim,
                          queries(Q), delim.
graph([E])            --> edgeline(E).
graph([E|Es])         --> edgeline(E), graph(Es).
edgeline(edge(S,E,W)) --> city(S), whitespace,
                          city(E), whitespace,
                          distance(D), newline, {
                          atoi( D, W )}.
delim                 --> "?\n".
queries([Q])          --> queryline(Q).
queries([Q|Qs])       --> queryline(Q), queries(Qs).
queryline(query(S,E)) --> city(S), whitespace,
                          city(E), newline.
whitespace            --> space.
whitespace            --> space, whitespace.
space                 --> " ".
space                 --> "\t".
city([L])             --> letter(L).
city([L|Ls])          --> letter(L), city(Ls).
distance([D])         --> digit(D).
distance([D|Ds])      --> digit(D), distance(Ds).
newline               --> "\n".
letter(L)             --> [L], {
                          char_code( 'a', Char_a ),
                          char_code( 'z', Char_z ),
                          char_code( 'A', Char_A ),
                          char_code( 'Z', Char_Z ),
                          ((L >= Char_a, L =< Char_z);
                           (L >= Char_A, L =< Char_Z))}.
digit(D)              --> [D], {
                          char_code( '0', Char_0 ),
                          char_code( '9', Char_9 ),
                          D >= Char_0, D =< Char_9}.

% prints a string to the screen
%
put_codes( [C|[]] ) :- !,
                       put_code( C ).
put_codes( [C|Cs] ) :- put_code( C ),
                       put_codes( Cs ).

% reads in everything until the EOF (code = -1) and puts it into Result
%
get_codes( Result ) :- get_code( C ),
                       get_codes_acc( C, Result ).
get_codes_acc( -1, [] ) :- !.
get_codes_acc( C, [C|Rest] ) :- get_code( Next ),
                                get_codes_acc( Next, Rest ).

% takes a string corresponding to the input for the program, and passes it
%  through the DCG parser defined above, and returns a pair of lists of edge()s
%  and query()s
%
parse( Input, Result ) :- s( Result, Input, [] ).

% maps the dijkstra() predicate over each query in the list
%
findShortest( [Q|[]] ) :- !,
                          dijkstra( Q ).
findShortest( [Q|Qs] ) :- dijkstra( Q ),
                          findShortest( Qs ).

% converts a numeric string to an integer
%  'bad things' may happen if argument 1 is not numeric
%
atoi( Str, Num ) :- atoi_acc( Str, 0, Num ).
atoi_acc( [], Num, Num ) :- !.
atoi_acc( [S|Ss], Num, Res ) :- char_code( '0', Char_0 ),
                                Next is (10 * Num) + (S - Char_0),
                                atoi_acc( Ss, Next, Res ).

% initializes the "edge()" predicate in preparation for the following assertions
:- dynamic( edge/3 ).

% actually builds a graph by asserting each edge predicate as true
%
% This is as if we had defined those predicates directly in the file... so if
%  the file contains some edge line "Airdrie Banff 93", then this will act just
%  as if we had placed the fact:
%      edge( "Airdrie", "Banff", 93 ).
%  here in this program.
%
setGraph( [E|[]] ) :- !,
                      asserta( E ).
setGraph( [E|Es] ) :- asserta( E ),
                      setGraph( Es ).

% this may be of some use
%
% Remember that A;B means "A or B".
%  To see why we do things this way, refer to the web page / tutorial:
%  http://www.csupomona.edu/~jrfisher/www/prolog_tutorial/2_15.html
%
connected( A, B ) :- edge( A, B, _ );
                     edge( B, A, _ ).

% this is where the real work (for part A) happens
%
% (It is your job to fill in ths function.)
%
dijkstra( query( S, E ) ) :- put_codes( S ),
                             put_codes( " " ),
                             put_codes( E ),
                             put_codes( " (dist)\n" ).

% The top level for the program. Reads in the provided file, parses it into
%  edge() and query() lists, calls all the edges, then finds each shortest path
%  asked for.
main :- get_codes( File ),
        parse( File, (Edges, Queries) ),
        setGraph( Edges ),
        findShortest( Queries ).

:- initialization( main ).