CSE4102: Programming Languages Spring 2022
Homework 6: Card Game 24, Coins Puzzle and Minimum Spanning Tree (Prolog)
Ob jectives
In this homework we solve a few interesting problems using Prolog. We practice how to implement BFS, MST in Prolog and how to use binary expression trees to find solutions to a card game.
Copyright By PowCoder代写 加微信 powcoder
Question 1: Card game 24
In this game, 4 cards are randomly picked from a standard deck of 52 cards. We will use the values of these 4 cards and a combination of addition, subtraction, multiplication, division, and parentheses to produce the value 24. Note that each of the 4 cards can only be used once. The values of the cards
A, 2, 3, 4, 5, 6, 7, 8, 9, 10, J, Q, K,
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13,
respectively.
For example, if the 4 cards chosen are “A 2 3 Q”, we can produce the value 24 by doing the following operation:
(3 – 2 + 1) * 12 = 24
Note that there are many possible solutions for a given 4-card combination. For instance the cards “A 2 3 Q” can produce 33 different solutions which produce 24. Read the following link for more information about the game:
https://en.wikipedia.org/wiki/24_Game
To solve this problem, we will get familiar with the binary expression tree, which is a kind of binary tree used to represent expressions. In this type of binary tree, each internal node corresponds to an operator and each leaf node corresponds to an operand. For example, the expression 1 ∗ (2 ∗ (3 ∗ 4)) can be represented using a binary expression tree as in Figure 1. It is not difficult to show that for our scenario where we have 4 numbers, we have 5 different binary expression trees, as shown in Figure 2.
We can use this knowledge to play the game. We can implement five clauses for the predicate cal that correspond to these five binary expression trees.
For example, in predicate cal(Values, X), Values is the list of values of 4 cards. For example, Values could be [1,9,11,13] which corresponds to the four cards in list [A, 9, J, K]. And X is a list representation of a solution
*(-(1,13),-(9,11))
Note the solution is in the form of prefix expressions. This solution is (1 − 13) ∗ (9 − 11) as a infix expression. The list X for this solution is
Figure 1: Binary expression tree that represents 1*(2*(3*4))
Figure 2: 5 trees
[’*’, ’(’, ’-’, ’(’, 1, ’,’, 13, ’)’, ’,’,’-’,9, ’,’, 11, ’)’, ’)’]
We can use the predicate
print([H|T]) :- write(H), print(T).
print([]):- nl.
to print the list as
*(-(1,13),-(9,11))
We use the predicate solve to find and print out all the solutions of the four cards in list Cards. Note we first use the predicate trans to transform the list of four cards to a list of four values.
solve(Cards):-trans(Cards,Values),setof(X, cal(Values, X), L),
print_result(L),
length(L,Len),write(Len),write(’ solutions:’).
Note the predicate trans(Cards,Values) to convert a list of cards into a list of values. Below are some sample outputs. Note the results are printed using the format of prefix operators.
?- solve([a,9,j,k]).
*(-(1,13),-(9,11))
*(-(9,11),-(1,13))
*(-(11,9),-(13,1))
*(-(13,1),-(11,9))
4 solutions.
Here is another example.
?- solve([a,7,q,k]).
*(12,/(+(1,13),7))
*(12,/(+(13,1),7))
*(+(1,13),/(12,7))
*(+(13,1),/(12,7))
*(/(12,7),+(1,13))
*(/(12,7),+(13,1))
*(/(+(1,13),7),12)
*(/(+(13,1),7),12)
/(12,/(7,+(1,13)))
/(12,/(7,+(13,1)))
/(*(12,+(1,13)),7)
/(*(12,+(13,1)),7)
/(*(+(1,13),12),7)
/(*(+(13,1),12),7)
/(+(1,13),/(7,12))
/(+(13,1),/(7,12))
16 solutions.
The following the hardest one in my opinion.
?- solve([3,8,8,3]).
/(8,-(3,/(8,3)))
1 solutions.
Question 2: Coins Puzzle and BFS
This problem is from book ”Perplexing Puzzles and Tantalizing Teasers” by . This problem is the 9-th problem in the book. The following figure Figure 3 shows the description of this problem from the book.
Figure 3: Instruction for the coins puzzle.
Solve this problem using BFS. The expected output is the following.
[1,1,0,10,10]
[1,0,1,10,10]
[1,10,1,0,10]
[1,10,1,10,0]
[1,10,0,10,1]
[0,10,1,10,1]
[10,0,1,10,1]
[10,10,1,0,1]
[10,10,0,1,1]
Question 3: Minimum Spanning Tree
Airlines face a difficult problem of ensuring that their passengers can get between each of the airports they serve, in some number of steps, while simultaneously trying to minimize their costs.
A new airline, CSE4102 Airways, has already selected the set of airports they plan to serve. However, they have the following task remaining.
Given the costs of all routes they could possibly serve, figure out the cheapest routes that allows any passenger to get from one airport to another in some finite number of steps.
For example, the table below shows the set of flights available, and their costs. Note that the table below omits the symmetric entries. Namely, while the PVD row has no entries, the PVD column specifies connectivity with 2 airports {JFK,ORD} which implies that you can take those two flights in any direction.
AP BOS BWI* DFW JFK LAX MIA ORD PVD SFO
BOS – – BWI – – DFW – – JFK – – LAX – – MIA – – ORD – – PVD – – SFO – –
– 187 – 1258 867 – 184 – 946 621
– 2704 – –
– 1391 1235 1121
– – – – – – – – – – – –
– – – – – – – – – – – –
such: the first line contains a single integer, denoting the number of airports in
– – 849 1846 – –
Test cases are formatted as
the graph, followed by a newline character. The remaining lines will be composed of two three letter airport codes separated by a single whitespace followed by an integer and a new line character. Each line represents a bidirectional flight containing two airports whose flight cost is given by the numeric value. Consider the sample input below as an example.
ORD BWI 621 ORD BOS 867 BOS SFO 2704 ORD SFO 1846 BWI JFK 184 MIA BWI 946 JFK MIA 1090 BOS JFK 187 ORD DFW 802 LAX MIA 2342 PVD JFK 144 MIA BOS 1258 LAX SFO 337 DFW JFK 1391 DFW SFO 1464 ORD JFK 740 DFW LAX 1235 MIA DFW 1121 PVD ORD 849
On the example described earlier, the MST would be 5
LAX : SFO DFW ORD : BWI DFW DFW : ORD LAX MIA : BWI
The below output confirms that and the total cost of the MST is 4456.
?- solve(Tree,TotalCost).
Tree = [lax-sfo, dfw-lax, bwi-mia, ord-dfw, jfk-bos, jfk-pvd, bwi-jfk, ord-bwi],
TotalCost = 4456.
BWI BOS ORD MIA
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com