[QUIZ] Crosswords (#10)

[Ruby Quiz]

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.

 

[jim]

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

 

[Markus Koenig]

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

 

[trans. (T. Onoma)]

--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 uzzle
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 uzzle
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--

 

[James Edward Gray II]

This is my solution.

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

 

[trans. (T. Onoma)]

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.

 

[Andrew Johnson]

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
([email protected] - @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)
([email protected]) === 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

 

[Clark]

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

 

[Brian Schröder]

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

 

[Pit Capitain]

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

 

[Jim Menard]

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

 

[trans. (T. Onoma)]

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.
/ \ (e-mail address removed)

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

 

[Pit Capitain]

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

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

 

[Brian Schröder]

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/

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

 

[James Edward Gray II]

I've also attached a sample input file.

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]

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.

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

James Edward Gray II