CSCI 310 Logic
Programming Project
In this project
you will practice writing programs from a logical point of view. You are to use SWI Prolog (installed in the
labs, available free on line) to write
your programs. You should load your
programs from a file, and capture the output from the debug window to another
file using cut and paste. You should
turn in your program file as well as your output file by emailing it to me, allisodl@oneonta.edu, as a single zip
file. Be sure to include comments in
your program file (at least giving your name) and also include any supporting
functions you needed to write. For this
assignment, you are allowed to use any of the Prolog functions we discussed or
wrote in class. Anything else you need,
you should include code for in your program file.
1. To get warmed up, write a function, hlbackwards, that takes a list as input, and returns a
list in which the elements of the toplevel list are
in reverse order. Here is a sample
execution:
?-
hlbackwards([a,b,[c,d],e],X).
X=[e, [c, d], b, a]
Yes
?-
2. To
continue warming up, write a function, llbackwards, that takes a
list as input, and returns a list in which every list and sublist
is in reverse order. Here is a sample
program execution:
?- llbackwards([a,[b,c],[[d,e,[f],g],h,i]],X).
X=[[i, h, [g, [f], e,
d]],[c, b], a]
Yes
?-
3. Write a function, palindrome, that takes a list as input and returns the
original list if the list is a palindrome, ie reads
the same in both directions, and otherwise returns the original list made into
a palindrome by reversing it and appending it to itself, but not replicating
the last element. Here is a sample run:
?-
palindrome([a,b,[c,d],e],X).
X=[a,b,[c,d],e,[d,c],b,a]
?-
palindrome([a,[b,c,[d]],[[d],c,b],a],X).
X=[a,[b,c,[d]],[[d],c,b],a]
?-
4. Write a function, permutations, that takes a list as input and generates a list
containing all possible permutations of the list elements. Here is a sample application:
?-
permutations([1,2,3],X).
X=[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
Yes
?-
5. Write a function, ionah, that takes a single number as input and
prints out the solution to the inverted disk problem for that many disks. This is the problem of moving a stack of k
disks of increasing size from bottom to top, from the first peg to the third
peg with another peg that may be used as well, subject to the condition that a
smaller disk is never put on top of a larger one, and only one disk may be
moved at a time. Here is a sample run:
?-
ionah(3).
move disk from peg 1 to peg 3
move disk from peg 1 to peg 2
move disk from peg 3 to peg 2
move disk from peg 1 to peg 3
move disk from peg 2 to peg 1
move disk from peg 2 to peg 3
move disk from peg 1 to peg 3
Yes
?-
6. Write a function, sequence,
that takes a single integer as input and prints out a list containing that many
terms of the sequence defined by:
Here
is a sample execution:
?-
sequence(7,X).
X=[0,1,2,5,12,29,70]
Yes
?-
7. Write a program to argue with
yourself. Your program should take
statements that are typed in as a list and change the pronouns and negate
them. For instance, you should change to I, are should change to am
not, and so on. Here is a possible sample session:
?-
argue([you,are,a,stupid,computer],X).
X=[i,am,not,a,stupid,computer]
Yes
?-
argue([you,are],Y).
Y=[i,am,not]
Yes
?-argue([are],Z).
Z=[am,not]
Yes
?-
Notice
that bad things can happen if the input is not chosen carefully (for instance, you
are too becomes I
am not too). Try to cover as many standard
English patterns as you can to minimize the cases in which nonsense is
returned.
8. Write a function, bubblesort, that takes a list of numbers as input and
returns the list sorted in ascending order using a bubblesort.
?-
bubblesort([1,3,7,11,2,5,8,6,4],X).
X=[1,2,3,4,5,6,7,8,11].
Yes.
?-
To
help you with this program, here should be a quicksort, done in Prolog:
quicksort([X|Xs],Ys) :-
partition(Xs, X, Littles, Bigs),
quicksort(Littles,
Ls),
quicksort(Bigs, Bs),
append(Ls, [X|Bs],
Ys).
quicksort([],[]).
partition([X|Xs], Y, [X|Ls], Bs) :- X =< Y,
partition(Xs, Y, Ls, Bs).
partition([X|Xs], Y, Ls, [X|Bs]) :- X > Y,
partition(Xs, Y, Ls, Bs).
partition([], Y, [], []).