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