12coins.cpp

#include <algorithm>
#include <iostream>
#include <numeric>
#include <vector>
#include <iterator>

// There are 12 coins. One of them is fake and has a slightly different weight
// (either lighter or heavier) than the real coins. You have a balance. Using
// only 3 measurements you must find the fake coin and tell wether is heavier
// or ligher.

int norm(int n)
{
    return n < 0 ? -1 : (n > 0 ? 1 : 0);
}

template<class InputIt>
int compare(InputIt v1_start, InputIt v1_end, InputIt v2_start, InputIt v2_end)
{
    return norm(std::accumulate(v1_start, v1_end, 0) - std::accumulate(v2_start, v2_end, 0));
}

int solve(std::vector<int> &v)
{
    int ret1, ret2, ret3;

    // First thing, split the 12 coins in 3 groups of 4 coins each.
    std::vector<int> v1(v.begin(), v.begin() + 4);
    std::vector<int> v2(v.begin() + 4, v.begin() + 8);
    std::vector<int> v3(v.begin() + 8, v.end());

    // Compare two groups of coins.
    ret1 = compare(v1.begin(), v1.end(), v2.begin(), v2.end());
    if (ret1 == 0) {
        // The 3rd group of 4 coins has the fake coin. Now, compare 3 coins
        // from the 3rd group, with 3 coins from standard.
        ret2 = compare(v3.begin(), v3.begin() + 3, v1.begin(), v1.begin() + 3);
        if (ret2 != 0) {
            // Compare the weight of the first two coins in the 3rd group.
            ret3 = compare(v3.begin(), v3.begin() + 1, v3.begin() + 1, v3.begin() + 2);
            if (ret3 == 0) {
                // The two coins in the 3rd group weigh the same, this means
                // that the 3rd coin (the 11th coin) is the fake one.
                return ret2 * 11;
            } else {
                // ret2 (the result of the previous weighing) tells wether the
                // fake coin is lighter or heavier. It ret3 == ret2 (the
                // results of the 3rd weighing is equals to the result of the
                // previous one, the 9th coin is the fake one, othewise, the
                // 10th coin is the fake one.
                return ret2 * (ret2 == ret3 ? 9 : 10);
            }
        } else {
            // The weight is the same, this means the 4th coin in the 3rd group
            // (i.e. the 12th coin) is the fake one.
            ret3 = compare(v3.begin() + 3, v3.end(), v1.begin() + 3, v1.end());
            return ret3 * 12;
        }
    } else {
        std::vector<int> v4(v1.begin(), v1.end());
        std::vector<int> v5(v2.begin(), v2.end());

        // The fake coin can be either in 1st group or in the 2nd group. To
        // find which one, do the following: replace first 3 coins from group 1
        // with 3 coins from the reference group and switch 4th coin from group
        // 1 with 1st coin from group 2.
        std::copy(v3.begin(), v3.begin() + 3, v4.begin());
        std::swap(v4[3], v5[0]);

        // Compare the updated groups.
        ret2 = compare(v5.begin(), v5.end(), v4.begin(), v4.end());
        if (ret2 == 0) {
            // We have now equilibrium, the fake coin it's one of those 3 coins
            // that were removed from group 1. The first weighing told us
            // wether the fake coin is easier or heavier.
            ret3 = compare(v1.begin(), v1.begin() + 1, v1.begin() + 1, v1.begin() + 2);
            if (ret3 == 0) {
                // The first two coins in group 1 weigh the same, the fake
                // coin is the third one.
                return ret1 * 3;
            } else {
                // Compare the result of the 1st and last weighing to choose
                // between the 1st and the 2nd coin.
                return ret1 * (ret1 == ret3 ? 1 : 2);
            }
        } else if (ret2 == ret1) {
            // The fake coin it's one of those two coins that were switched.
            // The first weighing told us whether the fake coin is easier or
            // heavier. Compare the 1st coin from group 3 (which is actually
            // 4th coin in the original 2nd group with a coin from the
            // reference group.
            ret3 = compare(v5.begin(), v5.begin() + 1, v3.begin(), v3.begin() + 1);
            if (ret3 == 0) {
                // We need to negate here the result of the first weighing
                // because, we know that 5th coin is the fake one and original
                // group 1 being havier than original group 2, actually means
                // that coin 5 is lighter, and vice-versa.
                return -ret1 * 5;
            } else {
                return ret1 * 4;
            }
        } else {
            // The fake coin it's one the 3 coins from group 2 that weren't
            // changed. Compare the weight of the 2nd and 3rd coins in the
            // group. The 2nd weighing told us wether the fake coin is heavier
            // or lighter.
            ret3 = compare(v5.begin() + 1, v5.begin() + 2, v5.begin() + 2, v5.begin() + 3);
            if (ret3 == 0) {
                // They weigh the same, 8th coin is the fake one.
                return ret2 * 8;
            } else {
                // If the 2nd and 3rd weighings gave the same result, 6th coin
                // it's the fake one, otherwise it's the 7th one.
                return ret2 * (ret2 == ret3 ? 6 : 7);
            }
        }
    }

    // Not reached.
    return 0;
}

int main(int argc, char *argv[])
{
    int ret;
    bool good = true;

    for (int i = 0; i < 12; ++i) {
        std::vector<int> v(12);
        for (int j = 0; j < 12; ++j) {
            v[j] = 1;
        }

        // Test for a lighter fake coin.
        v[i] = 0;
        ret = solve(v);
        if (ret != -(i + 1)) {
            std::cout << "Failed for lighter coin " << (i + 1) << ", ret=" << ret << std::endl;
            good = false;
        }

        // Test for a heavier fake coin.
        v[i] = 2;
        ret = solve(v);
        if (ret != (i + 1)) {
            std::cout << "Failed for heavier coin " << (i + 1) << ", ret=" << ret << std::endl;
            good = false;
        }
    }

    if (good)
        std::cout << "Everything ok " << std::endl;

    return 0;
}