# Perl Weekly Challenge 109: Four Squares Puzzle

by Abigail

## Challenge

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.

### Example

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


## Discussion

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.

### Brute force

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

### Equal differences

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.

## Solutions

### Perl

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.

### Ruby

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.

### Other languages

We also have solutions for AWK, Lua and Node.js, implementing the Equal differences strategy, and Bash, C and Python solutions implementing the Brute force strategy.

Please leave any comments as a GitHub issue.