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.
Quiz Summary
The summary for this week's quiz should be:
Go read all submitted solutions until you understand them.
However, since I would probably be lynched for that, I'll try to be more specific. Here's some of what you're missing out on if you stop at just this summary.
Markus Koenig wrote a very nice solution in 20 minutes. The code
is very approachable and worth a look.
Jamis Buck gave his standard great solution, along with a tricky
test file to try solutions on.
T. Onoma passively builds puzzles, much like cellular automata
work. The solution is commented out and thus pretty approachable.
Andrew Johnson provided a very compact, yet not overly
complicated solution.
Clark took a different approach than most, building up the
display normally, and then removing the double borders.
Brian Schröder went above and beyond the call, as usual. (I'll be
blamed for that.) He actually attempted to make this puzzle into
something useful, by fitting words into the layout to make an
actual crossword challenge.
Pit Capitain did some heavy modification of the core classes to
setup a solution. Of particular note are the methods Array#weave()
and String#gub2!(), the latter of which handles 2D Regexps.
Finally, Harry Ohlsen chimed in with something that wasn't
actually a solution, but was an interesting example of real
world usage.
Do look these over, if you haven't already.
Now, let's break one down. Here's the setup from Jim Freeze's solution:
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
# ...
Nothing tricky there. First, initialize some constants and variables. After that, the private method build_puzzle() outlines the process. Let's dig deeper into each of those steps:
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
# ...
Step one. Again, pretty simple. Read the layout file. Break it down by row at each "\n" character and by square at each space. (Note: This solution does require the spaces from the quiz description.) Find the dimensions of the puzzle.
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
# ...
These two methods handle step two, dropping filled border squares. Working here in what is still the character-by-character layout makes things easier. Jim uses a simple transpose() to make essentially 2D search and replaces. More than one submission capitalized on this technique, but it still wows dummies like me.
The search and replace logic is two-fold: Turn all Xs at the beginning or end of the line into spaces and turn all Xs next to spaces into spaces. Repeat this until there are no more changes. This causes the edges to creep in until all filled border squares have been eliminated.
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
# ...
Here's the third step, numbering squares. The approach here is much the same as step two. A combination of transpose() and gsub!() are used to mark squares at the beginning of words with a # character. Words are defined as a run of # and/or _ characters at the beginning of a line or after a filled box or open space.
With #s in place, it's a simple matter to replace them with an actual number. The code is a little arcane there, because #s have to be checked in the normal "@grid" and in "grid_prime", the transposed grid.
Now that the grid has been doctored into the desired format, we need to wrap cells in borders and space, then stringifying them. Here's the code for that:
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
The method to_s() drives the conversion process. It walks the doctored up grid calling cell() to do the formatting and overlay() to place it in the puzzle.
cell() just adds # borders and space as defined by the quiz, based on the cell type it is called on.
overlay() is clever. It just happily draws cells. However, it's called with placements close enough together to "overlay" the borders, reducing them to a single line.
(Note: This "collapsing borders" technique is common in many aspects of programming. Examine the output of the mysql command line tool, GNU Chess, or a hundred other tools. It's also common for GUI libraries to combine borders of neighboring elements.)
With an array of the entire puzzle assembled, to_s() finishes with few calls to join().
The trivial "main" program combines build and display:
puts cwp.to_s
Jim Mernard's solution was remarkably similar to the solution I just showed, which just proves that all guys named Jim program the same. That's why I have to go by James, my solution was terrible.
My thanks go out to all people puzzled by this quiz, especially those who felt the need to do something about it.
Tomorrows quiz involves building a "WOPR" and teaching it not to launch nuclear missiles...
