*Now solving a linear equation over GF(2) is something apparently very few libraries can do*
That's quite easy to implement, so easy that, well... see Algorithm::GaussianElimination::GF2.
Using that module, the Lights On problem gets reduced to:
`use strict;
use warnings;
use Algorithm::GaussianElimination::GF2;
use 5.010;
(@ARGV >= 1 and @ARGV <= 2) or die "Usage:\n $0 len [width]\n\n";
my ($len, $w) = @ARGV;
unless (defined $w) {
$w = int sqrt($len);
$w++ unless $w * $w == $len;
}
my $a = Algorithm::GaussianElimination::GF2->new;
for my $ix (0..$len-1) {
my $eq = $a->new_equation;
$eq->b(1);
$eq->a($ix, 1);
my $up = $ix - $w;
$eq->a($up, 1) if $up >= 0;
my $down = $ix + $w;
$eq->a($down, 1) if $down < $len;
my $left = $ix - 1;
$eq->a($left, 1) if $left % $w + 1 != $w;
my $right = $ix + 1;
$eq->a($right, 1) if $right % $w and $right < $len;
}
my ($sol, @base0) = $a->solve;
if ($sol) {
my @sol = @$sol;
while (@sol) {
my @row = splice @sol, 0, $w;
say "@row";
}
for my $sol0 (@base0) {
say "sol0:";
my @sol0 = @$sol0;
while (@sol0) {
my @row = splice @sol0, 0, $w;
say "@row";
}
}
}
else {
say "no solution found"
}
`
On my computer the 14x14-7 problem gets solved in 0.06 seconds. |
Comment onRe: Lights out puzzle (non-perl solution)SelectorDownloadCode