CS 232 Assignment 1 Due: Tuesday, Sept. 19

Problem 1: Missionaries and Cannibals (30 points)

In his book, Artificial Intelligence, Patrick Winston stresses that good representations are the key to good problem solving. This problem is borrowed from Winston's book and illustrates this principle. Consider the following puzzle:

Missionaries and Cannibals
Three missionaries and three cannibals are standing on the west bank of a river. A boat is available that will hold either one or two people. If the missionaries are ever outnumbered on either bank, the cannibals will eat them. Determine a sequence of trips that will get everyone across the river to the east bank.

This exercise becomes simple to solve once you have the right representation. Consider the pictorial representation shown below:

Nodes in the picture indicate the number of missionaries and cannibals on the west bank. The solid-line arrow indicates a trip from the west bank to the east bank, and the dotted-line arrow indicates a trip from east to west. In the above example, the node in the upper right corner represents the starting state for the problem. A trip with two cannibals from west to east is followed by a trip with one cannibal from east to west. Because west-to-east and east-to-west trips must alternate, any valid sequence of trips must consist of alternating solid-line arrows and dotted-line arrows.

Part a: On the representation above, first identify (fill in) all nodes that represent safe states, in which the missionaries are not in danger of being eaten. Then find a path that takes you through the safe states and also satisfies the constraint on the number of passengers in the boat during each river crossing. This path represents a solution to the problem.

Part b: In our introduction to search, it was shown that the problem of searching for the solution to a problem can often be visualized using a search tree that captures the possible states of the problem solution (in the nodes of the tree) and transitions between these states (as the branches of the tree). For the missionaries and cannibals problem, construct a search tree that includes all possible paths toward a solution. The tree should include all the dead-end paths as well as successful solution paths, and should not contain any loops (repetition of the same state along a single path). Write information in each node that captures all the essential information about the state of the problem solution at that moment, and only include nodes that represent valid states. Each branch in the tree should represent a valid river crossing - label each of the branches with the passengers in the boat during the crossing. When you have drawn a complete search tree, answer the following questions:

1. Suppose you want to use a blind search method to find a solution, either depth-first or breadth-first search. Which search method would be more efficient, given the structure of the tree (i.e. which method would need to explore fewer nodes before reaching a goal)?
2. How many valid sequences of boat crossings exist to solve this problem? Consider two sequences to be different if there is at least one step in the process that differs between them.
3. Examine the contents of nodes in different parts of the tree. Suppose you decide to use breadth-first search to solve this problem. What information could you record as you proceed with the search that could help to make the search more efficient (i.e. could reduce the number of partial paths that need to be expanded)?

Part c: Indicate whether the following statements are true or false, and explain why:

1. The amount of search conducted by a branch-and-bound search using underestimates of the distance remaining to the goal is independent of the accuracy of the distance estimate, provided it is still an underestimate.
2. Best-first search is guaranteed to find an optimal path (i.e. shortest or lowest cost path) if one exists.
3. In branch-and-bound search using underestimates of the distance remaining to the goal, the first path encountered that contains the goal node is guaranteed to be the shortest possible path to the goal.

Problem 2: Generating Madlibs (30 points)

Madlibs are partial stories that are completed by filling in random words that are provided by someone who is unaware of the partial story. For example, I could ask you to provide an adjective, noun, verb, another adjective, and a place. You might say "creepy", "elephant", "jump", "silly" and "dorm". If I started with the following (very short) madlib:

   Once upon a time there was a adjective noun
   who liked to verb in a adjective place

then your words would create the following completed story:

   Once upon a time there was a creepy elephant
   who liked to jump in a silly dorm

The story doesn't make much sense, but that's the fun of madlibs! In this problem, you will write some LISP functions to create madlibs. To begin, copy the file ~cs232/download/assign1.lisp to your directory. This file contains one top-level function named madlibs:

(defun madlibs ()
   (print (fill-madlib
            '(Once upon a time there lived a adjective noun)))
   (print (fill-madlib
            '(who liked to verb in a adjective place)))
   (print "THE END"))

Your goal is to complete the definition of the function fill-madlib that has a single input list and which returns a new list in which words like adjective, noun, verb and place, are replaced by a random word of the particular type. Before completing the fill-madlib function, first define the following helper functions:

• Define a function named select that has a single input that is a list of words, and which returns a single word that is selected randomly from the input list. For example, the function call (select '(red white blue)) should return either RED, WHITE or BLUE. The built-in random function can be used to generate a random location in the list. random has a single input integer, n, and returns a random integer between 0 and n-1. For example, (random 10) returns a random integer between 0 and 9. In your definition of select, use nested function calls so that the body of the definition consists of a single LISP expression.
• Define functions named adjective, noun, verb and place that have no inputs, and which return a random word of the given type. For example, the function call (adjective) should return a random adjective. The definitions of these functions should use the select function and include a list of specific words of your choosing.

Once these helper functions are implemented and tested, you can then define the fill-madlib function described above. You should define the fill-madlib function using recursion. Hint: Consider the new-replace function defined in Common LISP Lab #2. When you are done with fill-madlib, define a function to create your own madlib story (you can just modify the existing madlibs function). All of your functions should be placed inside the assign1.lisp code file. Place a comment either before or inside each function that briefly describes what it does.

When you have completed the code for this problem, submit your code electronically by connecting to the subdirectory containing your assign1.lisp code file, and executing the following command in Unix:

submit cs232 madlibs assign1.lisp

You should also hand in a hardcopy of your assign1.lisp code file.

Problem 3: Lab #1 and Lab #2 Exercises (40 points)

Complete Exercises 1-3 from Labs #1 and #2. Your solution code can be placed directly into the lab1.lisp and lab2.lisp files. Drop off an electronic copy of each file by connecting to the subdirectory that contains your completed lab1.lisp and lab2.lisp, and executing the following Unix commands:

submit cs232 lab1 lab1.lisp

submit cs232 lab2 lab2.lisp

Also hand in a hardcopy of your lab1.lisp and lab2.lisp code files.