You are given four squares as below with numbers named
a,b,c,d,e,f,g.(1) (3) ╔══════════════╗ ╔══════════════╗ ║ ║ ║ ║ ║ a ║ ║ e ║ ║ ║ (2) ║ ║ (4) ║ ┌───╫──────╫───┐ ┌───╫─────────┐ ║ │ ║ ║ │ │ ║ │ ║ │ b ║ ║ d │ │ f ║ │ ║ │ ║ ║ │ │ ║ │ ║ │ ║ ║ │ │ ║ │ ╚══════════╪═══╝ ╚═══╪══════╪═══╝ │ │ c │ │ g │ │ │ │ │ │ │ │ │ └──────────────┘ └─────────────┘Write a script to place the given unique numbers in the square box so that sum of numbers in each box is the same.
Input: 1,2,3,4,5,6,7 Output: a = 6 b = 4 c = 1 d = 5 e = 2 f = 3 g = 7 Box 1: a + b = 6 + 4 = 10 Box 2: b + c + d = 4 + 1 + 5 = 10 Box 3: d + e + f = 5 + 2 + 3 = 10 Box 4: f + g = 3 + 7 = 10
First observation is that solutions are not unique. If \(a = x_1\),
\(b = x_2\), \(c = x_3\), \(d = x_4\), \(e = x_5\), \(f = x_6\),
\(g = x_7\) is a solution, then \(a = x_7\), \(b = x_6\), \(c = x_5\),
\(d = x_4\), \(e = x_3\), \(f = x_2\), \(g = x_1\) is a solution as well.
(We are calling two numbers different if they have different indices in
@numbers, even if the value of the numbers are the same).
Even without symmetry, solutions do not need to be unique. For the given example, there are eight different solutions:
\[ \begin{array}{|ccccccc|r|} a & b & c & d & e & f & g & \text{sum} \\ \hline 3 & 7 & 2 & 1 & 5 & 4 & 6 & 10 \\ 4 & 5 & 3 & 1 & 6 & 2 & 7 & 9 \\ 4 & 7 & 1 & 3 & 2 & 6 & 5 & 11 \\ 5 & 6 & 2 & 3 & 1 & 7 & 4 & 11 \\ 6 & 4 & 1 & 5 & 2 & 3 & 7 & 10 \\ 6 & 4 & 5 & 1 & 2 & 7 & 3 & 10 \\ 7 & 2 & 6 & 1 & 3 & 5 & 4 & 9 \\ 7 & 3 & 2 & 5 & 1 & 4 & 6 & 10 \\ \end{array} \]
The column \(\text{sum}\) indicates to which total the values in the squares sum.
There are different ways to solve this problem.
One way of tackling this problem is to just try all possibilities. There are only \(7! = 5040\) different ways to assign \(7\) values to \(7\) variables, so this is quite feasable. And we can improve on that, there are ways to reduce the number of possibilities tried. For instance, if we have picked values for \(a\), \(b\), \(c\), and \(d\), we can check whether \(a + b = b + c + d\). If not, we don't have to iterate over the possible assignments of \(e\), \(f\) or \(g\).
Looking at the problem statement, we have
\[ T = \begin{cases} a + b & (1) \\ b + c + d & (2) \\ d + e + f & (3) \\ f + g & (4) \end{cases} \]
where \(T\) is the sum of the values of a square.
From \((1)\) and \((2)\) it follows that:
\[ \begin{array}{lr} a + b = b + c + d \implies a = c + d \implies d = a - c & (5) \end{array} \]
In the same way, from \((3)\) and \((4)\) it follows that:
\[ \begin{array}{lr} f + g = d + e + f \implies g = e + d \implies d = g - e & (6) \end{array} \]
From \((5)\) and \((6)\) we get:
\[ \begin{array}{lr} d = a - c = g - e & (7) \end{array} \]
Formula \((7)\) gives us the insight how to efficiently tackle the problem: we have to find two pairs of numbers whose differences are equal to a fifth number. Once we this quintet, there are only two more values to assign, which we can easily check for.
Our Perl solution follows the second strategy explained above.
Assuming the given numbers are in an array called @numbers,
we start off by finding the differences between all pairs of
numbers. If a difference is present in @numbers, we store the
indices of the numbers in a datastructure %differences. This
hash uses the elements of @numbers as keys. The values are array
refs, where each element is 2-element array with indices; the indices
indicate which elements in @numbers have the given difference.
my %differences = map {$_ => []} @numbers;
for (my $x = 0; $x < @numbers; $x ++) {
for (my $y = $x + 1; $y < @numbers; $y ++) {
my $diff = $numbers [$x] - $numbers [$y];
push @{$differences { $diff}} => [$x, $y] if $differences { $diff};
push @{$differences {-$diff}} => [$y, $x] if $differences {-$diff};
}
}
We will now iterate over the numbers d in @numbers, and find all
pairs of pairs of numbers whose difference is d, which the added
restriction all five involved numbers are different. (Remember that we
call two numbers different if they have different indices in @numbers,
even if the values are the same).
for (my $d_i = 0; $d_i < @numbers; $d_i ++) {
my $d = $numbers [$d_i];
my @diffs = @{$differences {$d}};
#
# Now, find two pairs where all indices are different.
#
for (my $x = 0; $x < @diffs; $x ++) {
#
# Ignore a difference involving d_i.
#
next if $diffs [$x] [0] == $d_i ||
$diffs [$x] [1] == $d_i;
for (my $y = $x + 1; $y < @diffs; $y ++) {
#
# Second difference cannot involve the number at d_i,
# and the indices involved in the second difference
# must be different from the first difference.
#
next if $diffs [$y] [0] == $d_i ||
$diffs [$y] [1] == $d_i ||
$diffs [$x] [0] == $diffs [$y] [0] ||
$diffs [$x] [0] == $diffs [$y] [1] ||
$diffs [$x] [1] == $diffs [$y] [0] ||
$diffs [$x] [1] == $diffs [$y] [1];
At this moment, $diffs [$x] and $diffs [$y] contain four different
indices, all different from $d_i, such that $d == $numbers [$d_i],
$d == $numbers [$diffs [$x] [0]] - $numbers [$diffs [$x] [1]], and
$d == $numbers [$diffs [$y] [0]] - $numbers [$diffs [$y] [1]].
We can now assign the values in $diffs [$x] and $diffs [$y] to
$a_i, $c_i, $g_i, and $e_i, the indices where in @numbers
we can find the values for a, c, g, and e. We don't have to
consider the opposite, that is, assume that $diffs [$x] contains
$g_i and $e_i, and $diffs [$y] contains $a_i and $c_i: this
would lead to a symmetric solution, and we deal with that later.
my ($a_i, $c_i) = @{$diffs [$x]};
my ($g_i, $e_i) = @{$diffs [$y]};
We now have two indices not used, and two variables to assign them to:
$b_i, and $f_i.
We'll find the two unused indices:
my %indices = map {$_ => 1} keys @numbers;
delete $indices {$_} for $a_i, $c_i, $d_i, $e_i, $g_i;
We will now try both possible assignments, and check whether all the squares sum to the same value. If so, we print the solution, and the reverse:
foreach my $try ($left, [reverse @$left]) {
my ($b_i, $f_i) = @$try;
#
# Do we have a winner?
#
next unless $numbers [$a_i] + $numbers [$b_i] ==
$numbers [$b_i] + $numbers [$c_i] + $numbers [$d_i] ==
$numbers [$d_i] + $numbers [$e_i] + $numbers [$f_i] ==
$numbers [$f_i] + $numbers [$g_i];
#
# Print result, and the reverse, so we get all
# possible solutions.
#
my @solution =
@numbers [$a_i, $b_i, $c_i, $d_i, $e_i, $f_i, $g_i];
local $, = " ";
say @solution;
say reverse @solution;
Find the full program on GitHub.
For our Ruby solution, we opt to use the brute force strategy: we try all possible combinations, but we move to the next one as soon as we know we cannot reach a solution with the current picks so far.
Let numbers be an array containing the seven given numbers. We then
start by picking an a and a b:
numbers . each_with_index do |a, a_i|
numbers . each_with_index do |b, b_i|
next if a_i == b_i
target = a + b
Once we have an a and a (different b), we define target as
the sum of a and b. This is the sum of the values in the first
square, and the other squares need to sum to the same value.
Next, we pick a c and a d, and check whether b, c and d
sum to target (second square):
numbers . each_with_index do |c, c_i|
next if a_i == c_i || b_i == c_i
numbers . each_with_index do |d, d_i|
next if a_i == d_i || b_i == d_i || c_i == d_i
next if target != b + c + d
Then, we pick e and f, and check whether d, e, and f sum
to target (third square):
numbers . each_with_index do |e, e_i|
next if a_i == e_i || b_i == e_i || c_i == e_i ||
d_i == e_i
numbers . each_with_index do |f, f_i|
next if a_i == f_i || b_i == f_i || c_i == f_i ||
d_i == f_i || e_i == f_i
next if target != d + e + f
Finally, we pick g, and check whether f and g sum to target
(fourth and final square). If so, we have a solution, and we print it:
numbers . each_with_index do |g, g_i|
next if a_i == g_i || b_i == g_i ||
c_i == g_i || d_i == g_i ||
e_i == g_i || f_i == g_i
next if target != f + g
puts "#{a} #{b} #{c} #{d} #{e} #{f} #{g}"
Find the full program on GitHub.