Hand in: email your solution (as a plain text file) to barak+cs351@cs.nuim.ie

Due: 09:00 on Mon 10-Dec-2007.

Teamwork is encouraged. Please work in teams of up to three (3) people. Just turn in one (1) solution set, with the entire team listed at the top, sorted by how much each person contributed. (The order will not affect grades; it will be used only for my own consistency checking of scores at the end of the course.)

NUIM/CS351 Assignment 5

Fun with Prolog

1. Simple list processing

   Implement the relations

   1. noah, which bundles element from a list two-by-two, as in noah([a,b,c,d,e,f,g,h],[[a,b],[c,d],[e,f],[g,h]]).

   2. hack_hunks, which is true when its first argument, a list, is the concatenation of the elements of its second argument, a list of lists all of which are the same length. So for instance,

        ?- hack_hunks([a,b,c,d,e,f,g,h],[[a],[b],[c],[d],[e],[f],[g],[h]]).
        yes
      
        ?- hack_hunks([a,b,c,d,e,f,g,h],[[a,b],[c,d],[e,f],[g,h]]).
        yes
      
        ?- hack_hunks([a,b,c,d,e,f,g,h,i],[[a,b,c],[d,e,f],[g,h,i]]).
        yes
      
        ?- hack_hunks([a,b,c,d,e,f,g,h,i],[[a,b,c],X,[g,h,i]]).
        X=[d,e,f]
      

   3. perm, which is true if its first argument and second argument, both lists, are permutations of each other.

        ?- perm([a,b,c],[b,c,a]).
        yes
      
        ?- perm([a,b,c],X).
        %% hit 'a' to see all solutions; the order here is arbitrary:
        X=[a,b,c].
        X=[a,c,b].
        X=[b,a,c].
        X=[b,c,a].
        X=[c,a,b].
        X=[c,b,a].
      

2. Solve a puzzle

   Consider the following game. You have a string of x's and o's, which we represent as a list, e.g., [o,x,o,x,x,o,o]. The objective is to eliminate all but one x. You can do this by making jumps, meaning an x can jump over an adjacent x provided there is an o on the other side, and in the process the spot it vacated and the x it jumped over both become o. So for instance, in one such move, the above list can be converted to [o,x,o,o,o,x,o].

   Define one_move which is true when, of its two arguments, the second is a legal result of making ONE such move starting with the first argument. Eg,

     ?- one_move([o,x,o,x,x,o,o],R).
     %% hit 'a' to see all solutions; the order here is arbitrary:
     R=[o,x,o,o,o,x,o]
     R=[o,x,x,o,o,o,o]
   

   Define move_seq which is true when given a list of positions each of which consists of a legal move from the previous position. Eg,

     ?- move_seq([[o,x,o,x,x,o,o],[o,x,x,o,o,o,o],[x,o,o,o,o,o,o]]).
     true
   
     ?- move_seq([[o,x,o,x,x,o,o],M1,[x|M2]]).
     M1=[o,x,x,o,o,o,o]
     M2=[o,o,o,o,o,o]
   

   Use this machinery to generate a puzzle that is soluble in ten moves. (By running things "backwards" from a solution.)

   Use this machinery to solve this puzzle from a nontrivial starting position of your own devising.

3. Computer comedy

   (Inspired by the MADLIB toy.)

   Define a predicate funny which is true when it is given a grammatical but funny (according to your own limited idiosyncratic tastes) English sentence, represented as a list of words. For instance, if you have the sense of humour of a three-year-old, funny([my,little,sister,is,a,poopy,head]). You should be able to run it in generative mode, so funny(X) will spit out a succession of hilarious sentences, of gradually increasing length.

   This is meant to allow you to both do some parsing and have some fun. On the parsing side, you should define sub-predicates to generate a noun phrase, a verb phrase, and prepositional phrase, etc, in turn defined using sub-predicates for verbs, nouns, adjectives, articles, etc, so that this will generate a variety of grammatical sentences. By appropriate choice of vocabulary at the bottom of this system, you can get incongruous but amusing juxtapositions.