handout #14

CS372—Comparative Programming Languages

Prolog Programming Assignment #4

due 3 pm Friday, September 26th

For this assignment you are to implement a prolog predicate that finds combinations of words that constitute an anagram of other words.  For example, consider the phrase “george w bush”.  A legal anagram of this phrase would have to include exactly the same letters (2 g’s, 2 e’s, 1 o, etc), but they could be arranged in a different order to form words.  For example, legal anagrams include “brew goes hug” and “brush egg woe”.

To solve this problem, you will need access to a dictionary of words.  We might want to run the anagram predicate with different dictionaries, so the dictionary will appear in its own file and will be loaded separately.  There are 3 different dictionaries called dict1.pl (around 50 words, for testing purposes), dict2.pl (around 4 thousand words) and dict3.pl (around 20 thousand words).

We are providing you with a set of utility predicates in a file called hw4.pl.  Included are the utilities member, append and remove, all of which Stuart used in his solution to this problem.  Also included is a predicate called anagram that takes 0 arguments that interacts with the user, prompting for a phrase and a maximum number of words to include in the answer and showing all valid answers.  See the sample log of execution at the end of this document to see how to use this predicate.

You are to implement a 4-argument version of anagram.  Prolog isn’t confused by the fact that there is also a 0-argument version of this predicate.  Your 4-argument predicate anagram(L, N, D, R) takes 3 input values (an instiated list of atoms in L, an instantiated integer in N and an instantiated list of words in D) and computes an output value R.  The list L will contain the phrase to work with (e.g, [george, w, bush]).  The value N indicates the maximum number of words to allow in the answer (notice that this is a maximum—it’s okay to produce an answer with fewer words).  The value D is the dictionary to use in solving the problem (a list of word atoms).  R should be set to a list of the words in the answer (e.g., [brew,goes,hug] or [brush,egg,woe]).  Your predicate should produce each possible answer exactly once.  Notice that the order of words within the answer matters, so [brew,goes,hug] and [hug,goes,brew] are different answers.  It doesn’t matter what order you produce the various answers as long as you produce each answer exactly once.

You will obviously want to write some helper predicates in addition to the 4-argument anagram predicate.  You will also want to use the built-in name predicate that converts an atom into a list of letters.

If you find yourself writing predicates to count the occurrences of various letters in the original phrase or to find all permutations of the letters in the original phrase, then you are probably on the wrong track and might end up with something that is extremely inefficient.  Only a small number of words from the dictionary will be relevant to any given anagram problem.  Think in terms of how you would know that a given word from the dictionary is relevant to the current problem.

You can copy the various dictionary files and the file hw4.pl from the class directory by giving the following commands on lectura:

cp /home/cs372/fall03/dict* .
cp /home/cs372/fall03/hw4.pl .

You should turn in your solution using turnin with the identifier 372prolog4.

Log of Execution

> prolog

SICStus 3.8.4 (sparc-solaris-5.6): Mon Jun 12 18:49:23 MET DST 2000

Licensed to cs.arizona.edu

| ?- [anagram, dict1].

{consulting /home/reges/372/fall03/anagram.pl...}

{consulted /home/reges/372/fall03/anagram.pl in module user, 0 msec 3480 bytes}

{consulting /home/reges/372/fall03/dict1.pl...}

{consulted /home/reges/372/fall03/dict1.pl in module user, 0 msec 1912 bytes}

 

yes

| ?- anagram.

Phrase to scramble (as a list of atoms)? [laura, bush].

Max words in result? 3.

[aura,blush]

[blush,aura]

 

no

| ?- anagram.

Phrase to scramble (as a list of atoms)? [barbara, bush].

Max words in result? 3.

[abash,bar,rub]

[abash,rub,bar]

[bar,abash,rub]

[bar,rub,abash]

[rub,abash,bar]

[rub,bar,abash]

 

no

| ?- anagram.

Phrase to scramble (as a list of atoms)? [george, w, bush].

Max words in result? 2.

 

no

| ?- anagram.

Phrase to scramble (as a list of atoms)? [george, h, bush].

Max words in result? 2.

 

no

| ?- anagram.

Phrase to scramble (as a list of atoms)? [george, h, w, bush].

Max words in result? 3.

[beg,gush,whore]

[beg,whore,gush]

[bough,grew,she]

[bough,she,grew]

[grew,bough,she]

[grew,she,bough]

[gush,beg,whore]

[gush,whore,beg]

[she,bough,grew]

[she,grew,bough]

[whore,beg,gush]

[whore,gush,beg]

 

no