#include #include #include #include #include using namespace std; // In our BFS, what is a state? In this case, a state is the set of // indices into the filenames (and since order is unimportant, set is // sufficient.) // We could change this into an informed search (and might actually have // to if we really had 1000 filenames with differences in every column) by // defining an operator that checks how good a split is (say, what the // maximum size unsplit is) and change our BFS queue into a priority queue. #define state set // Check if we split the set. // This works recursively: if there are 0 or 1 things passed to us, // then we have split the set! If there are more than that and // no more columns to split on, then we failed. // If none of those conditions holds, then split on the first index // we were given, and check if ALL splits hold after we make that split. bool solved(vector& s, state splits) { // Base cases. if (s.size() <= 1) return true; if (splits.size() == 0) return false; // The index we are going to split on now int cur = *(splits.begin()); splits.erase(splits.begin()); // Make that split. map > m; for (int i = 0; i < s.size(); i++) { m[s[i][cur]].push_back(s[i]); } // For each set of strings that went the same way in that split, // check if we can split those with the remaining columns. for (map >::iterator i = m.begin(); i != m.end(); ++i) { // If any is not solved, then the puzzle ain't solved if (not solved(i->second, splits)) return false; } // If we made it this far, then everything is great. return true; } // For a list of strings, find the set of columns that actually changed. set calcChanged(vector& curSet) { // Our return value set ret; for (int i = 0; i < 27; i++) { // If anything from 1..n is different than index 0, then this column // should be returned. char cur = curSet[0][i]; for (int j = 1; j < curSet.size(); j++) { if (curSet[j][i] != cur) { ret.insert(i); break; } } } return ret; } // Just a normal BFS void solve(vector curSet) { state start; // Keep track of how many levels we have done. This // lets us stop when we get to 10 deep. map depth; list toVisit; // Get the set of columns that are worth looking at set changed = calcChanged(curSet); // Initial setup toVisit.push_back(start); depth[start] = 0; // Do it while (not toVisit.empty()) { // Get the next state state cur = toVisit.front(); toVisit.pop_front(); // If we are done, give up if (depth[cur] > 10) { cout << "NO SET" << endl; return; } // If we solved it, print the solution. if (solved(curSet, cur)) { // state is just a set, set's print in sorted order state::iterator i = cur.begin(); cout << *i + 1; ++i; for (; i != cur.end(); ++i) { cout << " " << *i + 1; } cout << endl; return; } // Otherwise, for each column that could be changed for (set::iterator i = changed.begin(); i != changed.end(); ++i) { // If that column isn't in our split already if (cur.count(*i) == 0) { state newState = cur; newState.insert(*i); // And that state isn't already visited if (depth.count(newState) == 0) { // Visit it and note the depth depth[newState] = depth[cur] + 1; toVisit.push_back(newState); } } } } // Technically, this won't happen since each line is unique. cout << "NO SET" << endl; } int main() { string cur; vector curSet; while (cin >> cur) { if (cur == "SEP") { solve(curSet); curSet.resize(0); } else { curSet.push_back(cur); } } if (curSet.size()) solve(curSet); }