Beefy Boxes and Bandwidth Generously Provided by pair Networks
Do you know where your variables are?

Re^2: Lights out puzzle (non-non-perl solution)

by salva (Abbot)
on Dec 01, 2011 at 18:33 UTC ( #941139=note: print w/replies, xml ) Need Help??

in reply to Re: Lights out puzzle (non-perl solution)
in thread Lights out puzzle

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.

Log In?

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://941139]
and all is quiet...

How do I use this? | Other CB clients
Other Users?
Others avoiding work at the Monastery: (7)
As of 2017-10-18 12:05 GMT
Find Nodes?
    Voting Booth?
    My fridge is mostly full of:

    Results (244 votes). Check out past polls.