# Word Search Generator (#159, again)

**URL:** <https://www.ruby-forum.com/t/word-search-generator-159-again/134521>\
**Category:** Ruby\
**Created:** [April 11, 2008, 5:51pm UTC](https://www.ruby-forum.com/t/word-search-generator-159-again/134521 "2008-04-11T17:51:47Z")\
**Posts on this page:** 4\
**Page:** 1

<div class="post-metadata">

**Author:** ![mansfiem](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/m/fbc32d/32.png) [@mansfiem](https://www.ruby-forum.com/u/mansfiem)\
**Post date:** [April 11, 2008, 5:51pm UTC](https://www.ruby-forum.com/t/word-search-generator-159-again/134521/1 "2008-04-11T17:51:47Z")

</div>

Okay, hopefully the third time with #159 is the charm. I decided to  
give myself a week before representing the Guardian of Middle-earth  
quiz, so instead we have something new. I’ve focused on the core  
problem and not attempted to deal with all questions or possibilities  
in the description, so this should be better for y’all.

Anyway, onto the quiz!

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

The three rules of Ruby Q. 2:

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 Q. 2 by submitting ideas as often as you can! (A  
permanent, new website is in the works for Ruby Q. 2. Until then,  
please visit the temporary website at

3. Enjoy!

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

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

Quiz #159

Word Search Generator

A word search puzzle presents a grid of seemingly random letters and a  
list of words. The goal of the puzzle is to find and mark all the  
words from the list hidden within the grid, searching along straight  
lines (horizontal, vertical and diagonal).

Your task for this week’s quiz is to write a Ruby program that  
generates word search puzzles, given a list of words and the desired  
width and height for the puzzle. A call to the script will look like  
this:

```
genpuzzle.rb words.txt 6x8

```

The first argument is the list of words, one word per line in a text  
file. The second argument is the dimensions of the puzzle, width by  
height.

Your program should output two files. The first file, search.txt,  
should contain the puzzle itself. All characters should be separated  
by spaces to allow the puzzle solver room to mark found words. As an  
example, here is a 6x8 puzzle containing the words from “zero” to  
“nine”. (Please view with fixed-width font if this does not display  
properly in your browser or email program.)

```
e a e g g w
e e n i n t
r n o h h f
h q e g i r
t z i v u q
o e e o e l
w r f g e s
t o u s i x

```

The second file, solution.txt, should contain the same puzzle with the  
answers marked, like this:

```
e . e . . .
| |
e e-n-i-n t
| | /
r n o . h f
| \ / /
h . e g i r
| X / /
t z i v u .
  |/ / X
o e e o e .
| | / \
w r f . . s
| |
t o . s-i-x

```

---

<div class="post-metadata">

**Author:** ![mansfiem](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/m/fbc32d/32.png) [@mansfiem](https://www.ruby-forum.com/u/mansfiem)\
**Post date:** [April 11, 2008, 6:04pm UTC](https://www.ruby-forum.com/t/word-search-generator-159-again/134521/2 "2008-04-11T18:04:42Z")

</div>

If you want a list of words to play with (aside from “zero” to  
“nine”), here is a list I’ve been testing on my own solution. My quick-  
n-dirty naive solution can (usually) fit these into a 24x24 word  
search:

abstract  
algorithm  
argument  
block  
class  
closure  
condition  
constant  
continuation  
delegate  
evaluate  
exception  
expression  
factory  
function  
generator  
global  
identifier  
immutable  
inheritance  
instance  
interface  
iterator  
keyword  
literal  
local  
method  
message  
object  
operator  
overload  
parameter  
polymorphism  
primitive  
prototype  
recursion  
reference  
reflection  
scope  
stack  
statement  
template  
type  
virtual

(Note one thing I realized, after writing my first version of the  
code, is that “type” is a subword of “prototype”. Methinks I’ll amend  
my solution to warn about such things.)

---

<div class="post-metadata">

**Author:** ![mansfiem](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/m/fbc32d/32.png) [@mansfiem](https://www.ruby-forum.com/u/mansfiem)\
**Post date:** [April 18, 2008, 3:31pm UTC](https://www.ruby-forum.com/t/word-search-generator-159-again/134521/3 "2008-04-18T15:31:46Z")

</div>

Apologies for the late summary… it will be coming today. New quiz  
will show up tomorrow.

---

<div class="post-metadata">

**Author:** ![mansfiem](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/m/fbc32d/32.png) [@mansfiem](https://www.ruby-forum.com/u/mansfiem)\
**Post date:** [April 16, 2008, 1:54am UTC](https://www.ruby-forum.com/t/word-search-generator-159-again/134521/4 "2008-04-16T01:54:05Z")

</div>

On 4/11/08, Matthew M. [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid) wrote:

> The three rules of Ruby Q. 2:  
> Your task for this week’s quiz is to write a Ruby program that  
> generates word search puzzles, given a list of words and the desired  
> width and height for the puzzle.

Here’s my solution - it’s mostly brute force, but it does attempt to  
place the first letter of a new word on an existing letter in the  
grid. If it gets stuck it will remove some placed words and try again.  
It usually fits the list of programming words into a 20x20 grid, but  
sometimes it takes a long time to get there.

## -Adam

Directions = [[1,0],[1,1],[0,1],[-1,1],[-1,0],[-1,-1],[0,-1],[1,-1]]  
Mark = [‘|’, ‘\’, ‘-’, ‘/’, ‘|’, ‘\’, ‘-’, ‘/’]

#$ShowProgress = true

class CrossWord  
attr\_accessor :word, :place, :dir  
def initialize w  
@word=w  
@dir=0  
@place=nil  
end  
def unplaced?  
@place==nil  
end  
end

class CharGrid  
def initialize cols,rows  
@w=cols  
@h=rows  
@g=“.”_(@w_@h)  
@ref\_count = Array.new(@w\*@h){0}  
@iterations = 0  
end

#fills the grid with words  
def fill words  
iterations = 0  
@words = words.map{|w| CrossWord.new(w)}  
words\_todo = @words.select{|w|w.unplaced?}  
until words\_todo.empty?  
words\_todo.each{|cw| place cw }  
words\_todo = @words.select{|w|w.unplaced?}.sort\_by{rand}  
if (iterations+=1) %(@w+@h)==0  
#if we are getting stuck, try removing some words  
puts “#{togo = words\_todo.size} to go…”  
words\_done = (@words-words\_todo).sort\_by{rand}  
(togo\*2).times{|i| words\_todo\<\< remove(words\_done[i]) if  
words\_done[i]}  
end  
end  
end

#returns the obfuscated grid  
def to\_s  
puz = @g.dup  
puz.size.times{|i|puz[i]=(‘a’…‘z’).to\_a[rand(26)] if puz[i]==?.}  
sln=[]  
newwidth=(2\*@w-1)  
@h.times{|r| sln\<\<puz[r\*@w,@w].split(‘’)\*’ ’  
sln\<\<’ '\*newwidth  
}  
sln  
end

#returns the packed grid  
def pack  
s=‘’  
@h.times{|r| s\<\<@g[r\*@w,@w]\<\<“\n” }  
s  
end

#returns the exploded grid  
def solution  
sln=[]  
newwidth=(2\*@w-1)  
@h.times{|r| sln\<\<@g[r\*@w,@w].split(‘’)_’ ’  
sln\<\<’ 'newwidth  
}  
 @words.each\_with\_index{|cw,i|  
next unless cw.place  
pt = [cw.place/@w2, cw.place%@w_2]  
(cw.word.size-1).times {  
pt[0]+=Directions[cw.dir][0]  
pt[1]+=Directions[cw.dir][1]  
sln[pt[0]][pt[1]] =  
case sln[pt[0]][pt[1]]  
when 32 then Mark[cw.dir]  
when ?-,?| then ?+  
else ?X  
end  
pt[0]+=Directions[cw.dir][0]  
pt[1]+=Directions[cw.dir][1]  
}  
}  
sln  
end

private

#tries to put word in grid  
#starts search at overlap with previously placed words  
def place cw  
@words.sort\_by{rand}.each{|otherword|  
startpt = find\_overlap(cw, otherword)  
return if test\_place(cw, startpt)  
}  
end

#tests if cw overlaps with placed testword.  
#returns point of overlap if so.  
def find\_overlap cw, testword  
return nil if testword.unplaced?  
if (offset = testword.word.index cw.word[0])  
startpt = testword.place  
offset.times{startpt=nextp(startpt,testword.dir)}  
else  
startpt = nil  
end  
startpt  
end

# takes suggested starting point, or picks a random one, and

# tries to fit cw in grid - tests all 8 directions.

def test\_place cw, suggestion=nil  
dir=randDir  
start= suggestion || randStart(cw.word[0])  
8.times do  
pt = start  
good = true  
cw.word.each\_byte{|chr|  
good = (@g[pt]==?. || @g[pt]==chr) && (pt=nextp(pt,dir))  
break unless good  
}  
return add(cw, start, dir) if good  
dir=(dir+1)%8  
end  
nil  
end

#find next grid index in given direction  
def nextp pos, dir  
#don’t allow to step off the edge  
if (pos\<@w && (3…5).include?(dir)) or  
(pos+@w \>= @g.size && [0,1,7].include?(dir)) or  
(pos%@w == 0 && (5…7).include?(dir)) or  
(pos%@w+1 == @w && (1…4).include?(dir))  
return nil  
end  
pos+Directions[dir][0]\*@w+Directions[dir][1]  
end

#adds word at index in direction  
def add cw, idx, dir  
puts “+#{cw.word}” if $ShowProgress  
cw.dir = dir  
pt = cw.place = idx  
cw.word.each\_byte{|chr|  
@g[pt]=chr  
@ref\_count[pt]+=1  
pt=nextp(pt,dir)  
}  
return [idx,dir]  
end

#removes word from grid  
def remove cw  
p “-#{cw.word}” if $ShowProgress  
pt = cw.place  
cw.word.each\_byte{|chr|  
@g[pt]=?. if 0== (@ref\_count[pt]-=1)  
pt=nextp(pt,cw.dir)  
}  
cw.place=nil  
cw  
end

#finds random start for word begining with matchchar  
def randStart matchChar  
start = rand(@w\*@h)  
start= (start+1)%(@w\*@h) until (@g[start]==?. ||  
@g[start]==matchChar)  
start  
end

def randDir  
rand(8)  
end  
end

if **FILE** == $0  
gridsize = ARGV[1].split(‘x’).map{|v|v.to\_i}  
g = CharGrid.new \*gridsize  
words=File.open(ARGV[0],“r”).read.split.sort\_by{|s|s.length}.reverse  
puts “unsolvable!” or exit if (words[0].size\>gridsize.max)

g.fill words  
puts g.pack  
File.open(“search.txt”,“w”){|f|f.puts g.to\_s}  
File.open(“solution.txt”,“w”){|f|f.puts g.solution}  
end