From: Ruby Quiz <james@...>
Date: 2005-05-19T23:16:10+09:00
Subject: [SUMMARY] Cows and Bulls (#32)

This game isn't much of a challenge to implement, but it's plenty hard enough to
actually play.  I don't even want to tell you how many guesses it took me to
figure out the simple word "yes", while testing my solution.  Worse, it had me
so shaken by that point all it had to say was, "I'm thinking of an 11 letter
word." to send me straight to Control-C!  I don't think so.

The solutions are interesting as usual.  Brian Schroeder was the only one who
tried an AI player and it's a pretty basic implementation.  It just randomly
guesses groups of letters, ruling out letters it knows don't work (0 cows and 0
bulls), until it gets pretty lucky and nails the word.  Brian also used the
readline library for his client, which is a very nice feature.  Take a look if
you haven't seen that used before.  (I hadn't.)  You can find both of the above
highlights in Brian's cows-and-bulls-client.rb file.

Ilmari Heikkinen's code was simple and easy to follow.  Might want to glance in
there if need to see an example of basic socket usage.  (Both Ilmari and Brian
rolled their own client and server code.)

I'll look into my code below this time.  I was pretty lazy and cheated
everywhere I could, so that should make it easy to summarize.  (Further
reinforcing that I really am lazy!)

Let's start with my cowsnbulls library:

	#!/usr/local/bin/ruby -w

	class WordGame
		DICTIONARY = %w{cow moon}
		
		def self.load_dictionary( file_name )
			DICTIONARY.clear
			
			File.foreach(file_name) do |line|
				line.downcase!
				line.gsub!(/[^a-z]/, "")
				
				next if line.empty?
				
				DICTIONARY << line
			end
			DICTIONARY.uniq!
		end
		
		# ...

The first thing any good word game needs is a dictionary and you can see my
version here.  Initially, I just assigned "cow" and "moon" for testing purposes
(unit tests not shown).  Then I added the class method load_dictionary() for
providing a real dictionary.  Technically, this method reassigns a constant,
which may feel wrong to some of you, but it's really just intended for the
initial load.  You can see that it's a line-by-line read and I downcase() and
remove any non-letter characters.  Because that process could create duplicates,
I end with a call to uniq!().

		# ...
		
		def initialize( size = nil )
			@word = nil

			if size
				count = 0
				DICTIONARY.each do |word|
					if word.size == size
						count += 1
						@word = word if rand(count) == 0
					end
				end
			end
		
			@word = DICTIONARY[rand(DICTIONARY.size)] if @word.nil?
		end

		attr_accessor :word
		
		# ...

The only goal of initialize() is to pick the word for the game.  The only time
that's at all tricky, is when we are given a size preference.  I could have made
that section shorter with a call to find_all() and a random pick from the
resulting set, but I decided to be clever and do all the work with a single walk
of the dictionary.  To do that, I adapted the popular "read a random line from a
file" algorithm.  I just count the correct sized words passed and replace my
word choice whenever rand(count) == 0.  That assures that the first correctly
sized word is replaced 100% of the time, the second 50%, the third 33.33%, etc. 
That gives us a fair random pick, only walking the list once.  The final line of
the method is our fall back plan (random pick), if a size was not given or
found.

I didn't originally have the accessor for word and it's not used in any code
I'll show today.  Unfortunately, it was a necessary evil for my Web interface
(not shown).

Let's get to the actual game code:

		# ...
		
		def guess( word )
			answer = @word.dup
			word   = word.downcase.gsub(/[^a-z]/, "")
			
			return true if word == answer

			bulls = 0
			word.scan(/[a-z]/).each_with_index do |char, index|
				break if index == answer.size
				if char == answer[index, 1]
					word[index, 1] = answer[index, 1] = "."
					bulls += 1
				end
			end
			
			cows = 0
			word.scan(/[a-z]/).each do |char|
				if index = answer.index(char)
					answer[index, 1] = "."
					cows += 1
				end
			end
			
			return cows, bulls
		end
		
		def word_length(  )
			@word.length
		end
	end

The guess() methods is really the entire game.  It starts by making a duplicate
of the answer word, so it's free to damage it, and normalizing the provided
guess word, same as I did with the dictionary words.  If they're the same at
that point, we return true to indicate a win.  Otherwise, we return a two
element Array containing a count of "cows" and "bulls".

Bulls are counted simply by looking for like characters at each index.  When
found, we set that index to a nonsense character (".") in both guess and answer,
to keep them from affecting our count of cows.  That count again scan()s the
guess word letter-by-letter, but this time index() is used to find a match in
the answer, allowing it to occur anywhere.  Again, the answer location is set to
a nonsense character, in case the same letter occurs more than once.

The word_length() method just returns the length of the selected word, as
expected.

We'll skip the rest of the code in that file.  All it does it to create a
command-line interface, when the library is executed.  That doesn't have
anything to do with the quiz solution and it's not as cool as Brian's readline
enhanced version, so look there instead.

Here is my actual solution, the server:

	#!/usr/local/bin/ruby -w

	require "gserver"
	require "cowsnbulls"
	require "optparse"

	class TelnetServer < GServer
		def self.handle_telnet( line, io )          # minimal Telnet
			line.gsub!(/([^\015])\012/, "\\1")      # ignore bare LFs
			line.gsub!(/\015\0/, "")                # ignore bare CRs
			line.gsub!(/\0/, "")                    # ignore bare NULs

			while line.index("\377")                # parse Telnet codes
				if line.sub!(/(^|[^\377])\377[\375\376](.)/, "\\1")
					# answer DOs and DON'Ts with WON'Ts
					io.print "\377\374#{$2}"
				elsif line.sub!(/(^|[^\377])\377[\373\374](.)/, "\\1")
					# answer WILLs and WON'Ts with DON'Ts
					io.print "\377\376#{$2}"
				elsif line.sub!(/(^|[^\377])\377\366/, "\\1")
					# answer "Are You There" codes
					io.puts "Still here, yes."
				elsif line.sub!(/(^|[^\377])\377\364/, "\\1")
					# do nothing - ignore IP Telnet codes
				elsif line.sub!(/(^|[^\377])\377[^\377]/, "\\1")
					# do nothing - ignore other Telnet codes
				elsif line.sub!(/\377\377/, "\377")
					# do nothing - handle escapes
				end
			end
			
			line
		end
		
		# ...

You can see that I require Ruby's standard gserver in this code and that my
TelnetServer inherits from GServer.  More on that in a bit.

The rest of that chunk code is just an ugly method filled with a bunch of calls
to gsub!().  I'm not much of a fan of using custom protocols when it can be
avoided, so my server is meant to talk to simple Telnet clients.  (You can
usually get away with using Telnet without any fancy coding, but this is a
minimal handler for Telnet codes.)  The method just cleanses the passed line of
Telnet codes, responding to them as needed.  It tells the Telnet client that we
aren't capable of any special features and ignores everything else.  That's as
basic as Telnet can be.

		# ...
		
		def initialize( port = 61676, *args )
			super(port, *args)
		end
		
		def serve( io )
			game = WordGame.new
			io.puts "I'm thinking of a #{game.word_length} word."
			loop do
				io.print "Your guess?  "
				try = self.class.handle_telnet(io.gets, io)
				
				results = game.guess(try)
				if results == true
					io.puts "That's right!"
					
					io.print "Play again?  "
					if self.class.handle_telnet(io.gets[0], io) == ?y
						game = WordGame.new
						io.puts "I'm thinking of a " +
						        "#{game.word_length} letter word."
					else
						break
					end
				else
					cows = if results.first == 1
						"1 Cow"
					else
						"#{results.first} Cows"
					end
					bulls = if results.last == 1
						"1 Bull"
					else
						"#{results.last} Bulls"
					end
					io.puts "#{cows} and #{bulls}"
				end
			end
		end
	end
	
	# ...

Back to GServer.  Using it is a simple two-step process.  First, you need to
initialize() the server and you can see that I do that here, just by setting a
port to listen on.  The only other step is to override serve(), to handle
individual connections.

As you can see, serve() gets passed an io object, that can be read from and
written to as needed.  My implementation is basically just a command-line
program using io instead of STDIN and STDOUT.  I do filter all input through
handle_telnet() to catch the codes, of course.  I tell the player the size of
the word, loop over their answers until they get it right, offer them a new
game, and end when they've had enough.  Notice that I don't need to worry about
threading in here.  GServer takes care of that for me.  When serve() returns,
the connection will be terminated.

GServer is great for these simple networking tasks.  It's not up to the
challenges of bigger server projects, but it's nice when the job is easy.

Here's the final bit of code:

	# ...
	
	listen_port = 61676
	ARGV.options do |opts|
		opts.banner = "Usage:  #{File.basename($0)}  [OPTIONS]"
		
		opts.separator ""
		opts.separator "Specific Options:"
		
		opts.on( "-d", "--dictionary DICT_FILE",
		         "The dictionary file to pull words from." ) do |dict|
			WordGame.load_dictionary(dict)
		end
		opts.on( "-p", "--port PORT", Integer,
		         "The port to listen for connections on." ) do |port|
			listen_port = port
		end

		opts.separator "Common Options:"

		opts.on( "-h", "--help",
		         "Show this message." ) do
			puts opts
			exit
		end
	end.parse!

	server = TelnetServer.new(listen_port)
	server.start
	server.join

Most of that code is just option parsing with optparse.  I'm allowing a port and
dictionary to be specified when the server is launched.

The final three lines kick off GServer.  I build an instance, passing the port;
start() the server process; and join() the server, so my code won't exit until
all the server Threads do.  That's all it takes to run GServer.

My thanks to Brian and Ilmari for the solutions and Pat for the quiz.  Good
stuff all around.

Tomorrow the I've got another submitted quiz for you, this time a tiling
problem...