Changeset 410

Timestamp:

08/01/06 15:35:32 (4 years ago)

Author:

vasi

Message:

damn gdb sucks

Files:

• icfp2006/trunk/black/black.cpp (modified) (2 diffs)

icfp2006/trunk/black/black.cpp

@@ -1 +1 @@
 #include <cstdio>
+#include <iostream>
+#include <iomanip>
+#include <fstream>
+
+#include <string>
 #include <vector>
+#include <iterator>
+#include <ext/numeric>
+
 using namespace std;
+using namespace __gnu_cxx;
+
+
+// Type magic
+typedef char (&no_tag)[1]; 
+typedef char (&yes_tag)[2]; 
+
+#define HAS_TRAIT(trait) \
+        template <typename T> struct has_##trait { \
+                template <typename U> static no_tag helper(...); \
+                template <typename U> static yes_tag helper(int, \
+                        typename U::trait* = 0); \
+                enum { value = sizeof(helper<T>(0)) == sizeof(yes_tag) }; \
+        }; \
+
+HAS_TRAIT(const_iterator);
+
+
+// Dumping
+template <typename T> void dump(const T& n, ostream &os = cout);
+template <typename T> void dump_short(const T& n, ostream& os = cout);
 
 
@@ -11 +40 @@
                 : dest(p_dest), plinks(p_plinks) { }
 };
-
-class BlackKnot {
-        vector<MarbleResult> m_results;
+ostream& operator<<(ostream& os, const MarbleResult& r) {
+        return (os << "{ dest: " << r.dest << ",  plinks: " << r.plinks << " }");
+}
+
+
+struct Switcher {
+        unsigned line;
+        unsigned pos;
+        
+        Switcher(unsigned p_line = 0, unsigned p_pos = 0)
+                : line(p_line), pos(p_pos) { }
+};
+ostream& operator<<(ostream& os, const Switcher& sw) {
+        return (os << "{ line: " << sw.line << ",  pos: " << sw.pos << " }");
+}
+
+
+struct BlackKnot {
+        vector<MarbleResult> results;
+        
+        typedef vector<Switcher> Solution;
+        
+        BlackKnot(const char *specfile);
+        
+        Solution solve() const;
+        void output_solution(const Solution& soln, ostream& os = cout) const;
+        
+        unsigned size() const { return results.size(); }
+};
+ostream& operator<<(ostream& os, const BlackKnot& black);
+
+
+class Solver {  
+        const BlackKnot& black;
+        
+        BlackKnot::Solution     switchers;
+        vector<unsigned>        marbles;                // What marble in each position?
+        vector<unsigned>        plinks_left;
+        unsigned                        line, pos;
+        
+        bool findSwitcher();
+        bool addSwitcher();
+        void removeSwitcher();
+        
+        void doSwitch(const Switcher& sw, bool forward);
+        bool checkDone() const;
         
 public:
-        BlackKnot(const char *specfile);
-        void dump() const;
-};
+        Solver(const BlackKnot& p_black);
+        BlackKnot::Solution solve();
+
+        friend ostream& operator<<(ostream& os, const Solver& s);
+};
+ostream& operator<<(ostream& os, const Solver& s);
 
 
 int main(int argc, char **argv) {
-        const char *spec = argc >= 1 ? argv[1] : NULL;
-        BlackKnot knot(spec);
-        knot.dump();
-//      knot.solve();
+        const char *specfile = argc >= 1 ? argv[1] : NULL;
+        BlackKnot knot(specfile);
+        dump(knot.results);
+        
+        BlackKnot::Solution soln = knot.solve();
+        knot.output_solution(soln);
+        
+        return 0;
 }
 
 
 BlackKnot::BlackKnot(const char *specfile) {
-        FILE *file = specfile ? fopen(specfile, "r") : stdin;
-        unsigned source, dest, plinks;
-        
-        while (fscanf(file, " %u -> ( %u , %u ) \n", &source, &dest, &plinks)
-                        == 3) {
-                if (source >= m_results.size()) {
-                        m_results.resize(source + 1);
-                }
-                m_results[source] = MarbleResult(dest, plinks);
-        }
-        
-        fclose(file);
-}
-
-void BlackKnot::dump() const {
-        for (size_t i = 0; i < m_results.size(); ++i) {
-                printf("%zu -> (%u,%u)\n", i, m_results[i].dest, m_results[i].plinks);
-        }
-}
+        ifstream infile;
+        istream* is;
+        if (specfile) {
+                infile.open(specfile);
+                is = &infile;
+        } else {
+                is = &cin;
+        }       
+        
+        string s;
+        while (getline(*is, s)) {
+                // No good C++ replacement for scanf
+                unsigned source, dest, plinks;
+                if (sscanf(s.c_str(), " %u -> ( %u , %u ) \n",
+                                &source, &dest, &plinks) != 3) {
+                        cerr << "Error reading: '" << s << "'" << endl;
+                        break;
+                }
+                
+                if (source >= results.size()) {
+                        results.resize(source + 1);
+                }
+                results[source] = MarbleResult(dest, plinks);
+        }
+        
+        if (infile.is_open()) {
+                infile.close();
+        }
+}
+
+void BlackKnot::output_solution(const BlackKnot::Solution& soln,
+                ostream& os) const {
+        BlackKnot::Solution::const_iterator iter = soln.begin();
+        unsigned line = 0;
+        
+        while (iter != soln.end()) {
+                unsigned pos = 0;
+                while (pos < size()) {
+                        if (iter != soln.end()
+                                        && iter->line == line && iter->pos == pos) {
+                                os << "><";
+                                pos += 2;
+                                ++iter;
+                        } else {
+                                os << "|";
+                                ++pos;
+                        }
+                }
+                os << "\n";
+                ++line;
+        }
+}
+
+ostream& operator<<(ostream& os, const BlackKnot& black) {
+        for (unsigned i = 0; i < black.size(); ++i) {
+                const MarbleResult& r = black.results[i];
+                os << i << " -> (" << r.dest << "," << r.plinks << ")\n";
+        }
+        return os;
+}
+
+BlackKnot::Solution BlackKnot::solve() const {
+        return Solver(*this).solve();
+}
+
+Solver::Solver(const BlackKnot& p_black)
+                : black(p_black), marbles(p_black.size()), line(0), pos(0)
+{
+        iota(marbles.begin(), marbles.end(), 0);
+        
+        plinks_left.reserve(black.size());
+        vector<MarbleResult>::const_iterator iter;
+        for (iter = black.results.begin(); iter != black.results.end(); ++iter) {
+                plinks_left.push_back(iter->plinks);
+        }
+}
+
+BlackKnot::Solution Solver::solve() {
+        findSwitcher();
+        return switchers;
+}
+
+
+bool Solver::findSwitcher() {
+        // Don't allow a completely empty line
+        unsigned last_line = line + 1;
+        
+        while (line <= last_line) {
+                if (pos < black.size() - 1) {
+                        if (addSwitcher()) {
+                                if (findSwitcher()) {
+                                        return true;
+                                } else {
+                                        removeSwitcher();
+                                }
+                        }
+                        ++pos;
+                } else {
+                        pos = 0;
+                        ++line;
+                        if (checkDone()) {
+                                return true;
+                        }
+                }
+        }
+        return false;
+}
+
+void Solver::doSwitch(const Switcher& sw, bool forward) {
+        unsigned orig_right = marbles[forward ? pos + 1 : pos];
+        int plink_delta = forward ? -1 : +1;
+        plinks_left[orig_right] += plink_delta;
+        
+        swap(marbles[pos], marbles[pos+1]);
+}
+
+
+bool Solver::addSwitcher() {
+        Switcher sw(line, pos);
+        
+        unsigned right = marbles[pos + 1];
+        if (plinks_left[right] == 0) {
+                return false;
+        }
+        doSwitch(sw, true);
+        
+        switchers.push_back(sw);
+        pos += 2; // Line gets fixed in findSwitcher
+        return true;
+}
+
+void Solver::removeSwitcher() {
+        Switcher sw(switchers.back());
+        switchers.pop_back();
+        
+        doSwitch(sw, false);
+        
+        line = sw.line;
+        pos = sw.pos;
+}
+
+bool Solver::checkDone() const {
+        for (unsigned i = 0; i < black.size(); ++i) {
+                const MarbleResult& result = black.results[i];
+                if (plinks_left[i] != 0 || marbles[result.dest] != i) {
+                        return false;
+                }
+        }
+        return true;
+}
+
+ostream& operator<<(ostream& os, const Solver& s) {
+        // TODO
+        return os;
+}
+
+
+// Normal types
+template <typename T, bool U> struct Dumper {
+        static void dump(const T& n, ostream& os, unsigned) { os << n; }
+        static void dump_short(const T& n, ostream& os) { os << n; }
+};
+
+// Containers
+template <typename T> struct Dumper<T, true> {
+        typedef typename T::value_type U;
+        
+        static void dump(const T& n, ostream& os, unsigned indent) {
+                string s1(indent, ' '), s2(indent + 1, ' ');
+                os << "{\n";
+                
+                typename T::const_iterator iter = n.begin();
+                unsigned idx = 0;
+                for ( ; iter != n.end(); ++idx, ++iter) {
+                        os << s2 << setw(3) << idx << ". ";
+                        Dumper<U, has_const_iterator<U>::value>::dump(*iter, os,
+                                indent + 2);
+                        os << ",\n";
+                }
+                os << s1 << "}";
+        }
+        
+        static void dump_short(const T& n, ostream& os) {
+                os << "{ ";
+                typename T::const_iterator iter = n.begin();
+                if (iter != n.end())
+                        os << *iter++;
+                while (iter != n.end())
+                        os << ", " << *iter++;
+                os << " }" << endl;
+        }
+};
+
+
+template <typename T> void dump(const T& n, ostream &os) {
+        Dumper<T, has_const_iterator<T>::value>::dump(n, os, 0);
+        os << endl;
+}
+
+template <typename T> void dump_short(const T& n, ostream& os) {
+        Dumper<T, has_const_iterator<T>::value>::dump_short(n, os);
+        os << endl;
+}