Weekly Challenge 089

Challenge 089

TASK #1 › GCD Sum

Task

You are given a positive integer $N. Write a script to sum GCD of all possible unique pairs between 1 and $N.

My solution

This is relatively straight forward. All possible unique pairs can be calculated with the first number from 1 to $N - 2, and the second number one more than the first number to $N.

It's then a matter of calculating the GCD for this combination. For this I have a subroutine _gcd that takes the minimum of the two numbers and work backwards to one. It will return the first value that can be divided by both numbers with no remainder.

Examples

» ./ch-1.pl 3
3

» ./ch-1.pl 4
7

TASK #2 › Magical Matrix

Task

Write a script to display matrix as below with numbers 1 - 9. Please make sure numbers are used once.

[ a b c ]
[ d e f ]
[ g h i ]

So that it satisfies the following:

a + b + c = 15
d + e + f = 15
g + h + i = 15
a + d + g = 15
b + e + h = 15
c + f + i = 15
a + e + i = 15
c + e + g = 15

My solution

My first thought was to just brute force this. The possible permutation is 9! = 362880, and even a half decent computer could figure this out pretty quickly.

But I took a slight different approach to make it even faster.

1. Work out all the possible ordered three digit combinations that sum to 15. It turns out there are only eight combinations: 1 5 9, 1 6 8, 2 4 9, 2 5 8, 2 6 7, 3 4 8, 3 5 7, 4 5 6
2. Using these rows, work out all combinations of these rows such that all numbers are used. There are twelve rows returned.
3. This now means the possible solutions are 6³ × 12 (2,592). We know that we won't need all of these. For example, the 1 will always be found in top left, top middle or centre position (all other places will be a mirror/flip of one of these).
4. At this point, I just use a brute force approach until I find a solution.
   1. Each row can be ordered one of six ways (abc, acb, bac, bca, cab, cba).
   2. For each of the twelve solutions, we can cycle through the six numbers combinations in each row.
   3. If a solution is found that meets the requirements, we print the solution and exit.

I'm looking forward to seeing how other Team PWC members tackle this task.

Examples

» ./ch-2.pl 
[ 6 1 8 ]
[ 7 5 3 ]
[ 2 9 4 ]

Comments

[Simon Green]

It seems I've overthought the second task, and not for the first time. James Smith's solution is a work of beauty. And much more efficient too.