A few weeks ago I’ve participated in Code Retreat in Poznań. The main theme of the workshop was not to learn some specific programming techniques, but rather to try working in pairs, in fact in many pairs, five or six, each for less than an hour.
The goal was to program Conway’s Game of Life, where each cell on rectangular board is born, lives or dies depending on the number of live neighbors (the live cell with 2 or 3 live neighbors survives, the dead cell with 3 live neighbors becomes alive).
The most common model is a two dimensional array. However, this approach has a drawback of the need to expand the array in all directions when new cells are to be born. Coding it correctly, with all test cases in less than an hour is not easy.
A friend in one of the pairs had a great idea: forget about an array and keep a set of live cells. Then, in each evolution step, expand this set with newly born cells and remove the ones which don’t survive.
We coded the solution in Ruby (without tests) and Java (with tests, in later session). Below is my personal try in Perl.
The concept can be neatly described in set theory. Let S be the set of live cells, neigh(c) is a function returning all neighbors of cell c. The set of candidates (potentially live cells in next round) is
$$ C = \bigcup_{c\in S} \mathrm{neigh}(c) $$
then the live set in the next round is
$$ S’ = \{ c\in C : |\mathrm{lneigh}(c)|=3 \vee c\in S \wedge |\mathrm{lneigh}(c)|=2 \} $$
\( \mathrm{lneigh}(c) \) being the set of live neighbors of c
$$ \mathrm{lneigh}(c) = \mathrm{neigh}(c) \cap S $$
The first version of code used plain hashes as sets, but using Set::Scalar gives cleaner code. There are some caveats, however.
use warnings;
use strict;
use Test::More;
use Set::Scalar;
# well, this should be default...
*Set::Scalar::Base::_strval = sub { "$_[0]" };
my @D = (
[ -1, -1 ], [ -1, 0 ], [ -1, 1 ],
[ 0, -1 ], [ 0, 1 ],
[ 1, -1 ], [ 1, 0 ], [ 1, 1 ]
);
my $h_rod = Set::Scalar->new(Seq::from_arr([-1,0], [0,0], [1,0]));
my $v_rod = Set::Scalar->new(Seq::from_arr([0,-1], [0,0], [0,1]));
my $set = Set::Scalar->new(Seq::from_arr([1, 2], [3, 4]));
ok $set->has(Seq->new(1,2)); # this wouldn't work without _strval redefinition
$set = $h_rod;
$set = step($set);
is $set, $v_rod;
$set = step($set);
is $set, $h_rod;
done_testing;
sub step {
my ($live) = @_;
my $candid = Set::Scalar->new(map { neigh($_) } $live->members);
return Set::Scalar->new(grep {
my @c_live_neigh = grep { $live->has($_) } neigh($_);
@c_live_neigh == 3 || @c_live_neigh == 2 && $live->has($_);
} $candid->members);
}
sub neigh {
my ($o) = @_;
map { Seq->new($o->[0] + $_->[0], $o->[1] + $_->[1]) } @D;
}
package Seq;
use overload '""' => sub {
return join ",", @{$_[0]};
};
sub new {
my $class = shift;
return bless [ @_ ], $class;
}
sub from_arr {
return map { Seq->new(@$_) } @_;
}
As Jarkko writes in the docs of Set::Scalar:
Using references (or objects) as set members has not been extensively tested. The desired semantics are not always clear: what should happen when the elements behind the references change? Especially unclear is what should happen when the objects start having their own stringification overloads.
Well, this is the case here. As we insert into the set the array refs, we need to convince Set::Scalar that two different refs are the same set element, if only the referred arrays have the same content.
However, stringification overload is not enough, as Set::Scalar additionally uses the refs addresses in its own stringification sub, _strval. So we need to redefine the sub to provide the set with our way of comparing things.
In fact, this was a big surprise to me: none of checked CPAN set distributions allowed the use of own identity methods. Even plain old hash-as-a-set is better in this regard, as stringification is performed to check for key presence:
my %hsh = map { $_ => $_ } ( Seq->new(1,2), Seq->new(3,4), Seq->new(1,2) );
is values(%hsh), 2;
Recent Comments