[QUIZ] Word Search Generator (#159, again)

[Matthew Moss]

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

<http://matthew.moss.googlepages.com/home>.

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.

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

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

 

[Matthew Moss]

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

 

[Adam Shelly]

The three rules of Ruby Quiz 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, lace, :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) if words_done}
end
end
end

#returns the obfuscated grid
def to_s
puz = @g.dup
puz.size.times{|i|puz=('a'..'z').to_a[rand(26)] if puz==?.}
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/@w*2, 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

 

[Matthew Moss]

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