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

ruby-talk
1

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

2

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

3

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

···

On 4/11/08, Matthew Moss <matthew.moss@gmail.com> wrote:

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.

---
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/@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

4

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