Question:

Using a programming language of your choice, or simple pseudo code, suggest a solution to the following problem.

A balance scale is a device for weighing. It has a balanced beam and two pans. When the pans contain exactly the same mass, the beam is in balance. Balance scales are used to compare the mass of objects by placing them in one pan, and combinations of standard weights in the other.

Assignment

Implement a function, balanceScale(2), which takes as input:

The function must choose as few as possible from the available weights to balance the scale. Two weights can be used on the same side of the scale, but you cannot use more than two weights in total. If a solution exists, your function should return two integer arrays (contained in some suitable data structure) with the weights (as integers) to be added in each pan. If it is not possible to balance the scale, then you should return a designated value (like a null object) to indicate this. You may assume that the solution is unique.

Example

Given the arguments \((5, 9)\) and \([1, 2, 6, 7]\), balanceScale() should return 6 and 2, for example as a pair \(([6], [2])\) of arrays, since $$5 + 6 = 11 = 9 + 2,$$ and since, in this case, there is no solution using only one of the weights in the list.

Toggle solution

Solution:

In the following explanation, let

In the solution, we consider three cases:

  1. A single weight is used, in which case we are looking for some \(w \in W\) such that \(w = d\).
  2. Two weights are used, both in the same pan. Here we need a pair of weights \(\{w, v\} \in \binom{W}{2}\) such that \(w + v = d\).
  3. Two weights are used, but one in each pan. So the pair \(\{w, v\}\) in this case must satisfy \(a + w = b + v\) or \(a + v = b + w\). In other words, \(|w - v| = d\).

The first case is clearly a linear time operation. Since we want to choose as few weights as possible; if a one weight solution exists, it must be given precedence. For the other two cases, we need to consider all subsets \(\{w, v\}\), typically using a loop-in-a-loop construct of this kind: 

for (i = 0; i < n; i++) {
    for (j = i + 1; j < n; j++) {
        printf ("(%d, %d)\n", a[i], a[j]);
    }
}

Using Haskell's list comprehension syntax: 

pairs [] = []
pairs (x:xs) = [(x, x') | x' <- xs] ++ pairs xs

The number of 2-element subsets of an \(n\)-element set is given by the binomial coefficient $$ \binom{n}{2} = \frac{n(n - 1)}{2} \in O(n^2) $$

so the running time is quadratic in the number of weights.

Code

Implementation in the D language: 

import std.stdio;
import std.math: abs;
import std.algorithm: canFind;

struct Pair(T)
{
    T fst;
    T snd;
}

alias Pair!(int[]) Result;
alias Pair!(int)   Config;

pure Result balanceScale(const Config initial, const int[] weights)
{
    const ulong N = weights.length;

    /* Absolute value of the difference between the two intial pan weights. */
    const int d = abs(initial.fst - initial.snd);

    pure Result result(int[] a, int[] b) {
        return initial.fst > initial.snd ? Result(a, b) : Result(b, a);
    }

    /* Special case: Is the scale already balanced? */
    if (0 == d) {
        return Result([], []);
    }

    /* Let a and b denote the inital weights placed in the left and right pan.
     * Then consider the one weight case first: For all weights w,
     *
     * - If |a - b| = w then put w in the min(a, b) pan.
     */
    foreach (i; 0..N) {
        const int w = weights[i];

        if (d == w) {
            return result([], [w]);
        }
    }

    /* Try two weights: Again, let a and b be the initial weights. Now take all
     * pairs (w, v) of weights from the input array.
     *
     * - If |a - b| = |w - v|, then put w and v in separate pans.
     * - If |a - b| = w + v, put both w and v in the same pan.
     */
    foreach (i; 0..N) {
        const int w = weights[i];

        foreach (j; (i + 1)..N) {
            const int v = weights[j];

            if (d == abs(w - v)) {
                return result([w], [v]);
            } else if (d == w + v) {
                return result([], [w, v]);
            }
        }
    }

    /* Cannot balance the scale. */
    return Result([-1], [-1]);
}

Implementation in Haskell: 

module Main where

import Control.Applicative ( (<|>) )
import Data.Function ( (&) )
import Data.List ( find )

pairs :: [a] -> [(a, a)]
pairs [] = []
pairs (x:xs) = [(x, x') | x' <- xs] ++ pairs xs

distance :: Num a => a -> a -> a
distance w v = abs (w - v)

balanceScale :: (Int, Int) -> [Int] -> Maybe ([Int], [Int])
balanceScale (fst, snd) weights
  | 0 == d = pure mempty               -- Is the scale already balanced?
  | d `elem` weights = balance [] [d]  -- Consider one weight case
  | otherwise = do                     -- Finally, try two weights
      (w, v) <- matchDiffBy (+)
      balance [] [w, v]
    <|> do
      (w, v) <- matchDiffBy distance
      balance [w] [v]
  where
    d = distance fst snd
    balance a b = pure (if fst > snd then (a, b) else (b, a))
    matchDiffBy op =
      let eq_d (x, y) = d == x `op` y
       in pairs weights & find eq_d