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 Schroeder 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:
#!/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
# ...
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:
# ... private methods continued ...
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.
# ... private methods continued ...
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.
# ... private methods continued ...
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:
# ... private methods continued ...
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:
cwp = CrossWordPuzzle.new(ARGV.shift)
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...
