This assignment is due at the "normal" Monday time. As such, grutoring hours are back to "normal". This is a very busy week for many people so please get started on this assignment right away. You are all set to go for everything except Part 6 (Towers of Hanoi).
This assignment has 6 parts. Please be sure to name your prolog rules exactly as we've specified in the assignment. This is important since some of your code will be tested by an automatic code tester which will look for precisely these names.
Note also that Prolog has some built-in rules. In particular, Prolog has a built-in length(L, N) which is true if and only if list L has length N. Prolog also has a built-in append(A, B, C) which is true if and only if the result of appending list B to the end of list A results in list C. You are welcome to use these built-ins. You may also want to define your own helper rules as needed or other predicates that we defined in class, e.g., permutation (that generates permutations), and member.
Finally, in this assignment (and henceforth on all prolog assignments), it's fine if your prolog rule finds the same solution more than once as long as it doesn't find it an infinite number of times! In other words, your prolog rules should halt, but may find the same solution a finite number of time.
| ?- remove(1, [2, 1, 3], [2, 3]). yes | ?- remove(1, [2, 1, 3], X). X = [2,3] ; no | ?- remove(1, [2, 3, 4], X). no | ?- remove(X, [1, 2, 3], [2, 3]). X = 1 ; no | ?- remove(X, [1, 2, 3], Y). X = 1, Y = [2,3] ; X = 2, Y = [1,3] ; X = 3, Y = [1,2] ; no
Your remove rule must be able to work when either the first or last argument, or both, are variables, as demonstrated above. You don't need to worry about the case that the second argument is a variable.
Submit your code in a file named part1.pl.
Recall that in rex we wrote a function called powerset which took as input a set S (a list of distinct items) and returned the powerset of S: The set of all subsets S. In rex, we had to come up with a clever algorithm (based on "weirdo analysis") and then implement it.
Now, we will do something even better in prolog! We'll write a rule called subset(List1, List2) which takes two lists List1 and List2 as input and infers whether List1 is a subset of List2. (Notice that since we're using lists to represent sets, we're implicitly assuming that any given element appears at most once in a list. Also, you should not assume anything about the order in which the elements are given in the lists.) No weirdo analysis here! We're simply teaching prolog how to infer that one set is a subset of another!
You may wish to use one or more helper rules. Your subset rule must work when it is given two actual lists and it must also work when the first argument is a variable and the second argument is an actual list. It need not work in the case that the second argument is a variable (although it's not hard to take care of that case either). For example:
| ?- subset([1, 2], [2, 1, 3]). yes | ?- subset([1, 2], [1]). no | ?- subset(X, [1, 2]). X = [] ; X = [1] ; X = [1,2] ; X = [2] ; X = [2,1] ;
Notice in the last example, the same subset appeared more than once (as [1, 2] and [2, 1]). This is fine, as long as your rule eventually stops and all correct answers are produced at least once. Moreover, the order in which the subsets are found and the order of the actual elements in the lists is unimportant. Submit your code in a file called part2.pl.
Place the code for this part of the assignment in a file called part3.pl .
You've been hired by the International Cottage of Pancakes (ICOP) to develop some software for their pancake chefs. A chef is presented with a stack of pancakes, each of different size. This stack is represented by a list. For example, the list [20, 10, 30] means that pancake with diameter 20 units is on the griddle, the pancake with diameter 10 units is on top of that pancake, the pancake with diameter 30 units is on the very top of the stack. (ICOP reinforces their pancakes with special ingredients to ensure that pancakes can be stacked with small pancakes below big ones!).
ICOP wishes to serve their pancake stacks in sorted order from SMALLEST at the bottom to LARGEST at the top. (Thank goodness their pancakes are reinforced to permit this!)
A pancake chef can insert a flipper in any position in the stack and then flip the pancakes above the flipper (thus reversing their order) onto the stack of pancakes below the flipper. For example, by placing the flipper at position 1 in the stack [20, 10, 30], we would insert the flipper immediately above pancake 1, that is above the pancake with diameter 20. When we now flip, the pancakes above the flipper get reversed, resulting in the list [20, 30, 10]. If we now stick the flipper at position 0 in the stack [20, 30, 10], that is under the bottommost pancake, we would now flip and get [10, 30, 20]. Now, we can stick the flipper at possition 1 again (immediately above the pancake with diameter 10) and the flip results in the stack [10, 20, 30]. This stack is sorted and the chef is happy!
Your job is to write a rule called pancakes(Stack, Number, Moves) which takes as input a list of pancakes called "Stack", an integer number "Number" indicating the number of flips to be performed, and a list "Moves" which contains exactly "Number" moves. pancakes(Stack, Number, Moves) is true if and only if the list of "Moves" contains exactly "Number" moves and these result in going from "Stack" to a sorted stack of the pancakes.
Using the example above, we could type
| ?- pancakes([20, 10, 30], 3, [1, 0, 1]).and prolog would say "yes".
Now, make sure that your pancakes rule works EVEN when the third argument, the list of Moves, is a variable. This will be the only argument that might ever be used as a variable and it allows the chef to determine a sequence of flips to sort the pancakes. For example,
| ?- pancakes([20, 10, 30], 3, X). X = [0,1,0] ; X = [1,0,1] ; no
Notice that prolog found TWO different ways to sort the pancakes in 3 moves. (Check to make sure that you agree that both solutions are valid!)
Notice also that the "Stack" may be arbitrarily large, but will never contain two pancakes of the same size.
Your job is to write "pancakes" in prolog! It may be helpful to use the built-in "length" and "append" rules. It may also be helpful to you to use the "reverse" rule from your previous homework and the "sorted" rule from the previous lecture. Here they are...
reverse([], []). reverse([F | R], List) :- reverse(R, RReverse), append(RReverse, [F], List). sorted([]). sorted([_]). sorted([X, Y | Rest]) :- X < Y, sorted([Y | Rest]).
In this problem you will write a prolog rule that evaluates arithmetic trees in prefix notation. You will use this rule in your solution to the 24 puzzle in Part 5 below.
Write a rule called eval( ATree, Result ) that infers whether the arithmetic tree, ATree evaluates to Result. An arthmetic tree is either a number, or a list of three elements: An operator, a left arithmetic tree, and a right arithmetic tree. Here are some examples of trees:
24 -- The number 24, a valid tree (note it's a number, not a list) ['+', 24, 2] -- The expression 24+2 ['-', ['/', 6, 3], 2] -- The expression (6/3)-2Notice that the arithmetic operators are represented in the tree as characters. You may assume the operator will be one of '+', '-', '*', or '/'. You can assume you will only have to handle integer division. Note that in prolog division ('/') is performed using '//'
Here are a few examples of how the eval predicate will work:
| ?- eval( 24, 22 ). no. | ?- eval( ['+', 5, 2], 7 ). yes. | ?- eval( ['-', ['*', 2, 4], 3], X ). X = 5 ; no.
Your eval predicate should work even when the second argument is a variable, but need not handle the case in which the tree is a variable.
To help get you started, we have provided an inference rule for the simplest tree, a number:
eval( R, R ) :- number(R).
The number predicate is true when its input is a number. Notice that it's not enough to simply state eval(R,R). as a fact because R is only a valid result of evaluating the tree if R is a number.
This problem asks you to use Prolog to provide a solver for a generalized version of the game "Twenty-Four". In the original game, players view a card with four numbers on it and try to make an arithmetic combination of the numbers using the operators +, -, *, / so that the result is 24 (parentheses are allowed but are implicit). Each number must be used exactly once. Each operator can be used any number of times.
In our generalization of the game, the fixed number 24 is replaced with an arbitrary value, the set of operators is specified in a list, and the list of numbers can have any length, not just 4. (By definition, no result can be made if the list is empty.)
Define a 4-ary rule called solve such that
solve(Operators, Numbers, Result, Tree)
will solve for an arithmetic tree named Tree using operators
Operators among the integers in
Numbers to give the final value Result. You may
assume that when we use the
solve rule the operators, numbers, and
result will always be specified but that the fourth argument, the
tree itself, may be left as a variable.
For example,
| ?- solve(['+'], [1, 2, 3], 6, ['+', 1, ['+', 2, 3]]). yes | ?- solve(['+', '*', '-'], [2, 3, 4, 5], 24, Tree). Tree = [*,[+,[-,3,2],5],4]
This means that we have found a solution Tree using operators +, *, and - on that will combine with set of numbers [2, 3, 4, 5] to yield 24. You may assume that the set of operators will always be a subset of ['+', '*', '-', '/'] and that '/' denotes integer division. In prolog, '/' is performed using // (which is why 1-line comments in prolog are prefaced by % and not //).
The eval predicate you wrote in Part 4 will be quite useful in solving this problem. You may also use any of Prolog's built-in rules and any helper rules that you like (including those that we wrote in class).
Here are some other examples of solve in action:
?- solve(['+'], [1, 1, 1, 1], 24, Tree). no. ?- solve(['+'], [24], 24, Tree). Tree = 24 ?- solve(['+', '*', '-'], [1, 2, 3, 4], 24, Tree). Tree = [*,1,[*,2,[*,3,4]]]Notice that a plain integer (e.g. 24) is the simplest possible solution tree (not [24]), and there are many more answers to the third example above.
This problem will require that you to think very carefully about the order in which rules are specified in your prolog rules. Remember from class that order matters!
A very good approach to this problem is to write a helper rule called tree that takes as input a list Operations of valid operations to be used, a list Numbers of numbers to be used and a Tree which is a tree in which the leaves of the tree are the numbers, where each number is used exactly once, the internal nodes in the tree are selected from Operations (with operations permitted to be used more than once). In fact, you might find it convenient to stipulate that the numbers at the leaves must occur exactly in the order (from left-to-right) that they are given in Numbers. (You can deal with permuting these numbers someplace else.) For example:
| ?- tree(['+', '*'], [1, 2, 3, 4], ['*', ['+', 1, 2], ['*', 3, 4]]). yes | ?- tree(['+', '*'], [1, 2, 3], X). X = [+,1,[+,2,3]] ; X = [+,1,[*,2,3]] ; X = [+,[+,1,2],3] ; X = [+,[*,1,2],3] ; X = [*,1,[+,2,3]] ; X = [*,1,[*,2,3]] ; X = [*,[+,1,2],3] ; X = [*,[*,1,2],3] ; no
Notice that in the first case we gave tree all three lists and it verified that the third list (a tree) could be constructed from the operations in the first list and the numbers in the second list. Then, in the second case, we "tricked" prolog into generating all possible trees with a given set of operations and numbers. Once you can do this, you're nearly done!
Please submit this part of the assignment in a file called part5.pl.
Wait until after Wednesday's lecture to complete this part of the assignment.
In this part of the assignment, you will write a Prolog program to solve the Towers of Hanoi puzzle. Please submit your solution in a file called part6.pl. You should carefully review the "fox, lettuce, hare" solution that we examined in class before embarking on this program. The big ideas in the two programs are very similar. Fortunately though, this Hanoi program is considerably shorter. (You should expect your program to be about 20 lines of Prolog code, not including comments and spacing between rules.) Your solution should specify valid moves in this puzzle and Prolog should use these rules to infer correct solutions to the puzzle. Here are the details:
[ [1, 2], [3, 4], [] ]
represents disk 1 on top of disk 2 on peg 1, disk 3 on top of disk 4 on
peg 2, and nothing
on peg 3.
[ [1, 2, 3, 4], [], [] ]
[ [], [], [1, 2, 3, 4] ]
| ?- valid([ [1, 2, 3], [], [] ], 12, [ [2, 3], [1], [] ]).
yes
This is valid because we went from the first configuration to the
second configuration via move "12".
Here's another example:
| ?- valid([ [1, 2], [], [3] ], 12, [ [2], [], [1, 3] ]).
no
In this case, it's possible to move from the first configuration to
the second configuration, but not by move "12".
Here's yet another example:
| ?- valid([ [1 , 2], [], [3] ], 31, [ [3, 1, 2], [], [] ]).
no
Although we did move a disk from peg 3 to peg 1 here, this move was
invalid because disk 3 cannot be placed on top of disk 1.
| ?- hanoi([ [1], [2], [3] ], [23, 13]).
yes
The answer here is "yes" because move "23" followed by "13" leaves us
in the final configuration.
Once this function is written, you can do the following:
| ?- hanoi( [ [1, 2, 3], [], [] ], Solution).
Solution = [12,13,21,13,12,31,12,31,21,23,12,13,21,13]
(Your Prolog program may find a different solution. The solution
found depends on the order in which the rules were defined. As long
as your Prolog program finds a correct solution, that's fine!)
| ?- retractall(marked(_)).
yes
Then, you should be able to run it again... .