Beefy Boxes and Bandwidth Generously Provided by pair Networks
Keep It Simple, Stupid
 
PerlMonks  

Re: Matrix Formation

by Rhose (Priest)
on Jun 17, 2003 at 20:07 UTC ( #266627=note: print w/ replies, xml ) Need Help??


in reply to Matrix Formation

Ok, I ran out of time working on the "brute force" checking, but here is the shell of a program which should reduce the number of numbers which need to be checked to a small enough set. Sorry I could not complete the program (as it was actually starting to be fun. *Smiles*)

#!/usr/bin/perl use strict; use warnings; use constant MATRIX_DIM => 3; # Set your matrix size here use constant MAX_NUM => (10 ** MATRIX_DIM) - 1; # Since you need to find 2 times the matrix width distinct numbers, yo +u cannot # have a divisor greater than the maximum number divided by that produ +ct. # # For example, a 3 x 3 matrix has a maximum number of 999. You need 6 +distinct # numbers to "solve" the matrix, so the maximum possible divisor would + be 166. # 166 would result in 166, 332, 498, 664, 830, and 996. # my $Divisor = int(MAX_NUM / (MATRIX_DIM * 2)); my @Num; my @Sol=(); sub CheckSolution { my $pNum=shift; my @Sol=(); # INCOMPLETE CODE # # Place code here which checks every combination of MATRIX_DIM numbe +rs as rows # and sees if there are MATRIX_DIM other numbers which can act as co +lumns. # # For example, for a 3 x 3 matrix, this code should go through each +combination # of three number (for rows) from the passed array and see if there +are three # other numbers which would work with the selected rows as columns. +This should # be a workable computation for all smaller matrix sizes. # return @Sol; } while ($Divisor >= 1) { @Num=(); foreach (1..int(MAX_NUM / $Divisor)) { next if (($Divisor * $_) < (MAX_NUM / 10)); #Skip numbers which be +gin with zero push @Num, ($Divisor * $_); } print 'Checking solution for divisor ',$Divisor,': ',join('-',@Num), +"\n"; @Sol=CheckSolution(\@Num); last if ($#Sol > -1); $Divisor--; } print "\n"; if ($#Sol > -1) { print 'Maximum divisor is ',$Divisor,', solution is ',join('-',@Sol) +,"\n"; } else { print 'No solution found...',"\n"; }

Update: I finished code which will work on any size matrix and posted it Here.

Please note: I use "work" in the loosest terms as solving the 4x4 took 1.5 hours on my notebook.


Comment on Re: Matrix Formation
Download Code
Re: Re: Matrix Formation
by tall_man (Parson) on Jun 18, 2003 at 19:38 UTC
    Here is a possible implementation of CheckSolution (for 3x3 only -- generalization is possible but it is left as an exercise for the reader):
    sub CheckSolution { my $pNum = shift; my @Sol=(); # Do some easy pair checks first. my @digmap; foreach my $n (@$pNum) { my @digits = split //,$n; foreach (0..$#digits) { push @{$digmap[$_]->{$digits[$_]}},$n; } } # Two or more with same first digit. my $ref0 = $digmap[0]; my @lst0 = grep { scalar(@{$ref0->{$_}}) > 1 } keys %$ref0; return @Sol if (! scalar(@lst0)); # Two or more with same middle digit. my $ref1 = $digmap[1]; my @lst1 = grep { scalar(@{$ref1->{$_}}) > 1 } keys %$ref1; return @Sol if (! scalar(@lst1)); # Two or more with same last digit my $ref2 = $digmap[2]; my @lst2 = grep { scalar(@{$ref2->{$_}}) > 1 } keys %$ref2; return @Sol if (! scalar(@lst2)); #print "Passed pair test\n"; # Use these lists for candidates for the three row positions. my @uppers = map { @{$ref0->{$_}} } @lst0; my @centers = map { @{$ref1->{$_}} } @lst1; my @bottoms = map { @{$ref2->{$_}} } @lst2; my ($upper, $center, $bottom); my ($a, $b, $c, $d, $e, $f, $g, $h, $i); my ($adg, $beh, $cfi); # hash to simplify checking for duplicates. my %wholeset = map { $_ => 1 } @$pNum; my (%t1, %t2, %t3); foreach $upper (@uppers) { %t1 = %wholeset; $t1{$upper} = 0; foreach $center (@centers) { next if (! $t1{$center}); %t2 = %t1; $t2{$center} = 0; foreach $bottom (@bottoms) { next if (! $t2{$bottom}); %t3 = %t2; $t3{$bottom} = 0; ($a, $b, $c) = split //,$upper; ($d, $e, $f) = split //,$center; ($g, $h, $i) = split //,$bottom; $adg = $a . $d . $g; next if (! $t3{$adg}); $t3{$adg} = 0; $beh = $b . $e . $h; next if (! $t3{$beh}); $t3{$beh} = 0; $cfi = $c . $f . $i; next if (! $t3{$cfi}); # Solution found - return it. return ($upper, $center, $bottom); } # bottom } # center } #upper return @Sol; }
    I tried this and it found the 132-792-660 (divisor 44) case in about 4 seconds.

Log In?
Username:
Password:

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

How do I use this? | Other CB clients
Other Users?
Others perusing the Monastery: (8)
As of 2015-07-05 21:33 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    The top three priorities of my open tasks are (in descending order of likelihood to be worked on) ...









    Results (68 votes), past polls