Homework Assignment 5

CS 2360
Winter 1997
Homework Assignment 5
Due no later than 8:00am, Monday, February 17, 1997

Renowned actress Tori Spelling is planning a big surprise for her daddy,
famous television producer Aaron Spelling.  Tori has saved up just
enough money to produce her own prime-time TV special, which will be
called "Aaron Spelling: A Retrospective".  To serve as co-hosts for the
special, Tori has called upon three other major stars from the Aaron
Spelling school of fine acting: Shannen Doherty ("Brenda" from "Beverly
Hills 90210"), Andrew Shue ("Billy" from "Melrose Place" and Tori's 
co-star on that show), and Jamie Luner ("Peyton" from "Savannah").  The
four of them have met for lunch at the posh Polo Lounge, and Tori has
convinced them all to sign contracts.  Now she has to get them across
town to a photographer's studio for some publicity photos, but she's
run into a problem.  The personal limo drivers for Shannen, Andrew, and 
Jamie are all on a break and nowhere to be found, taxis aren't 
omnipresent in Los Angeles like they are in most other cities, and Tori
came to the lunch in her two-seater BMW roadster.  It looks like Tori's
going to have to drive her new employees to the photo shoot, but she
can only drive one of them at a time.  As you might expect, Tori's not
about to let someone else drive her new BMW, so she's clearly going to
have to do all the driving.  And to make matters more complicated, she
doesn't dare leave some of the others alone at either the Polo Lounge or 
the photo studio.  Seems that Shannen can't stand Andrew and is likely 
to punch his lights out in Tori's absence, which will create some 
unwanted publicity.  Furthermore, Jamie hates Andrew too, and will 
likely clobber him if left alone with him.  So Tori doesn't dare leave 
Andrew alone with either Shannen or Jamie.  Fortunately, Jamie and 
Shannen tolerate each other, so there's no problem leaving them 
together, and everyone loves Tori, so nobody has a problem riding in the 
BMW with her.  But this is sooooo complicated!  What's a producer to do?

This is where you come to Tori's rescue.  Your job is to write a program
using Common LISP that will solve Tori's problem of getting the
hosts of her TV special from the restaurant to the photo studio in
her two-seater roadster within the constraints that Tori always drives
the roadster and Andrew is never left alone with either Shannen or
Jamie.  The program is to use a depth-first state-space search with
backtracking to find a solution to Ms. Spelling's dilemma.

The top-level function is to be called HELP-TORI and will take three 
arguments.  The first argument is the initial state of the problem, 
which might look like this:

  ((TORI SHANNEN JAMIE ANDREW)())

This list consists of two sublists.  The left sublist contains the names
of all the people who are at the Polo Lounge in this state (order is
unimportant).  The right sublist contains the names of all the people
who are at the photography studio in this state.  Note that while this
is the start state described in the story above, we might want to give
you a different start state, such as:

  ((SHANNEN JAMIE)(TORI ANDREW))

so be ready to accept any "legal" state description as an initial state.

The second argument is the goal state and has the same syntax as the
initial state.  Again, any "legal" state description is acceptable here.  
The goal state described in the story above looks like this (again, 
order of names is unimportant):

  (()(SHANNEN JAMIE TORI ANDREW))

The third argument is either nil or non-nil.  If the value is non-nil, 
your program should print to the terminal a trace of the sequence of 
states or moves being tried as the search progresses.  The trace should 
also point out where the program runs into a dead end and has to 
backtrack, as well as pointing out when the goal has been reached.  If 
the second argument is nil, no trace should be printed.  (You'll want to 
look up some of the print I/O stuff in some Common LISP book to make 
this pretty.  What the trace actually looks like is more or less up to
you, but it should be somehow informative to Dan, who is your grader
for this assignment, and who is therefore the final authority on what
exactly should be turned in.)

When the goal has been reached, HELP-TORI should terminate and return 
a list of successive states that constitutes the path from the 
initial state to the goal state.  So, if Dan invokes HELP-TORI in 
this way:

  (help-tori '((TORI SHANNEN JAMIE ANDREW)())
             '(()(TORI SHANNEN JAMIE ANDREW))
             nil)

your program should return something like:

( ((TORI SHANNEN JAMIE ANDREW) NIL)
  ((SHANNEN JAMIE) (TORI ANDREW))
  ((TORI SHANNEN JAMIE) (ANDREW))
  ((SHANNEN) (TORI JAMIE ANDREW))
  ((TORI SHANNEN ANDREW) (JAMIE))
  ((ANDREW) (TORI SHANNEN JAMIE))
  ((TORI ANDREW) (SHANNEN JAMIE))
  (NIL (TORI ANDREW SHANNEN JAMIE)) )

(I've made this list more readable than what will be returned by
HELP-TORI, but you shouldn't try to format what is returned.  On
the other hand, feel free to format the printed output of your
trace function(s).)

Your program may find a different path because your program may apply 
its operators in a different order than my hypothetical version of 
this program does.  If your program never finds the goal, it should
merely return NIL.

Follow the same guidelines that we've used in the past:  lots of
well-abstracted, well-named, cohesive, and readable functions, but no 
global variables, no assignment, and none of those traditional 
looping constructs that we haven't talked about yet---in short, 
no side effects (except for printing).

As I mentioned in class, this has the potential to require less
code than you might think at first, if you let LISP do the bulk of
the work for you.  Think before you code.  And remember, you can
never watch too much television.



Copyright 1997 by Kurt Eiselt.  All rights reserved.