/* From David Applegate, Feb 09 2008 This reads a file of generators specified as a command line argument, or from stdin if no argument is given. To compile: g++ -o a135463 a135463.cc Examples of lists of generators: cat A134948.gen 0 1 1 1 2 2 3 6 4 24 5 120 6 720 7 5040 8 40320 9 362880 cat A134962.gen 1 1 2 4 3 9 4 16 5 25 6 36 7 49 8 64 9 81 cat A135463.gen 1 1 1 2 4 8 3 9 27 4 16 64 5 25 125 6 36 216 7 49 343 8 64 512 9 81 729 cat A135464.gen 1 1 2 11 For example, A135463 A134439.gen generates terms from A134439, and A135463 A134439.gen | head -300 | awk '{print NR, $0;}' > b134439.txt generates a b-file. I fudged a bit for A134439 and A134692 - the code is designed to just go for closure, so that, say, since 7 doesn't occur in any square, you can get a valid entry that omits 7. For these, I just used a single generator rule which listed all squares (or cubes). cat A134439.gen 1 2 3 4 5 6 7 8 9 1 4 9 16 25 36 49 64 81 cat A134692.gen 1 2 3 4 5 6 7 8 9 1 8 27 64 125 216 343 512 729 */ #include <iostream> #include <sstream> #include <fstream> #include <vector> #include <string> #include <set> #include <map> #include <algorithm> using namespace std; struct entry { struct adjentry { string add; vector<entry>::iterator to; adjentry (const string& add_in, vector<entry>::iterator to_in) : add (add_in), to (to_in) {} }; string val; int count; size_t lowerbound; vector<adjentry> adj; entry (const string& val_in) : val (val_in), count (0), lowerbound (0) {} }; struct entryset { size_t tot_lowerbound; vector<entry> entries; }; struct NumberCmp { bool operator() (const string& a, const string& b) const { if (a.length() != b.length()) return (a.length() < b.length()); return (a < b); } }; void build_square_cube (set<string>& vals) { for (int d=1; d <= 9; ++d) { ostringstream os; os << d; vals.insert (os.str()); ostringstream os2; os2 << d*d; vals.insert (os2.str()); ostringstream os3; os3 << d*d*d; vals.insert (os3.str()); } } void prep_entries (const set<string>& vals, vector<entry>& puz, size_t& lb) { puz.clear(); for (set<string>::const_iterator i = vals.begin(); i != vals.end(); ++i) { bool is_substr = false; for (set<string>::const_iterator j = vals.begin(); j != vals.end(); ++j) { if (i == j) continue; size_t loc = j->find (*i); if (loc != string::npos) { is_substr = true; break; } } if (is_substr && i->length() != 1) continue; puz.push_back (*i); if (is_substr) { puz.back().count = 1; } else { puz.back().count = 0; } } for (vector<entry>::iterator i = puz.begin(); i != puz.end(); ++i) { if (i->val.length() == 1) { continue; } for (vector<entry>::iterator j = puz.begin(); j != puz.end(); ++j) { if (i == j) continue; for (size_t n = min(i->val.length(), j->val.length()) - 1; n > 0; --n) { if (i->val.substr (i->val.length() - n, n) == j->val.substr(0,n)) { i->adj.push_back (entry::adjentry (j->val.substr(n, j->val.length() - n), j)); } } } } for (vector<entry>::iterator i = puz.begin(); i != puz.end(); ++i) { if (i->count == 1) { i->lowerbound = 0; } else { i->lowerbound = i->val.length(); } } for (vector<entry>::iterator i = puz.begin(); i != puz.end(); ++i) { for (vector<entry::adjentry>::iterator j = i->adj.begin(); j != i->adj.end(); ++j) { if (j->add.length() < j->to->lowerbound) j->to->lowerbound = j->add.length(); } } lb = 0; for (vector<entry>::iterator i = puz.begin(); i != puz.end(); ++i) { lb += i->lowerbound; } } void gen_numbers (size_t len, const string& s, vector<entry>& puz, size_t& lb, entry& n, set<string,NumberCmp>& nums) { if (s.length() + lb > len) return; if (s.length() == len && lb == 0) { nums.insert (s); return; } if (s.length() >= len) return; for (vector<entry::adjentry>::iterator i = n.adj.begin(); i != n.adj.end(); ++i) { if (i->to->count == 0) lb -= i->to->lowerbound; i->to->count++; gen_numbers (len, s+i->add, puz, lb, *(i->to), nums); i->to->count--; if (i->to->count == 0) lb += i->to->lowerbound; } for (vector<entry>::iterator i = puz.begin(); i != puz.end(); ++i) { if (i->count == 0) lb -= i->lowerbound; i->count++; gen_numbers (len, s+i->val, puz, lb, *i, nums); i->count--; if (i->count == 0) lb += i->lowerbound; } } void gen_numbers (size_t len, const string& s, vector<entry>& puz, size_t& lb, set<string,NumberCmp>& nums) { if (s.length() + lb > len) return; if (s.length() == len && lb == 0) { nums.insert (s); return; } if (s.length() >= len) return; for (vector<entry>::iterator i = puz.begin(); i != puz.end(); ++i) { if (s.length() == 0 && i->val == "0") continue; if (i->count == 0) lb -= i->lowerbound; i->count++; gen_numbers (len, s+i->val, puz, lb, *i, nums); i->count--; if (i->count == 0) lb += i->lowerbound; } } void read_generators (istream& is, map<string, set<string> >& generators) { string buf; while (getline (is, buf)) { istringstream iss(buf); string src; iss >> src; string gen; while (iss >> gen) { generators[src].insert(gen); } } } void add_to_closure (map<string, set<string> >& generators, const string& s, set<string>& closure) { if (closure.find (s) != closure.end()) return; closure.insert (s); for (size_t i=0; i<s.length(); ++i) { string digit (s, i, 1); add_to_closure (generators, digit, closure); if (generators.find (digit) == generators.end()) continue; for (set<string>::iterator j = generators[digit].begin(); j != generators[digit].end(); ++j) { add_to_closure (generators, *j, closure); } } } void collect_valsets (set<set<string> >& valsets, map<string, set<string> >& generators, map<string, set<string> >::iterator cur, set<string>& curset) { if (cur == generators.end()) { if (curset.size() > 0) { set<string> closure; for (set<string>::iterator i = curset.begin(); i != curset.end(); ++i) { add_to_closure (generators, *i, closure); } valsets.insert (closure); } } else { const string& s = cur->first; ++cur; collect_valsets (valsets, generators, cur, curset); curset.insert (s); collect_valsets (valsets, generators, cur, curset); curset.erase (s); } } int main (int ac, char **av) { map<string, set<string> > generators; if (ac > 1) { ifstream is (av[1]); read_generators (is, generators); } else { read_generators (cin, generators); } #if 0 cout << "generators:" << endl; for (map<string, set<string> >::iterator i = generators.begin(); i != generators.end(); ++i) { cout << i->first << ":"; for (set<string>::iterator j = i->second.begin(); j != i->second.end(); ++j) { cout << " " << *j; } cout << endl; } #endif set<set<string> > valsets; set<string> valset; collect_valsets (valsets, generators, generators.begin(), valset); #if 0 cout << "string sets:" << endl; for (set<set<string> >::iterator i = valsets.begin(); i != valsets.end(); ++i) { for (set<string>::iterator j = i->begin(); j != i->end(); ++j) { cout << *j << " "; } cout << endl; } #endif vector<entryset> entrysets (valsets.size()); { vector<entryset>::iterator j = entrysets.begin(); for (set<set<string> >::iterator i = valsets.begin(); i != valsets.end(); ++i) { prep_entries (*i, j->entries, j->tot_lowerbound); #if 0 for (vector<entry>::iterator k = j->entries.begin(); k != j->entries.end(); ++k) { cout << k->val << ": lb " << k->lowerbound << " (" << k->count << "):"; for (vector<entry::adjentry>::iterator l = k->adj.begin(); l != k->adj.end(); ++l) { cout << " +" << l->add << "=" << l->to->val; } cout << endl; } cout << "lowerbound: " << j->tot_lowerbound << endl; cout << endl; #endif ++j; } } size_t len = 1; for (;;) { set<string,NumberCmp> nums; for (vector<entryset>::iterator i = entrysets.begin(); i != entrysets.end(); ++i) { string s = ""; gen_numbers (len, s, i->entries, i->tot_lowerbound, nums); } for (set<string,NumberCmp>::iterator i = nums.begin(); i != nums.end(); ++i) { cout << *i << endl; } ++len; } }