ACM Problems

[sans-hubris]

I have some problems from an intercollegiate ACM competition.

I'll list the first one, and once someone solves it, I'll list the next one.

A manufacturer wishes to encode the products it produces with unique codes expressed as a sequence of up to 32 uppercase letters. Every occurence of a particular product model will be encoded using the same number and the same group of letters, but in different permutations, of course.

For example a simple product code might include just the three letters A, B, and C. No more than six of this particular model product could be labeled with a code, however, since there are only six different codes that could be produced using A, B, and C (specifically ABC, ACB, BAC, BCA, CAB, and CBA.)

Some groups of letters from which codes are produced might include duplicates. For example, suppose the group included A, A, and B. The only codes that could be produced using this group are AAB, ABA, and BAA.

The manufacturer wants a program to aid in the generation of the product codes. Specifically, given an existing product code, determine and display the next sequential product code. The sequential ordering of product codes is naturally based on alphabetic ordering.

Input
The input will contain multiple cases. The input for each case is a single line containing between 1 and 32 uppercase letters immediately followed by the end of line character. The line following the last case will contain only a single end of line character.

Output
For each input case, display the next sequential product code on a line by itself, if one exists. If there is no next sequential code (that is, the input code is the last in the sequence of codes that can be created using the given group of letters), then display the message "*** No Successor ***".


Sample Input Expected Output
ACB BAC
ABCA ACAB
ZYXCAB ZYXCBA
ZYXCBA *** No Successor ***
<Blank line>

NB: vBulletin seems to like putting extra blank lines in the code boxes, FYI.

[sicarius]

Ok. I have a version implemented in Java. The algorithm is actually pretty easy. I used recursion, but of course you can do it iteratively. There are probably more ways as well. I split my code into two classes so I opted to post it on the web rather than directly to the forum. here is the link: http://www.speakcode.com/cf/index.html

have fun.

[l01yuk]

Well, I'm no the first to post it but here's an implementation in trad. c.

/*
Find the next viable product code.

*/

#include<stdio.h>
#include<stdlib.h>

usage()
{

puts("Usage: prod_code < uppercase code >");
exit(1);
}


compare(a,b)
char *a;
char *b;
{
if (a < b)
{
return -1;
}
if (a == b)
{
return 0;
}
if (a > b)
{
return 1;
}
}/* compare */

main(argc, argv)
int argc;
char *argv[];
{

char code[33];
int i, j, length = strlen(argv[1]);
char last, b;
int c, num;
char substr[33];


/* Make sure this was called ok. */
if(argc < 2 || argc > 2)
{
usage();
}

/* Make sure the string is not too long */
if(length > 32)
{
usage();
}

/* Make sure the input is actually uppercase chars */

strcpy(code,argv[1]);

for(i=0;i<length;i++)
{
if ( isupper(code[i]) == 0)
{
usage();
}
}

/* Check for no more codes. */
/* If no char has a larger char to its right this is the last itteration. */

for(i=0;i<length;i++)
{
if ( code[i] < code[i+1] )
{
break;
}

}/* for */

if ( i == length )
{ /* We have got to the end of the string. */
puts("*** no continuation ***");
exit(0);
}

/* Now to find the next code. */


/* Can we get away with swapping the last 2 chars. */
if (code[length - 1] > code[length - 2])
{
/* We got away with it */
b = code[length - 1];
code[length - 1] = code[length - 2];
code[length - 2] = b;

printf("\n%s\n",code);
exit(0);
}/* if */


last = code[length - 1];


for (i=(length - 1),c=0;i>=0;i--,c++)
{

substr[c] = code[i];

if (code[i-1] < code[i])
{ /* Find the next lowest char in substr. */

b = 'Z'; /* Default to a high char. */
for(j=0;j<=c;j++)
{
if ( (compare(substr[j],b) == -1) && (compare(substr[j],code[i-1]) == 1) )
{
b = substr[j];
num = j;
}
}/* for */

/* Swap b with the next lowest char from substr. */

last = code[i-1];
code[i-1] = substr[num];
substr[num] = last;


/* Now sort substr. */

qsort(&substr,strlen(substr),1,compare);


/* Reconstruct the line. */

code[i-1] = b;

for(j=0;i<length;j++,i++)
{
code[i] = substr[j];
}


/* Our work is done, no need to loop further. */
break;

} /* if */
} /* for */

printf("\n%s\n",code);

}/* main */