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

Discussion in 'Ruby' started by Matthew Moss, Apr 11, 2008.

  1. Matthew Moss

    Matthew Moss Guest

    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, Apr 11, 2008
    #1
    1. Advertising

  2. Matthew Moss

    Matthew Moss Guest

    Re: Word Search Generator (#159, again)

    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.)
    Matthew Moss, Apr 11, 2008
    #2
    1. Advertising

  3. Matthew Moss

    Adam Shelly Guest

    On 4/11/08, Matthew Moss <> 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) 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
    Adam Shelly, Apr 16, 2008
    #3
  4. Matthew Moss

    Matthew Moss Guest

    Re: Word Search Generator (#159, again)

    Apologies for the late summary... it will be coming today. New quiz
    will show up tomorrow.
    Matthew Moss, Apr 18, 2008
    #4
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. The Jetman
    Replies:
    0
    Views:
    302
    The Jetman
    Oct 31, 2003
  2. Ruby Quiz

    [QUIZ] Word Search (#107)

    Ruby Quiz, Dec 29, 2006, in forum: Ruby
    Replies:
    6
    Views:
    131
    William James
    Jan 3, 2007
  3. Matthew Moss

    [QUIZ] Food Database (#159)

    Matthew Moss, Mar 14, 2008, in forum: Ruby
    Replies:
    14
    Views:
    188
    ThoML
    Mar 23, 2008
  4. Matthew Moss

    [QUIZ] Guardian of Middle-earth (#159)

    Matthew Moss, Apr 4, 2008, in forum: Ruby
    Replies:
    8
    Views:
    89
    Matthew Moss
    Apr 10, 2008
  5. Matthew Moss
    Replies:
    3
    Views:
    137
    Spoton Software
    Apr 24, 2009
Loading...

Share This Page