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

Re: magic squares

by Limbic~Region (Chancellor)
on Apr 10, 2009 at 13:41 UTC ( [id://756822]=note: print w/replies, xml ) Need Help??


in reply to magic squares

sflitman,
Ok, I have one final contribution. This solution is still roughly O(N) where N is the number of names to check but it turns looking through the 206 unique squares into a hash lookup. It also has a couple of advantages over my previous solution. It only precalculates all solutions once and subsequently loads them from disk. Additionally, it displays all matching solutions, not just the first one found.
#!/usr/bin/perl use strict; use warnings; use Storable; my $db = 'msquare_solutions.db'; if (! -e $db) { my %possible; for my $x (5 .. 22) { for my $y (grep {$_ != $x} 1 .. int((25 - $x) / 2)) { my $max = 26 - $x - 2 * $y; my $min = $x - 2 * $y - 1; for my $z (grep {$_ != $x && $_ != $y} 1 .. ($min < $max ? + $min : $max)) { my @square = ( ($x + $y), ($x + $z), ($x - $y - $z), ($x - 2 * $y - $z), ($x), ($x + 2 * $y + $z) +, ($x + $y + $z), ($x - $z), ($x - $y) ); my @sol = map chr($_ + 64), @square; my $pow_iter = powerset(sort @sol); while (my @set = $pow_iter->()) { my $key = join '', @set; push @{$possible{$key}}, \@sol; } } } } store(\%possible, $db); } my $possible = retrieve($db); for (qw/PAUL JOHN MARTY SHEILA SMACK SUZY ELSA/) { my $key = join '', sort split //; if ($possible->{$key}) { for my $square (@{$possible->{$key}}) { print "$_ is contained within '@$square'\n"; } } else { print "No solution for $_\n"; } } sub powerset { # Choose any powerset iterator you want - ensure ascending order o +utput # I used my own from [id://394168] die "Implementation left as an exercise for the user"; }

Cheers - L~R

Log In?
Username:
Password:

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

How do I use this?Last hourOther CB clients
Other Users?
Others studying the Monastery: (6)
As of 2024-03-28 14:32 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found