From: Adam Shelly <adam.shelly@...>
Date: 2008-04-16T08:53:23+09:00
Subject: Re: [QUIZ] Word Search Generator (#159, again)

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.

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