http://www.perlmonks.org?node_id=266572

artist has asked for the wisdom of the Perl Monks concerning the following question:

Dear Monks

I found an interesting puzzle and here is my attempt to solve it. Let say we have NxN matrix.

```[
[1, 2]
[4, 8]
]
By Joining the columns and rows individually, I get the following four formed-numbers. 12,14,28,48 There Common Divisor is '2'. I like to find the matrix with the highest common divisor. Some condtions are..
• No two formed-numbers be same.
I can do it easily for 2x2 matrix and found highest divisor as 7. and the formed-numbers : 28,21,14,84.
```[[2,8]
[1,4]]
How I can do with higher dimentions more efficiently? Even for 3X3 with it has to test around billion numbers with my method.

```\$| += 1;
foreach my \$divider (2..9){
print "Divider \$divider\n";
N: foreach \$n (1111..9999){
next if \$n =~ /0\d+/;
@n = split //,\$n;
my \$count  = 0;
my @pairs;
my %pairs;
foreach (qw(01 02 13 23)){
my(\$p,\$q) = split //;
my \$num = \$n[\$p].\$n[\$q];
push @pairs, \$num;
next N if defined \$pairs{\$num};
\$pairs{\$num} = 1;
\$count++ if \$num % \$divider  == 0;
}
print join " " => @pairs,"\n" if \$count == 4;
}
}
Thanks
artist

Replies are listed 'Best First'.
Re: Matrix Formation
by pzbagel (Chaplain) on Jun 17, 2003 at 18:21 UTC

Some observations:

```next if \$n =~ /0\d+/;
• The \d+ is uneccesary in this line if you are just trying to skip numbers that contains zeroes. /0/ is adequate and infact, this regex misses numbers that end in zero such as 1120, 1130, etc.
```\$count++ if \$num % \$divider  == 0;
• The logic on this line is backwards, it should last if the result of % is non-zero, that way you will not have to check through all the number combinations if the first div fails.
```foreach my \$divider (2..9)
• Finally, if you are looking for the highest common divisor, you should turn this loop around and start with 9, I would also move it inside the foreach (qw(01 02 13 23)) and do a last if you find a valid divisor for all 4 numbers again stopping you from checking too many combinations.

HTH

Re: Matrix Formation
by Solo (Deacon) on Jun 17, 2003 at 19:28 UTC
The greatest common divisor of a set of integers is the product of the primes common to each factored integer (there's a better way to say that, but it's been 10+ years since Number Theory :)

So, your problem is reduced to factoring each of the N^N integers and somehow intersecting the resulting sets of factors.

Quantum::Superpositions claims to make factoring trivial (and possibly the rest of the program, as well).

Update: Hey, Look! Here's a new Q&A node that finds the intersection of sets. I wonder if it handles repeated items, since factorings may look like 8 = (2, 2, 2) or 45 = (3,3,5) for examples...

--Solo

--
You said you wanted to be around when I made a mistake; well, this could be it, sweetheart.
It's actually easier to find the greatest common divisor of two numbers than to factor them. There's an O(log N) algorithm for it. There's one in the snippets: greatest common factor and also one in Math::Pari.
```use Math::Pari qw(gcd);
my \$x = gcd(232,300);
print "gcd is \$x\n";
Update: A nested loop search is a good way to eliminate cases quickly:
```use strict;
my @nineset = (9, 8, 7, 6, 5, 4, 3, 2, 1);
my @tenset =  (9, 8, 7, 6, 5, 4, 3, 2, 1, 0);

# Array is arranged:
#  a b c
#  d e f
#  g h i

sub gcf {
my (\$x, \$y) = @_;
(\$x, \$y) = (\$y, \$x % \$y) while \$y;
return \$x;
}

sub multigcf {
my \$x = shift;
\$x = gcf(\$x, shift) while @_;
return \$x;
}

my (\$a, \$b, \$c, \$d, \$e, \$f, \$g, \$h, \$i);
my (\$abc, \$def, \$ghi, \$adg, \$beh, \$cfi);
my (\$gcf1, \$gcf2, \$gcf3, \$gcf4);

my \$maxgcf = 1;
my @maxsolution = ();
foreach \$a (@nineset) {
foreach \$b (@nineset) {
foreach \$c (@nineset) {
foreach \$d (@nineset) {
foreach \$g (@nineset) {
\$abc = \$a . \$b . \$c;
\$adg = \$a . \$d . \$g;
next if (\$gcf1 <= \$maxgcf || \$gcf1 == 1);
foreach \$e (@tenset) {
foreach \$f (@tenset) {
\$def = \$d . \$e . \$f;
next if (\$abc eq \$def || \$adg eq \$def);
next if (\$gcf2 <= \$maxgcf || \$gcf2 == 1);
foreach \$h (@tenset) {
\$beh = \$b . \$e . \$h;
next if (\$abc eq \$beh || \$adg eq \$beh || \$def
+eq \$beh);
\$gcf3 = multigcf(\$beh, \$def, \$abc, \$adg);
next if (\$gcf3 <= \$maxgcf || \$gcf3 == 1);
foreach \$i (@tenset) {
\$cfi = \$c . \$f . \$i;
next if (\$abc eq \$cfi || \$adg eq \$cfi || \$d
+ef eq \$cfi || \$beh eq \$cfi);
\$ghi = \$g . \$h . \$i;
next if (\$abc eq \$ghi || \$adg eq \$ghi || \$d
+ef eq \$ghi || \$beh eq \$ghi
|| \$cfi eq \$ghi);
\$gcf4 = multigcf(\$cfi, \$ghi, \$beh, \$def, \$a
next if (\$gcf4 <= \$maxgcf || \$gcf4 == 1);

# Found a good one so far.
\$maxgcf = \$gcf4;
@maxsolution = (\$a, \$b, \$c, \$d, \$e, \$f, \$g,
+ \$h, \$i);
} # i
} #h
} #f
} #e
} #g
} # d
} #c
} #b
} #a

(\$a, \$b, \$c, \$d, \$e, \$f, \$g, \$h, \$i) = @maxsolution;
print "\$a \$b \$c\n";
print "\$d \$e \$f\n";
print "\$g \$h \$i\n";
print "Common divisor is: \$maxgcf\n";
Result I get is:
```8 3 2
9 2 8
6 0 8
Common divisor is: 32
Update 2: I fixed a bug in the above program: I had \$e . \$f . \$i where I should have had \$c. \$f . \$i. Now I get the following:
```1 7 6
3 9 6
2 2 0
Common divisor is: 44
That's the correct maximum, according to artist. Total time to run was less than two seconds.

Update 3: Another way to do it which would be more practical for larger NxN: I once wrote a program to find answers to crossword puzzles where the word list is given. Starting from the highest number that produces enough N-digit results, make a list of all of its N-digit multiples and fit them to the crossing constraints. The first one that works is the answer.

Update 4: That's basically the solution Rhose has in mind, I think. The starting number he chose, 166, is too big because you need at least two numbers with the same first digit, two others with the same last digit, etc. I'm thinking hashes of digits by position might help.

Quantum::Superpositions claims to make factoring trivial (and possibly the rest of the program, as well).

Trivial perhaps, but slow for sure.

CountZero

"If you have four groups working on a compiler, you'll get a 4-pass compiler." - Conway's Law

Re: Matrix Formation
by CountZero (Bishop) on Jun 17, 2003 at 19:35 UTC

Some shortcuts:

• Carefuly construct your list of dividers: there is no need to check division by a number higher than 1/2 of the largest formed number. This means that you first construct your list of formed numbers and then your list of dividers.
• If one of the formed numbers is prime, all other formed numbers must be multiples of that prime number. Of course checking if a number is prime is very time-consuming, but if you check for a 3x3 matrix, the largest prime number should be less than 999/5 (since the smallest formed number is prime, the sixth number must be 5 x the smallest number). All prime numbers above that can be skipped. So by keeping a list of "forbidden prime numbers" you can avoid these.
• You can also skip all multiples of 10 as common divisors, since all multiples of 10 end in (at least) one zero and this must mean that the formed number of the last column must start with a zero, which is not allowed.

CountZero

"If you have four groups working on a compiler, you'll get a 4-pass compiler." - Conway's Law

Re: Matrix Formation
by Rhose (Priest) on Jun 17, 2003 at 20:07 UTC
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.

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.
Re: Matrix Formation
by CountZero (Bishop) on Jun 17, 2003 at 19:53 UTC

In the 3x3 matrix:

``` a b c
d e f
g h i
a, b, c, d and g cannot be zero, so only (combined) numbers which are accepted by the following regex are candidates /[1-9][1-9][1-9][1-9][0-9][0-9][1-9]0-9][0-9]/

This should weed out a bit more numbers than your regex.

CountZero

"If you have four groups working on a compiler, you'll get a 4-pass compiler." - Conway's Law

Re: Matrix Formation
by artist (Parson) on Jun 17, 2003 at 20:45 UTC

1.Antirice asked if I can repeat the numbers: Answer is yes: ie.. [ [1,2],[4,2]] is allowed.

2. pzbagel: In mentioning of next if \$n =~ /0\d+/;. \d+ was necessary to because I just don't wanted the formed-numbers that begins with 0. Anywhere else 0 in the number is fine. For 2x2 matrix this should work fine.

3. I like Rhose's appraoch as initiated by CountZero.

4. Other apporach:, Start forming matrix starting from the highest divisor.

4. Few other related challanges are

• Find a matrix for each divisor possible with lowest possible total of numbers in the matrix. ex.. [[1 2] [3,0]]:Total = 6
• Origianl matrix can have numbers with K digits. K > 1. Example: K= 2  [ [12, 34],[56,78]]
• It could be NXNXN Matrix : Example: 3 x 3 x 3 Matrix: If we take K= 1 here, according to Rhose's approach we will have 1000/27 = 35 as maximum divisor.

Update: tall_man's answer at Re: Re: Matrix Formation is a good but rather cumborsum attempt. The best answer for 3x3 matrix -> Highest divisor is '44'. I am sure coming up with 4x4 or 15x15 matrix answers would be quite challanging.