Programming_Languages_I/BackToAthens/movesBFS.pl at main · AntonisAk/Programming_Languages_I · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
/* moves.pl */
/* A prolog program that solves the back to Athens problem using custom (efficient) BFS */

/* Read input */
read_and_return(File, N, Grid) :-
    open(File, read, Stream),
    read_line(Stream, [N]),
    read_grid(Stream, N, Grid),
    close(Stream).

read_grid(Stream, N, Grid) :-
    ( N > 0 ->
	Grid = [Row|Rows],
        read_line(Stream, Row),
        N1 is N - 1,
        read_grid(Stream, N1, Rows)
    ; N is 0 ->
	Grid = []
    ).

read_line(Stream, List) :-
    read_line_to_codes(Stream, Line),
    atom_codes(A, Line),
    atomic_list_concat(As, ' ', A),
    maplist(atom_number, As, List).

/*-------------------------------------------*/

grid(Grid,X,Y,R):-
	nth0(X,Grid,XGrid),
	nth0(Y,XGrid,R),
	!.

conc([], Y, Y).
conc([A|X], Y, [A|Z]) :- conc(X, Y, Z).

legal_step(Grid,(X,Y,_,_,_),(XL,YL,X,Y,Dir)):-
	((XL is X+1, YL is Y+1, Dir = se);
	(XL is X  , YL is Y+1, Dir = e );
	(XL is X+1, YL is Y  , Dir = s );
	(XL is X-1, YL is Y+1, Dir = ne);
	(XL is X+1, YL is Y-1, Dir = sw);
	(XL is X  , YL is Y-1, Dir = w);
	(XL is X-1, YL is Y  , Dir = n);
	(XL is X-1, YL is Y-1, Dir = nw)),
	grid(Grid,X,Y,R1),
	grid(Grid,XL,YL,R2),
	R2 < R1.

next_step(Grid,(X,Y,_,_,_),(NextX,NextY,X,Y,Dir),Path):-
    legal_step(Grid,(X,Y,_,_,_),(NextX,NextY,X,Y,Dir)),
    \+ member((NextX,NextY,_,_,_),Path).


next_steps(_,[],[],Path,Path).
next_steps(Grid,[OldH|OldT],NewQueue,Prev,Path):-
	findall(Touples,next_step(Grid,OldH,Touples,Prev),List1),
	conc(Prev,List1,Prev1),
	next_steps(Grid,OldT,List2,Prev1,Path),
	conc(List1,List2,NewQueue).

/*-------------------------------------------*/


find_path(_,0,0,[]).
find_path(Prev,X,Y,[Dir|Path]):-
	member((X,Y,PrevX,PrevY,Dir),Prev),
	find_path(Prev,PrevX,PrevY,Path),
	!.


solve(_,_,[],_,[]).
solve(_,Goal,Queue,Path,Path):-
	member((Goal,Goal,_,_,_),Queue).
solve(Grid,Goal,Queue,Prev,Path):-
	next_steps(Grid,Queue,Queue1,Prev,Prev1),
    solve(Grid,Goal,Queue1,Prev1,Path).


moves(File,Moves):-
	read_and_return(File,Size,Grid),
	Goal is Size-1,
	solve(Grid,Goal,[(0,0,0,0,start)],[],Path),
	(((\+ member((Goal,Goal,_,_,_),Path))->
	Moves = impossible);
	(find_path(Path,Goal,Goal,MovesRev),
	reverse(MovesRev,Moves))),
	!.