.  This homework is a combination programming and “paper & pencil” assignment.

.  Due via Brightspace on Monday, December 4, 2023 11:59 PM Eastern Daylight Time.  Due to tim- ing considerations relating to the end of the semester, late submissions will not be accepted.   No exceptions.

.  For the Prolog questions, you should use SWI Prolog. Link is available on the course page.

.  For the Java questions, you should use Java 8. Link is available on the course page.

. You may collaborate and use any reference materials necessary to the extent required to understand the material.  All solutions must be your own, except that you may rely upon and use Prolog code from the lecture if you wish.  Homework submissions containing any answers or code copied from any other source, in part or in whole, will receive a zero score and be subject to disciplinary action.

For theory questions (Q3, Q6 and Q7), a PDF file hw4-<netid>-sols.pdf containing the answers.

Please submit your programming homework as a zip file, hw4-<netid>.zip in Brightspace.  The zip file should contain the PDF above and the following:

–  For Q1, hw4-<netid>-Q1.pl which should contain the reordered facts for question 1 and the new rules for sub-questions 3-7. Answer sub-question 2 using a comment in this file.

–  For the Prolog  Rules question (Q2), hw4-<netid>-Q2.pl which should contain your implemen- tation of all of the rules. You do not need to submit queries, although we will run our queries on your solutions.

–  For Q4, hw4-<netid>-Q4.pl which should contain all rules  necessary to make the solution work. Use comments to mark your modifications.

–  Q5 does not need to be turned in.

.  Make sure your Prolog code compiles before submitting.  If your Prolog code  does not compile for any reason,  it may not be graded.

1.  [20 points]  Investigating Prolog

Consider the following:

male(kevin) .

male(joe) .

male(tom) .

male(burt) .

male(ned) .

male(bob) .

male(troy) .

male(fred) .

male(jason) .

male(walt) .

parent(jane,kevin) .

parent(mary,jen) .

parent(wendy,jason) .

parent(sade,joe) .

parent(pebbles,walt) .

parent(steph,isabella) .

parent(kendra,bob) .

parent(tina,sade) .

parent(fred,pebbles) .

parent(walt,isabella) .

parent(burt,sade) .

parent(troy,jason) .

parent(troy,brandon) .

parent(wendy,brandon) .

parent(bob,joe) .

parent(jason,walt) .

parent(ned,bob) .

parent(tom,kevin) .

grandfather(X,Y)  :-  male(X),  parent(X,Z),parent(Z,Y) .

1.  Reorder the facts above to provide faster execution time when querying grandfather(jason,isabella) . List the re-ordered facts and briefly explain what you changed.

2.  Explain in your own words why the change above affects total execution time.  Show evidence of the faster execution time (provide a trace for each).  It is okay if your solution contains mirrored tuples, but you must briefly explain why they are appearing if you see them.

3.  Define new rule parents/2 that determines if both arguments are parents of the same child.

4.  Define new rule sibling/2 that determines if 2 people are full siblings (have the same two parents).

5.  Define new rule half sibling/2 that determines if 2 people are half-siblings  (have exactly one parent in common).

6.  Define new rule ancestor/2 that determines if the first argument is the ancestor of the second argument.

7.  Define new rule related/2 that determines if 2 people share a common ancestor.

2.  [20 points]  Prolog Rules

Write the Prolog rules described below in a file hw4-<netid>-prules.pl. All rules must be written using the subset of the Prolog language discussed in class. You may not, for example, call built-in library rules unless specifically covered in the slides. You may call your own rules while formulating other rules.  You do not need to turn in queries, although you should certainly test your rules using your own queries.

1. Write  a rule  remove items(I,L,O)  in which  O is the output list obtained by removing every occurrence of each item in List I from list L. The items in O should appear in the same order as L, only without the elements present in I.

Example:

?-  remove_items([1,3],[2,6,7,7,8,3,1,1,4,3],O) .

O  =   [2,6,7,7,8,4]

2. Write a rule my flatten(L1,L2) which transforms the list L1, whose elements could be nested lists, into a “flat” list L2 by replacing each list with its elements.

Example:

?-  my_flatten([a,  [b,   [c,  d],  e]],  X) .

X  =   [a,  b,  c,  d,  e]

3. Write a rule compress(L1,L2) where all the repeated consecutive elements of the list L1 should be replaced with a single copy of the element. The order of the elements should not be changed.

Example:

?-  compress([a,a,a,a,b,c,c,a,a,d,e,e,e,e],X) .

X  =   [a,b,c,a,d,e]

4. Write a rule encode(L1,L2) where all the repeated consecutive duplicates of elements are encoded as terms [N,E] where N is the number of duplicates of the element E. The order of the elements should not be changed.

Example:

?-  encode([a,a,a,a,b,c,c,a,a,d,e,e,e,e],X) .

X  =  [[4,a],[1,b],[2,c],[2,a],[1,d][4,e]]

5.  Modify the result of previous problem in such away that if an element has no duplicates it is simply copied into the result list.  Only elements with duplicates are transferred as [N,E] terms.  Name the rule as encode modified.

Example:

?-  encode_modified([a,a,a,a,b,c,c,a,a,d,e,e,e,e],X) .

X  =  [[4,a],b,[2,c],[2,a],d,[4,e]]

6. Write a rule rotate(L1,N,L2) where the list L2 is the modified version of list L1, with the elements rotated as N places to the left if N is a positive number, otherwise rotated as N places to the right. You can assume that list L1 is never empty and |N |  < length(L1), where | . |  is the absolute value operator.

Examples:

?-  rotate([a,b,c,d,e,f,g,h],3,X) .

X  =   [d,e,f,g,h,a,b,c]

?-  rotate([a,b,c,d,e,f,g,h],-2,X) .

X  =   [g,h,a,b,c,d,e,f]

3.  [10 points]  Unification

For each expression below that unifies, show the bindings.  For any expression that doesn’t unify, explain why it doesn’t. Assume that the unification operation is left-associative.

1.  d(15) & c(15)

2. 4 & X & 76

3.  a(X, b(3, 1, Y)) & a(4, Y)

4. b(1,X) & b(X,Y) & b(Y,1)

5.  a(1,X) & b(X,Y) & a(Y,3)

6.  a(X, c(2, B, D)) & a(4, c(A, 7, C))

7. e(c(2, D)) & e(c(8, D))

8. X & e(f(6, 2), g(8, 1))

9. b(X, g(8, X)) & b(f(6, 2), g(8, f(6, 2)))

10.  a(1, b(X, Y)) & a(Y, b(2, c(6, Z), 10))

11.  d(c(1, 2, 1)) & d( c(X, Y, X))

4.  [25 points]  Escape from the Vault

Tokyo, Rio, Berlin and Denver have just looted the Museum of Modern Arts and need to cross the Kosciusko Bridge in order to reach a deserted runway where Professor Plock’s aeroplane is waiting for them.  However, the bridge is fragile and can hold at most two of them at the same time.   Moreover, to cross the bridge a flashlight is needed to avoid traps and broken parts. The problem is that there is only one flashlight with one battery that lasts for only 60 minutes.  Each of them need different times to cross the bridge (in either direction):

Since there can be only two people on the bridge at the same time, they cannot cross the bridge all at once. Since they need the flashlight to cross the bridge, whenever two have crossed the bridge, somebody has to go back and bring the flashlight to the people on the other side that still have to cross the bridge. The problem now is: In which order can the above four cross the bridge in time (that is, in 60 minutes) to be saved from getting caught? Being the mastermind of the heist, you need to find the answer to the above conundrum.  You could have solved the problem in your head,  had you not been day drinking. The only possible way for you now is to try all possible combinations.  Curiously, the alcohol seems to have no effect on your ability to write logically correct software.  So, you decide to write some Prolog rules to answer this.

Writing a Prolog program for solving the riddle is in principle a rather straightforward task  (using backtracking) once one has figured out how to formulate the solution. The most difficult part is to find an appropriate term representation for the states of the search problem, i.e., the position of people on either side of the bridge and the position of the flashlight.  We are going to develop one such idea here. Let us assume that initially, everyone is on the left side of the bridge and want to cross over to the right side. We represent intermediate states of a bridge crossing by facts of the form st(P,L) where L is a list giving the people that are currently on the left side of the bridge and where P is a flag that indicates the position (left or right side) of the flashlight.  We denote movement from left to right as the rule r(L1) where L1 is a list of people who move from left to right.  Similarly, we define l(L2) to denote movement from right to left.

1. Write a rule time(P,T) where T is the time taken by person P to cross the bridge (in either direction). 2. Write a fact team(T) where T is a list of all four people who need to cross the bridge.

3. Write a rule cost(L,C) where C is the maximum time required for all the people in list L to cross the bridge (in either direction), assuming that they all can cross the bridge simultaneously.

4. Write two rules move(st(l,L1),  st(r,L2),  r(M),  C)  and move(st(r,L1),  st(l,L2),  l(M), C), where:

. move(st(l,L1),  st(r,L2),  r(M),  C): This movement is generated if the flashlight is on the left side of the bridge.  C is the time required to move people contained in the list M from left to right, where st(l,L1) is the old state and st(r,L2) is the new state. In this case, the time is determined by the predicate cost/2.  The list M of people to move to the right is computed by the predicate split/3, which computes lists of length 2, which are sorted to avoid redundancy caused by representing groups of people as lists.  Implementation of split/3 is provided to you:

split(L,[X,Y],M)   :-

member(X,L),

member(Y,L),

compare(<,X,Y),

subtract(L,[X,Y],M) .

Here, M is the list after removing X and Y from the list L.

. move(st(r,L1),  st(l,L2),  l(M),  C): This movement is generated if the flashlight is on the right side of the bridge.  C is the time required to move people contained in the list M from right to left on the bridge, where st(r,L1) is the old state and st(l,L2) is the new state.  In this move, it makes sense to send back only one person.  Therefore, the definition of move for this case uses the predefined member/2 1  predicate and computes the time by simply looking into the rule time/2.

5.  Finally, the trans/4 predicate generates all possible bridge crossings together with the required time, i.e., write a rule trans(I,F,M,C) where C is the amount of time needed to reach the final state F from initial state I and M is the ordered list of movements(refer to the example below for a clear understanding).

The cross/2 predicate formulates the search problem by giving the initial and final configuration of the search space. The definition of cross/2 is as follows:

cross(M,D)   :-

team(T),

trans(st(l,T),st(r,[]),M,D0),

D0=<D .

The solution to the original problem is then given by:

solution(M)   :-  cross(M,60) .

There are two possible answers to the above problem. So, upon executing solution/1 the final output should be:

?-  solution(M) .

M  =  [r([rio,  tokyo]),  l(tokyo),  r([berlin,  denver]),  l(rio),  r([rio,  tokyo])]  ; M  =  [r([rio,  tokyo]),  l(rio),  r([berlin,  denver]),  l(tokyo),  r([rio,  tokyo])]  .

Note: The order of the above solutions does not matter.

In this problem, your goal is to implement a class FileAdder which prompts the user for a file name and then prints the sum of all the integers in the file.  Specifically, the input file will have multiple lines of input where each line can either be a proper integer or something which is not an integer.  You need to fix the issues in the above programs and then use the code to implement the class FileAdder.  The solution should be a single Java file with class FileAdder in it. The code structure shall look like:

public  class  FileAdder  {

public  static  int  adder(String[]  elements)  {

/*

TODO

Fix  the  code  in  the  main()  procedure  of  the  Adder  class

and  use  it  here

In  general,

1 .  Iterate  through  the  elements  array:

-  if  the  current  element  in  an  Integer,  add  it  to  the  total

-  otherwise  print  "Ignoring  bad  input:  <current  element>" on  standard  output

Here,  <current  element>  must  be  replaced  by  the  actual  element . 2 .  Return  the  total

*/

}

public  static  String[]  readFile()  {

/*

TODO

Fix  the  issues  in  the  code  present  in  the  echoFile()  procedure of  the  FileEchoer  class  and  use  it  here

In  general,

1 .  Prompt  the  user  for  a  filename

2 .  Once  you  have  the  filename,  do  the  following:

-  if  the  file  is  present,  read  all  the  lines of  the  file  into  a  String  array

-  otherwise,  print  "Error  --  File  <file  name>  not  found" on  the  standard  output .

Here,  <file  name>  must  be  replaced  by  the  actual  file  name . 3.  Return  the  String  array

*/

}

public  static  void  main(String[]  args)  {

String[]  fileContents  =  FileAdder.readFile();

int  total  =  FileAdder.adder(fileContents);

System.out.println("The  total  is  "  +  total);

}

}

Submit a single file FileAdder.java with the class structure as described above. If you are not able to come up with a correct solution or the code doesn’t compile, please add comments at the beginning of your Java file so that you receive partial credit.

Note:

.  The documentation of the two above mentioned exception can be found in the footnote, NumberFormatException2  and FileNotFoundException3 .

.  The length of String[] array will never be greater than 1000.

. Integers can be positive as well as negative. All the integers will be in the range [-1000, 1000].

6.  [15 points]  Virtual Functions [Wait until after the November 28 lecture before attempting.]

This problem examines the difference between two forms of object assignment. In C++, local variables are stored on the run-time stack, while dynamically allocated data (created using the new keyword) is stored on the heap.

class  Vehicle  {

public:

int  x;

virtual  void  f();

void  g();

};

class  Airplane   :  public  Vehicle  {

public:

int  y;

virtual  void  f();

virtual  void  h();

};

void  inHeap()  {

Vehicle  *b1  =  new  Vehicle;  //  Allocate  object  on  the  heap

Airplane  *d1  =  new  Airplane;  //  Allocate  object  on  the  heap

b1->x  =  1;

d1->x  =  2;

d1->y  =  3;

b1  =  d1;  //  Assign  derived  class  object  to  base  class  pointer }

void  onStack()  {

Vehicle  b2;  //  Local  object  on  the  stack

Airplane  d2;  //  Local  object  on  the  stack

b2.x  =  4;

d2.x  =  5;

d2.y  =  6;

b2  =  d2;  //  Assign  derived  class  object  to  base  class  variable }

int  main()  {

inHeap();

onStack();

}

Answer the following questions:

Note: In the questions below, vtable pointer refers to an object’s hidden vtable pointer.

1.  Draw a picture of the stack, heap and vtables just before b1=d1  is executed during the call to inHeap.   Be sure to indicate where the  instance  variables  and vtable  pointers of the two objects are stored, and to which vtable(s) the respective vtable  pointers point.

2.  Re-draw your diagram from (1), showing the changes that result just after the assignment b1=d1. Be sure to clearly indicate where b1’s vtable pointer points.  Explain why b1’s vtable pointer points where it does.

3.  Draw a picture of the stack, heap and vtables just before b2=d2  is executed during the call to onStack.  Be sure to indicate where the instance  variables and vtable  pointers of the two objects are stored, and to which vtables the respective vtable  pointers point.

4.  Re-draw your diagram from  (3), showing the changes that result after the assignment b2=d2.  Be sure to clearly indicate where b2’s vtable pointer points.  Explain why b2’s vtable pointer points where it does.

5. We have used the assignment statements b1=d1 and b2=d2. Why are the opposite statements d1=b1 and d2=b2 not allowed?