/* C++ source of A160170, Richard J. Mathar, Jan 08 2010 */ #include <iostream> #include <vector> using namespace std ; /* define the macro PRINT_GNUPLOT if a gnuplot(1) file is to be created, like a160170.gp: gnuplot <<++ set terminal postscript portrait enhanced color unset border set size 1,0.75 set view 70,60 set ticslevel 0 set xrange [-5:5] set yrange [-5:5] set zrange [-5:5] set format x "" set format y "" set format z "" unset tics load "a160170.out" ++ Gv a160170*.eps This assumes that a160170.nul contains gnuplot(1) axis coordinates: 0 -5 0 0 5 0 -5 0 0 5 0 0 0 0 -5 0 0 5 */ /** A point in the 3D simple cubic integer grid */ class Pt { public: /** The three Cartesian coordinates */ int x,y,z ; Pt(int X, int Y, int Z) : x(X), y(Y), z(Z) { } } ; /* Pt */ /** A toothpick of length 2 in the 3D simple cubic grid, * aligned with one of the 3 coordinate axes. */ class Tp { public: /* its two terminating points */ Pt a; Pt b; /* constructor from the three cartesian coordinates * of each of the 2 ends */ Tp(int x1, int y1, int z1, int x2, int y2, int z2) : a(x1,y1,z1), b(x2,y2,z2) { } /** Compute the two toothpicks that cross the toothpick (which is from st to en) * at the point en. */ static vector<Tp> perp(const Pt & st, const Pt & en) { if ( st.x == en.x && st.y == en.y) /* original toothp is vertical */ { Tp fi(en.x-1, en.y, en.z, en.x+1, en.y, en.z) ; Tp se(en.x, en.y-1, en.z, en.x, en.y+1, en.z) ; vector<Tp> res ; res.push_back(fi) ; res.push_back(se) ; return res ; } else if( st.y == en.y && st.z == en.z) /* is horizontal parallel to x */ { Tp fi(en.x, en.y-1, en.z, en.x, en.y+1, en.z) ; Tp se(en.x, en.y, en.z-1, en.x, en.y, en.z+1) ; vector<Tp> res ; res.push_back(fi) ; res.push_back(se) ; return res ; } else /* is horizontal parallel to y */ { Tp fi(en.x-1, en.y, en.z, en.x+1, en.y, en.z) ; Tp se(en.x, en.y, en.z-1, en.x, en.y, en.z+1) ; vector<Tp> res ; res.push_back(fi) ; res.push_back(se) ; return res ; } } /* return true if the point pt is one of the ends of this tootpick here. */ bool has(const Pt & pt) const { return ( pt.x == a.x && pt.y == a.y && pt.z == a.z || pt.x == b.x && pt.y == b.y && pt.z == b.z) ; } /* return true if the point pt is the mid point of this tootpick here. */ bool hasMid (const Pt & pt) const { return ( 2*pt.x == a.x+b.x && 2*pt.y == a.y+b.y && 2*pt.z == a.z+b.z) ; } }; /* Tp */ /** A toothpick set */ class TpS { public: /** The set of all toothpicks */ vector<Tp> ts; /* Construct it form a vector of known toothpicks */ TpS( vector<Tp> & in) : ts(in) { } /** OEIS main functionality: count toothpick pairs (=X toothpicks) in the set */ int cnt() const { return ts.size()/2 ; } /** return true if p is a terminal point of any toothpick of this set */ bool isExp(const Pt & p) const { /* scan all toothpicks in the set and increment the counter by * 1 each time p is an end, and by 2 if p is a mid point */ int cnt = 0; for(int i=0; i< ts.size() ; i++) { if ( ts[i].has(p) ) cnt++ ; if ( ts[i].hasMid(p) ) cnt += 2 ; } /* return true if the counter is 1, else false */ return ( cnt == 1) ; } /** return the next generation of toothpicks, including the * tootpick of the current set (generation). */ TpS nextg() const { /* new generation, initially empty */ vector<Tp> res ; /* scan all tootpicks in the current set */ for(int i=0 ; i < ts.size() ; i++) { /* if one of the two ends of the tootpick in the current * set is an exposed point, construct the tootpick cross * and add its two tootpicks to the new generation. */ if ( isExp( ts[i].a ) ) { //cout << "is ex " << ts[i].a.x << " " << ts[i].a.y << endl ; vector<Tp> n = Tp::perp(ts[i].b,ts[i].a) ; res.push_back(n[0]) ; res.push_back(n[1]) ; } if ( isExp( ts[i].b ) ) { //cout << "is ex " << ts[i].b.x << " " << ts[i].b.y << endl ; vector<Tp> n = Tp::perp(ts[i].a,ts[i].b) ; res.push_back(n[0]) ; res.push_back(n[1]) ; } } #ifdef PRINT_GNUPLOT /* debug: print status for gnuplot(1) */ for(int i=0 ; i < res.size() ; i++) { cout << "set arrow from " << res[i].a.x << "," << res[i].a.y << "," << res[i].a.z << " to " << res[i].b.x << "," << res[i].b.y << "," << res[i].b.z << " nohead lt 2 " << endl ; } #endif /* append the toothpicks of the current set */ for(int i=0 ; i < ts.size() ; i++) { res.push_back( ts[i] ) ; #ifdef PRINT_GNUPLOT cout << "set arrow from " << ts[i].a.x << "," << ts[i].a.y << "," << ts[i].a.z << " to " << ts[i].b.x << "," << ts[i].b.y << "," << ts[i].b.z << " nohead " << endl ; #endif } #ifdef PRINT_GNUPLOT cout << "splot \"a160170.nul\" notitle" << endl ; cout << "unset arrow" << endl ; #endif return res ; } }; /* TpS */ /* Main function. No command line arguments. Makefile: a160170_2.eps: a160170.out a160170.gp a160170.nul a160170.gp a160170.out: a160170 $< > $@ a160170: a160170.cpp # $(CXX) -O -o $@ -DPRINT_GNUPLOT $< $(CXX) -O -o $@ $< */ int main(int argc, char *argv[]) { #ifndef PRINT_GNUPLOT cout << "0," ; #endif /* Start with crossed tootpick pointing from (-1,0,0) to (1,0,0) * and from (0,-1,0) to (0,1,0) */ Tp *rol = new Tp(-1,0,0,1,0,0) ; vector<Tp> rot; rot.push_back(*rol) ; delete rol ; rol = new Tp(0,-1,0,0,1,0) ; rot.push_back(*rol) ; delete(rol) ; /* Initialize the first generation with the toothpick set that * contains only this one toothpick */ TpS root(rot) ; /* loop over generations */ for(int g=2 ; #ifdef PRINT_GNUPLOT g < 12 ; #else g < 40 ; #endif g++) { /* print the current total count of toothpicks in that generation */ #ifndef PRINT_GNUPLOT cout << root.cnt() << ",\n" ; #else cout << "# g= " << g << " " << root.cnt() << endl ; cout << "set output \"a160170_" << g << ".eps\n" ; #endif /* add toothpicks to the exposed points */ TpS g = root.nextg(); root = g ; } cout << endl ; }