[QUIZ] Hangman (#130)

R

Ruby Quiz

The three rules of Ruby Quiz:

1. Please do not post any solutions or spoiler discussion for this quiz until
48 hours have passed from the time on this message.

2. Support Ruby Quiz by submitting ideas as often as you can:

http://www.rubyquiz.com/

3. Enjoy!

Suggestion: A [QUIZ] in the subject of emails about the problem helps everyone
on Ruby Talk follow the discussion. Please reply to the original quiz message,
if you can.

-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

by Brian Candler

Most people are probably familiar with the game of Hangman. The first player
picks a word or phrase, and the second player has to guess it a letter at a
time. If they make six wrong guesses (i.e. the target word does not contain the
guessed letter), they lose. If they guess the entire word before then, they win.

This quiz is to make a Hangman guessing player in Ruby. Play should proceed as
follows:

1. The program requests a word or phrase pattern, e.g. "-------".

2. The program suggests a letter, or may guess the entire word or phrase.

3. The user indicates which letter positions, if any, match that letter.
If none match, a life is lost. If six (or configurable) lives are lost,
the program loses.

The specification is otherwise open-ended to allow you to focus on whatever part
of the problem interests you. For example:

* You may choose the form of user interface (e.g. terminal, GUI toolkit,
web).

* You can just show the number of wrong guesses made, or you can actually
draw the hangman.

* You may concentrate on improving the play, for example by using a
dictionary to improve the guesses made at each stage. A suitable file
is /usr/share/dict/words on many Linux systems.

* A dynamic solution could start with an empty dictionary, and guess the
answer by chance. If it fails, it would prompt the user for the word
or phrase they were thinking of. It would add new words or phrases to
its dictionary so as to become a better player over time.

* You could investigate ways of precomputing a hangman decision tree,
optimizing it for the minimum number of wrong guesses along each branch.
The aim is to produce an unbeatable guesser for a given dictionary.

* You may wish to consider how best to decouple the UI from the guessing
logic, to enable different UI's to work with the same guessing engine,
or vice versa.
 
P

Paul Novak

The three rules of Ruby Quiz:

1. Please do not post any solutions or spoiler discussion for this quiz until
48 hours have passed from the time on this message.

2. Support Ruby Quiz by submitting ideas as often as you can:

http://www.rubyquiz.com/

3. Enjoy!

Suggestion: A [QUIZ] in the subject of emails about the problem helps everyone
on Ruby Talk follow the discussion. Please reply to the original quiz message,
if you can.

-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

by Brian Candler

Most people are probably familiar with the game of Hangman. The first player
picks a word or phrase, and the second player has to guess it a letter at a
time. If they make six wrong guesses (i.e. the target word does not contain the
guessed letter), they lose. If they guess the entire word before then, they win.

This quiz is to make a Hangman guessing player in Ruby. Play should proceed as
follows:

1. The program requests a word or phrase pattern, e.g. "-------".

2. The program suggests a letter, or may guess the entire word or phrase.

3. The user indicates which letter positions, if any, match that letter.
If none match, a life is lost. If six (or configurable) lives are lost,
the program loses.

The specification is otherwise open-ended to allow you to focus on whatever part
of the problem interests you. For example:

* You may choose the form of user interface (e.g. terminal, GUI toolkit,
web).

* You can just show the number of wrong guesses made, or you can actually
draw the hangman.

* You may concentrate on improving the play, for example by using a
dictionary to improve the guesses made at each stage. A suitable file
is /usr/share/dict/words on many Linux systems.

* A dynamic solution could start with an empty dictionary, and guess the
answer by chance. If it fails, it would prompt the user for the word
or phrase they were thinking of. It would add new words or phrases to
its dictionary so as to become a better player over time.

* You could investigate ways of precomputing a hangman decision tree,
optimizing it for the minimum number of wrong guesses along each branch.
The aim is to produce an unbeatable guesser for a given dictionary.

* You may wish to consider how best to decouple the UI from the guessing
logic, to enable different UI's to work with the same guessing engine,
or vice versa.

Great quiz! There is already plenty here to do, but one more idea for
'double-secret extra credit' would be to produce a 'hard word'
generator for a given dictionary.

Regards,

Paul.
 
J

Jesse Merriman

--Boundary-00=_LZUkGqSfYc67+su
Content-Type: Multipart/Mixed;
boundary="Boundary-00=_LZUkGqSfYc67+su"

--Boundary-00=_LZUkGqSfYc67+su
Content-Type: text/plain;
charset="utf-8"
Content-Transfer-Encoding: quoted-printable
Content-Disposition: inline

Here's my solution. I tried to tackle many of the suggested ideas:

- Extensible interface and AI. Just create a new file for the interface/ai,
give it the right filename, and implement the appropriate methods. Then
call hangman.rb with the correct --interface or --ai option.

- I've implemented a simple text interface and one based on Ncurses, just =
to
try it out. My ncurses code is ugly, but it works ok. I almost tried out
some animation & color a la the rain.rb ncurses example, but have no tim=
e.

- Implemented a random AI and one that tries to match items in a dictionar=
y,
though it does not add new words to it. It greps through the dictionary
file on each guess, but is still pretty quick with the 52848 word one I'm
testing with.

Downsides:

- Not much error checking. Inputing illegal positions and such is an easy
crash.

- Very little documentation.

hangman.rb is the executable, which creates an interface (subclass of
Interface::Core), and an AI (subclass of AI::Core), and passes them to a
Game object which controls the basic game flow. (Heh, 9 source files for
a quiz submission, a personal record.. :)

Usage: hangman.rb [--interface | -i INTERFACE]
[--interface-arg | -j INTERFACE_ARGUMENT]
[--ai | -a AI]
[--ai-arg | -b AI_ARGUMENT]

Simple UI / Dictionary AI full example:

$ cat dict.txt
CAR
CAT
DOCK
DOOR
RUBY
ACORN
HINGE
ZEBRA
$ ./hangman.rb -a dictionary
Enter a phrase pattern: ---
--- | Computer lives: 6
I guess A. What position(s) is it in? 2
-A- | Computer lives: 6
I guess C. What position(s) is it in? 1
CA- | Computer lives: 6
I guess R. What position(s) is it in?
CA- | Computer lives: 5
I guess T. What position(s) is it in? 3
CAT | Computer lives: 5

Woot! I win!

Ncurses UI / Random AI example end screen:

=E2=94=8C=E2=94=80=E2=94=80=E2=94=80=E2=94=80=E2=94=80=E2=94=80=E2=94=80=E2=
=94=80=E2=94=80=E2=94=80=E2=94=80=E2=94=80=E2=94=80=E2=94=80=E2=94=80=E2=94=
=80=E2=94=80=E2=94=80=E2=94=80=E2=94=80=E2=94=80=E2=94=80=E2=94=80=E2=94=80=
=E2=94=80=E2=94=80=E2=94=80=E2=94=80=E2=94=80=E2=94=80=E2=94=80=E2=94=80=E2=
=94=80=E2=94=80=E2=94=80=E2=94=80=E2=94=80=E2=94=80=E2=94=80=E2=94=80=E2=94=
=80=E2=94=80=E2=94=80=E2=94=80=E2=94=80=E2=94=80=E2=94=80=E2=94=80=E2=94=80=
=E2=94=80=E2=94=80=E2=94=80=E2=94=80=E2=94=80=E2=94=80=E2=94=80=E2=94=80=E2=
=94=80=E2=94=80=E2=94=80=E2=94=80=E2=94=80=E2=94=80=E2=94=80=E2=94=80=E2=94=
=80=E2=94=80=E2=94=80=E2=94=80=E2=94=80=E2=94=80=E2=94=80=E2=94=80=E2=94=80=
=E2=94=80=E2=94=80=E2=94=80=E2=94=80=E2=94=90
=E2=94=82 Hangman | =
=E2=94=82
=E2=94=82---------+ =
=E2=94=82
=E2=94=82 =
=E2=94=82
=E2=94=82 Phrase: V-- =
=E2=94=82
=E2=94=82 =
=E2=94=82
=E2=94=82 Computer guess: M =
=E2=94=82
=E2=94=82 Positions? =
=E2=94=82
=E2=94=82 =
=E2=94=82
=E2=94=82 =
=E2=94=82
=E2=94=82 . I lost! =
=E2=94=82
=E2=94=82 0 +--------+- =
=E2=94=82
=E2=94=82 | | =
=E2=94=82
=E2=94=82 _ | =
=E2=94=82
=E2=94=82 | | | =
=E2=94=82
=E2=94=82 + | =
=E2=94=82
=E2=94=82 -|- | =
=E2=94=82
=E2=94=82 / | \ | =
=E2=94=82
=E2=94=82 ^ | =
=E2=94=82
=E2=94=82 / \ | =
=E2=94=82
=E2=94=82 / \ | =
=E2=94=82
=E2=94=82 | =
=E2=94=82
=E2=94=82 =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D =
=E2=94=82
=E2=94=82 =
=E2=94=82
=E2=94=94=E2=94=80=E2=94=80=E2=94=80=E2=94=80=E2=94=80=E2=94=80=E2=94=80=E2=
=94=80=E2=94=80=E2=94=80=E2=94=80=E2=94=80=E2=94=80=E2=94=80=E2=94=80=E2=94=
=80=E2=94=80=E2=94=80=E2=94=80=E2=94=80=E2=94=80=E2=94=80=E2=94=80=E2=94=80=
=E2=94=80=E2=94=80=E2=94=80=E2=94=80=E2=94=80=E2=94=80=E2=94=80=E2=94=80=E2=
=94=80=E2=94=80=E2=94=80=E2=94=80=E2=94=80=E2=94=80=E2=94=80=E2=94=80=E2=94=
=80=E2=94=80=E2=94=80=E2=94=80=E2=94=80=E2=94=80=E2=94=80=E2=94=80=E2=94=80=
=E2=94=80=E2=94=80=E2=94=80=E2=94=80=E2=94=80=E2=94=80=E2=94=80=E2=94=80=E2=
=94=80=E2=94=80=E2=94=80=E2=94=80=E2=94=80=E2=94=80=E2=94=80=E2=94=80=E2=94=
=80=E2=94=80=E2=94=80=E2=94=80=E2=94=80=E2=94=80=E2=94=80=E2=94=80=E2=94=80=
=E2=94=80=E2=94=80=E2=94=80=E2=94=80=E2=94=98

=2D-=20
Jesse Merriman
(e-mail address removed)
http://www.jessemerriman.com/

--Boundary-00=_LZUkGqSfYc67+su
Content-Type: application/x-ruby;
name="ai_core.rb"
Content-Transfer-Encoding: 7bit
Content-Disposition: attachment;
filename="ai_core.rb"

module Hangman
module AI
def AI.looks_ok? possible_ai
possible_ai.respond_to? :guess
end

class Core
DefaultMaxLives = 6
DefaultLetters = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'

attr_reader :lives, :max_lives, :letter_pool

def initialize(lives = DefaultMaxLives, letters = DefaultLetters)
@lives = lives.to_i
@max_lives = lives.to_i
@letter_pool = letters.split(//)
end

def lose_life; @lives = [0, @lives-1].max; end

def dead?; @lives.zero?; end

private

def random_letter
@letter_pool[rand(@letter_pool.size)]
end
end
end
end

--Boundary-00=_LZUkGqSfYc67+su
Content-Type: application/x-ruby;
name="hangman.rb"
Content-Transfer-Encoding: 7bit
Content-Disposition: attachment;
filename="hangman.rb"

#!/usr/bin/env ruby

require 'game'
require 'getoptlong'

class String
# Taken & mildly modified from ActiveSupport.
def camelize(first_letter_in_uppercase = true)
if first_letter_in_uppercase
gsub(/\/(.?)/) { "::" + $1.upcase }.gsub(/(^|_)(.)/) { $2.upcase }
else
self[0].chr + self[1..-1].camelize
end
end
end

if __FILE__ == $0
Opts = GetoptLong.new(
[ '--interface', '-i', GetoptLong::REQUIRED_ARGUMENT ],
[ '--interface-arg', '-j', GetoptLong::REQUIRED_ARGUMENT ],
[ '--ai', '-a', GetoptLong::REQUIRED_ARGUMENT ],
[ '--ai-arg', '-b', GetoptLong::REQUIRED_ARGUMENT ] )

# defaults
interface = 'text'
ai = 'random'
iface_args, ai_args = [], []

Opts.each do |opt, arg|
case opt
when '--interface'; interface = arg
when '--interface-arg'; iface_args << arg
when '--ai'; ai = arg
when '--ai-arg'; ai_args << arg
end
end

begin
require "interface_#{interface}"
require "ai_#{ai}"

iface_class = Hangman::Interface.const_get(interface.camelize)
ai_class = Hangman::AI.const_get(ai.camelize)

iface = iface_class.new(*iface_args)
ai = ai_class.new(*ai_args)

raise 'Bad interface' unless Hangman::Interface.looks_ok?(iface)
raise 'Bad AI' unless Hangman::AI.looks_ok?(ai)

Hangman::Game.new(iface, ai).run
rescue LoadError => le
missing = /\-\- (.*)$/.match(le.message)[1]
$stderr.puts "Can't find #{missing}"
end
end

--Boundary-00=_LZUkGqSfYc67+su
Content-Type: application/x-ruby;
name="interface_core.rb"
Content-Transfer-Encoding: 7bit
Content-Disposition: attachment;
filename="interface_core.rb"

module Hangman
module Interface
def Interface.looks_ok? possible_iface
possible_iface.respond_to?:)phrase_pattern) and
possible_iface.respond_to?:)suggest) and
possible_iface.respond_to?:)display) and
possible_iface.respond_to?:)finish)
end

class Core; end
end
end

--Boundary-00=_LZUkGqSfYc67+su
Content-Type: application/x-ruby;
name="interface_n.rb"
Content-Transfer-Encoding: 7bit
Content-Disposition: attachment;
filename="interface_n.rb"

require 'interface_core'
require 'ncurses'

module Hangman
module Interface
# An Ncurses-based interface. Originally I called this Ncurses instead of N,
# but then to refer to the originaly Ncurses class you'd need to do
# Object::Ncurses.
class N < Core
def initialize
setup_screen
self
end

def phrase_pattern
@screen.mvaddstr 4, 2, 'Phrase:'
@screen.move *PhraseCoords
read_line
end

def suggest letter
@screen.mvaddstr 6, 2, 'Computer guess:'
@screen.mvaddstr 6, 18, letter
@screen.mvaddstr 7, 2, 'Positions? '
read_line.chomp.split(' ').map { |x| x.to_i - 1}
end

def display phrase, lives, max_lives
clear_fields
body_i = body_index lives, max_lives
draw Bodies[body_i], *BodyCoords

#@screen.mvaddstr *PhraseCoords, phrase # Damn, this doesn't work?
@screen.mvaddstr PhraseCoords.first, PhraseCoords.last, phrase
@screen.mvaddstr LivesCoords.first, LivesCoords.last, lives.to_s

@screen.refresh
end

def finish user_won
@screen.move 10, 30
if user_won
@screen.addstr 'I lost!'
else
@screen.addstr 'I won!'
end

read_line
Ncurses.endwin
end

private

def setup_screen
Ncurses.initscr
Ncurses.cbreak
Ncurses.noecho
@screen = Ncurses.stdscr
Ncurses.keypad @screen, true

@screen.border(*([0]*8))
@screen.mvaddstr 1, 1, ' Hangman |'
@screen.mvaddstr 2, 1, '---------+'

draw Platform, *PlatformCoords

@screen.refresh
end

def clear_fields
@screen.mvaddstr 7, 18, ' ' * 20
@screen.mvaddstr LivesCoords.first, LivesCoords.last, ' ' * 6
end

# Modified from the ncurses-ruby read_line.rb example. Still fugly.
def read_line
line = ''
pos = 0
x, y = [], []
Ncurses.getyx @screen, y, x
x, y = x.first, y.first
max_len = @screen.getmaxx - x - 1

loop do
@screen.mvaddstr y, x, line
@screen.move y, x + pos
char = @screen.getch
case char
when Ncurses::KEY_LEFT
pos = [0, pos - 1].max
when Ncurses::KEY_RIGHT
pos = [line.length, pos + 1].min
when Ncurses::KEY_ENTER, ?\n, ?\r
return line
when Ncurses::KEY_BACKSPACE, ?\177
line = line[0...([0, pos - 1].max)] + line[pos..-1]
pos = [0, pos - 1].max
@screen.mvaddstr(y, x + line.length, ' ')
when ' '[0]..255 # remaining printables
if (pos < max_len)
line[pos, 0] = char.chr
pos += 1
else
Ncurses.beep
end
else
Ncurses.beep
end
end
end

def body_index lives, max_lives
Bodies.size + (lives * (1 - Bodies.size) / max_lives).round - 1
end

def draw item, y, x
d = lambda { |line| @screen.mvaddstr(y, x, line); y += 1 }
item.each_line { |line| d[line.chomp] }
end

PhraseCoords = [4, 19]
LivesCoords = [11, 2]

PlatformCoords = [10, 2]
Platform = <<EOF
 
A

Andreas Launila

Ruby said:
This quiz is to make a Hangman guessing player in Ruby. Play should proceed as
follows:

I focused on building a program that makes good guesses.


== Algorithm overview

The guesser reads a dictionary and then builds a database (which is
reused) with the following information about each word:
* size
* positions of each character
* number of occurrences of each character

The basic algorithm is as follows:
* Remove all words that do not have a matching length.
* While the game has not been solved:
** Pick the character included in the most words still remaining.
** If the character is not in the word: remove all words with the character.
** If the character is in the word: remove all words that do not contain
the character at exactly the revealed positions.

=== Weaknesses

The algorithm is not optimal. The character that's included in the most
words is not necessarily the character which will give the largest
reduction in number of potential words since position is not considered.
Consider a dictionary with the following:

bdc
ebc
fcb

b and c are tied for number of occurrences, but b would be the better
choice. If we pick b we will in all cases be left with one potential
word. If we pick c and the word is one of the first two we get two
potential words.

My guess is that it's a good enough heuristic in most cases though.

Also note that this program is built on the assumption that the word is
picked randomly from the dictionary. More refined solutions could weigh
in the relative frequency of different words in normal English text.


== Speed

It takes about 40 minutes to create the database for a dictionary with
4*10^5 words, but it only has to be created once.

Computing all guesses for a word (i.e. from being given the length to
having the correct word) takes about 30 to 40 seconds for a dictionary
with 4*10^5 words. That time includes about 10 seconds to reset the
database from previous uses, another 10 seconds for pruning based on
word length and the rest for the remaining search.

=== Possible improvements

Much of the initial sorting could be precomputed (e.g. split words into
different table based on length and then only work against the table
with the specified length) to cut down on the time needed reset and do
the initial pruning. The first (and possibly some additional steps)
could also be precomputed.


== Dependencies

Requires a mysql database and the mysql-gem. You need to enter your
username, passwords and database name in HangmanGuesser#db_connection below.


== The code

#!/usr/bin/env ruby
# == Synopsis
#
# automated_hangman: plays a game of hangman with the word of your
# choice
#
# == Usage
#
# automated_hangman [OPTION] ... WORD
#
# -h, --help:
# show help
#
# -d, --dictionary [dictionary location]:
# sets up the database to use the specified dictionary (defaults to
# /usr/share/dict/words), can take some time
#
# WORD: The word that the program should try to guess.


require 'getoptlong'
require 'rdoc/usage'
require 'mysql'

# Describes a game of hangman.
class Hangman
LIVES = 6

# Creates a new game of hangman where word is the target word.
def initialize(word)
@guesses = []
@word_characters = word.chomp.downcase.split(//)
end

# Returns an array containing the incorrect guessed characters.
def incorrect_guesses
@guesses - @word_characters
end

# Guesses a specified character. Returns an array of indices (possibly
# empty) where the character was found.
def guess(char_guess)
@guesses << char_guess
indices = []
@word_characters.each_with_index do |character, index|
indices << index if character == char_guess
end
return indices
end

# Returns a string representation of the current progress.
def to_s
hidden_characters = @word_characters - @guesses
return @word_characters.join(' ') if hidden_characters.empty?
@word_characters.join(' ').gsub(
/[#{hidden_characters.uniq.join}]/, '_')
end

# Checks whether the player has won.
def won?
(@word_characters - @guesses).empty?
end

# Checks whether the player has lost.
def lost?
incorrect_guesses.size > LIVES
end

# Gets the number of characters in the word.
def character_count
@word_characters.size
end
end

# The guessing machine which picks the guesses.
class HangmanGuesser
# The location of the default dictionary to use.
DICTIONARY_FILE = '/usr/share/dict/words'
# An array of the characters that should be considered.
CHARACTERS = ('a'..'z').to_a
# Set this to true to see how the search progresses.
VERBOSE = true
# The maximum word length accepted.
MAX_WORD_LENGTH = 50

# The dictionary given should be the location of a file containing one
# word per line. The characters should be an array of all characters
# that should be considered (i.e. no words with other characters are
# included).
def initialize(hangman_game, characters = CHARACTERS)
@con = self.class.db_connection
@characters = characters
@hangman_game = hangman_game

reset_tables
prune_by_word_length @hangman_game.character_count
end

# Returns the guesses that the guesser would make.
def guesses
@guesses = []
log{ "There are #{word_count} potential words left." }
while not @hangman_game.won?
guess = next_guess
raise 'The word is not in the dictionary.' if guess.nil?
@guesses << guess
log{ "Guessing #{guess}" }
add_information(guess, @hangman_game.guess(guess))
log_state
log{ "\n" }
end
return @guesses
end

class << self
# Creates the database and populates it with the dictionary file
# located at the specified location. Only considers the specified
# characters (array).
def create_database(dictionary = DICTIONARY_FILE,
characters = CHARACTERS)
@con = db_connection
@characters = characters
@tables = ['words'] + @characters +
@characters.map{ |c| c + '_occurrences'}
create_tables
populate_tables File.open(dictionary)
end

# Connects to the database that should store the tables.
def db_connection
# Replace <username> and <password> with the database username and
# password.
Mysql.real_connect("localhost", <username>, <password>, "hangman")
end

private

# Creates the tables used to store words.
def create_tables
# Drop old tables.
@tables.each do |table|
@con.query "DROP TABLE IF EXISTS `#{table}`"
end

# Words table.
@con.query <<-"end_sql"
CREATE TABLE `words` (
`word_id` mediumint(8) unsigned NOT NULL AUTO_INCREMENT,
`word` varchar(#{MAX_WORD_LENGTH}) NOT NULL,
`length` tinyint(3) unsigned NOT NULL,
`removed` tinyint(1) unsigned NOT NULL DEFAULT '0',
PRIMARY KEY (`word_id`),
INDEX (`removed`),
INDEX (`length`)
) ENGINE=MyISAM
end_sql

# Tables for the number of occurrences of each character.
character_occurrences_table_template =<<-'end_template'
CREATE TABLE `%s_occurrences` (
`word_id` mediumint(8) unsigned NOT NULL,
`occurrences` tinyint(3) unsigned NOT NULL,
PRIMARY KEY (`occurrences`, `word_id`),
INDEX (`word_id`)
) ENGINE=MyISAM
end_template

# Tables for the positions of each character.
character_table_template =<<-'end_template'
CREATE TABLE `%s` (
`word_id` mediumint(8) unsigned NOT NULL,
`position` tinyint(3) unsigned NOT NULL,
PRIMARY KEY (`position`, `word_id`),
INDEX (`word_id`)
) ENGINE=MyISAM
end_template

@characters.each do |character|
@con.query character_occurrences_table_template % character
@con.query character_table_template % character
end
end

# Loads a dictionary into the database.
def populate_tables(dictionary_file)
# Disable the keys so that we don't update the indices while
# adding.
@tables.each do |table|
@con.query("ALTER TABLE #{table} DISABLE KEYS")
end

# Prepare statements.
add_word = @con.prepare(
"INSERT INTO words (word, length) VALUES (?, ?)")
add_character = {}
add_character_occurrences = {}
@characters.each do |character|
add_character[character] = @con.prepare(
"INSERT INTO #{character} (word_id, position) VALUES (?, ?)")
add_character_occurrences[character] = @con.prepare(
"INSERT INTO #{character}_occurrences " +
"(word_id, occurrences) VALUES (?, ?)")
end

# Populate the database.
previous_word = nil
dictionary_file.each_line do |line|
# Only consider words that only contain characters a-z. Make
# sure we don't get duplicates.
word = line.chomp.downcase
next if word == previous_word or word =~ /[^a-z]/ or
word.size > MAX_WORD_LENGTH

# Add the word, its character positions and number of
# occurrences.
add_word.execute(word, word.size)
word_id = @con.insert_id
characters = word.split(//)
characters.each_with_index do |character, position|
add_character[character].execute(word_id, position)
end
@characters.each do |character|
occurrences = characters.select{ |c| c == character }.size
add_character_occurrences[character].execute(
word_id, occurrences)
end

previous_word = word
end

# Generate the indices.
@tables.each do |table|
@con.query("ALTER TABLE #{table} ENABLE KEYS")
end
end
end

private

# Logs the current state of the guessing process.
def log_state
log do
messages = []
messages << @hangman_game.to_s
count = word_count
messages << "There are #{count} potential words left."
if count <= 10
res = @con.query('SELECT word FROM words WHERE removed = 0')
res.each{ |row| messages << row[0] }
res.free
end
messages.join("\n")
end
end

# Logs the string produced by the block (may not be executed at all).
def log(&block)
puts yield() if VERBOSE
end

# Gets the number of potential words left.
def word_count
res = @con.query('SELECT COUNT(*) FROM words WHERE removed = 0')
count = res.fetch_row[0].to_i
res.free
return count
end

# Computes the next character that should be guessed. The next guess
# is the character (that has not yet been tried) that occurrs in the
# most words remaining.
def next_guess
next_character = nil
max_count = 0
(@characters - @guesses).each do |character|
res = @con.query(
"SELECT COUNT(DISTINCT word_id) FROM #{character} " +
"NATURAL JOIN words WHERE removed = 0")
count = res.fetch_row[0].to_i
res.free
if count > max_count
next_character = character
max_count = count
end
end
return next_character
end

# Adds the information about at what indices in the word the specified
# character can be found to the guesser.
def add_information(character, indices)
if indices.empty?
# The character isn't in the word.
sql =<<-"end_sql"
UPDATE words SET removed = 1 WHERE removed = 0 AND word_id IN (
SELECT word_id FROM #{character}
)
end_sql
else
# Remove all words where the character isn't at the specified
# places.
sql =<<-"end_sql"
UPDATE words NATURAL JOIN #{character}_occurrences
SET removed = 1
WHERE removed = 0
AND (occurrences != #{indices.size}
OR word_id IN (
SELECT word_id FROM #{character}
WHERE position NOT IN (#{indices.join(', ')})
)
)
end_sql
end
@con.query(sql)
end

# Resets the table to start a new round of guesses.
def reset_tables
@con.query('UPDATE words SET removed = 0')
end

# Prunes all words that do not have the specified length.
def prune_by_word_length(expected_length)
@con.query(
"UPDATE words SET removed = 1 WHERE length != #{expected_length}")
end
end


opts = GetoptLong.new(
[ '--help', '-h', GetoptLong::NO_ARGUMENT],
['--dictionary', '-d', GetoptLong::OPTIONAL_ARGUMENT])
opts.each do |opt, arg|
case opt
when '--help'
RDoc::usage
when '--dictionary'
if arg != ''
HangmanGuesser.create_database(arg)
else
HangmanGuesser.create_database
end
end
end

if ARGV.size != 1
abort "Incorrect usage, see --help"
end

game = Hangman.new(ARGV[0])
guesses = HangmanGuesser.new(game).guesses
if game.won?
puts 'Successfully guessed the word.'
else game.lost?
puts 'Failed guessing the word.'
end
puts "Made the following guesses: #{guesses.join(', ')}"
puts "Expended a total of #{game.incorrect_guesses.size} lives."
 
J

James Edward Gray II

Not many people solved this one, so I wanted to see if it was too
tough. Didn't seem so:

#!/usr/bin/env ruby -wKU

puts "One moment..."
puts
words = File.open(ARGV.shift || "/usr/share/dict/words") do |dict|
dict.inject(Hash.new) do |all, word|
all.update(word.delete("^A-Za-z").downcase => true)
end.keys
end

guesses = Array.new

loop do
puts guesses.empty? ?
"Please enter a word pattern (_ _ _ _ for example):" :
"Please update your pattern according to my guess (_ i _ _
for example):"
pattern = $stdin.gets.to_s.delete("^A-Za-z_")
if pattern.include? "_"
if (guesses - pattern.delete("_").split("")).size > 6
puts "I'm out of guesses. You win."
puts
exit
end
else
puts "I guessed your word. Pretty smart, huh?"
puts
exit
end

choices = words.grep(/\A#{pattern.tr("_", ".")}\Z/i)
odds = Hash.new(0)
choices.each do |word|
word.split("").each do |l|
next if guesses.include? l
odds[l] += word.count(l)
end
end
guess = odds.max { |(_, c1), (_, c2)| c1 <=> c2 }.first rescue nil

guesses << guess
puts "I guess the letter '#{guess}'."
puts
end

__END__

James Edward Gray II
 
Y

Yossef Mendelssohn

Maybe people aren't trying this quiz because they're busy. I hope
it's not because they find it uninteresting. I banged out something
fairly quickly during the weekend and was waiting to find some time to
clean it up. It seems I won't get that, so I'm going to post what I
have now.

It's a fairly simple algorithm that uses a combination of the
"established" frequency order of letters in the English language, as
seen on Linotype machines, and a dictionary (/usr/dict/share/words, of
course) to provide the next guess. What I find interesting about this
is how many common words it cannot get before exhausting its allotment
of wrong guesses. For instance, it won't get "book". Sometimes I'm
surprised with the guesses it gives. Maybe the dictionary I'm using
is *too* large.

-------------------------------------------------------------------------------
#!/usr/bin/env ruby

ALLOWED_WRONG_GUESSES = 6

WORD_LIST_FILENAME = '/usr/share/dict/words'

WORD_LIST = {}

File.open(WORD_LIST_FILENAME) do |f|
f.each { |word| WORD_LIST[word.strip.downcase] = true }
end

FREQUENCY_ORDER = %w{etaoin shrdlu cmfwyp vbgkqj xz}.collect { |elem|
elem.split('') }.flatten

GUESSES_MADE = {}

puts 'Enter a word pattern'
old_pattern = pattern = gets.chomp

loop do
if pattern.match(/^[a-zA-Z\-]+$/)
if pattern.match(/-/)
if GUESSES_MADE.values.select { |val| val == false }.length >
ALLOWED_WRONG_GUESSES
puts 'crap I lost'
exit
end

regex = Regexp.new("^#{pattern.downcase.gsub(/-/, '.')}$")
possible_words = WORD_LIST.keys.select { |word|
word.match(regex) }
possible_letters = possible_words.collect { |word|
word.split('') }.flatten.uniq
guess = ((FREQUENCY_ORDER - GUESSES_MADE.keys) &
possible_letters).first
puts guess.upcase
pattern = gets.chomp

GUESSES_MADE[guess] = (pattern != old_pattern)
puts "wrong guesses made: #{GUESSES_MADE.values.select { |val|
val == false }.length}"
old_pattern = pattern
else
puts 'Yay I won'
exit
end
else
puts 'This pattern makes no sense.'
exit
end
end
 
J

James Edward Gray II

A second version of my code. Minor changes mainly to support me
testing it. I tried different guessing algorithms, but nothing beat
the original strategy with my dictionary.

First, this is a tiny words.rb lib used by both the guesser and test
scripts:

#!/usr/bin/env ruby -wKU

WORDS_CASH_FILE = "words.cache"

if File.exist? WORDS_CASH_FILE
WORDS = File.open(WORDS_CASH_FILE) { |file| Marshal.load(file) }
else
WORDS = File.open( ARGV.find { |arg| arg =~ /\A[^-]/ } ||
"/usr/share/dict/words" ) do |dict|
dict.inject(Hash.new) do |all, word|
all.update(word.delete("^A-Za-z").downcase => true)
end.keys
end
File.open(WORDS_CASH_FILE, "w") { |file| Marshal.dump(WORDS, file) }
end

__END__

Next, my guesser script which works the same as yesterday's version
but is optimized here and there for testing:

#!/usr/bin/env ruby -wKU

puts "One moment..."
puts
require "words"

choices = WORDS
guesses = Array.new

loop do
puts guesses.empty? ?
"Please enter a word pattern (_ _ _ _ for example):" :
"Please update your pattern according to my guess (_ i _ _
for example):"
$stdout.flush
pattern = $stdin.gets.to_s.delete("^A-Za-z_")

if (guesses - pattern.delete("_").split("")).size > 5 and
pattern.include? "_"
puts "I'm out of guesses. You win."
elsif not pattern.include? "_"
puts "I guessed your word. Pretty smart, huh?"
else
choices = choices.grep(/\A#{pattern.tr("_", ".")}\Z/i)
odds = Hash.new(0)
choices.each do |word|
word.split("").each do |l|
next if guesses.include? l
odds[l] += word.count(l)
end
end
guess = odds.max { |(_, c1), (_, c2)| c1 <=> c2 }.first rescue nil

guesses << guess
puts "I guess the letter '#{guess}'."
puts
next
end

puts
if ARGV.include? "--loop"
choices = WORDS
guesses = Array.new
else
break
end
end

__END__

Finally, this is my test script:

#!/usr/bin/env ruby -wKU

require "words"

results = Hash.new(0)
at_exit do
results[:total] = results[:right] + results[:wrong]
puts
puts "Words: #{results[:total]}"
puts "Guessed: #{results[:right]}"
puts "Missed: #{results[:wrong]}"
printf "Accuracy: %.2f%%\n", results[:right] / results
[:total].to_f * 100
puts
end
trap("INT") { exit }

IO.popen( File.join(File.dirname(__FILE__), "hangman.rb --loop"),
"r+" ) do |hangman|
WORDS.each do |word|
pattern = word.tr("a-z", "_")
loop do
input = String.new
hangman.each do |line|
input << line
break if input =~ /^(?:I'm out|I guessed)|:\Z/
end

if input =~ /^I'm out/
puts "It missed '#{word}'."
results[:wrong] += 1
break
elsif input =~ /^I guessed/
puts "It guessed '#{word}'."
results[:right] += 1
break
elsif input =~ /^I guess the letter '(.)'/
guess = $1
word.split("").each_with_index do |letter, i|
pattern[i, 1] = letter if letter == guess
end
end

hangman.puts pattern
end
end
end

__END__

James Edward Gray II
 
T

Thomas Wieczorek

------=_Part_7791_32033177.1184181018598
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 7bit
Content-Disposition: inline

2007/7/11 said:
Not many people solved this one, so I wanted to see if it was too
tough. Didn't seem so:
I was busy until today.

Here's my solution and my first quiz solution since I learn Ruby. It
wasn't that hard. I learned a lot about Ruby with it.
ruby hangman.rb [-w=word] [-l=lifes]
If you don't pass a word it will choose a random word from the
dictionary. Lifes is set to 6 if you don't provide it.

<code>
#Ruby Quiz 130
#solution by Thomas Wieczorek <[email protected]>
#11.07.2007
require 'yaml'
$debug = true

class Player

public

def initialize(word)
@word = word
@dictionary = YAML.load_file(DICTIONARYFILE)
@letters = ('a'..'z').to_a
@guessed = []
scan_dictionary(word)
end

def guess()
return @dictionary[0] if @dictionary.length == 1
while (true)
letter = @probabilities.pop
next if @guessed.include?(letter[0])
@guessed << letter[0]
break
end
return letter[0]
end

def word=(value)

if not value.include?(".") then
#lost
#unknown word
if not @dictionary.include?(value) then
@dictionary = load_dictionary()
@dictionary << value
File.open("dictionary.yaml", "w") { |f| YAML.dump(@dictionary, f) }
end
else
if @word.eql?(value) then
@word = value
scan_dictionary(value)
end
end
end

private

DICTIONARYFILE = "dictionary.yaml"

def scan_dictionary(masked)
@dictionary = @dictionary or load_dictionary()
@dictionary = @dictionary.grep(Regexp.new("^#{@word}$"))
set_probability()
end

def set_probability
alphabet = ('a'..'z').to_a
@probabilities = {}
alphabet.each { |l| @probabilities[l] = 0 }
@dictionary.each do |word|
word.each_byte do |letter|
#p letter
l = letter.chr
@probabilities[l] += 1 if alphabet.include?(l)
end
end

@probabilities = @probabilities.sort {|a,b| a[1]<=>b[1]}
end

def load_dictionary()
return YAML.load_file(DICTIONARYFILE)
end
end #of Player

def random_word
words = YAML.load_file("dictionary.yaml")
return words[rand(words.length)]
end

def check_for_letters(word, guess, masked_word)
if word.include?(guess) then
#puts "#{guess} is in #{word}"
word.length.times do |i|
if word.chr == guess then
masked_word = guess
end
end
end

return masked_word
end

def play_game(word = "", lifes = 6, give_output = false)
#user given word
word = random_word if word == ""
masked_word = word.gsub(/\w/, ".")
guess = ""

player = Player.new(masked_word)

while(lifes > 0)
#AI guesses a letter or word
puts "AI is looking for >#{masked_word}<" if give_output
guess = player.guess()
new_word = ""
won = false
puts "AI guessed '#{guess}'" if give_output
if guess.length == 1 then
masked_word = check_for_letters(word, guess, masked_word)

else
if guess.length > 1 then
break if guess == word
lifes -= 1
next
else
#nil
end
end

#wrong guess
if not masked_word.include?(guess) then
lifes -= 1
puts "AI lost a life. #{lifes} lifes left."
else
#found word
if masked_word == word then
break
else
#found a letter
player.word = masked_word
next
end
end
end

if lifes > 0 then
won = true
else
#give word to player to extend dictionary
player.word = word
won = false
end

return won, word, lifes
end #of play_game

won = false
word = ""
lifes = 6
if ARGV.length > 0
ARGV.each do |arg|
option = arg.split("=")
case option[0]
when "-w"
word = option[1]
when "-l"
lifes = option[1].to_i
end
end
end

won, word, lifes = play_game(word, lifes, true)

if won then
puts "AI won! It guessed \"#{word}\" with #{lifes} lifes left."
else
puts "Awww! Lost! AI couldn't guess \"#{word}\"."
end

</code>

------=_Part_7791_32033177.1184181018598
Content-Type: application/octet-stream; name=hangman.rb
Content-Transfer-Encoding: base64
X-Attachment-Id: f_f406se2t
Content-Disposition: attachment; filename="hangman.rb"

I1J1YnkgUXVpeiAxMzANCiNzb2x1dGlvbiBieSBUaG9tYXMgV2llY3pvcmVrIDx3aWVjem8ueW9A
Z29vZ2xlbWFpbC5jb20+DQojdGhlIGRpY3Rpb25hcnkgY29tZXMgZnJvbSBodHRwOi8vd3d3Lmp1
bmUyOS5jb20vSURQL2ZpbGVzL0dlcm1hbi50eHQgSSByZW1vdmVkIHRoZSBkdXBsaWNhdGVzIGFu
ZCB0aGUgR2VybWFuIHdvcmRzDQojMTEuMDcuMjAwNw0KcmVxdWlyZSAneWFtbCcNCiRkZWJ1ZyA9
IHRydWUNCg0KY2xhc3MgUGxheWVyDQoNCnB1YmxpYw0KDQogIGRlZiBpbml0aWFsaXplKHdvcmQp
DQogICAgQHdvcmQgPSB3b3JkDQogICAgQGRpY3Rpb25hcnkgPSBZQU1MLmxvYWRfZmlsZShESUNU
SU9OQVJZRklMRSkNCiAgICBAbGV0dGVycyA9ICgnYScuLid6JykudG9fYQ0KICAgIEBndWVzc2Vk
ID0gW10NCiAgICBzY2FuX2RpY3Rpb25hcnkod29yZCkNCiAgZW5kDQogIA0KICBkZWYgZ3Vlc3Mo
KQ0KICAgIHJldHVybiBAZGljdGlvbmFyeVswXSBpZiBAZGljdGlvbmFyeS5sZW5ndGggPT0gMQ0K
ICAgIHdoaWxlICh0cnVlKQ0KICAgICAgbGV0dGVyID0gQHByb2JhYmlsaXRpZXMucG9wDQogICAg
ICBuZXh0IGlmIEBndWVzc2VkLmluY2x1ZGU/KGxldHRlclswXSkNCiAgICAgIEBndWVzc2VkIDw8
IGxldHRlclswXQ0KICAgICAgYnJlYWsNCiAgICBlbmQNCiAgICByZXR1cm4gbGV0dGVyWzBdDQog
IGVuZA0KDQogIGRlZiB3b3JkPSh2YWx1ZSkNCiAgICANCiAgICBpZiBub3QgdmFsdWUuaW5jbHVk
ZT8oIi4iKSB0aGVuDQogICAgICAjbG9zdA0KICAgICAgI3Vua25vd24gd29yZA0KICAgICAgaWYg
bm90IEBkaWN0aW9uYXJ5LmluY2x1ZGU/KHZhbHVlKSB0aGVuDQogICAgICAgIEBkaWN0aW9uYXJ5
ID0gbG9hZF9kaWN0aW9uYXJ5KCkNCiAgICAgICAgQGRpY3Rpb25hcnkgPDwgdmFsdWUNCiAgICAg
ICAgRmlsZS5vcGVuKCJkaWN0aW9uYXJ5LnlhbWwiLCAidyIpIHsgfGZ8IFlBTUwuZHVtcChAZGlj
dGlvbmFyeSwgZikgfQ0KICAgICAgZW5kDQogICAgZWxzZQ0KICAgICAgaWYgQHdvcmQuZXFsPyh2
YWx1ZSkgdGhlbg0KICAgICAgICBAd29yZCA9IHZhbHVlDQogICAgICAgIHNjYW5fZGljdGlvbmFy
eSh2YWx1ZSkNCiAgICAgIGVuZA0KICAgIGVuZA0KICBlbmQNCiAgDQpwcml2YXRlIA0KDQogIERJ
Q1RJT05BUllGSUxFID0gImRpY3Rpb25hcnkueWFtbCINCiAgDQogIGRlZiBzY2FuX2RpY3Rpb25h
cnkobWFza2VkKQ0KICAgIEBkaWN0aW9uYXJ5ID0gQGRpY3Rpb25hcnkgb3IgbG9hZF9kaWN0aW9u
YXJ5KCkNCiAgICBAZGljdGlvbmFyeSA9IEBkaWN0aW9uYXJ5LmdyZXAoUmVnZXhwLm5ldygiXiN7
QHdvcmR9JCIpKQ0KICAgIHNldF9wcm9iYWJpbGl0eSgpDQogIGVuZA0KICANCiAgZGVmIHNldF9w
cm9iYWJpbGl0eQ0KICAgIGFscGhhYmV0ID0gKCdhJy4uJ3onKS50b19hDQogICAgQHByb2JhYmls
aXRpZXMgPSB7fQ0KICAgIGFscGhhYmV0LmVhY2ggeyB8bHwgQHByb2JhYmlsaXRpZXNbbF0gPSAw
IH0NCiAgICBAZGljdGlvbmFyeS5lYWNoIGRvIHx3b3JkfA0KICAgICAgd29yZC5lYWNoX2J5dGUg
ZG8gfGxldHRlcnwNCiAgICAgICAgI3AgbGV0dGVyDQogICAgICAgIGwgPSBsZXR0ZXIuY2hyDQog
ICAgICAgIEBwcm9iYWJpbGl0aWVzW2xdICs9IDEgaWYgYWxwaGFiZXQuaW5jbHVkZT8obCkNCiAg
ICAgIGVuZA0KICAgIGVuZA0KICAgIA0KICAgIEBwcm9iYWJpbGl0aWVzID0gQHByb2JhYmlsaXRp
ZXMuc29ydCB7fGEsYnwgYVsxXTw9PmJbMV19DQogIGVuZA0KICANCiAgZGVmIGxvYWRfZGljdGlv
bmFyeSgpDQogICAgcmV0dXJuIFlBTUwubG9hZF9maWxlKERJQ1RJT05BUllGSUxFKQ0KICBlbmQN
CmVuZCAjb2YgUGxheWVyDQoNCmRlZiByYW5kb21fd29yZA0KICB3b3JkcyA9IFlBTUwubG9hZF9m
aWxlKCJkaWN0aW9uYXJ5LnlhbWwiKQ0KICByZXR1cm4gd29yZHNbcmFuZCh3b3Jkcy5sZW5ndGgp
XQ0KZW5kDQoNCmRlZiBjaGVja19mb3JfbGV0dGVycyh3b3JkLCBndWVzcywgbWFza2VkX3dvcmQp
DQogIGlmIHdvcmQuaW5jbHVkZT8oZ3Vlc3MpIHRoZW4NCiAgICAjcHV0cyAiI3tndWVzc30gaXMg
aW4gI3t3b3JkfSINCiAgICB3b3JkLmxlbmd0aC50aW1lcyBkbyB8aXwNCiAgICAgIGlmIHdvcmRb
aV0uY2hyID09IGd1ZXNzIHRoZW4NCiAgICAgICAgbWFza2VkX3dvcmRbaV0gPSBndWVzcw0KICAg
ICAgZW5kDQogICAgZW5kDQogIGVuZA0KICANCiAgcmV0dXJuIG1hc2tlZF93b3JkDQplbmQNCg0K
ZGVmIHBsYXlfZ2FtZSh3b3JkID0gIiIsIGxpZmVzID0gNiwgZ2l2ZV9vdXRwdXQgPSBmYWxzZSkN
CiAgI3VzZXIgZ2l2ZW4gd29yZA0KICB3b3JkID0gcmFuZG9tX3dvcmQgaWYgd29yZCA9PSAiIg0K
ICBtYXNrZWRfd29yZCA9IHdvcmQuZ3N1YigvXHcvLCAiLiIpDQogIGd1ZXNzID0gIiINCg0KICBw
bGF5ZXIgPSBQbGF5ZXIubmV3KG1hc2tlZF93b3JkKQ0KDQogIHdoaWxlKGxpZmVzID4gMCkNCiAg
ICAjQUkgZ3Vlc3NlcyBhIGxldHRlciBvciB3b3JkDQogICAgcHV0cyAiQUkgaXMgbG9va2luZyBm
b3IgPiN7bWFza2VkX3dvcmR9PCIgaWYgZ2l2ZV9vdXRwdXQNCiAgICBndWVzcyA9IHBsYXllci5n
dWVzcygpDQogICAgbmV3X3dvcmQgPSAiIg0KICAgIHdvbiA9IGZhbHNlDQogICAgcHV0cyAiQUkg
Z3Vlc3NlZCAnI3tndWVzc30nIiAgaWYgZ2l2ZV9vdXRwdXQNCiAgICBpZiBndWVzcy5sZW5ndGgg
PT0gMSB0aGVuDQogICAgICBtYXNrZWRfd29yZCA9IGNoZWNrX2Zvcl9sZXR0ZXJzKHdvcmQsIGd1
ZXNzLCBtYXNrZWRfd29yZCkNCiAgICAgIA0KICAgIGVsc2UgDQogICAgICBpZiBndWVzcy5sZW5n
dGggPiAxIHRoZW4NCiAgICAgICAgYnJlYWsgaWYgZ3Vlc3MgPT0gd29yZA0KICAgICAgICBsaWZl
cyAtPSAxDQogICAgICAgIG5leHQNCiAgICAgIGVsc2UNCiAgICAgICAgI25pbA0KICAgICAgZW5k
DQogICAgZW5kDQogICAgDQogICAgI3dyb25nIGd1ZXNzDQogICAgaWYgbm90IG1hc2tlZF93b3Jk
LmluY2x1ZGU/KGd1ZXNzKSB0aGVuDQogICAgICBsaWZlcyAtPSAxDQogICAgICBwdXRzICJBSSBs
b3N0IGEgbGlmZS4gI3tsaWZlc30gbGlmZXMgbGVmdC4iDQogICAgZWxzZSAgICANCiAgICAgICNm
b3VuZCB3b3JkDQogICAgICBpZiBtYXNrZWRfd29yZCA9PSB3b3JkIHRoZW4NCiAgICAgICAgYnJl
YWsNCiAgICAgIGVsc2UNCiAgICAgICAgI2ZvdW5kIGEgbGV0dGVyDQogICAgICAgIHBsYXllci53
b3JkID0gbWFza2VkX3dvcmQNCiAgICAgICAgbmV4dA0KICAgICAgZW5kDQogICAgZW5kDQogIGVu
ZA0KDQogIGlmIGxpZmVzID4gMCB0aGVuDQogICAgd29uID0gdHJ1ZQ0KICBlbHNlDQogICAgI2dp
dmUgd29yZCB0byBwbGF5ZXIgdG8gZXh0ZW5kIGRpY3Rpb25hcnkNCiAgICBwbGF5ZXIud29yZCA9
IHdvcmQNCiAgICB3b24gPSBmYWxzZQ0KICBlbmQNCiAgDQogIHJldHVybiB3b24sIHdvcmQsIGxp
ZmVzDQplbmQgI29mIHBsYXlfZ2FtZQ0KDQp3b24gPSBmYWxzZQ0Kd29yZCA9ICIiDQpsaWZlcyA9
IDYNCmlmIEFSR1YubGVuZ3RoID4gMA0KICBBUkdWLmVhY2ggZG8gfGFyZ3wNCiAgICBvcHRpb24g
PSBhcmcuc3BsaXQoIj0iKQ0KICAgIGNhc2Ugb3B0aW9uWzBdDQogICAgICB3aGVuICItdyINCiAg
ICAgICAgd29yZCA9IG9wdGlvblsxXQ0KICAgICAgd2hlbiAiLWwiDQogICAgICAgIGxpZmVzID0g
b3B0aW9uWzFdLnRvX2kNCiAgICBlbmQNCiAgZW5kDQplbmQNCg0Kd29uLCB3b3JkLCBsaWZlcyA9
IHBsYXlfZ2FtZSh3b3JkLCBsaWZlcywgdHJ1ZSkNCg0KaWYgd29uIHRoZW4NCiAgcHV0cyAiQUkg
d29uISBJdCBndWVzc2VkIFwiI3t3b3JkfVwiIHdpdGggI3tsaWZlc30gbGlmZXMgbGVmdC4iDQpl
bHNlDQogIHB1dHMgIkF3d3chIExvc3QhIEFJIGNvdWxkbid0IGd1ZXNzIFwiI3t3b3JkfVwiLiIN
CmVuZA0K
------=_Part_7791_32033177.1184181018598--
 
T

Thomas Wieczorek

A few words to my solution:
- It saves the dictionary in a yaml file. If the AI doesn't know a
word, it will add it to the dictionary
- it guesses letters which have the highest possibility

It is a bit rough. I am happy about every suggestion to improve it.

2007/7/11 said:
I was busy until today.

Here's my solution and my first quiz solution since I learn Ruby. It
wasn't that hard. I learned a lot about Ruby with it.
ruby hangman.rb [-w=word] [-l=lifes]
If you don't pass a word it will choose a random word from the
dictionary. Lifes is set to 6 if you don't provide it.
 
J

James Edward Gray II

A second version of my code.

One last tiny tweak.
First, this is a tiny words.rb lib used by both the guesser and
test scripts:

#!/usr/bin/env ruby -wKU

WORDS_CASH_FILE = "words.cache"

if File.exist? WORDS_CASH_FILE
WORDS = File.open(WORDS_CASH_FILE) { |file| Marshal.load(file) }
else
WORDS = File.open( ARGV.find { |arg| arg =~ /\A[^-]/ } ||
"/usr/share/dict/words" ) do |dict|
dict.inject(Hash.new) do |all, word|
all.update(word.delete("^A-Za-z").downcase => true)
end.keys

Changing that line to:

end.keys.sort_by { |w| [w.length, w] }

helps me see where I'm at in the tests.
end
File.open(WORDS_CASH_FILE, "w") { |file| Marshal.dump(WORDS, file) }
end

__END__

James Edward Gray II
 
J

James Edward Gray II

Last tweak, I promise!

Here's a new version of the guesser script that fairs a bit better.
I found the improvement by trying some changes and running my testing
script:

#!/usr/bin/env ruby -wKU

puts "One moment..."
puts
require "words"

def frequency(words)
freq = Hash.new(0)
words.each do |word|
word.split("").each { |letter| freq[letter] += word.count(letter) }
end
freq
end
FREQ = frequency(WORDS).sort_by { |_, count| -count }.map { |letter,
_| letter }

choices = WORDS
guesses = Array.new

loop do
puts guesses.empty? ?
"Please enter a word pattern (_ _ _ _ for example):" :
"Please update your pattern according to my guess (_ i _ _
for example):"
$stdout.flush
pattern = $stdin.gets.to_s.delete("^A-Za-z_")

if (guesses - pattern.delete("_").split("")).size > 5 and
pattern.include? "_"
puts "I'm out of guesses. You win."
elsif not pattern.include? "_"
puts "I guessed your word. Pretty smart, huh?"
else
choices = choices.grep(/\A#{pattern.tr("_", ".")}\Z/i)
guess = frequency(choices).
reject { |letter, _| guesses.include? letter }.
sort_by { |letter, count| [-count, FREQ.index(letter)] }.
first.first rescue nil

guesses << guess
puts "I guess the letter '#{guess}'."
puts
next
end

puts
if ARGV.include? "--loop"
choices = WORDS
guesses = Array.new
else
break
end
end

__END__

James Edward Gray II
 
J

James Edward Gray II

Last tweak, I promise!

This time I really mean last. ;)

I found another change that improves the algorithm:

#!/usr/bin/env ruby -wKU

puts "One moment..."
puts
require "words"

def frequency(words)
freq = Hash.new(0)
words.each do |word|
word.split("").each { |letter| freq[letter] += word.count(letter) }
end
freq
end
FREQ = frequency(WORDS).sort_by { |_, count| -count }.map { |letter,
_| letter }

choices = WORDS
guesses = Array.new

loop do
puts guesses.empty? ?
"Please enter a word pattern (_ _ _ _ for example):" :
"Please update your pattern according to my guess (_ i _ _
for example):"
$stdout.flush
pattern = $stdin.gets.to_s.delete("^A-Za-z_")

bad_guesses = guesses - pattern.delete("_").split("")
if bad_guesses.size > 5 and pattern.include? "_"
puts "I'm out of guesses. You win."
elsif not pattern.include? "_"
puts "I guessed your word. Pretty smart, huh?"
else
choices = choices.grep(
bad_guesses.empty? ?
/\A#{pattern.tr("_", ".")}\Z/i :
/\A(?!.*[#{bad_guesses.join}])#{pattern.tr("_", ".")}
\Z/i
)
guess = frequency(choices).
reject { |letter, _| guesses.include? letter }.
sort_by { |letter, count| [-count, FREQ.index(letter)] }.
first.first rescue nil

guesses << guess
puts "I guess the letter '#{guess}'."
puts
next
end

puts
if ARGV.include? "--loop"
choices = WORDS
guesses = Array.new
else
break
end
end

__END__

James Edward Gray II
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

No members online now.

Forum statistics

Threads
473,744
Messages
2,569,484
Members
44,904
Latest member
HealthyVisionsCBDPrice

Latest Threads

Top