Welcome to the Monastery PerlMonks

Re: Matrix Formation

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

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.

Replies are listed 'Best First'.
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);

# 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;

\$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.

Create A New User
Node Status?
node history
Node Type: note [id://266627]
help
Chatterbox?
and all is quiet...

How do I use this? | Other CB clients
Other Users?
Others cooling their heels in the Monastery: (6)
As of 2017-10-23 07:03 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
My fridge is mostly full of:

Results (277 votes). Check out past polls.

Notices?