Programming Forums > Application Development > Software Design and Algorithms

Sane · Jul 1st, 2008, 1:38 PM

The test data for identification cards is too large to be attached, and has been uploaded here: http://www.2shared.com/file/3529149/5177bf74/cards.html

Identification Cards (Advanced)

Despite the difficulty of this problem, I am happy to see that several people attempted the problem.

Even though no one got the "correct" answer, most peoples' logic were very close and only some minor fixes were necessary to get perfect.

Jimbo's solution was the best, with only one change needed to get perfect.

--------------

The input files were carefully engineered to try to exploit every possible mistake.

Here is a description of each input file, to help you understand the cases you did not handle:

1) The Sample Data #1
2) The Sample Data #2
3) A test for being able to use single digit cards.
4) A very sparse graph where you could start with any card to arrange them all in a line.
5) A very sparse graph where two nodes have unbalanced in/out-degrees, but no Eulerian path.
6) A very dense graph with cards that have same start and end digits, and has to start and end on a specific card.
7) A sparse graph that is disconnected (Two lines can be formed). Each line can start on any card within its disjoint graph.
8) A very dense graph that is disconnected (Two lines can be formed). Each line can start on any card within its disjoint graph.
9) A dense graph that can start on any node, but follows a rather complicated path to use every card.
A) A sparse graph which has two obscure verticies with unbalanced in/out-degrees, but no Eulerian path.

Sparse/dense refers to how many different edges there are.
In the spare graphs, the first and last digits were mostly the same.
In the dense graphs, there were many different combinations of first and last digits.

--------------

Now, on to the solution.

Identification Cards is another problem involving graph theory.

The major observation is that the only thing that "matters" about a card is its first and last digit. It does not matter what the other digits are. This reduces the number of different cards from 1,000,000 to 100 (00 to 99); a great start.

In this question, the vertecies and edges of the graph are a little more difficult to identify.

In short: digits are the vertecies, and cards are the edges.

For example, the card "50009" joins the verticies "5" and "9" by a directed edge.

Thus, there are 10 vertecies (0-9) and 100 possible edges (10*10).

We can also label an edge according to how many duplicate edges exist between the two vertecies.

For example, here is some input data, and its corresponding graph:

(Toggle Plain Text)

Using every card is now the equivilent of traversing every edge exactly once.

Doing so is known as forming a Eulerian Path.

In this particular graph, the only possible Eulerian path starts at "2" and ends on "5":

(Toggle Plain Text)

2-1-1-5-2-5-2-9-5-2-9-5

20001
10001
10005
50302
20005
50502
20009
90005
50702
20509
90505

The reason you must start at "2", is because the number of edges that point to 2 is one less than the number of edges that leave 2.

Similarly, the reason the path must end at "5", is because the number of edges that point to 5 is one more than the number of edges that leave 5.

Just try to find a path that proves otherwise!

The number of 'pointing' and 'leaving' edges is referred to as a node's "in-degree" and "out-degree", respectively.

As it turns out, in a directed graph, there exists a Eulerian path if and only if the in-degree and out-degree of every node differ by no more than 1 on no more than 2 two nodes.

These two nodes are always the start and end nodes. If every node has the same in-degree and out-degree, the Eulerian path can start on any node (and will always end on that same node).

There are a couple additional things to handle:

Since numerous edges can exist between the same two nodes, you must be careful to make sure the degrees differ by no more than 1. Some people simply counted how many nodes were unbalanced. But there are many cases where a Eulerian path can't be found even if only two nodes are unbalanced.

For example,

(Toggle Plain Text)

1 has four edges to 2, and 2 has two edges to 1. Even though two nodes are unbalanced, no Eulerian path can be found.

The solution is to total the differences in in-degrees and out-degrees, and make sure it's less than or equal to 2.

The other problem is the digraph must be at least "weakly connected" (if the edges are made undirected, every vertex can be reached). The reason is because you can have two disjoint portions of the graph which both contain a Eulerian cycle, yet the total balance will still be 0.

For example,

(Toggle Plain Text)

The total balance is 0, yet no Eulerian path can be found since the graph is disconnected.

The solution is to treat the edges as undirected, and count the number of reachable vertecies with a depth first search. Then make sure it equals the number of vertecies which have been mentioned.

And here it is all together:

 C Syntax (Toggle Plain Text) 
#include <stdio.h>
#include <string.h>
#define MAX 10
#define ABS(x) ((x)<0?-(x):(x))
 
int vis[MAX] = {0};
int ins[MAX] = {0};
int out[MAX] = {0};
int undir[MAX][MAX] = {0};
char card[15];
 
int count(int i) {
    int j, s=0;
    if(vis[i]) return 0;
    vis[i] = 1;
    for(j=0; j<MAX; j++) if(undir[i][j]) s += count(j);
    return s+1;
}
 
int iseuler() {
    int i, delta=0;
    for(i=0; i<MAX; i++) delta += ABS(ins[i] - out[i]);
    return delta <= 2;
}
 
int main() {
    int i, j, k, n, dig=0;
 
    freopen("cards.in", "rt", stdin);
    freopen("cards.out", "wt", stdout);
 
    scanf("%d", &n);
    for(i=0; i<n; i++) {
        scanf("%s", card);
        j = card[0]-'0';
        k = card[strlen(card)-1]-'0';
        // Link vertecies with undirected edge
        undir[j][k] = undir[k][j] = 1;
        // Increment the degrees on each node
        out[j]++;
        ins[k]++;
        // Count existing vertecies
        if(!vis[j]) vis[j] = ++dig;
        if(!vis[k]) vis[k] = ++dig;
    }
 
    memset(vis, 0, sizeof(vis));
    if(count(j) == dig && iseuler()) printf("Yep!\n");
    else printf("Vladimir needs better entertainment.\n");
 
    return 0;
}
#include <stdio.h>
#include <string.h>
#define MAX 10
#define ABS(x) ((x)<0?-(x):(x))

int vis[MAX] = {0};
int ins[MAX] = {0};
int out[MAX] = {0};
int undir[MAX][MAX] = {0};
char card[15];

int count(int i) {
    int j, s=0;
    if(vis[i]) return 0;
    vis[i] = 1;
    for(j=0; j<MAX; j++) if(undir[i][j]) s += count(j);
    return s+1;
}

int iseuler() {
    int i, delta=0;
    for(i=0; i<MAX; i++) delta += ABS(ins[i] - out[i]);
    return delta <= 2;
}

int main() {
    int i, j, k, n, dig=0;
    
    freopen("cards.in", "rt", stdin);
    freopen("cards.out", "wt", stdout);
    
    scanf("%d", &n);
    for(i=0; i<n; i++) {
        scanf("%s", card);
        j = card[0]-'0';
        k = card[strlen(card)-1]-'0';
        // Link vertecies with undirected edge
        undir[j][k] = undir[k][j] = 1;
        // Increment the degrees on each node
        out[j]++;
        ins[k]++;
        // Count existing vertecies
        if(!vis[j]) vis[j] = ++dig;
        if(!vis[k]) vis[k] = ++dig;
    }

    memset(vis, 0, sizeof(vis));
    if(count(j) == dig && iseuler()) printf("Yep!\n");
    else printf("Vladimir needs better entertainment.\n");
    
    return 0;
}

Thread Tools
Show Printable Version Email this Page
Display Modes
Linear Mode Switch to Hybrid Mode Switch to Threaded Mode

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
SMAC #2 [06-08] - Escalator Troubles (Senior)	Sane	Software Design and Algorithms	5	Jul 2nd, 2008 12:29 AM
SMAC #1 [05-08] - Results	Sane	Software Design and Algorithms	6	Jun 2nd, 2008 5:56 PM
advanced user output	l2u	C++	6	May 9th, 2007 9:16 PM
dealing cards	brad sue	C	21	Mar 28th, 2006 2:21 AM
CSS3 Advanced Layout Module	titaniumdecoy	HTML / XHTML / CSS	1	Dec 25th, 2005 1:06 AM

Jul 1st, 2008, 1:38 PM	#1
Sane Programming Guru Join Date: Apr 2005 Location: Waterloo, Ontario Posts: 2,028 Rep Power: 6	SMAC #2 [06-08] - Identification Cards (Advanced) The test data for identification cards is too large to be attached, and has been uploaded here: http://www.2shared.com/file/3529149/5177bf74/cards.html Identification Cards (Advanced) Despite the difficulty of this problem, I am happy to see that several people attempted the problem. Even though no one got the "correct" answer, most peoples' logic were very close and only some minor fixes were necessary to get perfect. Jimbo's solution was the best, with only one change needed to get perfect. -------------- The input files were carefully engineered to try to exploit every possible mistake. Here is a description of each input file, to help you understand the cases you did not handle: 1) The Sample Data #1 2) The Sample Data #2 3) A test for being able to use single digit cards. 4) A very sparse graph where you could start with any card to arrange them all in a line. 5) A very sparse graph where two nodes have unbalanced in/out-degrees, but no Eulerian path. 6) A very dense graph with cards that have same start and end digits, and has to start and end on a specific card. 7) A sparse graph that is disconnected (Two lines can be formed). Each line can start on any card within its disjoint graph. 8) A very dense graph that is disconnected (Two lines can be formed). Each line can start on any card within its disjoint graph. 9) A dense graph that can start on any node, but follows a rather complicated path to use every card. A) A sparse graph which has two obscure verticies with unbalanced in/out-degrees, but no Eulerian path. Sparse/dense refers to how many different edges there are. In the spare graphs, the first and last digits were mostly the same. In the dense graphs, there were many different combinations of first and last digits. -------------- Now, on to the solution. Identification Cards is another problem involving graph theory. The major observation is that the only thing that "matters" about a card is its first and last digit. It does not matter what the other digits are. This reduces the number of different cards from 1,000,000 to 100 (00 to 99); a great start. In this question, the vertecies and edges of the graph are a little more difficult to identify. In short: digits are the vertecies, and cards are the edges. For example, the card "50009" joins the verticies "5" and "9" by a directed edge. Thus, there are 10 vertecies (0-9) and 100 possible edges (1010). We can also label an edge according to how many duplicate edges exist between the two vertecies. For example, here is some input data, and its corresponding graph: (Toggle Plain Text) 11 10001 10005 20001 20005 20009 20509 50302 50502 50702 90005 90505 11 10001 10005 20001 20005 20009 20509 50302 50502 50702 90005 90505 Using every card is now the equivilent of traversing every edge exactly once. Doing so is known as forming a Eulerian Path. In this particular graph, the only possible Eulerian path starts at "2" and ends on "5": (Toggle Plain Text) 2-1-1-5-2-5-2-9-5-2-9-5 20001 10001 10005 50302 20005 50502 20009 90005 50702 20509 90505 2-1-1-5-2-5-2-9-5-2-9-5 20001 10001 10005 50302 20005 50502 20009 90005 50702 20509 90505 The reason you must start at "2", is because the number of edges that point to 2 is one less than the number of edges that leave 2. Similarly, the reason the path must end at "5", is because the number of edges that point to 5 is one more than the number of edges that leave 5. Just try to find a path that proves otherwise! The number of 'pointing' and 'leaving' edges is referred to as a node's "in-degree" and "out-degree", respectively. As it turns out, in a directed graph, there exists a Eulerian path if and only if the in-degree and out-degree of every node differ by no more than 1 on no more than 2 two nodes. These two nodes are always the start and end nodes. If every node has the same in-degree and out-degree, the Eulerian path can start on any node (and will always end on that same node). There are a couple additional things to handle: Since numerous edges can exist between the same two nodes, you must be careful to make sure the degrees differ by no more than 1. Some people simply counted how many nodes were unbalanced. But there are many cases where a Eulerian path can't be found even if only two nodes are unbalanced. For example, (Toggle Plain Text) 12 102 112 122 21 201 12 102 112 122 21 201 1 has four edges to 2, and 2 has two edges to 1. Even though two nodes are unbalanced, no Eulerian path can be found. The solution is to total the differences in in-degrees and out-degrees, and make sure it's less than or equal to 2. The other problem is the digraph must be at least "weakly connected" (if the edges are made undirected, every vertex can be reached). The reason is because you can have two disjoint portions of the graph which both contain a Eulerian cycle, yet the total balance will still be 0. For example, (Toggle Plain Text) 1002 2001 5006 6005 1002 2001 5006 6005 The total balance is 0, yet no Eulerian path can be found since the graph is disconnected. The solution is to treat the edges as undirected, and count the number of reachable vertecies with a depth first search. Then make sure it equals the number of vertecies which have been mentioned. And here it is all together: C Syntax* (Toggle Plain Text) #include <stdio.h> #include <string.h> #define MAX 10 #define ABS(x) ((x)<0?-(x):(x)) int vis[MAX] = {0}; int ins[MAX] = {0}; int out[MAX] = {0}; int undir[MAX][MAX] = {0}; char card[15]; int count(int i) { int j, s=0; if(vis[i]) return 0; vis[i] = 1; for(j=0; j<MAX; j++) if(undir[i][j]) s += count(j); return s+1; } int iseuler() { int i, delta=0; for(i=0; i<MAX; i++) delta += ABS(ins[i] - out[i]); return delta <= 2; } int main() { int i, j, k, n, dig=0; freopen("cards.in", "rt", stdin); freopen("cards.out", "wt", stdout); scanf("%d", &n); for(i=0; i<n; i++) { scanf("%s", card); j = card[0]-'0'; k = card[strlen(card)-1]-'0'; // Link vertecies with undirected edge undir[j][k] = undir[k][j] = 1; // Increment the degrees on each node out[j]++; ins[k]++; // Count existing vertecies if(!vis[j]) vis[j] = ++dig; if(!vis[k]) vis[k] = ++dig; } memset(vis, 0, sizeof(vis)); if(count(j) == dig && iseuler()) printf("Yep!\n"); else printf("Vladimir needs better entertainment.\n"); return 0; } #include <stdio.h> #include <string.h> #define MAX 10 #define ABS(x) ((x)<0?-(x):(x)) int vis[MAX] = {0}; int ins[MAX] = {0}; int out[MAX] = {0}; int undir[MAX][MAX] = {0}; char card[15]; int count(int i) { int j, s=0; if(vis[i]) return 0; vis[i] = 1; for(j=0; j<MAX; j++) if(undir[i][j]) s += count(j); return s+1; } int iseuler() { int i, delta=0; for(i=0; i<MAX; i++) delta += ABS(ins[i] - out[i]); return delta <= 2; } int main() { int i, j, k, n, dig=0; freopen("cards.in", "rt", stdin); freopen("cards.out", "wt", stdout); scanf("%d", &n); for(i=0; i<n; i++) { scanf("%s", card); j = card[0]-'0'; k = card[strlen(card)-1]-'0'; // Link vertecies with undirected edge undir[j][k] = undir[k][j] = 1; // Increment the degrees on each node out[j]++; ins[k]++; // Count existing vertecies if(!vis[j]) vis[j] = ++dig; if(!vis[k]) vis[k] = ++dig; } memset(vis, 0, sizeof(vis)); if(count(j) == dig && iseuler()) printf("Yep!\n"); else printf("Vladimir needs better entertainment.\n"); return 0; } __________________ Looking for tough programming challenges? Try participating in Sane's Monthly Algorithms Challenges! Composing Techno is a little side hobby of mine. Techno by DJ Sane. All free for download.

Currently Active Users Viewing This Thread: 1 (0 members and 1 guests)

Programming Forums > Application Development > Software Design and Algorithms

SMAC #2 [06-08] - Identification Cards (Advanced)