I finally wrote code that could solve this problem, phew. This takes on the order of minutes to compute. The trick is in the symmetries and caching (otherwise, I wouldn't have come back here in years.)
Syntax of Output:
The
list of numbers :: list of numbers means a weighing of the left list of balls versus the right list of balls.
The
number[+|-] means a possible state. In the beginning, all states are possible, so the program lists all ball indices in both less weight and more weight.
8+ means the eighth ball is heavier than the rest.
In the solution, when a comparison is done, there are three possibilities: left is less that right, left is equal to right, left is greater than right.
The rest of the solution under each possibility is indented below each comparison possibility.
The output of the algo finds the first possible path only when it begins with 4 balls versus 4 balls. It tries comparing 1-1, 2-2, 3-3 and finally finds out at 4-4. I assumed that all comparisons must be made with equal number of scales on each side.
[edit1]Thought I was done with this piece, I was wrong. The algo is stepping on its own feet. Debugging this thing is not really the walk in the park.[/edit1]
Output
0 :: 1
0 1 :: 2 3
0 1 2 :: 3 4 5
0 1 2 3 :: 4 5 6 7
solved? 1
0-,0+,1-,1+,2-,2+,3-,3+,4-,4+,5-,5+,6-,6+,7-,7+,8-,8+,9-,9+,10-,10+,11-,11+,
0 1 2 3 :: 4 5 6 7
less
0-,1-,2-,3-,4+,5+,6+,7+,
0 1 4 :: 2 3 5
less
2-,3-,5+,
3 :: 2
less
3-,
equal
5+,
greater
2-,
equal
6+,7+,
2 :: 6
less
6+,
equal
7+,
greater
greater
2-,3-,4+,
2 :: 3
less
2-,
equal
4+,
greater
3-,
equal
8-,8+,9-,9+,10-,10+,11-,11+,
0 8 :: 9 10
less
8-,9+,10+,
9 :: 10
less
10+,
equal
8-,
greater
9+,
equal
11-,11+,
0 :: 11
less
11+,
equal
greater
11-,
greater
3-,8+,10-,
3 :: 10
less
3-,
equal
8+,
greater
10-,
greater
0+,1+,2+,3+,4-,5-,6-,7-,
0 4 5 :: 1 6 7
less
1+,6-,7-,
7 :: 6
less
7-,
equal
1+,
greater
6-,
equal
2+,3+,
6 :: 2
less
2+,
equal
3+,
greater
greater
0+,6-,7-,
6 :: 7
less
6-,
equal
0+,
greater
7-,
Fresh code, with all the commenting and possible mistakes.
//
// main.cpp
// 12balls
//
// Created by arithma on 12/24/12.
// Copyright (c) 2012 napkin. All rights reserved.
//
#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <algorithm>
#include <assert.h>
using namespace std;
const int k = 12;
struct state{
int index;
int weight;
bool operator<(state const & other) const{
if(index < other.index)
return true;
else if(index == other.index){
return weight < other.weight;
}
else{
return false;
}
}
};
struct test{
set<int> left;
set<int> right;
test() {}
test(set<int> _left, set<int> _right) : left(_left), right(_right) {}
bool apply(state const & s, int result){
assert(left.size() == right.size());
int r;
if(left.find(s.index)!=left.end())
r = +s.weight;
else if(right.find(s.index)!=right.end())
r = -s.weight;
else
r = 0;
return r == result;
}
set<state> filter(set<state> const & ss, int r){
set<state> result;
for(state s: ss){
if(apply(s, r)){
result.insert(s);
}
}
return result;
}
};
struct node{
set<state> ss;
set<int> left;
set<int> right;
node* less;
node* equal;
node* greater;
node() : less(nullptr), equal(nullptr), greater(nullptr) {}
node(node const & other) : less(nullptr), equal(nullptr), greater(nullptr){
ss = other.ss;
left = other.left;
right = other.right;
if(other.less != nullptr)
less = new node(*other.less);
if(other.equal != nullptr)
equal = new node(*other.equal);
if(other.greater != nullptr)
greater = new node(*other.greater);
}
node(set<state> const & _ss, set<int> _left, set<int> _right) : ss(_ss), left(_left), right(_right){
test t(left, right);
less = new node;
less->ss = t.filter(ss, -1);
equal = new node;
equal->ss = t.filter(ss, 0);
greater = new node;
greater->ss = t.filter(ss, 1);
}
void apply_map(map<int,int> m){
set<state> new_ss;
for(auto s: ss){
state new_state;
new_state.index = s.index;
new_state.weight = s.weight;
auto itr = m.find(s.index);
if(itr!=m.end()){
new_state.index = itr->second;
}
new_ss.insert(new_state);
}
ss = new_ss;
set<int> newleft;
for(auto i: left){
auto itr = m.find(i);
if(itr!=m.end())
newleft.insert(itr->second);
else
newleft.insert(i);
}
left = newleft;
set<int> newright;
for(auto i: right){
auto itr = m.find(i);
if(itr!=m.end())
newright.insert(itr->second);
else
newright.insert(i);
}
right = newright;
if(less != nullptr)
less->apply_map(m);
if(greater != nullptr)
greater->apply_map(m);
if(equal != nullptr)
equal->apply_map(m);
}
~node() {
if(less != nullptr)
delete less;
if(equal != nullptr)
delete equal;
if(greater != nullptr)
delete greater;
}
};
bool intersect(set<int> const & s, set<int> const & t){
for(auto i: s){
if(t.find(i) != t.end())
return true;
}
return false;
}
vector<set<int>> combinations(int n, int start, int c){
vector<set<int>> result;
if(c == 0){
set<int> s;
result.push_back(s);
return result;
}
for(int i = start; i < n-(c-1); i++){
int first = i;
vector<set<int>> subs = combinations(n, i+1, c-1);
for(auto s: subs){
s.insert(first);
result.push_back(s);
}
}
return result;
}
void print(set<state> ss){
for(auto s: ss){
cout << s.index << (s.weight == 1 ? "+" : "-") << ",";
}
}
void print(set<int> is){
for(auto i: is)
cout << i << " ";
}
void print(set<int> left, set<int> right){
for(auto i: left)
cout << i << " ";
cout << ":: ";
for(auto i: right)
cout << i << " ";
}
void indent(int n){
for(int i = 0; i < n; i++)
cout << "\t";
}
void print(node const & n, int indent = 0){
::indent(indent);
for(auto s: n.ss){
cout << s.index << (s.weight == 1 ? "+" : "-") << ",";
}
cout << endl;
if(n.ss.size()<=1)
return;
::indent(indent);
for(auto i: n.left)
cout << i << " ";
cout << ":: ";
for(auto i: n.right)
cout << i << " ";
cout << endl;
if(n.less != nullptr){
::indent(indent);
cout << "less" << endl;
print(*n.less, indent+1);
}
if(n.equal != nullptr){
::indent(indent);
cout << "equal" << endl;
print(*n.equal, indent+1);
}
if(n.greater != nullptr){
::indent(indent);
cout << "greater" << endl;
print(*n.greater, indent+1);
}
}
struct canonical {
int both, neg, pos;
canonical(set<state> const & ss, map<int,int> & perm_map){
set<int> p, n;
for(auto s: ss){
if(s.weight == -1)
n.insert(s.index);
else
p.insert(s.index);
}
set<int> b;
set<int> pcopy(p);
for(auto s: pcopy){
if(n.find(s) != n.end()){
p.erase(s);
n.erase(s);
b.insert(s);
}
}
set<int> free_indices;
perm_map = map<int,int>();
int idx = 0;
for(auto i: b){
if(i != idx){
perm_map[i] = idx;
free_indices.insert(i);
}
idx++;
}
for(auto i: p){
if(i != idx){
perm_map[i] = idx;
free_indices.insert(i);
}
idx++;
}
for(auto i: n){
if(i != idx){
perm_map[i] = idx;
free_indices.insert(i);
}
idx++;
}
assert(perm_map.size()==free_indices.size());
auto freeitr = free_indices.begin();
map<int,int> new_perm_map(perm_map);
for(auto itr = perm_map.begin(); itr != perm_map.end(); itr++, freeitr++){
new_perm_map[itr->second] = *freeitr;
}
perm_map = new_perm_map;
both = (int)b.size();
pos = (int)p.size();
neg = (int)n.size();
}
};
bool operator<(canonical const & first, canonical const & second)
{
if(first.both < second.both)
return true;
else if(first.both > second.both)
return false;
else if(first.neg < second.neg)
return true;
else if(first.neg > second.neg)
return false;
else return first.pos < second.pos;
}
map<int, int> invert(map<int, int> m){
map<int, int> result;
for(auto k: m){
result[k.second] = k.first;
}
return result;
}
void print(canonical const & c){
cout << "both: " << c.both << ", pos: " << c.pos << ", neg: " << c.neg << endl;
}
map<canonical,int> failed;
map<canonical, node> cache;
node solve(int balls, set<state> ss, int steps, bool & solved){
// indent(3-steps);
// cout << "steps = " << steps << endl;
if(ss.size()<=1){
solved = true;
node n;
n.ss = ss;
return n;
}
if(steps == 0){
solved = false;
node n;
return n;
}
{
map<int,int> perm;
canonical canon_ss = canonical(ss, perm);
// indent(3-steps);
// print(canon_ss);
{
auto itr = failed.find(canon_ss);
// if(itr != failed.end())
// cout << "found failed entry" << endl;
if(itr != failed.end() && steps <= itr->second){
// indent(3-steps);
// cout << "failed (cache)" << endl;
solved = false;
node n;
return n;
}
}
perm = invert(perm);
auto itr = cache.find(canon_ss);
if(itr != cache.end()){
// indent(3-steps);
// cout << "found prior!" << endl;
// print(itr->second);
solved = true;
node result = itr->second;
result.apply_map(perm);
return result;
}
}
for(int c = 1; c <= balls/2; c++){
vector<set<int>> combs = combinations(balls, 0, c);
for(auto l: combs) {
bool r_rentry = false;
for(auto r: combs) if(!intersect(l, r)){
if(steps == 3){
if(r_rentry)
break;
r_rentry = true;
indent(3-steps);
print(l, r);
cout << endl;
}
bool solvedLess, solvedEqual, solvedGreater;
node n(ss, l, r);
// indent(3-steps);
// cout << "lft: ";
// print(n.less->ss);
// cout << endl;
// indent(3-steps);
// cout << "eq: ";
// print(n.equal->ss);
// cout << endl;
// indent(3-steps);
// cout << "grt: ";
// print(n.greater->ss);
// cout << endl;
// indent(3-steps);
// cout << "solve less" << endl;
n.less = new node(solve(balls, n.less->ss, steps-1, solvedLess));
if(!solvedLess) continue;
// indent(3-steps);
// cout << "solve equal" << endl;
n.equal = new node(solve(balls, n.equal->ss, steps-1, solvedEqual));
if(!solvedEqual) continue;
// indent(3-steps);
// cout << "solve greater" << endl;
n.greater = new node(solve(balls, n.greater->ss, steps-1, solvedGreater));
if(!solvedGreater) continue;
solved = true;
map<int,int> perm;
canonical canon_states(ss, perm);
node canon_node(n);
canon_node.apply_map(perm);
// indent(3-steps);
// cout << "adding to cache" << endl;
// print(canon_node);
// cout << "saving solution" << endl;
// print(n);
// print(canon_node);
cache.insert(pair<canonical,node> {canon_states, canon_node});
return n;
}
if(steps == 3)
break;
}
}
solved = false;
{
map<int, int> perm;
canonical canon_states(ss, perm);
failed.insert(pair<canonical,int> {canon_states,steps});
}
node n;
return n;
}
int main()
{
if(false){
set<state> testss;
testss.insert(state{9, +1});
testss.insert(state{10, +1});
testss.insert(state{9, -1});
testss.insert(state{10, -1});
testss.insert(state{0, -1});
testss.insert(state{2, -1});
testss.insert(state{1, +1});
print(testss);
map<int,int> perm;
canonical canon(testss, perm);
print(canon);
for(auto p: perm){
cout << p.first << " -> " << p.second << endl;
}
node n;
n.ss = testss;
n.apply_map(perm);
print(n.ss);
cout << "Rev" << endl;
perm = invert(perm);
for(auto p: perm){
cout << p.first << " -> " << p.second << endl;
}
return 0;
}
set<state> ss;
for(int i = 0; i < k; i++){
state s = {i, +1};
ss.insert(s);
state t = {i, -1};
ss.insert(t);
}
bool solved;
node n = solve(k, ss, 3, solved);
cout << "solved? " << solved << endl;
print(n);
return 0;
}
