Word Blender (#108)

Here’s my submission. There are two programs: the first builds a set
of puzzles from a decent word list I found on line. Files like
/usr/dict/words have too many obscure words. The second is a (very)
simplistic game interface.

A “puzzle” is just a string of six or more 3-6 letter words, sorted by
length. The output of the first program is just one line per puzzle,
with the words separated by colons. The words are ROT13 encoded. The
puzzles.rb program generates 905 different puzzles.

Bob S.

---------- puzzles.rb ----------

puzzles.rb

generate puzzles for use by wordblend.rb program

usage: ruby puzzles.rb >puzzles.dat

require ‘open-uri’
require ‘yaml’

these urls point to text files with lists of 2000 commonest

English word “families”, including plurals and other forms.

this ends up generating reasonably good puzzles.

URIS = %w{
http://www1.harenet.ne.jp/~waring/vocab/wordlists/full1000.txt
http://www1.harenet.ne.jp/~waring/vocab/wordlists/full2000.txt
}

minimum number of words necessary to form a puzzle

MIN_SIZE = 6

define some helper functions

class String

returns string with characters in sorted order

def sort
split(//).sort.join
end

returns true if s is a subword of the string. both

the string and s must be sorted!

def subword?(s)
i = j = 0
while j < s.length
i += 1 while i < length and self[i] != s[j]
i < length or return false
j += 1
i += 1
end
true
end

end

grab the 3-6 letter words from word lists. sort each word by

character (e.g. ‘test’ becomes ‘estt’), and then accumulate

STDERR.puts “Fetching words…”
words = Hash.new {|h,k| h[k] = []}
URIS.each do |uri|
open(uri) do |f|
f.read.split.select {|w| w.length >= 3 and w.length <= 6}.each do
|word|
word.upcase!
sword = word.sort
words[sword] << word
end
end
end

find puzzles by looking at which sorted words are contained in

other six-character sorted words.

STDERR.puts “Finding puzzles…”
n = 0
words.keys.select {|w| w.length == 6}.each do |key|
puzzle = words.select {|ssub, subs| key.subword?(ssub)}.collect {|a|
a.last}.flatten.sort_by {|w| “#{w.length}#{w}”}
next if puzzle.size < MIN_SIZE
puts puzzle.join(‘:’)
end

---------- wordblend.rb ----------

wordblend.rb

simplistic Word Blend puzzle game

uses puzzles.dat file created by separate puzzles.rb program

class String
def rot13
tr ‘A-Za-z’, ‘N-ZA-Mn-za-m’
end
end

class Puzzle

attr_reader :words, :letters, :board

def self.pick
@@puzzles ||= IO.readlines(‘puzzles.dat’)
new(@@puzzles[rand(@@puzzles.size)].chomp.rot13.split(‘:’))
end

def initialize(words)
@words = words
scramble
@board = words.collect {|w| w.gsub(/./, ‘-’)}
end

def scramble
@letters = words.last.split(//).sort_by {rand}.join
scramble if words.include? @letters
end

def help
puts “Enter ‘Q’ to give up, ‘S’ to scramble letters”
end

def play
help
turn while board != words
puts board
end

def turn
puts board
puts
puts letters
while true
print "? "
guess = gets.strip.upcase
if guess == ‘’
help
redo
end
if guess == ‘S’
scramble
puts letters
redo
end
@board = words.dup if guess == ‘Q’
i = words.index(guess) and board[i] = guess
break
end
end

end

play a random game

p = Puzzle.pick
p.play

The regexes for me are fairly fast. For my regex that weeds out words
with repeated characters (I posted it before and it is fairly lengthy,
so I won’t post it again unless by request), a 10,000 word dictionary
(the one in my /usr/share/dict/words) takes less than .5 seconds to pick
the baseword and all related words. Under .2 seconds if it doesn’t weed
out words with repeated characters.

One thing I can see to optimize in your method is all the sorting. I
haven’t tested the performance yet, but sets might be the answer.

require ‘set’

class String
def letters
split(//).to_set
end
end

baseWordSet = baseWord.letters
dict.select {|x| x.letters.subset?(baseWordSet)}

It’s more readable, IMHO, at least.

Dan

On 1/9/07, Bob S. [email protected] wrote:

want to exclude reusing the same letter more than once

This could be sped up by precompiling the regexes I would guess.

Bob

Very interesting, you create a matching in the opposite direction,
matching
against the picked word vs against the dictionary of words, very nice. I
like this more than Daniel’s approach since it doesn’t involve creating
Regexps which grow as n^2 compared to the length of our word. This ends
up
going through all the words (length 3 to 6 anyhow) in the dictionary to
find
the matches. Finding all permutations would go through the dictionary
roughly the number of subwords times, taking log of the length of the
dictionary number of steps each time. For all but the largest of words
with
lots of subwords would the latter be slower, but the Regexp approach is
very
nice and simple, and I can’t decide what I like more.

It does bother me a bit though that I don’t know how long each regexp
takes
to run to get its match as I know that some Regexps do take quite a
while to
match or exclude some words, just not sure if this one would be one of
them.

If you are using *nix (unix, linux) then you can run "time " at the command line. This might work with Macs as well
because they are based on unix but I don’t have one so I’m not sure.

From within Ruby, you can do this:
require ‘benchmark’

puts Benchmark.measure do

program code here.

end

I agree that this was one of the best Ruby Q.zes. It is simple and
yet has different, but equally good, types of solutions (regex, sets,
etc.). I also enjoyed the opportunity to explore sets and things; more
RQs that can involve the standard library would be awesome.

Dan

On 1/9/07, Daniel F. [email protected] wrote:

    end

end

baseWordSet = baseWord.letters
dict.select {|x| x.letters.subset?(baseWordSet)}

It’s more readable, IMHO, at least.

Dan

I used sets in my submission, and the letters of each 6 letter word were
split in the above fashion so as to provide faster scanning (at least
according to one of the books I was reading the night before - please
correct me if I’m wrong). The answers to these questions was actually
what
I was hoping to hear when I said any feedback would be appreciated :slight_smile:

And yes, it’s definitely more readable - I wrestled with the idea of how
to
see if one array was a subset of another (and which way was more
efficient)
when I came across the concept of a set for the first time.
s2.subset?(s1)
sure made life easy and using it made it a lot easier to understand what
my
code was doing just by reading it.

One last question, which I’ve been thinking about but not able to
dedicate a
lot of time to is this: how do you ‘benchmark’ the speed of individual
programs? I’ve been wondering how fast my program is compared to others
since I wrote it.

And finally, here’s to you, Mr. Ruby Q. creator guy, for coming up
with a
Ruby quiz that really peaked my interest :slight_smile:

On Fri, 05 Jan 2007 22:05:52 +0900, Ruby Q. wrote:

all be constructed from the same six letters. This list must contain at least
one six-letter word.

Bonus points for building a completely functional game!

require ‘rubygems’
require ‘facets/core/enumerable/permutation’
require ‘set’

#usage: texttwist [word]

specifying a word will use /usr/share/dict/words to solve a TextTwist

problem. If no word is specified, a random word will be selected, to

generate an round of texttwist.

#load dictionary
matcher=Set.new
allwords=Array.new
open("/usr/share/dict/words") do |f|
f.each do |line|
line.chomp!
next if line !~ /^[a-z]+$/
matcher << line if line.length<=6
allwords << line if line.length==6
end
end

#generate subwords of a word
word=ARGV[0] || allwords[rand(allwords.length)]
thiswordmatcher=Set.new
word.split(//).each_permutation do |perm|
perm=perm.join
(3…6).each do |len|
candidate=perm[0,len]
if matcher.include?(candidate)
thiswordmatcher << candidate
end
end
end

#output
puts word
puts “======”
thiswordmatcher.each do |subword|
puts subword
end

Hi Ken,

Ken B. wrote:

#load dictionary
matcher=Set.new
allwords=Array.new

thiswordmatcher=Set.new

I’m interested in why you used a set for matcher and an array for
allwords. Was this a kindof random decision (many of mine are!) or is
there something that allwords needed to be able to do and so is an array
or vice versa?

Thanks,
Dan

On Wed, 10 Jan 2007 11:17:24 +0900, Daniel F. wrote:

allwords. Was this a kindof random decision (many of mine are!) or is
there something that allwords needed to be able to do and so is an array
or vice versa?

allwords needs array indexing to pick a random word from the array.
The sets, however, need duplicate removal and/or need include? to
operate
in O(1).

–Ken

On Jan 7, 2007, at 6:47 AM, Fedor L. wrote:

It just so happened that I was learning ruby last summer and wrote
a program to cheat for me at TextTwist. Needless to say the game
got boring really fast, but it was neat writing the program. I’ve
modified it a bit to instead play the game, but I’m a fairly new
user and would appreciate any feedback, both ruby related and
general programming.

Looking pretty good to me.

Also, I have the problem that when running this on Windows it
doesn’t allow me to manipulate files with Ruby, giving me a
Permission Denied error on File.open. Any idea why this might be?

Well, you pass open() three arguments:

File.open(“reducedwordlist#{i}.txt”, “w”, File::CREAT) do |fout|

I’m pretty sure that form has the third argument being the
permissions of the new file. Take out the File::CREAT, the “w” mode
string handles that automatically, and see if that fixes it up.

Hope that helps.

James Edward G. II

On Jan 9, 2007, at 6:28 PM, Daniel F. wrote:

If you are using *nix (unix, linux) then you can run "time " at the command line. This might work with Macs as well
because they are based on unix but I don’t have one so I’m not sure.

It works on a Mac, sure.

James Edward G. II

On Jan 7, 2007, at 6:41 PM, Daniel F. wrote:

Oops, that doesn’t match {3,6} just {6}.

regex = /^([a-z])(?!\1)([a-z])(?!\1|\2)([a-z])(?:(?!\1|\2|\3)([a-
z]))?(?:(?!\1|\2|\3|\4)([a-z]))?(?:(?!\1|\2|\3|\4|\5)([a-z]))?$/

Wow. That’s darn clever, but probably over abusing regular
expressions a bit, don’t you think? :wink:

James Edward G. II

On Jan 9, 2007, at 6:28 PM, Daniel F. wrote:

I also enjoyed the opportunity to explore sets and things; more RQs
that can involve the standard library would be awesome.

You make the quizzes and I will run them:

[email protected]

James Edward G. II

On Jan 9, 2007, at 6:11 PM, Jason M. wrote:

And finally, here’s to you, Mr. Ruby Q. creator guy, for coming
up with a Ruby quiz that really peaked my interest :slight_smile:

Thank Ben B… It was his idea.

James Edward G. II

That makes sense :).

On a side note, I did make some methods for getting a rand value from
any enumerable (they can be integrated as instance methods):

def rand_value_each(enum)
index = rand(enum.size)
curr = 0
enum.each {|x| return [x].flatten.last if curr == index; curr += 1 }
end

def rand_value_to_a(enum)
[rand_value_ary(enum.to_a)].flatten.last
end

def rand_value_ary(ary)
ary[rand(ary.size)]
end

Dan

It does hurt readability, however, if it is in a variable then the
readability goes up a little. regex is probably a bad name, tho.

noRepeats3-6Letters = …
dict.scan(noRepeats3-6Letters)

Even better would be a method that creates a regex for an arbitrary
length so it’s ugliness is never shown in its entirety in one
concentrated spot. The king of readability, I admit, doesn’t involve
/regexp?e[ns]/ at all.

class Array
def uniq?
(uniq == self)
end
end

class String
def letters
split(//)
end
end

dict.select {|x| x.length.between?(3, 6) && x.letters.uniq?}

dan

On Jan 10, 2007, at 2:18 PM, Daniel F. wrote:

On a side note, I did make some methods for getting a rand value
from any enumerable (they can be integrated as instance methods):

def rand_value_each(enum)
index = rand(enum.size)

Enumerable doesn’t have a size() method.

curr = 0
enum.each {|x| return [x].flatten.last if curr == index; curr += 1 }
end

James Edward G. II

T. W. Urp wrote:

Vincent F. wrote long time ago:

“Try transposing your matrix first, if that is what you need. Are you
dealing with transformation matrices (which are not real matrices) ?”
Yes indeed, SVG 2D transformation matrices. These matrices are 3x3.

They never taught me about transposing, just matrix multiplication, and
googel didnt help either. What is transposing (for transformation matrices)?

If you have a 3x3 matrix like:
a b c
d e f
g h i
then its transpose is:
a d g
b e h
c f i

If you have a 2x3 matrix like:
a b c
d e f
then its transpose is:
a d
b e
c f

In other words, swap rows and columns. (Excel even knows how to do
this, under Paste Special.)

T. W. Urp wrote:

They never taught me about transposing, just matrix multiplication, and
googel didnt help either. What is transposing (for transformation matrices)?

Also, RTFM :slight_smile:

C:>ri transpose
More than one method matched your request. You can refine
your search by asking for information on one of:

 Array#transpose, Matrix#transpose

C:>ri Array.transpose

Array#transpose
array.transpose -> an_array

 Assumes that _self_ is an array of arrays and transposes the rows
 and columns.

    a = [[1,2], [3,4], [5,6]]
    a.transpose   #=> [[1, 3, 5], [2, 4, 6]]

C:>ri Matrix.transpose

Matrix#transpose
transpose()

 Returns the transpose of the matrix.

   Matrix[[1,2], [3,4], [5,6]]
     => 1 2
        3 4
        5 6
   Matrix[[1,2], [3,4], [5,6]].transpose
     => 1 3 5
        2 4 6


 (also known as t)

Vincent F. wrote long time ago:

“Try transposing your matrix first, if that is what you need. Are you
dealing with transformation matrices (which are not real matrices) ?”
Yes indeed, SVG 2D transformation matrices. These matrices are 3x3.

They never taught me about transposing, just matrix multiplication, and
googel didnt help either. What is transposing (for transformation
matrices)?

Cameron McBride wrote:

“the included Matrix library in ruby is NOT FAST. There are other libs
that do this on the C level, such as NArray, that will allow much better
performance for some graphical uses.”

Thanks. While my simple graphic
genny isnt time-critical, and a SVG file might take 2-3 seconds to
render,
I will look into NArray. Is NArray what you would recommend?

“T. W. Urp” [email protected] writes:

Vincent F. wrote long time ago:

“Try transposing your matrix first, if that is what you need. Are you
dealing with transformation matrices (which are not real matrices) ?”
Yes indeed, SVG 2D transformation matrices. These matrices are 3x3.

They never taught me about transposing, just matrix multiplication,
and googel didnt help either. What is transposing (for
transformation matrices)?

Matthew 20:16 for the dimensions.