[QUIZ] Crosswords (#10)

Discussion in 'Ruby' started by Ruby Quiz, Dec 3, 2004.

  1. Ruby Quiz

    Ruby Quiz Guest

    The three rules of Ruby Quiz:

    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 by submitting ideas as often as you can:

    http://www.grayproductions.net/ruby_quiz/

    3. Enjoy!

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

    For this, the tenth Ruby Quiz, let's tackle a classic problem. I've seen it
    just about everywhere in some form or another, but I believe Donald E. Knuth may
    have first made it a popular challenge.

    This week's quiz is to layout crossword puzzles. A puzzle layout will be
    provided in a file, who's name will be passed as a command-line argument. Those
    layouts will be formatted as such:

    X _ _ _ _ X X
    _ _ X _ _ _ _
    _ _ _ _ X _ _
    _ X _ _ X X X
    _ _ _ X _ _ _
    X _ _ _ _ _ X

    Xs denote filled in squares and _s are where a puzzle worker would enter
    letters. Each row of the puzzle is on a new line. The spaces are a readability
    tool and should be ignored by your program. In the final layout, these squares
    should look like this:

    ###### Filled in square
    ######
    ######
    ######

    ###### Letter square
    # #
    # #
    ######

    Now, when we combine these squares, we don't want to double up on borders, so:

    _ _
    X _

    should become:

    ###########
    # # #
    # # #
    ###########
    ###### #
    ###### #
    ###########

    As a style point, many crosswords drop filled squares on the outer edges. We
    wouldn't want our Ruby generated crosswords to be unfashionable so we better do
    that too.

    X _ X
    _ _ _

    Would render as:

    ######
    # #
    # #
    ################
    # # # #
    # # # #
    ################

    The final step of laying out a crossword puzzle is to number the squares for
    word placement. A square is numbered if it is the first square in a word going
    left to right or top to bottom. Numbers start at 1 and count up left to right,
    row by row going down.

    Putting all that together, here is a sample layout. (This was generated from
    the layout format at the top of this quiz.)

    #####################
    #1 # #2 #3 #
    # # # # #
    ####################################
    #4 # ######5 # #6 #7 #
    # # ###### # # # #
    ####################################
    #8 # #9 # # #10 # #
    # # # # # # # #
    ##################### ###########
    # ######11 # #
    # ###### # #
    ####################################
    #12 #13 # ######14 #15 # #
    # # # ###### # # #
    ####################################
    #16 # # # # #
    # # # # # #
    ##########################

    Solutions should output (only) the finished crossword to STDOUT.
     
    Ruby Quiz, Dec 3, 2004
    #1
    1. Advertisements

  2. Ruby Quiz

    jim Guest

    Here is my solution. This took a few more LOC than I expected.

    #!/usr/bin/env ruby

    class CrossWordPuzzle
    CELL_WIDTH = 6
    CELL_HEIGHT = 4

    attr_accessor :cell_width, :cell_height

    def initialize(file)
    @file = file
    @cell_width = CELL_WIDTH
    @cell_height = CELL_HEIGHT

    build_puzzle
    end

    #######
    private
    #######

    def build_puzzle
    parse_grid_file
    drop_outer_filled_boxes
    create_numbered_grid
    end

    def parse_grid_file
    @grid = File.read(@file).split(/\n/)
    @grid.collect! { |line| line.split }
    @grid_width = @grid.first.size
    @grid_height = @grid.size
    end

    def drop_outer_filled_boxes
    loop {
    changed = 0
    changed += _drop_outer_filled_boxes(@grid)
    changed += _drop_outer_filled_boxes(t = @grid.transpose)
    @grid = t.transpose
    break if 0 == changed
    }
    end

    def _drop_outer_filled_boxes(ary)
    changed = 0
    ary.collect! { |row|
    r = row.join
    changed += 1 unless r.gsub!(/^X|X$/, ' ').nil?
    changed += 1 unless r.gsub!(/X | X/, ' ').nil?
    r.split(//)
    }
    changed
    end

    def create_numbered_grid
    mark_boxes(@grid)
    grid_prime = @grid.transpose
    mark_boxes(grid_prime)

    count = '0'
    @numbered_grid = []
    @grid.each_with_index { |row, i|
    r = []
    row.each_with_index { |col, j|
    r << case col + grid_prime[j]
    when /#/ then count.succ!.dup
    else col
    end
    }
    @numbered_grid << r
    }
    end

    # place '#' in boxes to be numbered
    def mark_boxes(grid)
    grid.collect! { |row|
    r = row.join
    r.gsub!(/([X ])([\#_]{2,})/) { "#{$1}##{$2[1..-1]}" }
    r.gsub!(/^([\#_]{2,})/) { |m| m[0]=?#; m }
    r.split(//)
    }
    end

    def cell(data)
    c = []
    case data
    when 'X'
    @cell_height.times { c << ['#'] * @cell_width }
    when ' '
    @cell_height.times { c << [' '] * @cell_width }
    when /\d/
    tb = ['#'] * @cell_width
    n = sprintf("\#%-*s\#", @cell_width-2, data).split(//)
    m = sprintf("#%-#{@cell_width-2}s#", ' ').split(//)
    c << tb << n
    (@cell_height-3).times { c << m }
    c << tb
    when '_'
    tb = ['#'] * @cell_width
    m = ['#'] + [' ']*(@cell_width-2) + ['#']
    c << tb
    (@cell_height-2).times { c << m }
    c << tb
    end
    c
    end

    def overlay(sub, mstr, x, y)
    sub.each_with_index { |row, i|
    row.each_with_index { |data, j|
    mstr[y+i][x+j] = data unless '#' == mstr[y+i][x+j]
    }
    }
    end

    def to_s
    puzzle_width = (@cell_width-1) * @grid_width + 1
    puzzle_height = (@cell_height-1) * @grid_height + 1

    s = Array.new(puzzle_height) { Array.new(puzzle_width) << [] }

    @numbered_grid.each_with_index { |row, i|
    row.each_with_index { |data, j|
    overlay(cell(data), s, j*(@cell_width-1), i*(@cell_height-1))
    }
    }
    s.collect! { |row| row.join }.join("\n")
    end
    public :to_s

    end#class CrossWordPuzzle

    cwp = CrossWordPuzzle.new(ARGV.shift)
    puts cwp.to_s
     
    jim, Dec 5, 2004
    #2
    1. Advertisements

  3. This is my solution.

    My first thought was to make a FormattedCrossword and a Crossword class
    and to let the latter have a #format method which creates a
    FormattedCrossword from its contents. But that would have led to much
    data duplication and complication, so I used a single Crossword class.

    The hearts of my solution are Crossword#calculate_layout and
    Crossword#display. Crossword#calculate_layout finds the locations of
    the numbers and clears any filled squares at the border (by calling the
    recursive method Crossword#empty_filled_square).

    This quiz took me only about 20 minutes, though it had some parts which
    first seemed easy but then weren't... that was really fun. :)

    Markus Koenig

    ----
    #!/usr/bin/env ruby

    def Array.make2d(h, w, value)
    # make a two-dimensional Array initialized with value
    line = [value] * w
    arr = Array.new
    h.times do
    arr.push line.dup
    end
    return arr
    end

    class Crossword
    # --instance vars--
    # @h: height
    # @w: width
    # @board: square types (2d array)
    # true: filled inner square
    # false: non-filled inner square
    # nil: previously filled outer square
    # @numbers: square number (2d array)
    # Integer: this number
    # nil: no number

    # output options
    CBORDER = '#'
    CFREE = ' '

    def Crossword.parse
    # parse ARGF

    arr = [[]]
    y = 0
    until ARGF.eof
    case ARGF.getc
    when ?_, ?-
    arr[y].push false
    when ?X, ?x
    arr[y].push true
    when ?\n
    if arr[y].length != 0
    arr.push []
    y += 1
    end
    end
    end

    h = (arr[y].length == 0) ? y : y + 1
    w = arr.map{|subarr| subarr.length}.max

    cw = Crossword.new(h, w)
    h.times do |y|
    w.times do |x|
    cw.board[y][x] = true if arr[y][x] != false
    end
    end
    return cw
    end

    def initialize(h, w)
    @h = h
    @w = w
    @board = Array.make2d(h, w, false)
    end

    attr_reader :board

    def empty_filled_square(y, x)
    # recursively replace a filled area with nils

    return if y < 0 or x < 0
    return if y >= @h or x >= @w
    return if @board[y][x] != true
    @board[y][x] = nil
    empty_filled_square y-1, x
    empty_filled_square y+1, x
    empty_filled_square y, x-1
    empty_filled_square y, x+1
    end
    private :empty_filled_square

    def calculate_layout
    # calculate @numbers and empty outer filled squares

    @numbers = Array.make2d(@h, @w, nil)

    current = 1
    @h.times do |y|
    @w.times do |x|
    next if is_filled(y, x)
    if (is_filled(y-1, x) and not is_filled(y+1, x)) \
    or (is_filled(y, x-1) and not is_filled(y, x+1))
    @numbers[y][x] = current
    current += 1
    end
    end
    end

    @h.times do |y|
    empty_filled_square y, 0
    empty_filled_square y, @w - 1
    end
    @w.times do |x|
    empty_filled_square 0, x
    empty_filled_square @h - 1, x
    end
    end
    private :calculate_layout

    def is_filled(y, x)
    return true if y < 0 or x < 0 or y >= @h or x >= @w
    @board[y][x]
    end
    def has_hborder(y, x)
    if y == 0
    @board[0][x] != nil
    elsif y == @h
    @board[y-1][x] != nil
    else
    @board[y-1][x] != nil or @board[y][x] != nil
    end
    end
    def has_vborder(y, x)
    if x == 0
    @board[y][0] != nil
    elsif x == @w
    @board[y][x-1] != nil
    else
    @board[y][x-1] != nil or @board[y][x] != nil
    end
    end
    def has_node(y, x)
    return true if y != 0 and has_vborder(y-1, x)
    return true if x != 0 and has_hborder(y, x-1)
    return true if y != @h and has_vborder(y, x)
    return true if x != @w and has_hborder(y, x)
    return false
    end
    private :is_filled, :has_hborder, :has_vborder, :has_node

    def display
    calculate_layout

    print(has_node(0, 0) ? CBORDER : CFREE)
    @w.times do |x|
    print((has_hborder(0, x) ? CBORDER : CFREE) * 4)
    print(has_node(0, x+1) ? CBORDER : CFREE)
    end
    puts
    @h.times do |y|
    print(has_vborder(y, 0) ? CBORDER : CFREE)
    @w.times do |x|
    if is_filled(y, x)
    print CBORDER * 4
    elsif @numbers[y][x]
    nm = @numbers[y][x].to_s
    print nm
    print CFREE * (4 - nm.length)
    else
    print CFREE * 4
    end
    print(has_vborder(y, x+1) ? CBORDER : CFREE)
    end
    puts
    print(has_vborder(y, 0) ? CBORDER : CFREE)
    @w.times do |x|
    print((is_filled(y, x) ? CBORDER : CFREE) * 4)
    print(has_vborder(y, x+1) ? CBORDER : CFREE)
    end
    puts
    print(has_node(y+1, 0) ? CBORDER : CFREE)
    @w.times do |x|
    print((has_hborder(y+1, x) ? CBORDER : CFREE) * 4)
    print(has_node(y+1, x+1) ? CBORDER : CFREE)
    end
    puts
    end
    end
    end


    # this is the "main" program
    cw = Crossword.parse
    cw.display
     
    Markus Koenig, Dec 5, 2004
    #3
  4. --Boundary-00=_XhysBH18e8PRhdV
    Content-Type: Multipart/Mixed;
    boundary="Boundary-00=_XhysBH18e8PRhdV"


    --Boundary-00=_XhysBH18e8PRhdV
    Content-Type: text/plain;
    charset="utf-8"
    Content-Transfer-Encoding: 7bit
    Content-Disposition: inline

    Hi --

    I must say that I'm impressed that someone wrote a solution in 20 minutes. My
    first pass took about an hour, but was never quite complete b/c I felt it was
    too hackish. I don't usually do these quizes, but I decided to take a good
    portion of a day out of my regular routine to try to write a nice version. It
    was fun, and I needed the break :)

    I looked at the problem from the point of view of a cellular automata. The
    main point of interest is the way in which I passively build the puzzle. As a
    "cell" is queried its "type" is determined on the fly. To determine the type,
    a cell must check to see what the type of its neighbors are, thus recursing
    the process. The results of each cell query are cached, short-circuiting the
    recursion.

    T.


    # crossit.rb --------------------------------------------------------

    module CrossWord

    CELL_WIDTH = 6
    CELL_HEIGHT = 4

    def self.build( str )
    Board.new( str ).build
    end

    class Board
    def initialize( layout )
    b = layout.upcase # upcase and duplicate input layout
    lines = b.split(/\n/) # split into array of lines of tokens
    @board = lines.collect{ |line| line.scan(/[_X]/) }
    @cnt=0 # set cell counter (for numbering)
    end

    def height ; @height ||= @board.length ; end
    def width ; @width ||= @board[0].length ; end

    # the board builds itself as it is called upon
    def board(y,x)
    return nil if @board[y][x] == 'P' # pending resolution
    # resolution complete
    return @board[y][x] if @board[y][x] != '_' and @board[y][x] != 'X'
    return @board[y][x] = 'u' if @board[y][x] == '_'
    # on edge
    return @board[y][x] = 'e' if y==0 or x==0 or y==height-1 or x==width-1
    if @board[y][x] == 'X' # could be edge or solid
    @board[y][x] = 'P' # mark as pending (prevents infinite recursion)
    return @board[y][x] = 'e' if # edge if neighbor is edge
    board(y-1,x) == 'e' or board(y,x+1) == 'e' or
    board(y+1,x) == 'e' or board(y,x-1) == 'e'
    end
    return @board[y][x] = 's' # else solid
    end

    # build the puzzle
    def build
    puzzle = Puzzle.new( height, width ) # new puzzle
    # edges must be done first since they clear spaces
    @board.each_with_index{ |line,y|
    line.each_with_index{ |cell,x|
    type = board(y,x)
    puzzle.push(type,y,x,nil) if type == 'e'
    }
    }
    # buildup all the solid and fill'in pieces
    @board.each_with_index{ |line,y|
    line.each_with_index{ |cell,x|
    type = board(y,x)
    cnt = upper_left?(type,y,x) ? (@cnt += 1) : ''
    puzzle.push(type,y,x,cnt) if type != 'e'
    } }
    puzzle.to_s # return the final product
    end

    # determines if a cell should be numbered
    def upper_left?(type,y,x)
    return false if type != 'u'
    return true if y == 0 and board(y+1,x) == 'u'
    return true if x == 0 and board(y,x+1) == 'u'
    if x != width-1 and board(y,x+1) == 'u'
    return true if board(y,x-1) == 'e'
    return true if board(y,x-1) == 's'
    end
    if y != height-1 and board(y+1,x) == 'u'
    return true if board(y-1,x) == 'e'
    return true if board(y-1,x) == 's'
    end
    return false
    end
    end

    # Puzzle is a simple matrix
    class Puzzle
    attr_reader :puzzle
    def initialize(height, width)
    @puzzle = [''] # build a blank to work on
    (height*(CELL_HEIGHT-1)+1).times{ |y|
    (width*(CELL_WIDTH-1)+1).times{ |x| @puzzle.last << '.' }
    @puzzle << ''
    }
    end
    def push(type,y,x,cnt)
    c = space(type,cnt)
    ny = y * CELL_HEIGHT - (y == 0 ? 0 : y) # adjust for first line
    nx = x * CELL_WIDTH - (x == 0 ? 0 : x) # adjust for first column
    @puzzle[ny+0][nx,CELL_WIDTH] = c[0]
    @puzzle[ny+1][nx,CELL_WIDTH] = c[1]
    @puzzle[ny+2][nx,CELL_WIDTH] = c[2]
    @puzzle[ny+3][nx,CELL_WIDTH] = c[3]
    end
    def space(type,cnt)
    case type
    when "u"
    [ "######",
    "#%s#" % "#{cnt} "[0,4],
    "# #",
    "######" ]
    when "s"
    [ "######" ] * 4
    when "e"
    [ " " ] * 4
    end
    end
    def to_s ; @puzzle.join("\n") ; end
    end
    end

    # ruby crossit.rb <layoutfile.cit>
    if $0 == __FILE__
    cwstr = nil
    if FileTest.file?( ARGV[0] )
    File.open( ARGV[0] ) { cwstr = gets(nil) }
    end
    $stdout << CrossWord.build( cwstr )
    end

    --Boundary-00=_XhysBH18e8PRhdV
    Content-Type: application/x-ruby;
    name="crossit.rb"
    Content-Transfer-Encoding: 7bit
    Content-Disposition: attachment;
    filename="crossit.rb"

    module CrossWord

    CELL_WIDTH = 6
    CELL_HEIGHT = 4

    def self.build( str )
    Board.new( str ).build
    end

    class Board
    def initialize( layout )
    b = layout.upcase # upcase and duplicate input layout
    lines = b.split(/\n/) # split into array of lines
    @board = lines.collect{ |line| line.scan(/[_X]/) } # split line into array of tokens
    @cnt=0 # set cell counter (for numbering)
    end

    def height ; @height ||= @board.length ; end
    def width ; @width ||= @board[0].length ; end

    # the board builds itself as it is called upon
    def board(y,x)
    return nil if @board[y][x] == 'P' # pending resolution
    return @board[y][x] if @board[y][x] != '_' and @board[y][x] != 'X' # resolution complete
    return @board[y][x] = 'u' if @board[y][x] == '_'
    return @board[y][x] = 'e' if y==0 or x==0 or y==height-1 or x==width-1 # on edge
    if @board[y][x] == 'X' # could be edge or solid
    @board[y][x] = 'P' # mark as pending (prevents infinite recursion)
    return @board[y][x] = 'e' if # edge if neighbor is edge
    board(y-1,x) == 'e' or board(y,x+1) == 'e' or
    board(y+1,x) == 'e' or board(y,x-1) == 'e'
    end
    return @board[y][x] = 's' # else solid
    end

    # build the puzzle
    def build
    puzzle = Puzzle.new( height, width ) # new puzzle
    # edges must be done first since they clear spaces
    @board.each_with_index{ |line,y|
    line.each_with_index{ |cell,x|
    type = board(y,x)
    puzzle.push(type,y,x,nil) if type == 'e'
    }
    }
    # buildup all the solid and fill'in pieces
    @board.each_with_index{ |line,y|
    line.each_with_index{ |cell,x|
    type = board(y,x)
    cnt = upper_left?(type,y,x) ? (@cnt += 1) : ''
    puzzle.push(type,y,x,cnt) if type != 'e'
    } }
    puzzle.to_s # return the final product
    end

    # determines if a cell should be numbered
    def upper_left?(type,y,x)
    return false if type != 'u'
    return true if y == 0 and board(y+1,x) == 'u'
    return true if x == 0 and board(y,x+1) == 'u'
    if x != width-1 and board(y,x+1) == 'u'
    return true if board(y,x-1) == 'e'
    return true if board(y,x-1) == 's'
    end
    if y != height-1 and board(y+1,x) == 'u'
    return true if board(y-1,x) == 'e'
    return true if board(y-1,x) == 's'
    end
    return false
    end

    end

    # Puzzle is a simple matrix
    class Puzzle
    attr_reader :puzzle
    def initialize(height, width)
    @puzzle = [''] # build a blank to work on
    (height*(CELL_HEIGHT-1)+1).times{ |y|
    (width*(CELL_WIDTH-1)+1).times{ |x| @puzzle.last << '.' }
    @puzzle << ''
    }
    end
    def push(type,y,x,cnt)
    c = space(type,cnt)
    ny = y * CELL_HEIGHT - (y == 0 ? 0 : y) # adjust for first line
    nx = x * CELL_WIDTH - (x == 0 ? 0 : x) # adjust for first column
    @puzzle[ny+0][nx,CELL_WIDTH] = c[0]
    @puzzle[ny+1][nx,CELL_WIDTH] = c[1]
    @puzzle[ny+2][nx,CELL_WIDTH] = c[2]
    @puzzle[ny+3][nx,CELL_WIDTH] = c[3]
    end
    def space(type,cnt)
    case type
    when "u"
    [ "######",
    "#%s#" % "#{cnt} "[0,4],
    "# #",
    "######" ]
    when "s"
    [ "######" ] * 4
    when "e"
    [ " " ] * 4
    end
    end
    def to_s ; @puzzle.join("\n") ; end
    end

    end

    if $0 == __FILE__
    cwstr = nil
    if FileTest.file?( ARGV[0] )
    File.open( ARGV[0] ) { cwstr = gets(nil) }
    end
    $stdout << CrossWord.build( cwstr )
    end

    --Boundary-00=_XhysBH18e8PRhdV
    Content-Type: text/plain;
    charset="utf-8";
    name="test1.cit"
    Content-Transfer-Encoding: 7bit
    Content-Disposition: attachment;
    filename="test1.cit"

    X _ _ _ _ X X
    _ _ X _ _ _ _
    _ _ _ _ X _ _
    _ X _ _ X X X
    _ _ _ X _ _ _
    X _ _ _ _ _ X

    --Boundary-00=_XhysBH18e8PRhdV--
    --Boundary-00=_XhysBH18e8PRhdV--
     
    trans. (T. Onoma), Dec 5, 2004
    #4
  5. Here's mine... again. (Feel bad about the early spoiler. Sorry!)

    This code is far from pretty. It was one of those solutions that kept
    getting fixes piled on until it works. I probably should has rewritten
    it, but it does work.

    If you did this problem in 20 minutes, you're about 5 times smarter
    than me.

    James Edward Gray II

    #!/usr/bin/env ruby

    class Square
    @@count = 1

    def initialize( holds_letter = false )
    @holds_letter = holds_letter
    @edge = false
    end

    attr_reader :holds_letter
    attr_accessor :edge

    def render( row, top, left, right, bottom )
    if @holds_letter
    number = ""
    if (top.nil? or not top.holds_letter) and
    (bottom and bottom.holds_letter)
    number = @@count.to_s
    @@count += 1
    elsif (left.nil? or not left.holds_letter) and
    (right and right.holds_letter)
    number = @@count.to_s
    @@count += 1
    end

    if top.nil? and left.nil?
    row[0] << "######"
    row[1] << sprintf("#%-4s#", number)
    row[2] << "# #"
    row[3] << "######"
    elsif top.nil?
    row[0] << "#####"
    row[1] << sprintf("%-4s#", number)
    row[2] << " #"
    row[3] << "#####"
    elsif left.nil?
    row[1] << sprintf("#%-4s#", number)
    row[2] << "# #"
    row[3] << "######"
    else
    row[1] << sprintf("%-4s#", number)
    row[2] << " #"
    row[3] << "#####"
    end
    else
    if @edge
    if top.nil? and left.nil?
    row[0] << " "
    row[1] << " "
    row[2] << " "
    row[3] << " "
    elsif top.nil?
    row[0] << " "
    row[1] << " "
    row[2] << " "
    row[3] << " "
    elsif left.nil?
    row[1] << " "
    row[2] << " "
    row[3] << " "
    else
    row[1] << " "
    row[2] << " "
    row[3] << " "
    end
    if right and not right.edge
    row.each { |e| e.sub!(/ $/, "#") }
    end
    if left and not left.edge
    row.each { |e| e.sub!(/ (.{5})$/, '#\1') }
    end
    if top and not top.edge
    row[0].sub!(/ +(#?)$/) do |m|
    "#" * (m.length - $1.length) + $1
    end
    end
    if bottom and not bottom.edge
    row[3].sub!(/ +(#?)$/) do |m|
    "#" * (m.length - $1.length) + $1
    end
    end
    else
    if top.nil? and left.nil?
    row[0] << "######"
    row[1] << "######"
    row[2] << "######"
    row[3] << "######"
    elsif top.nil?
    row[0] << "#####"
    row[1] << "#####"
    row[2] << "#####"
    row[3] << "#####"
    elsif left.nil?
    row[1] << "######"
    row[2] << "######"
    row[3] << "######"
    else
    row[1] << "#####"
    row[2] << "#####"
    row[3] << "#####"
    end
    end
    end
    end
    end

    board = [ ]
    while line = ARGF.gets
    board << [ ]
    line.chomp.delete(" ").each_byte do |c|
    if c == ?X
    board[-1] << Square.new
    else
    board[-1] << Square.new(true)
    end
    end
    end

    loop do
    changed = false
    board.each_with_index do |row, y|
    row.each_with_index do |cell, x|
    next if cell.holds_letter or cell.edge

    if x == 0 or y == 0 or x == board[0].size - 1 or y == board.size - 1
    cell.edge = true
    changed = true
    next
    end

    top = board[y - 1][x]
    left = board[y][x - 1]
    right = board[y][x + 1]
    bottom = board[y + 1][x]
    if (top and top.edge) or (left and left.edge) or
    (right and right.edge) or (bottom and bottom.edge)
    cell.edge = true
    changed = true
    end
    end
    end
    break if not changed
    end

    board.each_with_index do |row, y|
    drawn_row = ["", "", "", ""]
    row.each_with_index do |cell, x|
    top = y == 0 ? nil : board[y - 1][x]
    left = x == 0 ? nil : board[y][x - 1]
    right = x == board[0].size - 1 ? nil : board[y][x + 1]
    bottom = y == board.size - 1 ? nil : board[y + 1][x]

    cell.render drawn_row, top, left, right, bottom
    end
    drawn_row.each { |e| puts e if e.length > 0 }
    end
     
    James Edward Gray II, Dec 5, 2004
    #5
  6. Improvement. Change,
    def space(type,cnt) case type      when "u"        [ "######",          "#%s#" % "#{cnt}    "[0,4],          "#    #",          "######" ]
    to
    def space(type,cnt) case type when "u" [ "######", "#%-4s#" % cnt, "# #", "######" ]
    Thanks JEGII,T.
     
    trans. (T. Onoma), Dec 5, 2004
    #6
  7. I had a bit of time so I'll throw one into the pot as well:


    class Xword
    def initialize(spec)
    @spec = spec.gsub(/ +/,'').squeeze("\n")
    @height = @spec.count("\n")
    @width = (@spec.size - @height) / @height
    end
    def find_blanks
    1 while @spec.gsub!(/(^|B+)X/,'\1B') ||
    @spec.gsub!(/X(B+|$)/,'B\1') ||
    @spec.gsub!(/X(.*\Z)/,'B\1') ||
    @spec.gsub!(/\A(.*)X/,'\1B') ||
    @spec.gsub!(/X(.{#{@width}}B)/m,'B\1') ||
    @spec.gsub!(/(B.{#{@width}})X/m,'\1B')
    end
    def generate(c="#")
    find_blanks
    row = ((" " * 5) * @width) + " \n"
    @pstr = row * (@height * 3) + row
    @llen = row.size
    @cells = @spec.delete("\n")
    cell, count = -1, 0
    ( - @llen * 3).step(@llen * 3) do |i|
    (i...i + @llen - 5).step(5) do |j|
    cell += 1
    make_cell(j, c) if @cells[cell] != ?B
    fill_cell(j, c) if @cells[cell] == ?X
    next unless blank?(cell) and numerate?(cell)
    @pstr[j + @llen + 1, 2] = sprintf("%02d", count += 1)
    end
    end
    end
    def blank?(cell)
    () === cell and @cells[cell] == ?_
    end
    def numerate?(cell)
    mod = cell % @width
    (mod == 0 or !blank?(cell - 1)) &&
    (mod < @width and blank?(cell + 1)) or
    (!blank?(cell - @width) and blank?(cell + @width))
    end
    def make_cell(n,c)
    @pstr[n..n + 5] = c * 6
    @pstr[(n + @llen * 3)..((n + @llen * 3) + 5)] = c * 6
    4.times {|i| @pstr[n + @llen * i] = c}
    4.times {|i| @pstr[n + 5 + @llen * i] = c}
    end
    def fill_cell(n,c)
    @pstr[n + @llen + 1, 4] = c * 4
    @pstr[n + @llen * 2 + 1, 4] = c * 4
    end
    def to_s
    @pstr
    end
    end

    xword = Xword.new(File.read(ARGV[0]))
    xword.generate('@')
    puts xword
    __END__

    regards,
    andrew
     
    Andrew Johnson, Dec 5, 2004
    #7
  8. Ruby Quiz

    Clark Guest

    I build the full display with double borders and then remove
    them.

    Clark

    ---

    #!/usr/bin/env ruby

    class GraphicBlock
    attr_reader :arr

    def initialize(arr)
    @arr = arr
    end

    def add_right(other)
    result = @arr.zip(other.arr).collect do |line|
    line.join("")
    end
    GraphicBlock.new(result)
    end

    def add_below(other)
    GraphicBlock.new(@arr + other.arr)
    end

    def transpose
    result = @arr.collect { |row| row.split(//) }.
    transpose.collect { |line| line.join("") }
    GraphicBlock.new(result)
    end

    def collapse_column_borders(cell_width)
    result = @arr.each do |line|
    (line.size/cell_width).downto(1) do |i|
    border = (i*cell_width) - 1
    line[border, 2] = line[border, 2].include?("#") ? "#" : " "
    end
    end
    GraphicBlock.new(result)
    end

    def collapse_row_borders(cell_height)
    transpose.collapse_column_borders(cell_height).transpose
    end

    def to_s
    @arr.join("\n")
    end
    end


    class Crossword
    attr_reader :cell_width, :cell_height

    def initialize(filename, cell_width = 6, cell_height = 4)
    @cell_width = cell_width
    @cell_height = cell_height
    @puzzle = Array.new
    IO.foreach(filename) do |line|
    line = line.chomp.gsub(/ /, '')
    @puzzle << (row = Array.new)
    line.split('').each do |char|
    if (char == "X")
    row << :filled
    else
    row << :letter
    end
    end
    end
    remove_filled_border
    number_puzzle
    end

    def cell(i, j)
    if (i < 0 || i >= @puzzle.size ||
    j < 0 || j >= @puzzle.size)
    nil
    else
    @puzzle[j]
    end
    end

    def above(i, j) cell(i-1, j) end
    def below(i, j) cell(i+1, j) end
    def left(i, j) cell(i, j-1) end
    def right(i, j) cell(i, j+1) end

    def adjacent(i, j)
    [above(i, j), below(i, j), left(i, j), right(i, j)]
    end

    def unused_cell?(item)
    (item == nil) || (item == :filled)
    end

    def letter_cell?(item)
    !unused_cell?(item)
    end

    def puzzle_visit
    @puzzle.each_with_index do |row, i|
    row.each_with_index do |item, j|
    yield(item, i, j)
    end
    end
    end

    def remove_filled_border
    begin
    changed = false
    puzzle_visit do |item, i, j|
    if (item == :filled && adjacent(i, j).include?(nil))
    @puzzle[j] = nil
    changed = true
    end
    end
    end while (changed)
    end

    def number_puzzle
    count = 1
    puzzle_visit do |item, i, j|
    if (letter_cell?(item) &&
    ((unused_cell?(above(i, j)) && letter_cell?(below(i, j))) ||
    (unused_cell?(left(i, j)) && letter_cell?(right(i, j)))))
    @puzzle[j] = count
    count += 1
    end
    end
    end

    def graphics(item)
    arr = Array.new
    if (item == :filled)
    cell_height.times { |i| arr << "#" * cell_width }
    elsif (item == :letter)
    arr << "#" * cell_width
    (cell_height-2).times { |i|
    arr << "#" + " " * (cell_width-2) + "#"
    }
    arr << "#" * cell_width
    elsif (item != nil && item.integer?)
    arr << "#" * cell_width
    arr << sprintf("#%-*d#", cell_width-2, item)
    (cell_height-3).times { |i|
    arr << "#" + " " * (cell_width-2) + "#"
    }
    arr << "#" * cell_width
    else
    cell_height.times { |i| arr << " " * cell_width }
    end
    GraphicBlock.new(arr)
    end

    def draw_raw
    @puzzle.collect do |row|
    row.collect { |cell| graphics(cell) }.inject do |row_picture, g|
    row_picture.add_right(g)
    end
    end.inject do |full_picture, row_picture|
    full_picture.add_below(row_picture)
    end
    end

    def draw
    draw_raw.collapse_column_borders(cell_width).
    collapse_row_borders(cell_height)
    end
    end

    if __FILE__ == $0
    puzzle = Crossword.new(ARGV.first)
    print puzzle.draw.to_s + "\n"
    end
     
    Clark, Dec 5, 2004
    #8
  9. Here is my version. Nothing special, just a few branches and thats it. Only
    thing worth mentioning may be, that I only draw lines to the left, top, and the
    edge at the top-left of each cell to avoid drawing double lines.

    Everything in a highlighted version is at:
    http://ruby.brian-schroeder.de/quiz/crossword/

    Here comes the code:


    module Crossword
    class Cell
    attr_accessor :empty, :visible, :number

    def initialize(empty, visible = true, number = nil)
    self.empty = empty
    self.visible = visible
    self.number = number
    end

    def to_s
    (self.visible ? (self.empty ? (self.number ? "[%02d]" % self.number : '[
    ]') : '[XX]') : ' ')
    end
    end

    class Layout
    attr_accessor :cell_height, :cell_width

    private
    DIRS = [[-1,0], [0,-1], [1,0], [0,1]]

    # Prepare information of fields.
    #
    # Set bordering empty fields to nil. Some field may enter the stack twice,
    but its a bit shorter that way.
    def remove_empty_border
    stack = []
    for row in 0...height
    stack.push [row, 0] unless self[row, 0].empty
    stack.push [row, width-1] unless self[row, width-1].empty
    end
    for col in 0...width
    stack.push [0, col] unless self[0, col].empty
    stack.push [height-1, col] unless self[height-1, col].empty
    end

    while cell = stack.pop
    self[*cell].visible = false
    DIRS.each do | dir |
    neighbor = cell.zip(dir).map{|i,j| i + j}
    stack.push neighbor if self[*neighbor] and !self[*neighbor].empty and
    self[*neighbor].visible
    end
    end
    end

    # Prepare information of fields.
    #
    # Set Word Numbers based on the information of the four directly adjacent
    cells
    def number_cells
    n = 1
    for row in 0...height
    for col in 0...width
    cell = self[row, col]
    west, north, east, south = DIRS.map{|dx, dy| self[row + dx, col + dy]
    and self[row + dx, col + dy].empty }
    if cell.empty and ((!west and east) or (!north and south))
    cell.number = n
    n += 1
    end
    end
    end
    end

    public
    # create new layout from a file stream as described at
    http://www.grayproductions.net/ruby_quiz/quiz10.html
    def initialize(file, cell_width = 5, cell_height = 3)
    self.cell_width = cell_width
    self.cell_height = cell_height
    @lines = file.read.split("\n").map{ |line| line.scan(/[_X]/).map{|cell|
    Cell.new(cell == '_')} }
    remove_empty_border
    number_cells
    end

    def [](row, col)
    return @lines[row][col] if 0 <= row and 0 <= col and row < height and col
    < width
    return nil
    end

    def width() @lines[0].length end
    def height() @lines.length end

    # Create a layout as described at
    http://www.grayproductions.net/ruby_quiz/quiz10.html
    def to_s
    result = ''
    for r in 0..height
    lines = Array.new(cell_height) { '' }
    for c in 0..width
    # Differentiate the behaviour based on the visibility state of four
    cells at a time
    c1, c2, c3, c4 = self[r-1, c-1], self[r-1, c], self[r, c-1], self[r,
    c]
    v1, v2, v3, v4 = (c1 and c1.visible), (c2 and c2.visible), (c3 and
    c3.visible), (c4 and c4.visible)
    if v4
    lines[0] << '#' * cell_width
    (1...cell_height).each do | i | lines << '#' end
    else
    lines[0] << if v1 or v2 or v3
    '#'
    else
    ' '
    end
    lines[0] << if v2
    '#' * (cell_width - 1)
    else
    ' ' * (cell_width - 1)
    end
    if v3
    (1...cell_height).each do | i | lines << '#' end
    else
    (1...cell_height).each do | i | lines << ' ' end
    end
    end
    if v4
    if c4.empty
    lines[1] << c4.number.to_s.ljust(cell_width-1)
    (2...cell_height).each do | i | lines << ' ' * (cell_width-1)
    end
    else
    (1...cell_height).each do | i | lines << '#' * (cell_width-1)
    end
    end
    else
    (1...cell_height).each do | i | lines << ' ' * (cell_width-1)
    end
    end
    end
    result << lines.join("\n") << "\n"
    end
    result
    end
    end

    data = ARGV[0] ? File.new(ARGV[0]) : DATA

    puts Layout.new(data)
    end


    best regards,

    Brian
     
    Brian Schröder, Dec 5, 2004
    #9
  10. Ruby Quiz

    Pit Capitain Guest

    Hi all,

    here's another solution. When I read the quiz my first thought was about using
    regular expressions. So I first tried to extend gsub! to work both horizontally
    as well as vertically through a multi-line string. As others, I too had to solve
    some unexpected hurdles. I hope you find this version interesting.

    Regards,
    Pit


    class Array

    # converts a two-dimensional array into a multi-line string
    def to_s2
    map { |row| "#{row}\n" }.join
    end

    # inserts successive elements from other array between every two
    # elements of this array
    def weave other
    inject [] do |array, element|
    array << other.shift unless array.empty?
    array << element
    end
    end

    # weaves the rows of two two-dimensional arrays, see weave
    def weave2 other
    zip( other ).map { |row1, row2| row1.weave row2 }
    end

    end


    class String

    # splits a multi-line string into a two-dimensional array of
    # character strings
    def to_a2
    map { |row| row.chomp.split // }
    end

    # transposes a multi-line string like a two-dimensional array
    def transpose
    to_a2.transpose.to_s2
    end

    # in-place form of transpose
    def transpose!
    replace transpose
    end

    # like gsub!, but works both horizontally and vertically in a
    # multi-line string
    def gsub2! re, subst
    result1 = gsub! re, subst
    transpose!
    result2 = gsub! re, subst
    transpose!
    self if result1 || result2
    end

    # like Array#weave2, using multi-line strings
    def weave other
    to_a2.weave2( other.to_a2 ).to_s2
    end

    end


    # input patterns
    FILLED = "X"
    LETTER = "_"

    # intermediate patterns
    NUMBER = "N"
    OUTSIDE = "O"
    LINE = "#"
    EMPTY = " "

    # search patterns
    OUT_OR_EDGE = /^|#{OUTSIDE}|$/
    BEFORE_NEW_WORD = /^|#{OUTSIDE}|#{FILLED}/
    WORD = /#{LETTER}|#{NUMBER}/


    # removes spaces from input
    def remove_spaces
    @s.gsub!( / /, "" )
    end

    # marks outside cells (filled cells adjacent to edges or outside cells)
    def mark_outside_cells
    nil while \
    @s.gsub2!( /#{FILLED}(#{OUT_OR_EDGE})/, "#{OUTSIDE}\\1" ) or \
    @s.gsub2!( /(#{OUT_OR_EDGE})#{FILLED}/, "\\1#{OUTSIDE}" )
    end

    # marks beginnings of words
    def number_beginnings
    @s.gsub2! /(#{BEFORE_NEW_WORD})#{LETTER}(#{WORD})/, "\\1#{NUMBER}\\2"
    end

    # creates a pattern of delimiters between non-outside cells
    def delimiters s, delimiter, space, gsub_method = :gsub!
    r = s.dup
    r.send gsub_method, /^/, OUTSIDE
    r.send gsub_method, /[^#{OUTSIDE}\n]/, delimiter
    r.send gsub_method, /#{OUTSIDE}(?=#{delimiter})/, delimiter
    r.send gsub_method, OUTSIDE, space
    r
    end

    # duplicates every cell line, removing number marks
    def duplicate_cell_lines
    index = 0
    @s = @s.inject do |result, row|
    index += 1
    result << row
    result << row.gsub( NUMBER, LETTER ) if index % 2 == 1
    result
    end
    end


    # read layout
    @s = ARGF.read

    # process the layout
    remove_spaces
    mark_outside_cells
    number_beginnings

    # delimiting lines and corners
    v = delimiters @s, LINE, EMPTY
    h = delimiters( @s.transpose, FILLED, LETTER ).transpose
    c = delimiters @s, LINE, EMPTY, :gsub2!

    # combine layout and delimiters
    vs = v.weave @s
    ch = c.weave h
    @s = ch.transpose.weave( vs.transpose ).transpose

    # format the result
    duplicate_cell_lines
    num = 0
    @s.gsub! /./ do |char|
    case char
    when OUTSIDE, LETTER then " "
    when FILLED then "####"
    when NUMBER then "%-4i" % ( num += 1 )
    else char
    end
    end

    # output the result
    puts @s
     
    Pit Capitain, Dec 5, 2004
    #10
  11. Ruby Quiz

    Jim Menard Guest

    Here's mine. I changed the cell borders so they look like

    +----+
    | |
    | |
    +----+

    The only possibly interesting decision I made was to create a piece of
    "paper" onto which I drew each cell. Instead of worrying about other
    cells' borders, each cell drew itself completely. This means that the
    edges were re-drawn between adjacent cells. Removing this duplication
    would have been a premature optimization.

    #! /usr/bin/env ruby

    class Cell

    WIDTH = 6
    HEIGHT = 4

    attr_accessor :neighbors # Hash, key=:left, :right, :top,
    :bottom

    def Cell.from_char(c)
    return c == '_' ? WhiteCell.new : BlackCell.new
    end

    def initialize
    @neighbors = {}
    end

    def print_border_at(row, col, paper)
    x = col * (Cell::WIDTH - 1)
    y = row * (Cell::HEIGHT - 1)

    # corners
    paper[y][x] =
    paper[y][x+Cell::WIDTH-1] =
    paper[y+Cell::HEIGHT-1][x] =
    paper[y+Cell::HEIGHT-1][x+Cell::WIDTH-1] = '+'

    # top and bottom
    (Cell::WIDTH-2).times { | j | paper[y][x+1+j] = '-' }
    (Cell::WIDTH-2).times { | j | paper[y+Cell::HEIGHT-1][x+1+j] =
    '-' }

    # sides
    (Cell::HEIGHT - 2).times { | i |
    paper[y+1+i][x] = '|'
    paper[y+1+i][x+Cell::WIDTH-1] = '|'
    }
    end

    end

    class WhiteCell < Cell
    attr_accessor :clue_number

    def black?
    return false
    end

    def needs_clue_number?
    return ((@neighbors[:left].nil? || @neighbors[:left].black?) &&
    !@neighbors[:right].nil? && !@neighbors[:right].black?)
    ||
    ((@neighbors[:top].nil? || @neighbors[:top].black?) &&
    !@neighbors[:bottom].nil? &&
    !@neighbors[:bottom].black?)
    end

    def print_at(row, col, paper)
    print_border_at(row, col, paper)

    if @clue_number
    x = col * (Cell::WIDTH - 1)
    y = row * (Cell::HEIGHT - 1)
    s = @clue_number.to_s
    s.split(//).each_with_index { | char, i |
    paper[y+1][x+1+i] = char
    }
    end
    end
    end

    class BlackCell < Cell

    def initialize
    super
    @fill_char = '#'
    end

    def black?
    return true
    end

    def hidden?
    return @hidden
    end

    def needs_clue_number?
    return false
    end

    def hide
    return if hidden?
    @hidden = true
    @fill_char = ' '
    @neighbors.each_value { | cell | cell.hide if cell &&
    cell.black? }
    end

    def print_at(row, col, paper)
    return if hidden?

    print_border_at(row, col, paper)

    # fill center
    x = col * (Cell::WIDTH - 1)
    y = row * (Cell::HEIGHT - 1)
    (Cell::HEIGHT-2).times { | i |
    (Cell::WIDTH-2).times { | j | paper[y+1+i][x+1+j] = '#' }
    }
    end

    def print_scanline(i)
    print @fill_char * (Cell::WIDTH - 1)
    end

    def print_bottom
    print_scanline(0)
    end

    def print_right_wall
    print @fill_char
    end
    end

    class Puzzle

    def initialize(io)
    read_picture(io)
    introduce_neighbors()
    hide_outer_black()
    assign_clue_numbers()
    end

    def read_picture(io)
    @cells = []
    io.each_with_index { | line, i |
    line = line.chomp.gsub(/[^x_]/i, '')
    @cells = []
    line.split(//).each { | c | @cells << Cell.from_char(c) }
    }
    end

    def introduce_neighbors
    @cells.each_with_index { | row, i |
    row.each_with_index { | cell, j |
    cell.neighbors[:left] = @cells[j-1] unless j == 0
    cell.neighbors[:right] = @cells[j+1]
    cell.neighbors[:top] = @cells[i-1][j] unless i == 0
    cell.neighbors[:bottom] = @cells[i+1][j] if @cells[i+1]
    }
    }
    end

    def hide_outer_black
    @cells.first.each { | cell | cell.hide if cell.black? }
    @cells.last.each { | cell | cell.hide if cell.black? }
    @cells.each { | row |
    row.first.hide if row.first.black?
    row.last.hide if row.last.black?
    }
    end

    def assign_clue_numbers
    clue_number = 1
    @cells.each_with_index { | row, i |
    row.each_with_index { | cell, j |
    if cell.needs_clue_number?
    cell.clue_number = clue_number
    clue_number += 1
    end
    }
    }
    end

    def print
    paper = blank_paper
    @cells.each_with_index { | row, row_num |
    row.each_with_index { | cell, col_num |
    cell.print_at(row_num, col_num, paper)
    }
    }
    paper.each { | scanline | puts scanline.join }
    end

    def blank_paper
    width = @cells[0].size * (Cell::WIDTH - 1) + 10
    height = @cells.size * (Cell::HEIGHT - 1) + 10
    paper = []
    height.times { paper << (' ' * width).split(//) }
    return paper
    end

    end

    Puzzle.new(ARGF).print

    Jim
     
    Jim Menard, Dec 5, 2004
    #11
  12. On Sunday 05 December 2004 05:53 pm, Pit Capitain wrote:
    | Hi all,
    |
    | here's another solution. When I read the quiz my first thought was about
    | using regular expressions. So I first tried to extend gsub! to work both
    | horizontally as well as vertically through a multi-line string. As others,
    | I too had to solve some unexpected hurdles. I hope you find this version
    | interesting.

    Very intersting approach, Capitain. I had thought something like this would be
    but wasn't sure how to approach. In general a 2d "Sheet of Paper" String
    would be a useful class in general. I'd like to take your beginnings of such
    and build a dedicated class. Are you interested?

    T.

    | Regards,
    | Pit
    |
    |
    | class Array
    |
    | # converts a two-dimensional array into a multi-line string
    | def to_s2
    | map { |row| "#{row}\n" }.join
    | end
    |
    | # inserts successive elements from other array between every two
    | # elements of this array
    | def weave other
    | inject [] do |array, element|
    | array << other.shift unless array.empty?
    | array << element
    | end
    | end
    |
    | # weaves the rows of two two-dimensional arrays, see weave
    | def weave2 other
    | zip( other ).map { |row1, row2| row1.weave row2 }
    | end
    |
    | end
    |
    |
    | class String
    |
    | # splits a multi-line string into a two-dimensional array of
    | # character strings
    | def to_a2
    | map { |row| row.chomp.split // }
    | end
    |
    | # transposes a multi-line string like a two-dimensional array
    | def transpose
    | to_a2.transpose.to_s2
    | end
    |
    | # in-place form of transpose
    | def transpose!
    | replace transpose
    | end
    |
    | # like gsub!, but works both horizontally and vertically in a
    | # multi-line string
    | def gsub2! re, subst
    | result1 = gsub! re, subst
    | transpose!
    | result2 = gsub! re, subst
    | transpose!
    | self if result1 || result2
    | end
    |
    | # like Array#weave2, using multi-line strings
    | def weave other
    | to_a2.weave2( other.to_a2 ).to_s2
    | end
    |
    | end
    |
    |
    | # input patterns
    | FILLED = "X"
    | LETTER = "_"
    |
    | # intermediate patterns
    | NUMBER = "N"
    | OUTSIDE = "O"
    | LINE = "#"
    | EMPTY = " "
    |
    | # search patterns
    | OUT_OR_EDGE = /^|#{OUTSIDE}|$/
    | BEFORE_NEW_WORD = /^|#{OUTSIDE}|#{FILLED}/
    | WORD = /#{LETTER}|#{NUMBER}/
    |
    |
    | # removes spaces from input
    | def remove_spaces
    | @s.gsub!( / /, "" )
    | end
    |
    | # marks outside cells (filled cells adjacent to edges or outside cells)
    | def mark_outside_cells
    | nil while \
    | @s.gsub2!( /#{FILLED}(#{OUT_OR_EDGE})/, "#{OUTSIDE}\\1" ) or \
    | @s.gsub2!( /(#{OUT_OR_EDGE})#{FILLED}/, "\\1#{OUTSIDE}" )
    | end
    |
    | # marks beginnings of words
    | def number_beginnings
    | @s.gsub2! /(#{BEFORE_NEW_WORD})#{LETTER}(#{WORD})/, "\\1#{NUMBER}\\2"
    | end
    |
    | # creates a pattern of delimiters between non-outside cells
    | def delimiters s, delimiter, space, gsub_method = :gsub!
    | r = s.dup
    | r.send gsub_method, /^/, OUTSIDE
    | r.send gsub_method, /[^#{OUTSIDE}\n]/, delimiter
    | r.send gsub_method, /#{OUTSIDE}(?=#{delimiter})/, delimiter
    | r.send gsub_method, OUTSIDE, space
    | r
    | end
    |
    | # duplicates every cell line, removing number marks
    | def duplicate_cell_lines
    | index = 0
    | @s = @s.inject do |result, row|
    | index += 1
    | result << row
    | result << row.gsub( NUMBER, LETTER ) if index % 2 == 1
    | result
    | end
    | end
    |
    |
    | # read layout
    | @s = ARGF.read
    |
    | # process the layout
    | remove_spaces
    | mark_outside_cells
    | number_beginnings
    |
    | # delimiting lines and corners
    | v = delimiters @s, LINE, EMPTY
    | h = delimiters( @s.transpose, FILLED, LETTER ).transpose
    | c = delimiters @s, LINE, EMPTY, :gsub2!
    |
    | # combine layout and delimiters
    | vs = v.weave @s
    | ch = c.weave h
    | @s = ch.transpose.weave( vs.transpose ).transpose
    |
    | # format the result
    | duplicate_cell_lines
    | num = 0
    | @s.gsub! /./ do |char|
    | case char
    | when OUTSIDE, LETTER then " "
    | when FILLED then "####"
    | when NUMBER then "%-4i" % ( num += 1 )
    | else char
    | end
    | end
    |
    | # output the result
    | puts @s

    --
    ( o _ カラãƒ
    // trans.
    / \

    I don't give a damn for a man that can only spell a word one way.
    -Mark Twain

    [8,16,20,29,78,65,2,14,26,12,12,28,71,114,12,13,12,82,72,21,17,4,10,2,95].
    each_with_index{|x,i| $><<(x^'Begin landing your troops').chr}
    -Tadayoshi Funaba
     
    trans. (T. Onoma), Dec 6, 2004
    #12
  13. Ruby Quiz

    Pit Capitain Guest

    Please call me by my first name, Pit. Otherwise it interferes with the feeling
    of being among friends at ruby-talk :)
    Go ahead and take what you need. I fear I don't have enough time and - to be
    honest - interest to build and maintain a full featured class. But I'd be glad
    to answer questions in case you have any.

    Regards,
    Pit
     
    Pit Capitain, Dec 6, 2004
    #13
  14. I added a hackish CrosswordGenerator that finds a possible setup of words to
    fit the layout. Note that this code is ugly, violates OO Principles and a hack,
    but I wanted to share it in case somebody is interested.

    best regards,

    Brian

    I append the crossword generator below. For a sample output look at the url
    given above.


    module CrosswordGenerator
    class Wordlist < Array
    def initialize(file = '/usr/share/dict/words')
    super()
    self.replace File.read(file).upcase.split("\n").grep(/^[A-Z]*$/)
    end
    end

    class Filter
    attr_accessor :wordlist, :words

    def initialize
    @constraints = {}
    @length = {}
    @words = {}
    end

    def add_constraint(word_1, pos_1, word_2, pos_2)
    (@constraints[word_1] ||= []) << [[word_1, pos_1], [word_2, pos_2]]
    (@constraints[word_2] ||= []) << [[word_2, pos_2], [word_1, pos_1]]
    self
    end

    def add_length_constraint(word, length)
    @length[word] = length
    @words[word] = nil
    self
    end

    def set_word(index, word)
    @words[index] = word
    self
    end

    def unset_word(index)
    set_word(index, nil)
    self
    end

    def matching_words(word)
    re = '.' * @length[word]
    @constraints[word].each do | ((w1, i1), (w2, i2)) |
    re[i1] = @words[w2][i2] if @words[w2]
    end
    re = Regexp.new('^' + re + '$')
    @wordlists[word].grep(re)
    end

    def prepare
    @wordlists = {}
    @length.each do | index, length |
    re = /^.{#{length}}$/
    @wordlists[index] = wordlist.grep(re)
    end
    end
    end

    class Cell
    attr_accessor :h_word_length, :v_word_length, :number, :h_words, :v_words
    attr_accessor :h_word, :v_word

    def initialize
    @v_words = []
    @h_words = []
    end
    end

    class GeneratorLayout
    private
    def index_cells
    n = 1
    each_with_index do | cell, (row, col) |
    next unless cell
    cell.v_words << [cell, 0] if !self[row-1,col] and self[row+1, col]
    cell.h_words << [cell, 0] if !self[row,col-1] and self[row, col+1]
    cell.number, n = n, n+1 unless cell.v_words.empty? and
    cell.h_words.empty?
    end

    each_with_index do | cell, (row, col) |
    next unless cell
    if self[row-1, col]
    self[row-1, col].v_words.each do | word, index | cell.v_words <<
    [word, index + 1]; word.v_word_length = index + 2 end
    end
    if self[row, col-1]
    self[row, col-1].h_words.each do | word, index | cell.h_words <<
    [word, index + 1]; word.h_word_length = index + 2 end
    end
    end
    end

    public
    def initialize(file)
    @lines = file.read.split("\n").map{ |line| line.scan(/[_X]/).map{|cell|
    cell == '_' ? Cell.new : nil} }
    # Number Cells
    index_cells
    end

    def [](row, col)
    return @lines[row][col] if 0 <= row and 0 <= col and row < height and col
    < width
    return nil
    end

    def width() @lines[0].length end
    def height() @lines.length end

    def each_with_index
    @lines.each_with_index do | line, row | line.each_with_index do | cell,
    col | yield cell, [row, col] end end
    end

    def filter
    result = Filter.new
    each_with_index do | cell, (row, col) |
    next unless cell

    result.add_length_constraint(2 * cell.number, cell.h_word_length) if
    cell.h_word_length
    result.add_length_constraint(2 * cell.number + 1, cell.v_word_length)
    if cell.v_word_length

    cell.h_words.each do | cell1, index1 |
    cell.v_words.each do | cell2, index2 |
    result.add_constraint(2 * cell1.number, index1, 2 * cell2.number
    + 1, index2)
    end
    end
    end
    result
    end
    end

    def generate_(filter, wordlist, indices, &block)
    (block.call(filter); return true) if indices.empty?
    index = indices[0]
    filter.matching_words(index).each do | word |
    filter.set_word(index, word)
    generate_(filter, wordlist, indices[1..-1], &block)
    filter.unset_word(index)
    end
    end

    def generate(layout, wordlist = Wordlist.new, &block)
    filter = layout.filter
    filter.wordlist = wordlist
    word_indices = filter.words.keys.sort
    filter.prepare
    generate_(filter, wordlist, word_indices, &block)
    end
    end

    require 'crossword'
    include CrosswordGenerator

    data = ARGV[0] ? File.new(ARGV[0]) : DATA
    generator = GeneratorLayout.new(data.dup)
    layout = Crossword::Layout.new(data.dup)
    puts layout
    generate(generator) do | filter |
    puts "Solution:", filter.words.sort.map{ |i, w| "#{i / 2}#{i % 2 == 0 ? 'v' :
    'h'}: #{w}"}.join("\n")
    end

    __END__
    X _ _ _ _ X X
    _ _ X _ _ _ _
    _ _ _ _ X _ _
    _ X _ _ X X X
    _ _ _ X _ _ _
    X _ _ _ _ _ X
     
    Brian Schröder, Dec 6, 2004
    #14
  15. This is a wonderful test file.

    Did you try your program with it? It doesn't quite get it right,
    though it's very close. ;)

    James Edward Gray II
     
    James Edward Gray II, Dec 8, 2004
    #15
  16. My mistake. It does get it 100% right. I read the layout wrong.

    James Edward Gray II
     
    James Edward Gray II, Dec 8, 2004
    #16
    1. Advertisements

Ask a Question

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

You'll need to choose a username for the site, which only take a couple of moments (here). After that, you can post your question and our members will help you out.