So here's my solution. It doesn't use caching yet.
Pastie Version:
http://pastie.org/3368456
// MinComparisons
// arithma
//
#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <algorithm>
#include <assert.h>
using namespace std;
typedef vector<string> vec;
struct bounds{
int min, max;
};
bounds getBounds(vec const &in);
struct partition
{
vec eq;
vec neq;
bounds bounds;
void setBounds(){
::bounds beq = getBounds(eq);
::bounds bneq = getBounds(neq);
bounds.max = ::max(beq.max, bneq.max);
bounds.min = ::max(beq.min, bneq.min);
}
bool operator<(partition const & other) const {
return bounds.max < other.bounds.max;
}
};
typedef map<char, ::partition> charMap;
typedef vector< ::partition> parts;
int comparisons(vec const &in);
void prune(vec &in);
parts partitions(vec const &in, int idx);
int main ()
{
string strs[] = {
"fVq9jcBEMNrVl0M2A8VmfNPLgd7kK5JD",
"I9FlZT90gu2n9ywNFBljC7jce2rR0SFJ",
"lGOmu7loH80DbOyaYqzQBGwTPDwHlr8u",
"rFqF5g9u5TXAAXM2sdxHpfZ4VzFBOgNN",
"lGOmu7loH80DbOyfb6NuuWcEP81D7J5r",
"tEANjAjjNwvGfG3uhjjAtFfg3OmYXVK2",
"lGOmu7loH80DOyncyYpajmdnNIGH6HSu",
"zQUwjMzloRmzlR5jYuvaaa9sqo9AH09B",
"JsNn1Hu7J2FjMxoi8t49AogNogfPKlk6",
"lGOmu7loH80DbOyFbtVa1K1m6UxQFvX5"};
vec input(strs, strs + 10);
/*
string strs[] = {
"aaa", "aab", "aba", "abb", "bcc", "bcd", "bdc", "bdd"
};
vec input(strs, strs + 8);
*/
cout << comparisons(input) << endl;
return 0;
}
int comparisons(vec const &in){
vec c = in;
prune(c);
bounds b = getBounds(c);
if(b.min == b.max) return b.min;
parts p;
int cols = (int)in[0].size();
for(int col = 0; col < cols; col++){
parts colPartitions = partitions(in, col);
p.insert(p.end(), colPartitions.begin(), colPartitions.end());
}
sort(p.begin(), p.end());
int min = b.max;
for(parts::iterator itr = p.begin(); itr < p.end(); itr++){
if(itr->bounds.min >= min)
continue;
int t = max(comparisons(itr->eq), comparisons(itr->neq));
min = ::min(t, min);
}
return min + 1;
}
void prune(vec &in){
int strings = (int)in.size();
int cols = (int) in[0].size();
vector<bool> same(cols, true);
for(int col = 0; col < cols; col++){
char firstColChar = in[0][col];
for(int str = 1; str < strings; str++){
if(in[str][col] != firstColChar){
same[col] = false;
break;
}
}
}
for(int col = cols - 1; col >= 0; col--){
if(same[col]){
for(int str = 0; str < strings; str++){
in[str].erase(in[str].begin() + col);
}
}
}
}
parts partitions(vec const &in, int idx){
charMap charMap;
set<char> chars;
int strings = (int)in.size();
for(int i = 0; i < strings; i++){
chars.insert(in[i][idx]);
}
for(set<char>::iterator c = chars.begin(); c != chars.end(); c++){
for(int i = 0; i < strings; i++){
if(*c == in[i][idx]){
charMap[*c].eq.push_back(in[i]);
}
else{
charMap[*c].neq.push_back(in[i]);
}
}
prune(charMap[*c].eq);
prune(charMap[*c].neq);
charMap[*c].setBounds();
}
parts result;
for(charMap::iterator itr = charMap.begin(); itr != charMap.end(); itr++){
result.push_back(itr->second);
}
return result;
}
bounds getBounds(vec const &in){
bounds result;
int height = (int)in.size();
int width = (int)in[0].size();
result.max = max(width, height-1);
int min = 0;
int pw2 = 1;
while(pw2 < height){
pw2 *= 2;
min++;
}
result.min = min;
assert(result.min <= result.max);
return result;
}