Toggle navigation
?
users online
Logout
Open hangout
Open chat for current file
% In the documentation here, we follow these conventions: % ? before a variable name: the variable can be instantiated or not % + before a variable name: the variable is an input, must be instantiated % - before a variable name: the variable is an output nonempty([_|_]). % square_at_front(?ListL, ?ListA) % Example: ListL=[x,y,x,y,z], ListA=[x,y] square_at_front(L,A) :- nonempty(A), append(A,R,L), prefix(A,R). % square_free_peano(?List, +Alphabet, ?PeanoNumber) % True when List is of length PeanoNumber, with entries taken from the List % Alphabet, and List does not contain the pattern XX, where X is any list. % Example: [x,y,x] is square-free % Example: [z,x,y,x,y] is not square-free % PeanoNumber is a "term" of the form s(s(...s(zero))). square_free_peano([],_,zero). square_free_peano([H|T], Alphabet, s(N)) :- square_free_peano(T,Alphabet,N), member(H,Alphabet), \+ square_at_front([H|T],_). % square_free(?List, +Alphabet, +Number) % Variant of square_free_peano with an actual integer number as input instead of a % "Peano number". The downside is that Number must be instantiated. square_free([],_,0). square_free([H|T],Alphabet,N) :- number(N), N > 0, M is N-1, square_free(T,Alphabet,M), member(H,Alphabet), \+ square_at_front([H|T],_). %sandwich_at_front(?ListL, ?ListA, ?ListB) % Example: ListL=[x,y,z,z,x,y,w], ListA=[x,y], ListB=[z,z] % Non-example: ListL=[x,y,z,x,y] sandwich_at_front(L,A,B) :- nonempty(A), append(A,R,L), same_length(A,B), append(B,S,R), prefix(A,S). % sandwich_free_peano(?List, +Alphabet, ?PeanoNumber) % True when List is of length PeanoNumber, with entries taken from the List % Alphabet, and List does not contain the pattern XYX, where X and Y are any % lists (not necessarily distinct) of the same length. % Example: [z,x,y,x] is not sandwich-free % Example: [z,z,z] is not sandwich-free % Example: [x,x,y,y,x] is sandwich-free % PeanoNumber is a "term" of the form s(s(...s(zero))). sandwich_free_peano([],_,zero). sandwich_free_peano([H|T], Alphabet, s(N)) :- sandwich_free_peano(T,Alphabet,N), member(H,Alphabet), \+ sandwich_at_front([H|T],_,_). % sandwich_free(?List, +Alphabet, +Number) % Variant of sandwich_free_peano with an actual integer number as input instead % of a "Peano number". The downside is that Number must be instantiated. sandwich_free([],_,0). sandwich_free([H|T],Alphabet,N) :- number(N), N > 0, M is N-1, sandwich_free(T,Alphabet,M), member(H,Alphabet), \+ sandwich_at_front([H|T],_,_). % sandwich_free_not_extensible_peano(?List, +Alphabet, ?PeanoNumber) sandwich_free_not_extensible_peano(L,Alphabet,N) :- sandwich_free_peano(L,Alphabet,N), forall(member(X,Alphabet), sandwich_at_front([X|L],_,_)). % sandwich_free_not_extensible(?List, +Alphabet, +Number) sandwich_free_not_extensible(L,Alphabet,N) :- sandwich_free(L,Alphabet,N), forall(member(X,Alphabet), sandwich_at_front([X|L],_,_)). % square_free_greedy(?List, +Alphabet, +Number) % Variant of square_free which always greedily picks the first letter of the % Alphabet that works. square_free_greedy([],_,0) :- !. square_free_greedy([H|T], Alphabet, N) :- number(N), N > 0, M is N-1, square_free_greedy(T,Alphabet,M), member(H,Alphabet), \+ square_at_front([H|T],_), !. % sandwich_free_greedy(?List, +Alphabet, +Number) % Variant of sandwich_free which always greedily picks the first letter of the % Alphabet that works. sandwich_free_greedy([],_,0) :- !. sandwich_free_greedy([H|T],Alphabet,N) :- number(N), N > 0, M is N-1, sandwich_free_greedy(T,Alphabet,M), member(H,Alphabet), \+ sandwich_at_front([H|T],_,_), !. how_many_square_free_alphabet_3(N,Count) :- aggregate_all(count, square_free(_,[x,y,z],N), Count). how_many_sandwich_free_alphabet_3(N,Count) :- aggregate_all(count, sandwich_free(_,[x,y,z],N), Count). /* % Various queries you might want to try: square_free_peano(L,[x,y],(s(s(s(zero))))). square_free_peano(L,[x,y],(s(s(s(s(zero)))))). square_free(L,[x,y],3). square_free(L,[x,y],4). sandwich_free_peano(L,[x,y],(s(s(s(s(s(zero))))))). sandwich_free_peano(L,[x,y],(s(s(s(s(s(s(zero)))))))). sandwich_free(L,[x,y],5). sandwich_free(L,[x,y],6). numlist(0,23,L),maplist(how_many_square_free_alphabet_3,L,XS). numlist(0,23,L),maplist(how_many_sandwich_free_alphabet_3,L,XS). */