1  /*
   2   * Problem:  Find the shortest string that contains all sub-strings
   3   *           of length "n" where each substring is a unique n-digit
   4   *           number.
   5   *
   6   * Algorithm: Create a directed graph, with each node being an (n-1)
   7   *            digit number, and each edge connecting one (n-1) digit number
   8   *            with all (n-1) digit numbers that could follow in the sequence.
   9   *            Each edge represents the n-digit numbers, and a Eulerian Cycle
  10   *            on this graph will yield the correct sequence.
  11   * 
  12   * In-depth: Imagine a directed graph of nodes, with one node for every
  13   *           (n-1) digit number. Each node has 10 edges leaving
  14   *           from it: one for every digit that would create an
  15   *           n digit number from the node's (n-1) digit number. The
  16   *           destination of each edge is the next (n-1) digit number
  17   *           made up of the last (n-1) digits of the n digit number
  18   *           that the edge represents.
  19   * 
  20   *           Example: If n is 3, then each node represents a 2 digit
  21   *           number. The node "01", for example, has 10 directed edges
  22   *           leaving from it, representing "010", "011", "012", etc.
  23   *           The node on the other end of the "010" edge is the "10"
  24   *           node; the node on the other end of the "011" edge is the "11"
  25   *           node, etc.
  26   *
  27   *           From this graph, it is easy to see that a path can start at
  28   *           some node "x" and trace every edge (a Eulerian Path) and end
  29   *           up back at "x" (a Eulerian Cycle, actually). Because every edge
  30   *           represents one distinct n digit number, all of them will be
  31   *           represented exactly once. Because every node has 10 edges coming
  32   *           in and 10 edges leaving, we are guaranteed to find a Eulerian Cycle.
  33   * 
  34   *           Once the cycle is found, walking it and printing out the numbers
  35   *           that are represented by the edges will give a proper sequence.
  36   */
  37  
  38  #include <map>
  39  #include <vector>
  40  #include <list>
  41  #include <string>
  42  #include <iostream>
  43  #include <cstdlib>
  44  #include <cstring>
  45  #include <cerrno>
  46  #include <cmath>
  47  
  48  #include <assert.h>
  49  
  50  using namespace std;
  51  
  52  /******************************************************************/
  53  /* Graph classes */
  54  
  55  /* All member data is public - it breaks encapsulation style,
  56     but it's nice and quick to write and use */
  57  
  58  class Node;
  59  
  60  class Edge
  61  {
  62  public:
  63    /* The node this edge goes to */
  64    Node *node;
  65    
  66    /* So we only get used once */
  67    int used;
  68  
  69  public:
  70    /* Create a new edge to the node */
  71    Edge(Node *n) {
  72      node = n;
  73      used = 0;
  74    }
  75  };
  76  
  77  class Node
  78  {
  79  public:
  80    /* This node's value */
  81    int value;
  82    
  83    /* This node's outgoing edges (10 of them in practice) */
  84    vector<Edge *> edges;
  85  
  86  public:
  87    /* Create a new node with a value */
  88    Node(int n) {
  89      value = n;
  90    }
  91    
  92    /* Destroy a node */
  93    ~Node() {
  94      for (int i = 0; i < edges.size(); i++) {
  95        delete edges[i];
  96      }
  97    }
  98  
  99    /* Return an unused edge, or NULL if no more remain */
 100    Edge *unusedEdge() {
 101      for (int i = 0; i < edges.size(); i++) {
 102        if (edges[i]->used == 0) return edges[i];
 103      }
 104      
 105      return NULL;
 106    }
 107    
 108    /* Decide if any edges are unused */
 109    bool hasUnusedEdges() {
 110      return (unusedEdge() != NULL);
 111    }
 112  };
 113  
 114  class Path
 115  {
 116  public:
 117    typedef list<Node *> NodeList;
 118    
 119    NodeList nodes;
 120    
 121  public:
 122    void printSequence(int n) {
 123      /* Print out the sequence of numbers. Start with the first
 124         node, and work through them all. The first node gets all of
 125         its digits printed. All of the rest only need to print their
 126         last digit. */
 127      NodeList::iterator i = nodes.begin();
 128      NodeList::iterator end = nodes.end();
 129  
 130      cout.width(n - 1);
 131      cout.fill('0');
 132      cout << (*i)->value;
 133      
 134      cout.width(0);
 135  
 136      ++i;
 137      
 138      for (; i != end; ++i) {
 139        cout << ((*i)->value % 10);
 140      }
 141      
 142      cout << endl;
 143    }
 144  
 145    /* Insert p's nodes into this path at position i */
 146    void merge(Path *p, NodeList::iterator i) {
 147      /* We can only insert if the new path starts at the iterator. */
 148      assert(p->nodes.front() == *i);
 149      
 150      /* We won't need the first node of the new path, because
 151         it is the same as the i'th node of our path */
 152      p->nodes.erase(p->nodes.begin());
 153      
 154      /* Insert all of the nodes of the new path after the i'th node
 155         of our path.
 156        
 157         Before:
 158        
 159          (i-2) .. (i-1) .. i .. (i+1) .. (i+2)
 160       
 161         After:
 162       
 163          (i-2) .. (i-1) .. i .. (all of p's nodes) .. (i+1) .. (i+2)
 164        
 165         Because p started and ended at i, the result is still
 166         a path - just longer.
 167       */
 168  
 169      /* Insert() inserts before the arg, so we want i + 1 */
 170      ++i;
 171      nodes.insert(i, p->nodes.begin(), p->nodes.end());
 172      
 173      /* Clean up p - it is no longer needed */
 174      delete p;
 175    }
 176  };
 177  
 178  class Graph
 179  {
 180  public:
 181    typedef map<int, Node*> NodeMap;
 182  
 183    /* A mapping from the node's number to the node */
 184    NodeMap nodes;
 185  
 186    int size;
 187    int num_edges;
 188      
 189  public:
 190    /* Create all the nodes and edges for a graph
 191     * full of (n-1) digit numbers */
 192    Graph(int n) {
 193      /* For an n-1 digit number, we need 10^(n-1) nodes */
 194      size = (int)pow(10.0, n - 1);
 195      
 196      /* Create every node */
 197      for (int i = 0; i < size; i++) {
 198        nodes[i] = new Node(i);
 199      }
 200      
 201      /* For every node, make an edge to every other node
 202         that contains the last n-2 digits of this node
 203         plus the next digit (from 0 to 9). Each edge represents
 204         an n-digit number, the first n-1 digits being the
 205         "from" node, and the last n-1 digits being the "to"
 206         node. For example, with 3 digit numbers, we'd create
 207         one edge going from "01" to "18" representing "018",
 208         and from "01" to "19" representing "019", etc. */
 209      num_edges = 0;
 210      
 211      int mod = (int)pow(10.0, n - 2);
 212      
 213      for (int i = 0; i < size; i++) {
 214        for (int j = 0; j < 10; j++) {
 215          /* Calculate the new n-1 digit number - it starts with
 216             the last n-2 digits of i, and ends with j */
 217  
 218          int k = i % mod; /* Mod off the first digit */
 219          k *= 10;         /* Make room for the new digit */
 220          k += j;          /* Add in the new digit */
 221  
 222          assert(k < size);
 223          
 224          /* Create an edge from nodes[i] to nodes[k] */
 225          nodes[i]->edges.push_back(new Edge(nodes[k]));
 226          
 227          num_edges++;
 228        }
 229      }
 230    }
 231    
 232    /* Destroy a graph and all memory */
 233    ~Graph() {
 234      for (int i = 0; i < nodes.size(); i++) {
 235        delete nodes[i];
 236      }
 237    }
 238  
 239    /* Find and return a path for one single cycle. This cycle
 240       is found by walking from unused edge to unused edge until
 241       no more unused edges leave the node we're on.
 242  
 243       Because there are an even number of incoming and outgoing
 244       edges, and because they are equal, a cycle always exists.
 245       See findCompleteCycle() below for more information.
 246     */
 247    Path *findCycle(Node *node) {
 248      Path *p = new Path();
 249      Node *n = node;
 250  
 251      /* The path starts at the node and walks around unused edges */
 252      p->nodes.push_back(n);
 253      
 254      while (true) {
 255        
 256        /* Choose an edge that isn't used */
 257        if (n->hasUnusedEdges()) {
 258          Edge *e = n->unusedEdge();
 259          
 260          /* Use it by pushing the node it goes to
 261             on our path */
 262          e->used = 1;
 263          n = e->node;
 264          p->nodes.push_back(n);
 265        } else {
 266          /* No more unused edges - we must have completed a cycle */
 267          assert(n == node);
 268          break;
 269        }
 270      }
 271      
 272      return p;
 273    }
 274    
 275    /* Find and return a cycle that traverses every edge. Start
 276       by finding any cycle. Because this graph is fully-connected
 277       and because every node has an even number of incoming edges
 278       and an even number of outgoing edges and the incoming edges
 279       and the outgoing edges are the same number, then we are
 280       guaranteed a few things:
 281       
 282       (1) We can always find a cycle. If you can enter a node,
 283           you are either at the node you started on or there is
 284           a free edge that you can leave on.
 285       
 286       (2) Once we find a cycle, if there are any un-traversed
 287           edges left, we can find a new cycle on un-traversed
 288           edges. Simply start at the node with un-traversed
 289           edges, and follow along. See (1).
 290       
 291       (3) We can combine any two cycles that share a node into
 292           one larger cycle.
 293     
 294       (4) Because the graph is fully-connected, we will eventually
 295           be able to connect all of the cycles into one large one.
 296        
 297       This means we can create one cycle that traverses every edge.
 298       We do this by starting with an empty path. We find one cycle,
 299       and add it to the path. Then, as we start from the beginning
 300       of the path and walk along it, every node we reach that has
 301       unused edges leaving it will generate a new path that we will
 302       find and add to the current path at that node. When we are finished
 303       walking this ever-growing path, we will have a complete cycle
 304       because no node on the path will have any more edges leaving it.
 305    */
 306    Path *findCompleteCycle() {
 307      Path *p = new Path();
 308      
 309      /* Iterator */
 310      Path::NodeList::iterator i;
 311      
 312      /* Start at the first node */
 313      p->nodes.push_back(nodes[0]);
 314      i = p->nodes.begin();
 315  
 316      while (true) {
 317        
 318        /* Find a node along the path that has edges leaving it.
 319           Start by looking at the current node. */
 320        while ((*i)->hasUnusedEdges()) {
 321          
 322          /* Create a new cycle from this node, and merge it onto
 323             our path */
 324          Path *q = findCycle(*i);
 325          p->merge(q, i); /* This also deletes q */
 326        }
 327  
 328        /* Walk one step along the path, since the current node
 329           has no more unused edges */
 330        ++i;
 331        
 332        /* If we are at the end of the path (we have walked all
 333           of the edges and we are back at the beginning), we
 334           are done */
 335        if (i == p->nodes.end()) {
 336           /* Have we covered all the edges? We should have nodes for
 337              every edge (with one node repeated at the beginning and end)
 338            */
 339          assert(p->nodes.size() == num_edges + 1);
 340          
 341          /* Does the path start and end at the same place? */
 342          assert(p->nodes.front() == p->nodes.back());
 343          
 344          /* We are done */
 345          break;
 346        }
 347      }
 348      
 349      return p;
 350    }
 351  };
 352  
 353  /******************************************************************/
 354  /* The algorithm */
 355  
 356  static void print_sequence(int n)
 357  {
 358    assert(n > 0);
 359    assert(n <= 6);
 360    
 361    /* 1 is trivial, and our graph algorithm needs at least 2 anyhow */
 362    if (n == 1) {
 363      cout << "0123456789" << endl;
 364      return;
 365    }
 366    
 367    /* Generate the graph */
 368    Graph *g = new Graph(n);
 369    
 370    /* Find a Eulerian Cycle */
 371    Path *p = g->findCompleteCycle();
 372    
 373    /* Print the path */
 374    p->printSequence(n);
 375    
 376    /* Clean up */
 377    delete p;
 378    delete g;
 379  }
 380  
 381  /******************************************************************/
 382  /* Main driver */
 383  
 384  int main(int argc, char **argv)
 385  {
 386    if (argc != 2) {
 387      cerr << "Usage: safecrack <n>, where 1 <= n <= 6\n";
 388      exit(1);
 389    }
 390    
 391    int n = atoi(argv[1]);
 392  
 393    if (n < 1 || n > 6) {
 394      cerr << "Invalid number in input: " << n << endl;
 395      exit(1);
 396    }
 397  
 398    print_sequence(n);
 399    return 0;
 400  }