CODEWITHSUNDEEP
numbersprologsum
eszik.k
eszik.k

Reputation: 1781

Prolog - Summing numbers

I am new in prolog. I have found breadth first search program in the internet which is search for routes between cities. I want to extend the program to store and calculate distances. But I can't figure out how to do it.

The original code:

move(loc(omaha), loc(chicago)).
move(loc(omaha), loc(denver)).
move(loc(chicago), loc(denver)).
move(loc(chicago), loc(los_angeles)).
move(loc(chicago), loc(omaha)).
move(loc(denver), loc(los_angeles)).
move(loc(denver), loc(omaha)).
move(loc(los_angeles), loc(chicago)).
move(loc(los_angeles), loc(denver)).

bfs(State, Goal, Path) :-
    bfs_help([[State]], Goal, RevPath), reverse(RevPath, Path).

bfs_help([[Goal|Path]|_], Goal, [Goal|Path]).
bfs_help([Path|RestPaths], Goal, SolnPath) :-
    extend(Path, NewPaths),
    append(RestPaths, NewPaths, TotalPaths),
    bfs_help(TotalPaths, Goal, SolnPath).

extend([State|Path], NewPaths) :-
    bagof([NextState,State|Path],
          (move(State, NextState), not(member(NextState, [State|Path]))),
          NewPaths), !.
extend(_, []).

Output:

1 ?- bfs(loc(omaha), loc(chicago), X).
X = [loc(omaha), loc(chicago)] ;
X = [loc(omaha), loc(denver), loc(los_angeles), loc(chicago)] ;
false.

I have tried this:

bfs(A,B,Path,D) :-
   bfs(A,B,Path),
   path_distance(Path,D).

path_distance([_], 0).
path_distance([A,B|Cs], S1) :-
   move(A,B,D),
   path_distance(Cs,S2),
   S1 is S2+D.

bfs(A,B, Path) :-
    bfs_help([[A]], B, RevPath), reverse(RevPath, Path).

bfs_help([[Goal|Path]|_], Goal, [Goal|Path]).
bfs_help([Path|RestPaths], Goal, SolnPath) :-
    extend(Path, NewPaths),
    append(RestPaths, NewPaths, TotalPaths),
    bfs_help(TotalPaths, Goal, SolnPath).

extend([State|Path], NewPaths) :-
    bagof([NextState,State|Path],
          (move(State, NextState,_), not(member(NextState, [State|Path]))),
          NewPaths), !.
extend(_, []).

Output: 

5 ?- bfs(loc(omaha), loc(chicago), X,D).
false.

What i want:

1 ?- bfs(loc(omaha), loc(chicago), X, D).
X = [loc(omaha), loc(chicago)] ;
D = 1
X = [loc(omaha), loc(denver), loc(los_angeles), loc(chicago)] ;
D = 6
false.

Please anyone help me to solve this problem! Sorry for my english.

Upvotes: 2

Views: 120

Answers (1)

false
false

Reputation: 10102

It seems cheapest to define a relation path_distance/2. That is not the most elegant way, but it should serve your purpose:

bfs(A,B,Path,D) :-
   bfs(A,B,Path),
   path_distance(Path,D).

path_distance([_], 0).
path_distance([A,B|Cs], S1) :-
   move(A,B,D),
   path_distance([B|Cs],S2),
   S1 is S2+D.

You might also reconsider bfs/3 a bit. The query

?- bfs(A,B, Path).

Gives rather odd results.

Both move/2 and move/3 are now used. Thus:

move(A,B) :-
   move(A,B,_).

move(loc(omaha), loc(chicago),1).
move(loc(omaha), loc(denver),2).
move(loc(chicago), loc(denver),1).
move(loc(chicago), loc(los_angeles),2).
move(loc(chicago), loc(omaha),1).
move(loc(denver), loc(los_angeles),2).
move(loc(denver), loc(omaha),1).
move(loc(los_angeles), loc(chicago),2).
move(loc(los_angeles), loc(denver),3).

Upvotes: 2

Related Questions