[SUMMARY] Crosswords (#10)

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