% CSE3401 Winter 2012- assignment 2 % Vida Movahedi % Question 1(a) % Predicate noEven(L,N) is true when N is the number of even numbers % in list L. % I am writing this predicate using a simple recursive design. % noEven(L,_):- var(L), !, % in case L is not known write('First argument must be a known list.'),nl, fail. noEven(L,_):- \+is_list(L),!,% in case L is given, but it's not a list write('First argument must be a list.'),nl,fail. noEven([],0). % in case of empty list noEven([X|_],_):- \+integer(X), !, %if list has non-integer elements write('First argument must be a list of integers.'), nl, fail. noEven([X|L],N):- % finally calculation of N, note (1- X mod 2) is 1 for even X and 0 for odd X noEven(L,N1), N is N1 +1- X mod 2. % Question 1(b) % Predicate repCount(L,X,N) is true when N is the number of occurences % of X in list L. % This predicate is written using a simple recursive design. % repCount(L,_,_):- var(L),!, % in case L is not known write('First argument must be a known list.'),nl, fail. repCount(L,_,_):- \+is_list(L),!, % in case L is given, but it's not a list write('First argument must be a list.'),nl,fail. repCount([],_,0). % in case of empty list repCount([X|L], X, N) :- % in case it encounters an occurence of X repCount(L,X,N1), N is N1+1, !. %(Cut: this is the correct rule in this case, don't try the next clause for another solution). repCount([_|L], X, N):- repCount(L, X, N). % otherwise, (X is not the head) look in the tail for occurences of X % =============================================================== % Question 2 % 2(a) % digitsR(N,L) returns the digits of N in list L % assumptions: N is given, and is a natural number, % L is list of digits starting from the least significant digit digitsR(X,_):- var(X), !, write('First argument must be known!'), nl, fail. digitsR(X,_):- \+((integer(X), X>0)),!, write('First argument must be a natural number'), nl, fail. digitsR(X,[X]):- X<10,!. digitsR(X, [Y|L]) :- Y is X mod 10, Z is X//10, digitsR(Z, L). % 2(b) % sumDigits(N,S) returns the sum of digits of N in S % An accumulator is used to keep the sum (calculated so far). % Note error cases are handled by digitsR sumDigits(N,S):- digitsR(N,L), sumacc(L, 0, S). sumacc([], A,A). sumacc([X|L], A, S):- A1 is A + X, sumacc(L, A1, S). % 2(c) % finding digits of a number by difference lists digitsD(X,_):- var(X), !, write('First argument must be known!'), nl, fail. digitsD(X,_):- \+((integer(X), X>0)),!, write('First argument must be a natural number'), nl, fail. digitsD(X,R) :- digD(X, R, []). digD(X, [X|H], H):- X<10, !. digD(X, R, H):- Z is X // 10, Y is X mod 10, digD(Z, R, H1), digD(Y, H1, H). % 2(d) % finding digits of a list of numbers by difference lists digLists(L,_):- var(L), !, write('First argument must be a known list.'), nl, fail. digLists(L,_):- \+is_list(L), !, write('First argument must be a known list.'), nl, fail. digList(L,R):- digL(L, R, []). dig1(X, [L|Hole], Hole) :- digD(X,L). digL([], Hole, Hole). digL([X|L], R, Hole):- dig1(X, R, Hole1), digL(L, Hole1, Hole). % ================================================================ % Question 3 % depthLevel(L1,L2) returns a list L2 of elements in L1 and their depth % in the list % Difference Lists are used in the code depthLevel(L1,_):- var(L1),!, write('First argument must be a known list.'), nl, fail. depthLevel(L1,_):- \+is_list(L1),!, write('First argument must be a known list.'), nl, fail. depthLevel(L1, L2):- tL(L1, 0, L2, []). forOne(H, I, [[H, I]|Hole], Hole). tL([H|T], I, P, Hole):- !, J is I+1, tL(H,J, P, Hole1), ppx(T, J, Hole1, Hole). tL(X, I, P, Hole) :- forOne(X, I, P, Hole). ppx([],_, Hole, Hole). ppx([H|T], I, P, Hole):- tL(H, I, P, Hole1), ppx(T, I, Hole1, Hole). % ================================================================== % Question 4 % % 4(a)- finding the next number in a sequence, % assumption: code returns false if first arg not in list seq(X,Y) :- seq(1, 1, X, Y). seq(X, _, X1, _):- X > X1, !, fail. seq(X, Y, X, Y):- !. seq(A, B, X, Y) :- next(A, B, C), seq(B, C, X, Y). next(A, B, C) :- C is A + 2 * B. % 4(b)- finding N elements of sequence after X and % returning in L % uses accumulators, and therefore reverses the list seqN(X,N,L):- seqAcc(X,N, [], L). seqAcc(_,0, A,L):-!, reverse(A,L). seqAcc(X,N, A,L):- seq(X,Y),!, N1 is N-1, seqAcc(Y,N1, [Y|A], L). seqAcc(X,_,_,_) :- write(X), write(' is not a member of this sequence!'), nl, fail. % =============================================================== % Question 5 % part (a)- reading a map file % assumption: the map file is given and written correctly readmap(Filename, NoRows, NoCols, M):- open(Filename, read, S), current_input(SI), set_input(S), read(NoRows), read(NoCols),read(M), close(S), set_input(SI). % part (b)- moving in a map from old location to new location, % given size of the map % assumption: valid moves are moves to right and down % move is only valid inside the map. % since we are increasing either row or col, % C2>1 and R2>1 ensure starting inside the map % C2=1, C2 =< NC. move([R1,C1], [R2,C2], [NR,_]):- R2 is R1+1, C2 is C1, R2>1, R2 =< NR. % part (c)- reading a location in map % assumption: M corresponds to a map structure with NR rows % and NC columns; arguments of M correspond to % concatenation of rows of the map % We therefore need to calculate N as (R-1)*NC+C % Note: code will return false if Loc is not in map getPosMap(M, NR, NC, [R,C], A):- R>0, R=0, C=