Skip to content

Instantly share code, notes, and snippets.

@Shiro-Raven

Shiro-Raven/battleship.pl

Last active March 13, 2020 13:12
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save Shiro-Raven/fb4493d846f40a303fc0cfcab20a088f to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save Shiro-Raven/fb4493d846f40a303fc0cfcab20a088f to your computer and use it in GitHub Desktop.
Download ZIP
battleship Prolog solver
Raw
battleship.pl
:- use_module(library(clpfd)).
%10*10 test
at(3, 5, c).
at(5, 0, w).
at(9, 6, c).
%4*4 test
%at(2,0,c).
%at(2,1,r).
%This part was included in the hints file on the MET website
maplist2(_, [], []).
maplist2(P, [X|Xs], [Y|Ys]) :-
call(P, X, Y),
maplist(P, Xs, Ys).
pretty_print([],_,_).
pretty_print([Head|Tail],W,H):-
%print(pretty_print_h(W,[Head|Tail],L1)),
pretty_print_h([Head|Tail],W,L1),
pretty_print(L1,W,H).
pretty_print_h(Rest,0,Rest):-nl.
pretty_print_h([],N,[]):-N>0,nl.
pretty_print_h([H|T],W,Rest):-
W>0,
print(H),print(' '),
W1 is W -1 ,
pretty_print_h(T,W1,Rest).
% This predicate does exactly as the description says: if the list
% starts with an l, it must be followed by an r
mycheck([]).
mycheck([l]).
mycheck([H|T]):- member(H,[c,w]),mycheck(T).
mycheck([l,r|T]):- mycheck(T).
%Those just follow the description
getZeroth([H|T],H).
rest([],[]).
rest(L,R):- getZeroth(L,H), append([H],R,L).
%This follows the instruction as well
list_to_llists(L,W,LLists):-
length(L,N),
Diff is mod(N,W),
N1 is N-Diff-1,
subList(0,N1,L,L1),
list_to_llists_helper(L1,0,W,LLists).
%base case to helper
list_to_llists_helper(L,I,_,[]):-
length(L,Ln),
I >= Ln.
% take sublists of length W from I to I+W then moves to I+W+1 to I+W+2
% puts it in a list of lists
list_to_llists_helper(L,I,W,LLists):-
I2 is I + W -1,
length(L,Ln),
I2 < Ln,
subList(I,I2,L,Sublist),
I3 is I2 + 1,
list_to_llists_helper(L,I3,W,LLists1),
append([Sublist],LLists1,LLists).
subList(_,_,[],[]).
% if I1>I2 return [] as in the test cases
subList(I1,I2,_,[]):-
I1>I2.
% if 0<I1<I2 then decrease both I1 & I2 till I1 reaches 0
subList(I1,I2,[_|T],Sub):-
I1>0,
I1=<I2,
I11 is I1 - 1,
I21 is I2 - 1,
subList(I11,I21,T,Sub).
%when you reach I1 = 0 start taking elements
subList(I1,I2,[H|T],Sub):-
I1=0,
I2>0,
I21 is I2 - 1,
subList(I1,I21,T,Sub1),
Sub = [H|Sub1].
% when I2 reaches 0 start returning
subList(_,I2,[H|_],[H]):-
I2 = 0.
%follows the instruction
collect_hints(Hl):- setof(at(X,Y,Z),at(X,Y,Z),Hl) .
%base case for ensure_hints
ensure_hints(_,[],_,_).
%calculates the index, checks the hints, then checks the others
ensure_hints(L,[H1|T1],W,H):-
length(L,N),
N =:= W*H,
H1 = at(I,J,X),
K is J*W + I,
nth0(K,L,X),
ensure_hints(L,T1,W,H).
%follows the description
random_assignment([]).
random_assignment([H|T]):-
member(H,[w,c,l,r]),
random_assignment(T).
% this predicate works on full grid only, it divides the list to
% sublists and checks each row individually
check_rows([],_,_,_).
check_rows(L,W,H,R):-
list_to_llists(L,W,LL),
length(L,N1),
N1 > 0,
flatten(LL,FLL),
length(FLL,N2),
N1 == N2,
checkrowH(LL,W,H,R).
%this predicate works only on partial grid, it checks the full rows,
% then gets the incomplete one and checks it using checkshortrow/2
check_rows(L,W,H,R):-
list_to_llists(L,W,LL),
length(L,N1),
N1 > 0,
length(LL,N3),
flatten(LL,FLL),
length(FLL,N2),
\+(N2 == N1),
N11 is N1 -1,
subList(N2,N11,L,Missrow),
checkrowH(LL,W,H,R),
nth0(N3,R,Misstot),
checkshortrow(Missrow,Misstot).
% this predicate is only for experimenting and is not used for the
% battleship predicate
getMissrow(N1,N2,N3,L,Tots,Missrow,Misstot):-
A is N1 -1,
subList(N2,A,L,Missrow),
nth0(N3,Tots,Misstot).
% this predicate checks each sublist with the corresponding total
checkrowH([],_,_,_).
checkrowH([H|T],Wid,Hei,[HT|TT]):- check_row(H,HT),
checkrowH(T,Wid,Hei,TT).
%this predicate checks if a list contains the correct number of vessels
check_row([],0).
check_row([H|T],Tot):- member(H,[l,r,c]), NTot is Tot - 1, NTot >= 0 ,check_row(T,NTot).
check_row([w|T],Tot):- check_row(T,Tot).
% same as check_row, but since the row is incomplete, the total can
% remain more than 0
checkshortrow([],N):- N >= 0.
checkshortrow([arbit|_],N):- N >= 0.
checkshortrow([H|T],Tot):- member(H,[l,r,c]), TotNew is Tot - 1, checkshortrow(T,TotNew).
checkshortrow([w|T],Tot):- checkshortrow(T,Tot).
% checks first if the list is incomplete using the fixer predicate, if
% yes, it completes it with arbitrary values, transposes it, and goes to
% the checkcolH
check_columns(L,Wid,Hei,Cols):- fixer(Wid,Hei,L,LL),
list_to_llists(LL,Wid,RL),
transpose(RL,LTra),
checkcolH(LTra,Wid,Hei,Cols).
% this predicate checks each sublist individually, if it contains an
% arbitary value, it treats the sublist as a shortrow, if not, then it
% checks the sublist as a complete row, thus the check_row predicate
checkcolH([],_,_,_).
checkcolH([H|T],Wid,Hei,[Ht|Tt]):- containsArbit(H),
checkshortrow(H,Ht),
checkcolH(T,Wid,Hei,Tt).
checkcolH([H|T],Wid,Hei,[Ht|Tt]):- \+(containsArbit(H)),
check_row(H,Ht),
checkcolH(T,Wid,Hei,Tt).
% this predicates keeps filling a list with arbitrary values till its
% length is equal to the given one
fixer(W,H,L,L):- length(L,Len), Len is W*H.
fixer(W,H,L,R):- length(L,Len), Len < W*H, append(L,[arbit],LL), fixer(W,H,LL,R).
%checks if the list contains the arbitrary value 'arbit'
containsArbit([arbit|_]).
containsArbit([H|T]):- \+(H == arbit), containsArbit(T).
%checks for the length, then calls the countCs/2 predicate
check_submarines([],_,_,_).
check_submarines(L,W,H,Total):- length(L,Len),
Len =< W*H,
countCs(L,0,Total).
% this works for full grid only, grid is divided to sublists and calls
% count Ls
check_destroyer(L,W,H,Total):- length(L,Len),
Len is W*H,
countLs(L,0,0,W,Total).
% this works only for partial grid, it allows for l's being less than
% the equal
check_destroyer(L,W,H,Total):- length(L,Len),
Len < W*H,
countLs(L,0,0,W,Counted),
Counted =< Total.
% counts the 'c's in the grid and checks if they are equal to the total
% using the accumulator method
countCs([],Acc,Acc).
countCs([c|T],Acc,Tot):- NewAcc is Acc +1,NewAcc =< Tot, countCs(T,NewAcc,Tot).
countCs([H|T],Acc,Tot):- \+H = c, countCs(T,Acc,Tot).
% counts the L's in a 1D list, however it returns false whenever there's
% an L at the end of a row because a row can't end with an L
countLs([],Acc,_,_,Acc).
countLs([l|T],Acc,Ind,W,Tot):- NewAcc is Acc +1, N is Ind +1, \+(0 is mod(N,W)), countLs(T,NewAcc,N,W,Tot).
countLs([H|T],Acc,Ind,W,Tot):- \+(H == l), N is Ind +1, countLs(T,Acc,N,W,Tot).
battleship(L,W,H,Subs,Dests,ListRow,ListCol):-
Len is W*H,
length(L,Len),
collect_hints(Hint),
ensure_hints(L,Hint,W,H),
check_rows(L,W,H,ListRow),
check_columns(L,W,H,ListCol),
mycheck(L),
check_submarines(L,W,H,Subs),
check_destroyer(L,W,H,Dests),
random_assignment(L).
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment