Beefy Boxes and Bandwidth Generously Provided by pair Networks
Pathologically Eclectic Rubbish Lister

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

by salva (Monsignor)
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.

Comment on Re^2: Lights out puzzle (non-non-perl solution)
Download Code

Log In?

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://941139]
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others meditating upon the Monastery: (6)
As of 2014-09-23 06:50 GMT
Find Nodes?
    Voting Booth?

    How do you remember the number of days in each month?

    Results (210 votes), past polls