Project 5

Project files

All files: p5.zip

• Code skeletons:
  • warmup.pl
  • maze.pl

• Files for command line submission (see "Submission" for usage)
  • .submit
  • submit.jar

Project description

This project will give you some experience programming in Prolog. To help you understand Prolog's strengths relative to other programming languages, we are having you reimplement pieces of previous projects in Prolog. Your submission will include this reimplementation, as well as a short essay comparing your Prolog vs. your other implementations, identifying strengths and weaknesses from your own point of view.

Part 1. Warmup

Write your solutions to this part in the file warmup.pl.

• Write a predicate prod(P,L) that calculates the product of the elements of L. P should be 1 if the list is empty. (L will always be given.)

  ?- prod(P,[1,2,3]).
  P = 6
  

• Write a predicate add_tail(L,M,E) that takes a list M and a single element E and finds a new list L, where E is appended to the back of M. (Note: Do not use the append predicate) (Two of the three parameters will always be given.)

  ?- add_tail(L,[1,2,3],4).
  L = [1,2,3,4].
  
  ?- add_tail([1,2,3,4], SL, 4).
  SL = [1,2,3].
  
  ?- add_tail([1,2,3,4], [1,2,3], X).
  X = 4.
  

• Write a predicate fill(L,X,N) that finds a list L containing N copies of X. If N ≤ 0, then L should be the empty list. (N will always be given.)

  ?- fill(L,20,4).
  L = [20,20,20,20]
  
  ?- fill([20,20,20,20],X,4).
  X = 20.
  

• Write a predicate rindex(I,L,E) that takes a list L and a single element E and finds the position I of the last occurrence of that element in the list (indexed by zero). If the element is not in the list, then I should be -1. (L and E will always be given.)

  ?- rindex(I,[1,2,3,2],2).
  I = 3
  

• Write a predicate even_elts(L,M) that takes a list M and finds a new list L containing the elements at even indices (0th, 2nd, 4th, etc). (M will always be given.)

  ?- even_elts(L,[b,a,t,m,a,n]).
  L = [b,t,a]
  

• Write a predicate sublist(S,M,N,L) that finds a new list S containing the elements of L starting with the M'th element and ending with the N'th element, inclusive. S should be the empty list if M > N. Otherwise, S should contain elements at indeces in the intersection of {M,M+1,...,N-1,N} and {0,1,...,length of S-1} (which may also be empty). M, N, and L will always be given.

  ?- sublist(S,1,3,[b,a,t,m,a,n]).
  S = [a,t,m].
  
  ?- sublist(S,2,1,[b,a,t,m,a,n]).
  S = [].
  
  ?- sublist(S,1,999,[b,a,t,m,a,n]).
  S = [a,t,m,a,n].
  

• Write a predicate rotate(L,M,N) that finds a new list L containing the same elements as M, "rotated" N times to the right. The behavior of rotate for N less than 0 is the same as N equal to 0. (M and N will always be given; note that N can be arbitrarily large.)

  ?- rotate(L,[1,2,3,4],0).
  L = [1,2,3,4]
  
  ?- rotate(L,[1,2,3,4],1).
  L = [4,1,2,3]
  
  ?- rotate(L,[1,2,3,4],2).
  L = [3,4,1,2]
  
  ?- rotate(L,[1,2,3,4],4).
  L = [1,2,3,4]
  

• Write a predicate unzip(Lefts,Rights,Pairs) with the following relationship: Pairs is a list of pairs; Lefts is the list consisting of each of the left elements of Pairs, while Rights is the list consisting of each of the right elements. The elements should appear in Lefts and Rights in the same order as they did in Pairs. We will query unzip/3 in any of the following four ways:

  ?- unzip(L,R,[[1,2],[3,4],[5,6]]).         /* unzip the pairs: Lefts and Rights not given */
  L = [1,3,5],
  R = [2,4,6].
  
  ?- unzip([1,3,5], [2,4,6], _zipped).       /* zip the list: Pairs not given */
  _zipped = [[1, 2], [3, 4], [5, 6]].
  
  ?- unzip([1,3,5], R, [[1,2],[3,4],[5,6]]). /* half-unzip the list: Rights is not given */
  R = [2,4,6].
  
  ?- unzip(L, [2,4,6], [[1,2],[3,4],[5,6]]). /* half-unzip the list: Lefts is not given */
  L = [1,3,5].
  

• Write a predicate poly(CL,X,V) where CL is a list of integers [c₁,...,c_n, c_n+1], X is an integer, and the task is to find V which should be equal to c₁*Xⁿ + ... + c_n*X + c_n+1. If CL is empty, then V is 0, regardless of X's value. (Hint: use the built-in length/2 predicate.) (CL and X will always be given.)

  ?- poly([1,0,0], 5, V).        /* V = 1*5^2 + 0 + 0 */
  V = 25.
  
  ?- poly([1,0,2,4,-3], -1, V).  /* V = 1*(-1)^4 + 0*(-1)^3 + 2*(-1)^2 + 4*(-1) - 3 */
  V = -4.
  

• Write a predicate in_set(L) that checks if the sequence of characters in the list L belongs to the set
  S = {a^n b^n a^m b^m | n,m >= 1} U {a^n b^m a^m b^n | n,m >= 1} .
  Or to put it another way, it is true when the string represented by L is recognized by the following CFG:

     S -> T | V
     T -> UU
     U -> aUb | ab
     V -> aVb | aWb
     W -> bWa | ba
  

  Here are some examples:

  ?- in_set([a,a,b,b,a,b]).
  true.
  
  ?- in_set([a,a,a,b,b,a,a,b,b,b]).
  true.
  
  ?- in_set([a,a,a,b,b,a,b,b,b]).
  false.
  

  Note: in_set/1 must return a single true/false. To this end, you must use cuts. (Some value of L will always be given.)

Part 2. Mazes

In this part of the project, you will reimplement elements of the mazes project. All solutions should be a file maze.pl (the link is a skeleton file that should contain your answer).

Maze descriptions

• maze(N,SX,SY,EX,EY). This fact indicates that:
  • The height and width of the maze is N cells,
  • The default starting position is SX,SY, and
  • The ending position is EX,EY.
• cell(X,Y,Dirs,Wts). A fact of this form describes a cell in the maze. In particular, it says that the cell at position X,Y, has open walls as described by Dirs, the list of directions. More precisely:
  • The list Dirs will contain at most one of each of the atoms u, d, l, and r, which designate openings going up, down, left, or right, respectively.
  • Recall from project one that the coordinate system places 0,0 in the upper left corner of the maze.
  • The Wts component of the fact indicates the weights granted to paths following the respective direction. That is, each element in Dirs has a corresponding weight in Wts.
  As an example, the fact cell(1,0,[r,d],[16.6, 0.89]) indicates that the cell at 1,0 has two open walls: one leading to the right (to cell 2,0) with weight 16.6, and one leading down (to cell 1,1) with weight 0.89.
• path(N,SX,SY,Dirs). This fact describes a path named N (a string) through the maze starting at position SX,SY and following the directions given by Dirs. For example, the fact path("path1",0,3,[u,r,u,l,u]) indicates that there is a path "path1" that starts at 0,3 and follows the given directions to end up at position 0,0.

What to program

• stats(U,D,L,R). This predicate will count the number of open walls in the maze for each of the four directions. Note that for a well-formed maze, the U and D counts will always match, as will the L and R counts. For our example maze:

  ?- stats(U,D,L,R).
  U = D, D = 8,
  L = R, R = 7 
  

• okpath(N,Wt). This predicate will confirm that the path named N is indeed a legal, defined path for the maze, and that its rounded integer weight is Wt; that is, if the floating-point weight of the path is W, then Wt is such that W is round(Wt). For our example, the path given above, named "path1", can be queried as follows:

  ?- okpath("path1",Wt).
  Wt = 100
  

• bestpath(N,Wt). This predicate holds for the path named N which has the shortest weight among all named paths. For our example, we could determine this path as follows:

  ?- bestpath(N,Wt).
  N = [112, 97, 116, 104, 49],
  Wt = 100
  

  (Notice that N here is a list of integers; this is the list representation of the string "path1" where the numbers are character codes for the respective letters.) Hint: Use the Prolog findall/3 predicate with okpath to collect all the weights of all legal paths into a list, find the minimum of the list, and then locate the path name with that weight using okpath again.
  
  
• reachable(C,Cs).This predicate defines list Cs as containing all cells reachable via some path starting from C.
  
  Hint: We recommend you implement this predicate using an auxiliary predicate reachable(Cs0,Ws,Fs) as follows:
  
  reachable(C,Cs) :- reachable([C],[],Fs).
  
  The predicate reachable(Cs0,Ws,Fs) identifies all cells Fs reachable from the cells in list Cs0 where cells in Ws have already been processed; ultimately when no work is left to do, Ws = Fs.

  ?- reachable([0,0],Fs).
  Fs = [[0, 3], [0, 2], [3, 2], [3, 1], [1, 0], [2, 0], [2, 1], [3|...], [...|...]|...].
  

  In the public tests, we use this query to determine whether a maze is solvable, i.e.,:

  ?- maze(_,SX,SY,EX,EY), reachable([SX,SY],Fs), member([EX,EY],Fs).
  SX = EX, EX = EY, EY = 0,
  SY = 3,
  Fs = [[0, 0], [0, 1], [3, 2], [3, 1], [3, 3], [2, 3], [2, 2], [2|...], [...|...]|...] 
  

Submission

You may either submit over the web or under command line interface.

Submitting over the web

Submit your archive directly to the submit server by clicking on the submit link in the column "web submission".

Next, use the submit dialog to submit your p4.pl file directly.

Select your file using the "Browse" button, then press the "Submit project!" button.

Submitting in command line interface

The first time you submit this way you will be asked to enter your directory ID and password. All files in the directory (and its subdirectories) will then be put in a jar file and submitted to the submit server. If your submission is successful you will see the message:

Academic Integrity

The Campus Senate has adopted a policy asking students to include the following statement on each assignment in every course: "I pledge on my honor that I have not given or received any unauthorized assistance on this assignment." Consequently your program is requested to contain this pledge in a comment near the top.

Please carefully read the academic honesty section of the course syllabus. Any evidence of impermissible cooperation on projects, use of disallowed materials or resources, or unauthorized use of computer accounts, will be submitted to the Student Honor Council, which could result in an XF for the course, or suspension or expulsion from the University. Be sure you understand what you are and what you are not permitted to do in regards to academic integrity when it comes to project assignments. These policies apply to all students, and the Student Honor Council does not consider lack of knowledge of the policies to be a defense for violating them. Full information is found in the course syllabus---please review it at this time.