Identify the Counterfeit Coin
Autumn Tournament (2009)
Submission name: coins.cpp
Problem summary
Exactly one of 12 coins has a different weight, but it may be heavier or lighter. Given three balance-scale results, identify the coin and direction if unique, report impossible if contradictory, or indefinite if multiple hypotheses remain.
Input
Three lines, each containing four left-pan coin numbers, one of < > =, and four right-pan coin numbers. The eight coin numbers on a line are distinct.
Output
A coin number immediately followed by + or −, or impossible, or indefinite.
Constraints
12 coins numbered 1…12; exactly three weighings of four coins against four.
Worked example
Original statement sample.
Input
1 2 3 10 > 4 5 6 11 1 2 3 11 > 7 8 9 10 1 4 7 10 < 2 5 8 12
Output
2+
Solution analysis
- There are only 24 hypotheses: choose the counterfeit coin and choose whether its weight deviation is +1 or −1. The exact small deviation does not matter because the other equal-weight coins cancel between equal-sized pans.
- For each weighing and hypothesis, add the deviation if the suspect is on the left, subtract it if on the right, and otherwise use zero. Its sign predicts >, <, or =. Retain a hypothesis only if all three predictions agree with the input.
- In the sample, coin 2 being heavy makes the first two left pans heavier and the third right pan heavier. Every other hypothesis conflicts with at least one weighing, so the unique answer is 2+. If no hypothesis survives output impossible; if more than one survives output indefinite.
Why it works
One and only one of the 24 coin/direction hypotheses describes the stipulated physical situation. Equal counts of genuine coins cancel, so the simulated signs are exact. Testing all hypotheses therefore retains precisely the situations consistent with all evidence.
Watch out. An absent suspect predicts equality. Reverse the sign when the suspect is on the right pan. Different heavy/light explanations of the same coin still mean indefinite.
Commented C++17 solution
An independently written complete program with standard headers.
// Key idea: One and only one of the 24 coin/direction hypotheses describes the stipulated physical
// situation. Equal counts of genuine coins cancel, so the simulated signs are exact.
#include<array>
#include<iostream>
#include<utility>
#include<vector>
using namespace std;
struct Weighing{
array<int,4>left;
array<int,4>right;
char relation;
};
int main(){
array<Weighing,3>data;
for(auto&weighing:data){
for(int&coin:weighing.left){
cin>>coin;
}
cin>>weighing.relation;
for(int&coin:weighing.right){
cin>>coin;
}
}
vector<pair<int,int>>possible;
for(int suspect=1;suspect<=12;suspect++){
for(int deviation:{-1,1}){
bool valid=true;
for(auto weighing:data){
int difference=0;
for(int coin:weighing.left){
if(coin==suspect){
difference+=deviation;
}
}
for(int coin:weighing.right){
if(coin==suspect){
difference-=deviation;
}
}
char predicted=difference<0?'<':difference>0?'>':'=';
if(predicted!=weighing.relation){
valid=false;
}
}
if(valid){
possible.push_back({suspect,deviation});
}
}
}
if(possible.empty()){
cout<<"impossible\n";
}
else if(possible.size()!=1){
cout<<"indefinite\n";
}
else{
cout<<possible[0].first<<(possible[0].second>0?'+':'-')<<'\n';
}
}