From: Ruby Quiz <james@...>
Date: 2006-10-05T22:09:23+09:00
Subject: [SUMMARY] Story Generator (#96)

The solutions to this quiz where wildly creative, both in form and output.  I'm
still having nightmares about poor Little Red-Cap and Princess Lily.

The chief element of all the solutions was randomness.  Jim Menard and Morton
Goldberg took game engines (already a bit random) and added an autoplay mode to
drain stories out of them.  Myself and Jordan randomized sentence construction
to varying degrees and slung together a mess of invented lines.  The other
solutions narrowed their tale telling focus to a specific genre and randomized
the story elements themselves.  The end results were quite varied and certainly
entertaining!

I really wish we could go through all of those solutions and talk about the
unique approach of each one.  This week, even more than usual, each idea was
quite unique.  Unfortunately time and space demand that I pick one.  Do look the
others over though, so you can learn from the clever people who played with the
quiz.

Below I'm going to discuss the code from Boris Prinz.  Boris took the randomized
story elements approach and ended up with a pretty flexible system.  On top of
that, the code is just plain cool and worth a look.  Before we dive in though,
here's a story produced by a sample run of Boris's code:

	Once upon a time little red-cap met the huntsman although the huntsman lived
	in the village. Then the wolf was delighted. Then he took a piece of cake.
	Grandmother snored very loud, but little red-cap swallowed up grandmother,
	and the huntsman saw a bottle of wine. Later he snored very loud. The wolf
	was not afraid of little red-cap although he got deeper and deeper into
	grandmother's house. Little red-cap opened the stomach of mother. She ran 
	straight to grandmother's house. Little red-cap saw a bottle of wine. The
	huntsman ran straight to grandmother's house. Soon the wolf was delighted. 
	The huntsman walked for a short time by the side of grandmother.
	The End.

Alright, let's see how the misadventures of Little Red-Cap get constructed. 
Here's the beginning of the code:

	class Base
	  def self.constructor *args
	    attr_accessor(*args)
	    define_method :initialize do |*values|
	      (0...args.size).each do |i|
	        self.instance_variable_set("@#{args[i]}", values[i])
	      end
	    end
	  end
	  def to_s
	    @name
	  end
	end

Boris decided to take a metaprogramming approach to the large amount of classes
that would need to be built.  The first step was to simplify the building of
constructors for the classes, with a class method that rolls an initialize()
plus some accessors for you.  This is pretty close to redefining Ruby's Struct
class and it may be possible to use that instead, though the addition of the
to_s() to pull the name attribute complicates this slightly.

Let's see how this class method gets used:

	class Character < Base
	  constructor :name, :gender
	end
	
	class Action < Base
	  constructor :name, :objects_or_types
	end
	
	class Item < Base
	  constructor :name
	end
	
	class Place < Base
	  constructor :name
	end

	class Bridge < Base
	  constructor :name
	end

Here we see classes for the story elements being assembled.  All of these
examples have the name element used by to_s() and Character and Action define
additional elements for those types.

Remember all the work being done by this simple call.  In the case of Character
for example, a constructor is built to accept and set the two parameters and
name(), name=(), gender(), and gender=() are defined as instance methods of the
class.

The next class forms a new base type for some sentence construction elements:

	class PronounBase < Base
	  constructor :gender
	  class << self
	    attr_accessor :cases
	  end
	  def to_s
	    cases = self.class.cases
	    @gender == :female ? cases[0] : cases[1]
	  end
	end

With pronouns the code needs to worry about the gender of the referred to
Character.  To support this a class level attribute is defined that can hold
both cases (female and male) and to_s() is modified to make the right choice
based on the assigned gender.

Now we can examine the extended family of this class:

	class PossessiveAdjective < PronounBase
	  self.cases = ['her', 'his']
	end
	
	class Pronoun < PronounBase
	  self.cases = ['she', 'he']
	end
	
	class ReflexivePronoun < PronounBase
	  self.cases = ['herself', 'himself']
	end

Boris takes another metaprogramming step to help with the construction, storage,
and selection of these entities:

	class Entities
	  def initialize klass
	    @entities = []
	    @klass  = klass
	    yield(self)
	  end
	  def create *args
	    @entities << @klass.new(*args)
	  end
	  def pick
	    @entities[rand(@entities.size)]
	  end
	end

This class is an object container.  You tell it the kind of objects you will
store in it at construction time.  After that, you can use create() to construct
an object of the indicated type and add it to the collection.  When needed,
pick() returns a random object from the collection.

Here's the code that populates the containers for the Little Red-Cap story
world:

	CAST = Entities.new(Character) do |c|
	  c.create 'little red-cap', :female
	  c.create 'mother',         :female
	  c.create 'grandmother',    :female
	  c.create 'the wolf',       :male
	  c.create 'the huntsman',   :male
	end
	
	ACTIONS = Entities.new(Action) do |a|
	  a.create 'met', [Character]
	  a.create 'gave', [Item, 'to', Character]
	  a.create 'took', [Item]
	  a.create 'ate', [Item]
	  a.create 'saw', [Item]
	  a.create 'told', [Character, 'to be careful']
	  a.create 'lived in', [Place]
	  a.create 'lied in', [Place]
	  a.create 'went into', [Place]
	  a.create 'ran straight to', [Place]
	  a.create 'raised', [PossessiveAdjective, 'eyes']
	  a.create 'was on', [PossessiveAdjective, 'guard']
	  a.create 'thought to', [ ReflexivePronoun,
	                           '"what a tender young creature"' ]
	  a.create 'swallowed up', [Character]
	  a.create 'opened the stomach of', [Character]
	  a.create 'looked very strange', []
	  a.create 'was delighted', []
	  a.create 'fell asleep', []
	  a.create 'snored very loud', []
	  a.create 'said: "oh,', [Character, ', what big ears you have"']
	  a.create 'was not afraid of', [Character]
	  a.create 'walked for a short time by the side of', [Character]
	  a.create 'got deeper and deeper into', [Place]
	end
	
	ITEMS = Entities.new(Item) do |i|
	  i.create 'a piece of cake'
	  i.create 'a bottle of wine'
	  i.create 'pretty flowers'
	  i.create 'a pair of scissors'
	end
	
	PLACES = Entities.new(Place) do |p|
	  p.create 'the wood'
	  p.create 'the village'
	  p.create 'bed'
	  p.create "grandmother's house"
	  p.create 'the room'
	end
	
	BRIDGES = Entities.new(Bridge) do |b|
	  5.times{b.create '.'}
	  b.create ', because'
	  b.create ', while'
	  b.create '. Later'
	  b.create '. Then'
	  b.create '. The next day'
	  b.create '. And so'
	  b.create ', but'
	  b.create '. Soon'
	  b.create ', and'
	  b.create ' until'
	  b.create ' although'
	end
	
	ALL = { Character => CAST,   Action => ACTIONS,
	        Place     => PLACES, Item   => ITEMS }

I know that's a lot of code, but you can see that it's really just object
construction in groups.  There are two points of interest in the above code,
however.

First note that we begin to get hints of sentence structure where the ACTIONS
are constructed.  The second parameter for those seems to be a mapping of the
elements and joining phrases that come after the action.  We will see how that
comes together shortly now.

Also of interest is the simple but effective first line of BRIDGES construction.
By adding the ordinary period five times, the scale is tilted so that it will
randomly be selected more often.  This gives the final text a more natural flow.

Here's the class that turns all of those simple lists into sentences:

	class Sentence
	  attr_accessor :subject
	  def initialize
	    @subject = CAST.pick
	    @verb    = ACTIONS.pick
	    @objects = []
	    @verb.objects_or_types.each do |obj_or_type|
	      if String === obj_or_type
	        @objects << obj_or_type
	      else
	        if obj_or_type == PossessiveAdjective or
	           obj_or_type == ReflexivePronoun
	          @objects << obj_or_type.new(@subject.gender)
	        else
	          thingy = ALL[obj_or_type].pick
	          if thingy == @subject
	            thingy = ReflexivePronoun.new(thingy.gender)
	          end
	          @objects << thingy
	        end
	      end
	    end
	  end
	
	  def to_s
	    [@subject, @verb, @objects].flatten.map{|e| e.to_s}.join(' ')
	  end
	end

The constructor does the heavy lifting here.  First a subject and verb are
selected from the appropriate lists.  The rest of the method turns the sentence
patterns we examined earlier into an actual list of objects.  Strings are just
added to the list, PossessiveAdjectives and ReflexivePronouns are constructed
based on the gender of the subject, and everything else is a random pick from
the indicated list but swapped with a pronoun if the subject comes up again. 
With the sentence pieces tucked away in instance variables, to_s() can just
flatten() and join() the list to produce a final output.  (The call to map() is
not needed since join() automatically stringifies the elements.)

We only need one more class to turn those sentences into a complete story. 
Here's the code:

	require 'enumerator'
	
	class Story
	  def initialize
	    @sentences = []
	    1.upto(rand(10)+10) do
	      @sentences << Sentence.new
	    end
	    combine_subjects
	  end
	
	  # When the last sentence had the same subject, replace subject with
	  # 'he' or 'she':
	  def combine_subjects
	    @sentences.each_cons(2) do |s1, s2|
	      if s1.subject == s2.subject
	        s2.subject = Pronoun.new(s1.subject.gender)
	      end
	    end
	  end
	
	  # Combine sentences to a story:
	  def to_s
	    text = 'Once upon a time ' + @sentences[0].to_s
	    @sentences[1..-1].each do |sentence|
	      bridge = BRIDGES.pick.to_s
	      text += bridge + ' ' +
	              ( bridge[-1,1] == '.' ? sentence.to_s.capitalize :
	                                      sentence.to_s )
	    end
	    text.gsub!(/ ,/, ',') # a little clean-up
	    text.gsub!(/(.{70,80}) /, "\\1\n")
	    text + ".\nThe End.\n"
	  end
	end
	
	puts Story.new.to_s

Here the constructor creates a random number of sentences (between 10 and 19)
and modifies them if needed with a call to combine_subjects().  The comment
gives you the scoop on that one, which just replaces the second of two
consecutive subjects with a pronoun.

Finally, to_s() produces the end result.  The first sentence is combined with
the immortal opening "Once upon a time" to get us started.  After that, each
sentence is joined to the story using one of the BRIDGES we saw in the entity
construction, careful to maintain proper capitalization for the added sentence. 
A few Regexps are used to tidy up and and the story closed with "The End."

You can see in the final line of the program is all it takes to produce a
solution.  A Story is constructed, stringified, and printed to the screen. 
(Again the call to to_s() is not required, since puts() will handle this for
you.)

Once upon a time a band of seven Rubyists discovered the mysterious Ruby Quiz. 
Together they unlocked its mysterious and enlightened the entire realm of
programmers.  The quizmaster was eternally grateful for their efforts and shared
knowledge.  The end.

Tomorrow we will continue our word games, but turn our focus to Posix commands
instead of using a normal dictionary...