/* cubes.java Letter Cubes, 2013 Mid-Central Programming Competition, Problem E Java Solution by Andy Harrington Basic recursive search. Checking along the way and backtracking is essential since with 4 dice there are C(23, 5)*C(17, 5)*C(11, 5) = 96197645544 possible die combinations The basic constraint is that any two letters in the same word cannot be on the same die. This is recorded in 2D array: sep. Initially all the letters from the dice and the possible extra are gathered in order into the string: used. The recursion makeDice systematically tries to add the next letter to the current die, or if a non-terminal die is full, remove all those letters from the stock of remaining letters to try in the later dice. By always trying letters closest to the beginning of the alphabet first, there is no need to sort the data in a solution, when all are placed. */ import java.util.*; import java.io.*; public class cubes { static char FIRST = 'A', LAST = 'Z'; //char range static int SIDES= 6, // sides on die nDice, // nCh/SIDES nCh; // number of symbols used static char unused; // one die character not in any word, or '-'. static String[] words; // given strings from input static int nWords; // number of words static String used; // all char use, in sorted order, must fill dice static boolean[][] sep; // sep[ch1][ch2] is true if ch1, ch2 in same word static char[] sol; // start of potential solution, SIDES per die public static void main(String[] args) throws Exception { String file = (args.length > 0) ? args[0] : "cubes.in"; Scanner in = new Scanner(new File(file)); nWords = in.nextInt(); while (nWords != 0) { unused = in.next().charAt(0); words = new String[nWords]; for (int i = 0; i < nWords; i++) words[i] = in.next(); solve(); nWords = in.nextInt(); } } static void solve() { sep = new boolean[LAST+1][LAST+1]; // pairs forced on separate dice nDice = words[0].length(); for (int i = 0; i < nWords; i++) { // for each word for (int j = 0; j < nDice-1; j++) { // mark each char ch1 = words[i].charAt(j); // char pair for (int k = j+1; k < nDice; k++) { // as being char ch2 = words[i].charAt(k); // on separate sep[ch1][ch2] = sep[ch2][ch1] = true; // dice } } } used = ""; // accumulate used characters in alphabetical order for (char ch1 = FIRST; ch1 <= LAST; ch1++) for (char ch2 = FIRST; ch2 <= LAST; ch2++) if (ch1 == unused || sep[ch1][ch2]) { used += ch1; break; } nCh = used.length(); judgeCheck(); // judge consistency check sol = new char[nCh]; makeDice(null, 0, 0); // recursively build up sol judgeWrapup(); // judge check } static void makeDice(char[] toTry, int iSol, int iTry) { // toTry is ordered array of char left (not in completed dice). // If iSol == nCh, note solution, done. // IF iSol % SIDES == 0, set up next die search, set lowest char. // Otherwise try adding char toTry[iTry] to current die. if it works, // recurse and try further addition. // Also continue seaching for current die location, // if there are enough characters left. if (debug) showParam(toTry, iSol, iTry); // judge check if (nSol == MAXSOL) return; if (iSol == nCh) { // have solution String s = new String(sol); // insert blanks in sol for (int i = SIDES; i < nCh; i+= SIDES) System.out.print(s.substring(i-SIDES, i) + " "); System.out.println(s.substring(nCh-SIDES)); nSol++; // judge check return; } int solOffs = iSol % SIDES; // how far into current die if (solOffs == 0) { // start new die char[] newTry; if (iSol == 0) newTry = used.toCharArray(); else { // have a die done, another die to do newTry = new char[toTry.length - SIDES]; //extract latest die int sOffs = iSol - SIDES, iOffs = 0; for (char c: toTry) if (c == sol[sOffs]) sOffs++; else newTry[iOffs++] = c; } sol[iSol] = newTry[0]; // must start new die with least char makeDice(newTry, iSol+1, 1); sol[iSol] = (char)0; // undo completed change for later tests return; } // case where a second or later ch added to a die if (fits(iSol, toTry[iTry])) { // try to use current char sol[iSol] = toTry[iTry]; makeDice(toTry, iSol+1, iTry+1); sol[iSol] = (char)0; // undo completed change for later tests } iTry++; if (iTry + SIDES - solOffs <= toTry.length) // skip current char, go makeDice(toTry, iSol, iTry); // on, if enough left } static boolean fits(int iSol, char ch) { // true if ch compatible with previous characters on the latest die for (int i = iSol - iSol % SIDES; i < iSol; i++) if (sep[sol[i]][ch]) return false; return true; } ////////// rest for judges' testing /////////// static boolean debug = false; static int MAXSOL = 2, // require unique, check if more nSol, // number of solutions found - shound end as 1 dataSetsAllowed = 20; // problem limit static void judgeCheck() { nSol = 0; dataSetsAllowed--; if (dataSetsAllowed < 0) System.err.println("!!! Extra dataset"); for (String w: words) { if (w.indexOf(unused) >= 0) System.err.format("%s contains 'unused' %s%n", w, unused); if(w.length() != nDice) System.err.format("%s wrong length%n", w); } shln("used: " + used); int errDiff = SIDES*nDice - nCh; if(errDiff != 0) System.err.format("number of letters off: %d%n", errDiff); } static void judgeWrapup() { if (nSol != 1) System.err.format("!!! %d solutions", nSol); } static void showParam(char[] toTry, int iSol, int iTry) { if (toTry != null) shln(String.format("try: %s; iSol: %d; iTry: %d%nsol: %s%n", new String(toTry), iSol, iTry, new String(sol).replace((char)0, '-'))); } static void shln(String s) { show(s+'\n'); } static void show(String s) { if (debug) System.err.print(s); } }