CS 2360
Winter 1998
Homework Assignment 5
Due no later than 8:00am, Monday, February 23, 1998
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 (formerly "Brenda"
from "Beverly Hills 90210"), Andrew Shue ("Billy" from "Melrose Place"
and Tori's co-star on that show), and Jamie Luner (formerly "Peyton"
from "Savannah" and now waiting to be killed off on "90210"). 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 Z3 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 four
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 a list of pairs of people who can't stand to
be with each other, such as:
((SHANNEN ANDREW)(ANDREW JAMIE))
The fourth 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 the TAs.
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 we invoke HELP-TORI in
this way:
(help-tori '((TORI SHANNEN JAMIE ANDREW)())
'(()(TORI SHANNEN JAMIE ANDREW))
'((ANDREW SHANNEN)(ANDREW JAMIE))
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. Oh, keep in mind that not only can people ride
from the Polo Lounge to the photo studio with Tori, but they can also
ride from the studio to the Polo Lounge.
You'll want to write your program to be general enough that we can
add more people to the puzzle, along with more or different pairs
of people who can't be left alone together. The only constants
here that you can count on are (1) Tori is always the driver of
the BMW and (2) the car will always have only two seats.
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,
stay within the functional programming paradigm and use no side
effects (except for printing).
This program 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 1998 by Kurt Eiselt. All rights reserved.
Last revised: February 18, 1998