ITEC 380 2008fall ibarland

home—info—lectures—exams—archive

hw05
prolog exercises

Write the following Prolog predicates:

• (15pts) last(List, Item), which succeeds exactly when Item is the last item in List. (This rule should fail if List is empty, of course.)
• (10pts) nextToLast(List, Item) which succeeds exactly when Item is the next-to-last item in List. (This rule should fail if List has fewer than two items, of course.)
• (10pts) lastTwoReversed(List, ListOf2) which succeeds exactly when ListOf2 contains the last and the second-to-last item of List (in that order).
• (10pts) reverseLastTwo(List, NewList) succeeds exactly when NewList is like List except that the last two items have been reversed. (This rule will fail if List has fewer than two items.)
• (20pts extra credit) Write program to

  leg(roa,ord).
  leg(roa,clt).
  leg(roa,nyc).
  
  leg(ord,nyc).
  leg(ord,atl).
  leg(ord,lax).
  
  

Here are some examples:

last([1,2,3], 3).
Yes
last([1,2,3], 4).
No

last([1,2,3], Y).
Y=3

last([], Y).
No

last(Y, 3).
Y=[3].

nextToLast([1,2,3], 2).
Yes

nextToLast([1,2,3], 3).
No

nextToLast([1,2,3], Y).
Y=2

nextToLast([1], Y).
No

nextToLast(Y, 3).
Y=[3, _h114].      % does not have to be 114

lastTwoReversed([1,2,3], Y).
Y=[3,2]

lastTwoReversed([1], Y).
No

reverseLastTwo([1,2,3,4], Y).
Y=[1,2,4,3]

reverseLastTwo([1,2], Y).
Y=[2,1]

reverseLastTwo([1], Y).
No

Note that xsb Prolog contains several list functions which you are NOT to use for this assignment. If you need a list function, then should simply write it yourself.

This assignment can be done relatively easily by reversing the list and then operating on it, and if necessary reversing the results. Please note that this method of solution will not earn full marks for the assignment. Of course, you can try this method as you are figuring out how to do the assignment, but if you want full credit for what you do, you should not use reverse in your solution.

Please be certain to use these exact names. I will not grade your program if your names are not exactly correct. Also, make sure that you do not mix up the names.

Please make sure that you test your program completely.

You may use any prolog system to write your program, but you should test it on xsb on rucs which is where I will run it for grading. Several free versions on prolog are available for download, including xsb and jlog.

As ever, your program should follow good style, including appropriate white space, meaningful variable names, and as well as a header comment with your name, the name of the assignment, etc.. (You can have comments describing how a predicate works if you want; however, you can also assume your program is being read by somebody who understands the fundamentals of Prolog.)

The following extra credit is available, due the last day of class. Note that you must pledge that you did not find/study a solution to this problem on-line (searching in a graph).

• (10pts extra credit) Write a program to compute a series of connecting flight-legs from one city to another. The knowledge base will include all the individual (one-way) flight-legs. For example, one knowledge base might be:

  % Facts: leg(roa,ord). leg(roa,clt). leg(roa,nyc). leg(ord,nyc). leg(ord,atl). leg(ord,lax). leg(clt,atl). leg(atl,iah). leg(lax,nyc). leg(nyc,iah).

  Half credit if your program works when no cycles exist (that is, if the flights form a dag -- “directed acyclic graph”), and full points if your code works in the presence of cycles.)
  Also (for 2 of the 10pts): What is a single rule that can be added to the knowledgebase, so that all legs are two-way? (Why is it important that this rule is added after all the leg facts?)
• (10pts extra credit) Expand the previous solution to find a shortest list of legs from one city to another (where “shortest” means “fewest number of legs”). Remember, you can use the query findall to gather all the solutions into a list. For example: findall(X, parent(X,bob), AllMatchesForX). (Note that the first “argument” to findall must be a variable, and the second term is a query which involves that variable.)

home—info—lectures—exams—archive

©2008, Ian Barland, Radford University Last modified 2008.Nov.26 (Wed)

Please mail any suggestions (incl. typos, broken links) to iba�rlandrad�ford.edu