Anagram Generator in Ruby

generate.rb

#!/usr/bin/env ruby

# usage:
# ruby generate.rb phrase wordfile
#
# example:
# ruby generate.rb "be a mean cat" words.txt
# => a act be name
# => a be cat name
# => a act bee man
# => a bee cat man

class AnagramGenerator
  def initialize(words, phrase)
    @words = words.group_by { |w| normalize(w).length }
    @phrase = normalize(phrase)
  end

  # returns a string with only alpha characters (no spaces or symbols)
  def normalize(text)
    text.downcase.scan(/[a-z]/).join
  end

  # removes each character (individually) of a word and returns the remaining phrase
  # returns nil if all characters were not found
  def remove_word(word, phrase)
    phrase.chars.to_a.tap do |chars|
      word.chars.each do |char|
        if index = chars.index(char)
          chars.delete_at(index)
        else
          return nil
        end
      end
    end.join
  end

  # recursively searches for matching words in the phrase
  def anagrams(phrase=nil)
    phrase ||= @phrase
    return [[]] if phrase.empty?
    all = []
    (1..phrase.length).each do |length|
      ph = phrase.dup
      Array(@words[length]).each do |word|
        normal = normalize(word)
        if phrase_without_word = remove_word(normal, ph)
          anagrams(phrase_without_word).each do |set|
            all << ([word] + set).sort
          end
        end
      end
    end
    all.uniq
  end
end

if $0 == __FILE__
  words = File.read(ARGV[1]).split(/\r?\n/)
  puts AnagramGenerator.new(words, ARGV[0]).anagrams.map { |p| p.join(' ') }
end

generate_spec.rb

require 'rspec'
require './generate'

describe AnagramGenerator do
  describe '#remove_word' do
    before do
      @gen = AnagramGenerator.new([], '')
    end

    it 'removes a single character' do
      @gen.remove_word('b', 'abc').should == 'ac'
    end

    it 'removes multiple characters' do
      @gen.remove_word('ba', 'abc').should == 'c'
    end

    it 'returns nil if all characters were not found' do
      @gen.remove_word('baz', 'abc').should be_nil
    end
  end

  describe '#anagrams' do
    it 'finds single word matches' do
      AnagramGenerator.new(['a', 'b', 'c'], 'b').anagrams.should == [['b']]
    end

    it 'finds multi-word matches' do
      AnagramGenerator.new(['ba', 'll', 'b', 'a', 'l'], 'ball').anagrams.should == [['a', 'b', 'l', 'l'],
                                                                                    ['a', 'b', 'll'],
                                                                                    ['ba', 'l', 'l'],
                                                                                    ['ba', 'll']]
      AnagramGenerator.new(['you', 'cat', 'act'], 'youcat').anagrams.should == [['cat', 'you'],
                                                                                ['act', 'you']]
    end
  end
end

words.txt

a
able
about
account
acid
across
act
addition
adjustment
advertisement
after
again
against
agreement
air
all
almost
among
amount
amusement
and
angle
angry
animal
answer
ant
any
apparatus
apple
approval
arch
argument
arm
army
art
as
at
attack
attempt
attention
attraction
authority
automatic
awake
baby
back
bad
bag
balance
ball
band
base
basin
basket
bath
be
beautiful
because
bed
bee
before
behaviour
belief
bell
bent
berry
between
bird
birth
bit
bite
bitter
black
blade
blood
blow
blue
board
boat
body
boiling
bone
book
boot
bottle
box
boy
brain
brake
branch
brass
bread
breath
brick
bridge
bright
broken
brother
brown
brush
bucket
building
bulb
burn
burst
business
but
butter
button
by
cake
camera
canvas
card
care
carriage
cart
cat
cause
certain
chain
chalk
chance
change
cheap
cheese
chemical
chest
chief
chin
church
circle
clean
clear
clock
cloth
cloud
coal
coat
cold
collar
colour
comb
come
comfort
committee
common
company
comparison
competition
complete
complex
condition
connection
conscious
control
cook
copper
copy
cord
cork
cotton
cough
country
cover
cow
crack
credit
crime
cruel
crush
cry
cup
cup
current
curtain
curve
cushion
damage
danger
dark
daughter
day
dead
dear
death
debt
decision
deep
degree
delicate
dependent
design
desire
destruction
detail
development
different
digestion
direction
dirty
discovery
discussion
disease
disgust
distance
distribution
division
do
dog
door
doubt
down
drain
drawer
dress
drink
driving
drop
dry
dust
ear
early
earth
east
edge
education
effect
egg
elastic
electric
end
engine
enough
equal
error
even
event
ever
every
example
exchange
existence
expansion
experience
expert
eye
face
fact
fall
false
family
far
farm
fat
father
fear
feather
feeble
feeling
female
fertile
fiction
field
fight
finger
fire
first
fish
fixed
flag
flame
flat
flight
floor
flower
fly
fold
food
foolish
foot
for
force
fork
form
forward
fowl
frame
free
frequent
friend
from
front
fruit
full
future
garden
general
get
girl
give
glass
glove
go
goat
gold
good
government
grain
grass
great
green
grey
grip
group
growth
guide
gun
hair
hammer
hand
hanging
happy
harbour
hard
harmony
hat
hate
have
he
head
healthy
hear
hearing
heart
heat
help
high
history
hole
hollow
hook
hope
horn
horse
hospital
hour
house
how
humour
I
ice
idea
if
ill
important
impulse
in
increase
industry
ink
insect
instrument
insurance
interest
invention
iron
island
jelly
jewel
join
journey
judge
jump
keep
kettle
key
kick
kind
kiss
knee
knife
knot
knowledge
land
language
last
late
laugh
law
lead
leaf
learning
leather
left
leg
let
letter
level
library
lift
light
like
limit
line
linen
lip
liquid
list
little
living
lock
long
look
loose
loss
loud
love
low
machine
make
male
man
manager
map
mark
market
married
mass
match
material
may
meal
measure
meat
medical
meeting
memory
metal
middle
military
milk
mind
mine
minute
mist
mixed
money
monkey
month
moon
morning
mother
motion
mountain
mouth
move
much
muscle
music
nail
name
narrow
nation
natural
near
necessary
neck
need
needle
nerve
net
new
news
night
no
noise
normal
north
nose
not
note
now
number
nut
observation
of
off
offer
office
oil
old
on
only
open
operation
opinion
opposite
or
orange
order
organization
ornament
other
out
oven
over
owner
page
pain
paint
paper
parallel
parcel
part
past
paste
payment
peace
pen
pencil
person
physical
picture
pig
pin
pipe
place
plane
plant
plate
play
please
pleasure
plough
pocket
point
poison
polish
political
poor
porter
position
possible
pot
potato
powder
power
present
price
print
prison
private
probable
process
produce
profit
property
prose
protest
public
pull
pump
punishment
purpose
push
put
quality
question
quick
quiet
quite
rail
rain
range
rat
rate
ray
reaction
reading
ready
reason
receipt
record
red
regret
regular
relation
religion
representative
request
respect
responsible
rest
reward
rhythm
rice
right
ring
river
road
rod
roll
roof
room
root
rough
round
rub
rule
run
sad
safe
sail
salt
same
sand
say
scale
school
science
scissors
screw
sea
seat
second
secret
secretary
see
seed
seem
selection
self
send
sense
separate
serious
servant
sex
shade
shake
shame
sharp
sheep
shelf
ship
shirt
shock
shoe
short
shut
side
sign
silk
silver
simple
sister
size
skin

skirt
sky
sleep
slip
slope
slow
small
smash
smell
smile
smoke
smooth
snake
sneeze
snow
so
soap
society
sock
soft
solid
some

son
song
sort
sound
soup
south
space
spade
special
sponge
spoon
spring
square
stage
stamp
star
start
statement
station
steam
steel
stem
step
stick
sticky
stiff
still
stitch
stocking
stomach
stone
stop
store
story
straight
strange
street
stretch
strong
structure
substance
such
sudden
sugar
suggestion
summer
sun
support
surprise
sweet
swim
system
table
tail
take
talk
tall
taste
tax
teaching
tendency
test
than
that
the
then
theory
there
thick
thin
thing
this
thought
thread
throat
through
through
thumb
thunder
ticket
tight
till
time
tin
tired
to
toe
together
tomorrow
tongue
tooth
top
touch
town
trade
train
transport
tray
tree
trick
trouble
trousers
true
turn
twist
umbrella
under
unit
up
use
value
verse
very
vessel
view
violent
voice
waiting
walk
wall
war
warm
wash
waste
watch
water
wave
wax
way
weather
week
weight
well
west
wet
wheel
when
where
while
whip
whistle
white
who
why
wide
will
wind
window
wine
wing
winter
wire
wise
with
woman
wood
wool
word
work
worm
wound
writing
wrong
year
yellow
yes
yesterday
you
young