Isn't this one a fun problem? Three cheers to Mark Jason Dominus for
introducing it to me.
The solutions were fantastic as well. In particular, people found many
interesting ways to render the output: using some Unixisms in the terminal,
using curses, rendering trivial image formats like PPM and XPM, building images
programmatically with RMagick, and even 3D rendering with OpenGL. All of those
were very cool.
I'm going to show my own code below, but I will take a few diversions as we go.
Here's the start of my simulator class:
#!/usr/bin/env ruby -w
class SimFrost
def initialize(width, height, vapor)
@ticks = 0
@grid = Array.new(height) do
Array.new(width) { rand(100) < vapor ? "." : " " }
end
@grid[height / 2][width / 2] = "*"
end
attr_reader :ticks
def width
@grid.first.size
end
def height
@grid.size
end
# ...
This setup code creates the grid object, filled with the particles described in
the quiz using the quiz example notation. Several other solvers used Symbols or
constants for these element which reads a lot better.
My grid is just Arrays of columns inside an Array of rows. This is called "row
major" order. It's a little backwards to the way we normally think, because you
index with a Y coordinate and then the X, but that's easy enough to fix with a
helper method. It's also great for showing results, because you can process
them row by row.
The other three methods are just accessors for attributes of the simulation.
One interesting point of discussion raised on the mailing list by Christoffer
Lerno was that populating the grid as I do above, by testing a percentage for
every cell, doesn't necessarily fill the grid with that exact percent of
elements. The smaller the grid, the more likely you are to be off. For
example:
>> percent = 30
=> 30
>> grid = Array.new(100) { rand(100) < 30 ? "." : " " }
=> [" ", ".", ".", " ", " ", " ", ..., " "]
>> grid.grep(/\./).size
=> 37
Notice how the actual percentage is off from my requested percentage by seven
percent. This is less of an issue the bigger the grid gets and small grids
don't tend to be too interesting anyway, but there will usually be some level of
error with this approach.
To solve this, you really need to calculate the percentage against the full grid
size and ensure that you fill exactly that many cells. Christoffer's code for
that was:
require 'enumerator'
percentage = 30
width = 30
height = 20
vapour = width * height * percentage / 100
vacuum = width * height - vapour
grid = []
(Array.new(vacuum, ' ') + Array.new(vapour, '.')).
sort_by { rand }.
each_slice(width) { |s| grid << s }
Laziness won out though and most of us used the trivial cell by cell fill
strategy.
Getting back to my code, here are two more methods on the simulator:
# ...
def complete?
not @grid.flatten.include? "."
end
def to_s
@grid.map { |row| row.join }.join("\n")
end
# ...
These are pretty easy. First, complete?() just tells us if we are done by
checking for any remaining vapor particles. The other method, to_s(), is just a
nested join() on the grid object used to output results.
Now we're ready for the heart of the simulation:
# ...
def tick
(tick_start...height).step(2) do |y|
(tick_start...width).step(2) do |x|
cells = [ [x, y ],
[wrap_x(x + 1), y ],
[wrap_x(x + 1), wrap_y(y + 1)],
[x, wrap_y(y + 1)] ]
if cells.any? { |xy| cell(xy) == "*" }
cells.select { |xy| cell(xy) == "." }.
each { |xy| cell(xy, "*") }
else
rotated = cells.dup
if rand(2).zero?
rotated.push(rotated.shift)
else
rotated.unshift(rotated.pop)
end
new_cells = rotated.map { |xy| cell(xy) }
cells.zip(new_cells) { |xy, value| cell(xy, value) }
end
end
end
@ticks += 1
end
private
def tick_start; (@ticks % 2).zero? ? 0 : 1 end
def wrap_x(x) x % width end
def wrap_y(y) y % height end
def cell(xy, value = nil)
if value
@grid[xy.last][xy.first] = value
else
@grid[xy.last][xy.first]
end
end
end
# ...
The tick() method is where the action is. It walks the grid neighborhood by
neighborhood making changes. Note that cells are managed as just two element
Arrays and I use the human-friendly X-before-Y notation. I also build the
neighborhood by putting the cells in clockwise order. This means a rotation is
just a shift() and push(), or pop() and unshift() to go the other way.
Cell access is all handled through the cell() helper method, which switches the
order for row major access. Christoffer Lerno had an interesting approach to
this cell access problem where he defined a handful of methods with some
metaprogramming:
class Neighbourhood
2.times do |y|
2.times do |x|
class_eval %Q{
def xy#{x}#{y}; @grid[@x + #{x}, @y + #{y}]; end
def xy#{x}#{y}=(v); @grid[@x + #{x}, @y + #{y}] = v; end
}
end
end
# ...
This allowed him to define rotations as:
# ...
def ccw90
self.xy00, self.xy10, self.xy01, self.xy11 = xy10, xy11, xy00, xy01
end
def cw90
self.xy00, self.xy10, self.xy01, self.xy11 = xy01, xy00, xy11, xy10
end
# ...
Getting back to my code, I also have wrappers for X and Y coordinates so I can
properly handle the grid edges with modulo arithmetic. This code only ever runs
off the right and bottom edges of the grid and only by one cell, so we don't
need to worry about negative numbers.
Finally, tick_start() toggles the neighborhood offset for me, though Dave Burt
did it with some cool bitwise XOR operations that looked like this:
>> offset = 0
=> 0
>> offset ^= 1
=> 1
>> offset ^= 1
=> 0
>> offset ^= 1
=> 1
Now that we have a simulator, we're ready for some display code. The first
display model I built was based on the Unix terminal because it was so easy to
do:
# ...
class UnixTerminalDisplay
BLUE = "\e[34m"
WHITE = "\e[37m"
ON_BLACK = "\e[40m"
CLEAR = "\e[0m"
def initialize(simulator)
@simulator = simulator
end
def clear
@clear ||= `clear`
end
def display
print clear
puts @simulator.to_s.gsub(/\.+/, "#{BLUE + ON_BLACK}\\&#{CLEAR}").
gsub(/\*+/, "#{WHITE + ON_BLACK}\\&#{CLEAR}").
gsub(/ +/, "#{ ON_BLACK}\\&#{CLEAR}")
end
end
# ...
Here we just wrap a simulator with some search and replace logic. The regexen
are used to wrap the icons in terminal escape codes to color them. The code
also shells out to clear, or uses the cached result, to erase the terminal
before each round of drawing.
While that's easy to code, it's not portable or flashy. Simulations look so
much better in graphical representations and as I mentioned before, solvers
produced those in a variety of ways.
My own solution to the graphics problem is another trick I learned from Mark
Jason Dominus. Believe it or not, there are a few super trivial image formats
that you can hand roll in no time. It pays to learn one of them, for situations
like this, when you just need some quick and dirty image output. You can always
use a converter to get them into more popular image formats. That's exactly how
I built the quiz movie.
There are a few versions of the PPM image format, but the one I used goes by the
following rules:
1. Start the image file with P6 on its own line.
2. The second line is the width in pixels, followed by the height in
pixels, followed by the color range (just use 255 for this) as a
space delimited list of integers. For example, a 640 by 480 image
has a second line of: 640 480 255.
3. From that point on, the rest of data is binary. Each pixel is
represented by three characters which represent the amount of red,
green, and blue coloring in that pixel. The numeric byte value of
the character is the amount for the color it represents.
Watch how easy that is to code up:
# ...
class PPMImageDisplay
BLUE = [0, 0, 255].pack("C*")
WHITE = [255, 255, 255].pack("C*")
BLACK = [0, 0, 0 ].pack("C*")
def initialize(simulator, directory)
@simulator = simulator
@directory = directory
Dir.mkdir directory unless File.exist? directory
end
def display
File.open(file_name, "w") do |image|
image.puts "P6"
image.puts "#{@simulator.width} #{@simulator.height} 255"
@simulator.to_s.each_byte do |cell|
case cell.chr
when "." then image.print BLUE
when "*" then image.print WHITE
when " " then image.print BLACK
else next
end
end
end
end
private
def file_name
File.join(@directory, "%04d.ppm" % @simulator.ticks)
end
end
# ...
The image implementation I just described in encapsulated in the display()
method. The binary values are handled by constants at the top of the class.
Note how easy it is to build PPM's RGB colors using pack(). The rest of the
class just creates a directory to hold the frame images and builds file names
based on the current tick count.
Finally, we come to the application code of my solution:
if __FILE__ == $PROGRAM_NAME
require "optparse"
options = { :width => 80,
:height => 22,
:vapor => 30,
:output => UnixTerminalDisplay,
:directory => "frost_images" }
ARGV.options do |opts|
opts.banner = "Usage: #{File.basename($PROGRAM_NAME)} [OPTIONS]"
opts.separator ""
opts.separator "Specific Options:"
opts.on( "-w", "--width EVEN_INT", Integer,
"Sets the width for the simulation." ) do |width|
options[:width] = width
end
opts.on( "-h", "--height EVEN_INT", Integer,
"Sets the height for the simulation." ) do |height|
options[:height] = height
end
opts.on( "-v", "--vapor PERCENT_INT", Integer,
"The percent of the grid filled with vapor." ) do |vapor|
options[:vapor] = vapor
end
opts.on( "-t", "--terminal",
"Unix terminal display (default)." ) do
options[:output] = UnixTerminalDisplay
end
opts.on( "-i", "--image",
"PPM image series display." ) do
options[:output] = PPMImageDisplay
end
opts.on( "-d", "--directory DIR", String,
"Where to place PPM image files. ",
%Q{Defaults to "frost_images".} ) do |directory|
options[:directory] = directory
end
opts.separator "Common Options:"
opts.on( "-?", "--help",
"Show this message." ) do
puts opts
exit
end
begin
opts.parse!
rescue
puts opts
exit
end
end
simulator = SimFrost.new( options[:width],
options[:height],
options[:vapor] )
setup = options[:output] == PPMImageDisplay ?
[simulator, options[:directory]] :
[simulator]
terminal = options[:output].new(*setup)
terminal.display
until simulator.complete?
sleep 0.5 if options[:output] == UnixTerminalDisplay
simulator.tick
terminal.display
end
end
While that looks like a lot of code, most of it is just option parsing where I
fill an options Hash. The last twelve lines are where the interesting stuff
happens. A simulator is constructed and then wrapped in a display class. From
there we go into the main event loop which is just sleep (terminal display
only), tick(), and draw until the simulation is complete?().
My thanks to all the super cool Ruby programmers who can literally create ice
with the movements of their fingers.
Ruby Quiz will now take a two week vacation so I can get out of town and have a
little fun. Send me some great quiz ideas while I'm gone and we will get them
into play when I return.