[QUIZ] Crosswords (#10)

ruby-talk
1

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.

2

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][i]
             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 Freeze
Code Red. Code Ruby

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. :slight_smile:

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

4

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 :slight_smile:

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

crossit.rb (3.53 KB)

test1.cit (85 Bytes)

5

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[i] << '#' 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[i] << '#' end
            else
              (1...cell_height).each do | i | lines[i] << ' ' 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[i] << ' ' * (cell_width-1)
end
            else
              (1...cell_height).each do | i | lines[i] << '#' * (cell_width-1)
end
            end
          else
            (1...cell_height).each do | i | lines[i] << ' ' * (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
http://www.brian-schroeder.de/

6

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

7

I originally thought I would have my solution work in two passes--the first,
effectively building a formatted string, and the second emitting the string
to the chosen stream. I decided to try and do it in one pass, though,
building the layout and emitting the string in a single pass.

I used two classes: Definition, which was just the encapsulation of the
input, and Formatter, which performed the layout formatting.

I've also attached a sample input file. :slight_smile:

ruby-quiz.layout (540 Bytes)

···

##########################################################################
# Jamis Buck's solution to Ruby-Quiz #10:
##########################################################################

module Layout

  class Definition
    def initialize( string )
      @lines = string.split( $/ ).map { |l| l.gsub(/\s/,"") }
      @properties = Hash.new
    end

    def rows
      @lines.length
    end

    def columns
      @lines.first.length
    end

    def []( x, y )
      return false if ( x < 0 ) || ( y < 0 )
      return false if ( x >= columns ) || ( y >= rows )
      @lines[y][x] == ?_
    end

    def property( x, y, name )
      @properties[ [x,y,name] ]
    end

    def set_property( x, y, name, value )
      @properties[ [x,y,name] ] = value
    end
  end

  class Formatter
    def initialize( definition )
      @definition = definition
    end

    CELL_WIDTH = 5
    CELL_HEIGHT = 3

    NUMBER_TOKEN = "%-3s"

    FILLED_CELL = [ "#####", "#####", "#####" ]
    EMPTY_CELL = [ "#####", "##{NUMBER_TOKEN} ", "# " ]
    BLANK_CELL = [ "`^^^^", "< ", "< " ]

    WALL = "#"
    SPACE = " "

    def format( output=STDOUT )
      number = 1
      @definition.rows.times do |row|
        CELL_HEIGHT.times do |row_y|
          @definition.columns.times do |col|
            cell = @definition[col,row] ? EMPTY_CELL : FILLED_CELL
            line = cell[row_y]

            number_str = ""
            if cell[row_y].include?(NUMBER_TOKEN) && @definition[col,row]
              if ( !@definition[col-1,row] && @definition[col+1,row] ) ||
                 ( !@definition[col,row-1] && @definition[col,row+1] )
              # begin
                number_str = number.to_s
                number += 1
              end
            elsif !@definition[col,row]
              if has_exit_path( col, row )
                line = BLANK_CELL[row_y]
                clear_left = has_exit_path( col-1, row )
                clear_up = has_exit_path( col, row-1 )
                clear_corner = has_exit_path( col-1, row-1 )
                up_char = clear_up ? SPACE : WALL
                left_char = clear_left ? SPACE : WALL
                corner_char = clear_corner && clear_left && clear_up ?
                  SPACE : WALL
                line = line.tr( "`^<", "#{corner_char}#{up_char}#{left_char}" )
              else
                @definition.set_property( col, row, :exit_path, false )
              end
            end

            output << line % number_str
          end
          puts( @definition[@definition.columns-1,row-1] &&
            row_y == 0 || @definition[@definition.columns-1,row] ?
            WALL : SPACE )
        end
      end

      @definition.columns.times do |col|
        if !@definition[col,@definition.rows-1]
          if col == 0 || col > 0 && !@definition[col-1,@definition.rows-1]
            print SPACE
          else
            print WALL
          end
          print SPACE*4
        else
          print WALL*5
        end
      end

      if @definition[@definition.columns-1,@definition.rows-1]
        print WALL
      end

      puts
    end

    def has_exit_path( col, row )
      @visited = Hash.new
      find_exit_path_recurse( col, row )
    end
    private :has_exit_path

    def find_exit_path_recurse( col, row )
      return false if @definition[col,row]
      return false if @visited[ [col,row] ]
      @visited[ [col,row] ] = true

      return true if @definition.property( col, row, :exit_path )
      return false if @definition.property( col, row, :exit_path ) == false

      if col == 0 || col == @definition.columns-1 ||
         row == 0 || row == @definition.rows-1
      #begin
        @definition.set_property( col, row, :exit_path, true )
        return true
      end

      found = ( col > 0 && !@definition[col-1,row] &&
        find_exit_path_recurse( col-1, row ) )

      found = found || ( col < @definition.columns-1 &&
        !@definition[col+1,row] && find_exit_path_recurse( col+1, row ) )

      found = found || ( row > 0 && !@definition[col,row-1] &&
        find_exit_path_recurse( col, row-1 ) )

      found = found || ( row < @definition.rows-1 && !@definition[col,row+1] &&
        find_exit_path_recurse( col, row+1 ) )

      if found
        @definition.set_property( col, row, :exit_path, true )
        return true
      end

      return false
    end
    private :find_exit_path_recurse

  end

  def format( file, output=STDOUT )
    definition = Definition.new( File.read( file ) )
    Formatter.new( definition ).format( output )
  end
  module_function :format

end

Layout.format( ARGV.first, STDOUT ) if __FILE__ == $0

--
Jamis Buck
jgb3@email.byu.edu
http://www.jamisbuck.org/jamis

8

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]
      left = board[y][x - 1]
      right = board[y][x + 1]
      bottom = board[y + 1]
      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]
    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]
    
    cell.render drawn_row, top, left, right, bottom
  end
  drawn_row.each { |e| puts e if e.length > 0 }
end

···

On Dec 5, 2004, at 8:07 AM, Markus Koenig wrote:

This is my solution.

9

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.

10

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
      (0...@pstr.size - @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)
      (0...@cells.size) === 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

11

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[i].size)
       nil
     else
       @puzzle[i][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[i][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[i][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

12

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] =
             paper[y][x+Cell::WIDTH-1] =
             paper[y+Cell::HEIGHT-1] =
             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] = '|'
             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[i] =
             line.split(//).each { | c | @cells[i] << Cell.from_char(c) }
         }
     end

     def introduce_neighbors
         @cells.each_with_index { | row, i |
             row.each_with_index { | cell, j |
                 cell.neighbors[:left] = @cells[i][j-1] unless j == 0
                 cell.neighbors[:right] = @cells[i][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, jimm@io.com, http://www.io.com/~jimm/
"An object at rest cannot be stopped!"
     -- The Evil Midnight Bomber What Bombs At Midnight

13

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.

···

On Sunday 05 December 2004 05:53 pm, Pit Capitain wrote:

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.
/ \ transami@runbox.com

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'[i]).chr}
-Tadayoshi Funaba

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

···

On Mon, 6 Dec 2004 05:47:52 +0900 Brian Schröder <ruby@brian-schroeder.de> wrote:

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/

--
Brian Schröder
http://www.brian-schroeder.de/

15

trans. (T. Onoma) schrieb:

Very intersting approach, Capitain.

Please call me by my first name, Pit. Otherwise it interferes with the feeling of being among friends at ruby-talk :slight_smile:

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?

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

16

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. :wink:

James Edward Gray II

···

On Dec 5, 2004, at 8:21 AM, Jamis Buck wrote:

I've also attached a sample input file. :slight_smile:

17

My mistake. It does get it 100% right. I read the layout wrong.

James Edward Gray II

···

On Dec 8, 2004, at 12:57 PM, James Edward Gray II wrote:

On Dec 5, 2004, at 8:21 AM, Jamis Buck wrote:

I've also attached a sample input file. :slight_smile:

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. :wink:

18

>
>>I've also attached a sample input file. :slight_smile:
>
>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. :wink:

My mistake. It does get it 100% right. I read the layout wrong.

Gah. Thanks for the heart-attack, James. :slight_smile: I was pretty sure I'd
tested it--glad to hear that it works correctly after all.

- Jamis

···

On 04:03 Thu 09 Dec , James Edward Gray II wrote:

On Dec 8, 2004, at 12:57 PM, James Edward Gray II wrote:
>On Dec 5, 2004, at 8:21 AM, Jamis Buck wrote:

James Edward Gray II

--
Jamis Buck
jgb3@email.byu.edu
http://www.jamisbuck.org/jamis