Use the following commands to download and unpack the distribution code:
$ wget https://amirkamil.github.io/homework/hw4/starter-files.tar.gz $ tar xzf starter-files.tar.gz
You may work alone or with a partner. Please see the syllabus for partnership rules. As a reminder, you may not share any part of your solution outside of your partnership. This includes code, test cases, and written solutions.
This assignment requires you to write code in Prolog. The officially supported interpreter for this course is SWI-Prolog. Installation instructions are on the download page. If you are using Mac OS, you can install with Macports or Homebrew, which will place the swipl interpreter in your path. You may also use the web-based version for this assignment. The CAEN machines have installations of SWI-Prolog:
module load swiprolog
You may find the built-in length and append predicates useful for this assignment.
List manipulation. Write a predicate add_to_all that, given three arguments, is true if the third is the result of inserting the first argument at the front of each list contained in the second argument. For example,
add_to_all(a, [[], [b], [c, d]], [[a], [a, b], [a, c, d]])
is true, whereas
add_to_all(a, [[], [b], [c, d]], [[a, b], [a, c, d]])
is not.
Write your solution in add_to_all.pl.
There are several tests in add_to_all.in. Each query ends in !, which is the Prolog cut operator, preventing more solutions from being explored once a solution has been found. We include this to ensure consistent output for different solutions to a problem.
If you have SWI-Prolog installed, you can compare the results to the expected output using:
$ swipl -q add_to_all.pl < add_to_all.in | diff - add_to_all.correct
Merge sort. In this question, we will implement merge sort on lists of integers. Write your code in mergesort.pl.
Implement a merge predicate that relates two sorted lists to their merge:
?- merge([1, 3, 8], [2, 4, 5], Z). Z = [1, 2, 3, 4, 5, 8] .
You will need to use the built-in comparison operations.
Now implement a mergesort predicate that relates a list to its sorted counterpart. Print out the "input" list in the recursive rule using writeln, as in the distribution code:
?- mergesort([4, 8, 5, 3, 1, 2, 6, 9, 7], X). [4,8,5,3,1,2,6,9,7] [4,8,5,3,1] [4,8,5] [4,8] [3,1] [2,6,9,7] [2,6] [9,7] X = [1, 2, 3, 4, 5, 6, 7, 8, 9] .
When splitting up a list for the recursive terms, the two sublists should either be the exact same size, or the first sublist should be exactly one item larger than the second. You may find the built-in length and append predicates helpful here.
The tests above are in merge.in and sort.in.
Matching. In this question, we will implement an algorithm for matching people to a set of tasks. Each person expresses ranked preferences for some subset of the tasks, and the goal is to find an assignments of tasks to people such that everyone is assigned a task in their preference list. The algorithm will also take into account the preference ranks themselves when assigning a task.
Consider a set of tasks, a set of people who can be assigned a task, and a set of preferences for each person for some subset of the tasks. The following is an example:
| Fe | Wei | Gwyn | Ting | |
|---|---|---|---|---|
| Task 1 | 1 | 1 | ||
| Task 2 | 2 | |||
| Task 3 | 1 | 2 | 2 | |
| Task 4 | 2 | 1 |
Here there are four tasks and four people, each with their top two preferences for tasks. Our goal is to determine a matching of tasks to people that takes into account each person's preference.
We will implement a match predicate that can be used as follows:
?- match([[task1, [fe, 1], [gwyn, 1]],
[task2, [fe, 2]],
[task3, [wei, 1], [gwyn, 2], [ting, 2]],
[task4, [wei, 2], [ting, 1]]
],
[fe, wei, gwyn, ting], A).
The first argument encodes the preferences. It is a list with one element per task, and a task itself is represented as a list consisting of the task name followed by preferences for that task. Each preference is a list containing the name of a person and their preference rank for the task. Thus, Task 1 is represented as [task1, [fe, 1], [gwyn, 1]], where Fe ranks it as her first choice and Gwyn also ranks the task as her first choice.
The second argument is a list of names of people who can be assigned tasks. The last argument is the actual resulting assignments of tasks to people. The following is one possible solution to the query above:
A = [[task1, gwyn, 1], [task2, fe, 2], [task3, wei, 1], [task4, ting, 1]].
The overall algorithm we implement is as follows:
The beauty of logic programming is that if the algorithm gets stuck, e.g. by assigning a person to a task such that the remaining assignments are infeasible, it automatically backtracks to look for another solution.
We will start by implementing helper predicates before proceeding to match. Place all code for this question in match.pl.
Write a predicate smaller that is true if the first argument has a shorter length than the second argument:
?- smaller([1, 2], [3, 4, 5]). true. ?- smaller([1, 2, 3], [3, 4, 5]). false.
Now complete the implementation of the smallest predicate that relates a list of lists to the shortest list contained within the list of lists. If two lists have the same length, the leftmost such list should be preferred:
?- smallest([[1, 2], [3, 4, 5], [6, 7]], L). L = [1, 2].
In order for the matching algorithm to be efficient, the smallest predicate needs to be implemented tail recursively. As such, we write the smallest_helper predicate that relates a list of remaining items to the smallest item seen so far and the smallest item overall. Implement the recursive cases for this predicate.
You will need to prevent the interpreter from finding a solution that is not the leftmost of the shortest length, such as by using negation. The built-in findall predicate finds all solutions to a query. Your implementation of smallest should result in the following:
?- findall(L, smallest([[1, 2], [3, 4, 5], [6, 7]], L), Results). Results = [[1, 2]].
Implement an assign predicate that relates a list of preferences, a list of people, a person out of the latter list, and their preference rank from the first list. The elements of the first list are each a list of two atoms, the first being a person and the second their preference rank for the task.
The following is an example of a query:
?- assign([[fe, 3], [wei, 2], [gwyn, 3], [ting, 1]],
[fe, gwyn, wei], Person, Rank), !.
Person = wei,
Rank = 2.
Your implementation should find the person with the minimum preference rank, as long as they are in the list of people in the second argument. However, it should not cut off the search space when it finds the minimal solution. Instead, if another solution is requested, it should find the person with the next lowest rank. Where two people have the same rank, it should first find the leftmost of the two in the preference list:
?- assign([[fe, 3], [wei, 2], [gwyn, 3], [ting, 1]],
[fe, gwyn, wei], Person, Rank).
Person = wei,
Rank = 2 ;
Person = fe,
Rank = 3 ;
Person = gwyn,
Rank = 3 ;
false.
You will find the built-in member predicate useful, as well as one of the sort predicates. Find the documentation on the SWI-Prolog website.
With findall, your implementation of assign should result in the following:
?- findall([Person, Rank],
assign([[fe, 3], [wei, 2], [gwyn, 3], [ting, 1]],
[fe, gwyn, wei], Person, Rank),
Results).
Results = [[wei, 2], [fe, 3], [gwyn, 3]].
Finally, implement the match predicate, which relates a list of tasks, a list of people, and a list of assignments.
A task is a list where the first item is the task ID, and the remaining items are preferences for the task, each consisting of a list of a person and a preference rank:
[task1, [fe, 1], [gwyn, 1]] % task1 is the task ID
The assignment list contains a list for each task, containing the task ID, the person assigned to it, and the preference rank of the person for the task:
[[task1, gwyn, 1], [task2, fe, 2], [task3, wei, 1], [task4, ting, 1]]
Implement the algorithm described above for match. You may find the built-in select/3 predicate useful for Steps 3 and 4.
The following is an example, using the provided sorted_match predicate to produce a sorted list of assignments:
?- sorted_match([[task1, [fe, 1], [gwyn, 1]], [task2, [fe, 2]],
[task3, [wei, 1], [gwyn, 2], [ting, 2]],
[task4, [wei, 2], [ting, 1]]],
[fe, wei, gwyn, ting], A), !.
A = [[task1, gwyn, 1], [task2, fe, 2], [task3, wei, 1], [task4, ting, 1]].
A more complex query, using the actual preferences for EECS 280 staff for lab sections from Winter 2017 (but with names changed), is in match2.in. Your implementation of match should be efficient enough to find a solution in less than a second.
(Optional) Write a new predicate optimal_match that finds an optimal matching, such that the sum total of the assigned preferences is minimized. As an example, the complex query in match2.in has an optimal assignment that results in a total of 58 rather than the 63 produced by the algorithm above.
Hint: The interpreter will continue to look for solutions after the first one. Come up with a way to force it to look for a better solution until no better solution exists. You will also need to cut off a search path as soon as it becomes clear that it cannot lead to a better solution.
Using our implementation, finding an optimal assignment takes about ten seconds on an iMac computer.
(Optional) Extras. This question is optional and will not be graded. Its purpose is to provide more practice with logic programming. If you choose to do it, write your answers in extras.pl.
Write a predicate sublists that relates a list of items to another list that contains every sublist of the first. For instance, the goal
sublists([1, 2, 3], X)
succeeds with
X = [[], [3], [2], [2, 3], [1], [1, 3], [1, 2], [1, 2, 3]]
You may find it useful to use add_to_all in your definition.
Note: By default, the swipl interpreter will truncate output. Type in the w character to see the full output.
Write a predicate unzip that succeeds if its first argument is the "zip" of the second and third arguments, meaning that it interleaves the items from the second and third arguments. The second argument is required to be exactly the same length as, or one item larger than, the third argument. For example:
?- unzip([a, b, c, d, e, f], Evens, Odds). Evens = [a, c, e], Odds = [b, d, f]. ?- unzip([a, b, c, d, e], Evens, Odds). Evens = [a, c, e], Odds = [b, d] .
Hint: You will likely find that you need two base cases, one for when the two lists have the same length and one for when the first list is one item larger.
For the prime sieve in lecture, we wrote a numbers predicate that relates a number N to an ordered list of numbers from 2 to N. However, the implementation in lecture takes quadratic time, since it uses the append predicate. Write another version of numbers that has a "tail-recursive" structure so that it only takes linear time.
Place your solutions to question 1 in the provided add_to_all.pl file, to question 2 in the mergesort.pl file, and to question 3 in match.pl. Submit add_to_all.pl, mergesort.pl, and match.pl to the autograder before the deadline. Be sure to register your partnership on the autograder if you are working with a partner.