% lists.pl % % Name: % Time spent and/or other thoughts: % % Our "nice" prolog settings: % See www.swi-prolog.org/pldoc/man?predicate=current_prolog_flag/2 % % This one prompts only when there are variables: :- set_prolog_flag( prompt_alternatives_on, groundness ). % This one sets some reasonable display defaults: :- set_prolog_flag(toplevel_print_options, [quoted(true), portray(true), attributes(portray), max_depth(999), priority(699)]). %% here are a couple of example predicates that might be helpful... % % member( E, L ) should be true if % E is a top-level member of the list L % member should work when E is a variable or bound to a value; % L should only be bound to a value % member( E, [E|_] ). member( E, [_|R] ) :- member( E, R ). % The following tests can be run by typing: % run_tests(member) :- begin_tests(member). test(memberT1, [nondet]) :- member(1, [1, 2, 3]), !. test(memberT2, [nondet]) :- member(2, [1, 2, 3]), !. test(memberT3, [nondet]) :- member(3, [1, 2, 3]), !. test(memberT4, [nondet]) :- member(b, [a, b, c]), !. test(memberT5) :- setof(One, member(One, [1,2,3,4]), All), All == [1,2,3,4]. test(memberT6, [nondet]) :- \+member(5, [1,2,3]). % no additional tests needed for member :- end_tests(member). % % range( L, H, List ) should be true if % List is a list of integers from L to H-1, % inclusive. Both L and H need to be bound to ints as inputs. % The third input, List, will then be generated. % range(L,H,[]) :- L >= H. range(L,H,[L|R]) :- L < H, M is L+1, range(M,H,R). % The following tests can be run by typing: % run_tests(range) :- begin_tests(range). test(rangeT1, [nondet]) :- range(40,43,[40,41,42]), !. test(rangeT2, [nondet]) :- range(43,40,[]), !. % no additional tests needed for range :- end_tests(range). %% [Part 1] rev( L, Rev ) % The following tests can be run by typing: % run_tests(rev) :- begin_tests(rev). test(revT1, [nondet]) :- rev([1] , [1]) , !. test(revT2, [nondet]) :- rev([1,2] , [2,1]) , !. test(revT3, [nondet]) :- rev([3,2,1], [1,2,3]), !. test(revT4, [nondet]) :- rev([a,b,c], W), W==[c,b,a], !. % include at least one additional test below: :- end_tests(rev). %% [Part 2] count( E, L, N ) % The following tests can be run by typing: % run_tests(count) :- begin_tests(count). test(countT1, [nondet]) :- count(spam, [oh,spam,spam,we,love,spam], 3), !. test(countT2, [nondet]) :- setof(N, count(oh, [oh,spam,spam,we,love,spam], N), Answer), Answer = [1]. test(countT3, [nondet]) :- setof(N, count(spam, [oh,spam,spam,we,love,spam], N), Answer), Answer = [3]. test(countT4, [nondet]) :- setof(N, count(alien, [oh,spam,spam,we,love,spam], N), Answer), Answer = [0]. test(countT5, [nondet]) :- setof(N, count(we, [oh,spam,spam,we,love,spam], N), Answer), Answer = [1]. % add additional tests below: :- end_tests(count). %% [Part 3] find( Pattern, Target, Index ) % The following tests can be run by typing: % run_tests(find) :- begin_tests(find). test(findT1, [nondet]) :- find([1, 2], [1, 2, 1, 2, 1], 0), !. test(findT2, [nondet]) :- \+find([], [1, 2, 1, 2, 1], _). test(findT3, [nondet]) :- setof(N, find([1,2],[1,2,1,2,1],N), Answer), Answer==[0, 2]. test(findT4, [nondet]) :- setof([N,P], find(P,[a,c,a,c],N),Answer), Answer == [[0, [a]], [0, [a, c]], [0, [a, c, a]], [0, [a, c, a, c]], [1, [c]], [1, [c, a]], [1, [c, a, c]], [2, [a]], [2, [a, c]], [3, [c]]]. % add additional tests below: :- end_tests(find). %% [Part 4] depth( E, Tree, N ) % a helper predicate to define a tree tree1( [ 42, [ 20, [10, [5, [], []], [18, [], []]], [] ], [ 100, [67, [50, [], []], []], [150, [], [2009, [], []]] ] ] ). % The following tests can be run by typing: % run_tests(depth) :- begin_tests(depth). test(depthT1, [nondet]) :- tree1( T1 ), depth( 42, T1, N ), T1==[42,[20,[10,[5,[],[]],[18,[],[]]],[]],[100,[67,[50,[],[]],[]],[150,[],[2009,[],[]]]]], N==0, !. test(depthT2, [nondet]) :- tree1( T1 ), setof(E, depth(E,T1,3),Answer), T1 = [42,[20,[10,[5,[],[]],[18,[],[]]],[]],[100,[67,[50,[],[]],[]],[150,[],[2009,[],[]]]]], Answer = [5,18,50,2009], !. % add additional tests below: % % NOTE - for this problem, you need to create your own (perhaps smaller) tree % and write at least one test using that... (Use the above example as a model.) :- end_tests(depth). %% [Part 5] insert( E, Tree, NewTree ) % The following tests can be run by typing: % run_tests(insert) :- begin_tests(insert). test(insertT1, [nondet]) :- tree1( T1 ), insert( 43, T1, NewTree ), T1 = [42,[20,[10,[5,[],[]], [18,[],[]]],[]], [100,[67,[50,[],[]],[]], [150,[],[2009,[],[]]]]], NewTree = [42,[20,[10,[5,[],[]], [18,[],[]]],[]], [100,[67,[50,[43,[],[]],[]],[]], [150,[],[2009,[],[]]]]], !. test(insertT2, [nondet]) :- tree1( T1 ), insert( 41, T1, NewTree ), T1 = [42,[20,[10,[5,[],[]],[18,[],[]]], []],[100,[67,[50,[],[]],[]], [150,[],[2009,[],[]]]]], NewTree = [42,[20,[10,[5,[],[]], [18,[],[]]],[41,[],[]]], [100,[67,[50,[],[]],[]], [150,[],[2009,[],[]]]]], !. % add an additional test below: % If you'd like to include a smaller tree, that is completely OK! :- end_tests(insert). %% [Part 6] path( A, B, Graph, Path ) % a helper predicate to define a graph graph1( [ [a,b], [b,c], [c,d], [b,w], [w,x], [x,z], [b,z] ] ). % The following tests can be run by typing: % run_tests(path) :- begin_tests(path). test(pathT1, [nondet]) :- graph1(G1), path( a, z, G1, P ), G1 = [[a,b],[b,c],[c,d],[b,w],[w,x],[x,z],[b,z]], P = [a,b,w,x,z], !. test(pathT2, [nondet]) :- graph1(G1), setof( P, path( a, z, G1, P ), Answer), G1 = [[a,b],[b,c],[c,d],[b,w],[w,x],[x,z],[b,z]], Answer = [[a,b,w,x,z],[a,b,z]], !. test(pathT3, [nondet]) :- graph1( G1 ), G2 = [ [z,a] | G1 ], setof( Path, path( a, z, G2, Path ),Answer ), member( [a,b,z], Answer ), G1 = [[a,b],[b,c],[c,d],[b,w],[w,x],[x,z],[b,z]], G2 = [[z,a],[a,b],[b,c],[c,d],[b,w],[w,x],[x,z],[b,z]], !. % add additional tests below: % % NOTE - again for this problem, you need to create your own (perhaps smaller) graph % and write at least one test using that... (Use the above example as a model.) :- end_tests(path).