Cows and Bulls (#32)

by Pat Eyler

My kids like to play a variant of "Cows and Bulls" when we're driving. One of them (the server, to use a computing term -- you'll see why in a minute) will think of a word (we usually play with either three or four letters), and the other (the client) will try to guess it. With each guess, the server will respond with the number of 'cows' (letters in the word, but not in the right place) and bulls (letters in the correct place in the word).

Here's a short example:

Server: (thinks of the word cow) I'm thinking of a three letter word.
Client: cab
Server: 0 cows and 1 bull
Client: cat
Server: 0 cows and 1 bull
Client: cot
Server: 0 cows and 2 bulls
Client: cow
Server: That's right!

This weeks quiz has a couple of flavors:

1) You can write a server that will play our version of "Cows and Bulls". It should follow a simplified version of the above, and look like:

Server: 3 # the number of letters in the word
Client: "cab"
Server: "0 1"
Client: "cat"
Server: "0 1"
Client: "cot"
Server: "0 2"
Client: "cow"
Server: 1 # indicating success

2) You should write also write a client that a player can interact with to play the game.

3) You can also write a player that will interact with the server and play a game.


Quiz Summary

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:

ruby
#!/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!().

ruby
# ...

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:

ruby
# ...

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:

ruby
#!/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.

ruby
# ...

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:

ruby
# ...

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...