Assignment 5: Prolog

Answer each of the following questions using SWI-Prolog on Linux. Write all the code yourself and, unless a question says otherwise, you can use any standard functions available when you launch SWI-Prolog (don’t import any extra libraries). Write any helper functions you think are useful.

For these questions we are only concerned with the first solution that’s returned. So you do not need to worry about extra solutions, or using the cut operator !.

Also, you can assume that all obvious pre-conditions for a function are true, and so you don’t need to check if function inputs are valid.

When it is time to submit your work, please put all your functions into a single file named a5.pl and submit it on Canvas.

1. (2 marks) Implement makelist(N, X, Lst) that works as follows:

   ?- makelist(3, a, X).
   X = [a, a, a]
   
   ?- makelist(4, [a,b], X).
   X = [[a, b], [a, b], [a, b], [a, b]]
   

   In other words, makelist(N, X, Lst) binds to Lst a new list consisting of N copies of X.

   You can assume N is 0 or greater.

2. (2 marks) Implement second_min(Lst, M) that calculates the second smallest number on a list like this:

   ?- second_min([2,8,4,6], X).
   X = 4
   
   ?- second_min([1,2], X).
   X = 2
   

   If the passed-in list has fewer than 2 elements, it should fail:

   ?- second_min([], X).
   false
   
   ?- second_min([6], X).
   false
   

   For simplicity, you can assume Lst has no duplicates.

3. (2 marks) Prolog has a function called numlist(Lo, Hi, Result) that creates a list of numbers from Lo to Hi. For example:

   ?- numlist(1,5,L).
   L = [1, 2, 3, 4, 5]
   

   Implement your own version of this called mynumlist(Lo, Hi, Result). Of course, don’t use numlist anywhere!

   Here’s some documentation for numlist, and other useful list functions.

4. (2 marks) Implement the function all_diff(Lst) that succeeds (i.e. returns true) just when Lst has no duplicate values, e.g.:

   ?- all_diff([7,2,1,9]).
   true
   
   ?- all_diff([7,2,7,9]).
   false
   

   If Lst is empty, or only has one element, then all_diff should succeed.

   You can use \+, the not operator, in your solution. It works like this:

   ?- \+ member(2, [2,4,1]).
   false
   
   ?- \+ 5 < 6.
   false.
   

5. (2 marks) Implement negpos(L, Neg, NonNeg) that partitions a list L of numbers into negatives and non-negatives. For example:

   ?- negpos([1,0,2,-3,2,-4,5], A, B).
   A = [-3, -4],
   B = [1, 0, 2, 2, 5]
   

   The order of the numbers in Neg and NonNeg doesn’t matter.

6. (5 marks) A 3x3 magic square is a grid of 9 numbers where each row and column add up to the same number (known as the magic number). The sum of the two diagonals does not matter.

   For example, this magic square has magic number 15:

   1 5 9
   6 7 2
   8 3 4
   

   Implement magic(L9, Result) that takes a list L9 of 9 numbers as input, and calculates a permutation of L9 that is magic. For example:

   ?- magic([1,2,3,4,5,6,7,8,9], Result).
   Result = [1, 5, 9, 6, 7, 2, 8, 3, 4]
   

   Result is in row-major order, i.e. it corresponds to this square:

   1 5 9
   6 7 2
   8 3 4
   

   Here’s another example:

   ?- magic([2,4,6,8,10,12,14,16,18], Result).
   Result = [2, 10, 18, 12, 14, 4, 16, 6, 8]
   

   This is the square (it’s magic number is 30):

    2 10 18
   12 14  4
   16  6  8
   

   If L9 does not have exactly 9 elements, then magic should return false.

   Depending upon the numbers in L9, there could be 0 or more solutions. When there’s no solution, your magic function should only take a few seconds to run.