UVa OJ Board

Code: Select all

#include <stdio.h>
#include <string.h>

typedef char word[17];
word dict[1001];
word words[100];
char line[81];
char linep[81];
char map[26], mapinv[26];
int at[17], count[17];
int n, i, j, len1, len2, letters_line;
int backtrack, nwords_line, solution;
char * cp;

int cmp(const void * x, const void * y)
{
    return (strlen((char *)x)-strlen((char *)y));
}

int count_letters(char * L)
{
    int l[26], c=0, k;
    char * cp = L;
    memset(l, 0, sizeof(int)*26);
    for(; *cp; cp++)
    {
        if(*cp == ' ') continue;
        l[*cp -'a']=1;
    }
    for(k=0;k<26;k++) if(l[k])c++;
    return c;
}

void print_stars()
{
    char * cp = linep;
    for(;*cp; cp++)
    {
        if(*cp == ' ') printf(" ");
        else printf("*");
    }
    printf("\n");
}

int is_solution(char * m, char * minv)
{
    int x = 0, y;
    for(y=0;y<26;y++)
    {
        if(!m[y]) continue;
        x++;
    }
    return x==letters_line;
}

void process_solution(char * m, char * minv)
{
    char * cp = linep;
    for(;*cp;cp++)
    {
        if(*cp == ' ') printf(" ");
        else printf("%c", minv[*cp-'a']);
    }
    printf("\n");
}

int done;
void search(int k, char * m, char * minv)
{
    char m_[26], minv_[26];
    int I, J, LEN;

    if(done || k>nwords_line+1) return;

    if(is_solution(m, minv))
    {
        process_solution(m, minv);
        done=solution=1;
    }
    else
    {
        LEN = strlen(words[k]);

        for(I=at[LEN];I<at[LEN]+count[LEN];I++)
        {
            memcpy(m_, m, 26*sizeof(char));
            memcpy(minv_, minv, 26*sizeof(char));
            backtrack = 0;
            for(J=0;J<LEN;J++)
            {
                if(!m_[dict[I][J]-'a'])
                {
                    m_[dict[I][J]-'a'] = words[k][J];
                    minv_[words[k][J]-'a'] = dict[I][J];
                }
                else if(m_[dict[I][J]-'a'] != words[k][J])
                {
                    backtrack=1; break;
                }
            }
            if(!backtrack) search(k+1, m_, minv_);
        }
    }
}

int empty(char * x)
{
    char * c = x;
    for(; *c; c++) if(*c != ' ' && *c != '\n') return 0;
    return 1;
}

int main()
{
    for(i = 0; i < 17; i++) { at[i] = 0; count[i] = 0; }

    scanf("%d\n", &n);

    for(i = 1; i <= n; i++) { scanf("%s\n", dict[i]); count[strlen(dict[i])]++; }

    qsort(dict+1, n, sizeof(word), cmp);

    len1 = strlen(dict[1]); at[len1] = 1;
    for(i = 2; i <= n; i++)
    {
        len2 = strlen(dict[i]);
        if(len1==len2) continue;
        at[len2] = i; len1 = len2;
    }

    while(fgets(line, 81, stdin))
    {
        if(empty(line)) continue;
        len1 = strlen(line);
        if(line[len1-1]=='\n') line[len1-1]='\0';
        done=solution=0;

        memset(map, 0, 26*sizeof(char));
        memset(mapinv, 0, 26*sizeof(char));

        letters_line = count_letters(line);

        strcpy(linep, line);
        nwords_line = 2;
        cp = strtok(line, " ");
        strcpy(words[1], cp);

        while((cp=strtok(0, " "))) strcpy(words[nwords_line++], cp);
        strcpy(words[nwords_line], "");
        nwords_line--;

        search(1, map, mapinv);
        if(!solution) print_stars();
    }
    return 0;
}

Code: Select all

int QW;
for(y=0;y<26;y++)
		for(QW=0;QW<26;QW++)
			if(QW != y && m[QW] != '\0' && m[y] != '\0' && m[QW] == m[y])
				return 0;

Code: Select all

1
and
zxc cxz

Code: Select all

and dna

Code: Select all

*** ***

Code: Select all

import java.util.*;

public class P843 {
    public static void main(String[] args) {
        Scanner c = new Scanner(System.in);
        int dictionarySize = c.nextInt();
        c.nextLine();

        // get the dictionary from the input stream:
        String[] words = new String[dictionarySize];
        for (int i = 0; i < words.length; i++)
            words[i] = c.nextLine();
        // get encrypted input
        String line = c.nextLine();
        while (c.hasNextLine() && line.trim().length() > 0) {
            String[] eWords = line.split(" ");
            String[] dWords = decryptWords(eWords, words);
            for (int i = 0; i < dWords.length; i++)
                if (i != dWords.length - 1) {
                    System.out.print(dWords[i] + " ");
                } else {
                    System.out.println(dWords[i]);
                }
            line = c.nextLine();
            if (line.trim().length() == 0)
                System.exit(0);
        }

    }

    private static String[] decryptWords(String[] eWords, String[] words) {

        String[] dWords = new String[eWords.length];
        
        // get copy of the dWords so that the original version not destroyed
        String[] eWordsCopy = Arrays.copyOf(eWords, eWords.length);
        // sort by length from the greatest to the smallest
        Arrays.sort(eWordsCopy, new Comparator<String>() {
            @Override
            public int compare(String w1, String w2) {
                return Integer.compare(w2.length(), w1.length());
            }
        });

        // initialize a key array to hold decrypted letters:
        char[][] keyArray = new char[2][26];
        for (int i = 0; i < 26; i++) {
            keyArray[0][i] = (char) ('a' + i);
            keyArray[1][i] = '*';
        }


        // restore keyArray original values if there is no solution to all words
        if (!matchWords(words, eWordsCopy, keyArray))
            for (int i = 0; i < 26; i++) {
                keyArray[0][i] = (char) ('a' + i);
                keyArray[1][i] = '*';
            }
        for (int i = 0; i < eWords.length; i++) {
            StringBuilder temp = new StringBuilder();
            for (int j = 0; j < eWords[i].length(); j++)
                temp.append(keyArray[1][eWords[i].charAt(j) - 97]);
            dWords[i] = temp.toString();
        }
        return dWords;
    }

    private static boolean matchWords(String[] words, String[] eWords, char[][] keyArray) {
        ArrayList<String> promisingWords = new ArrayList<>();
        String eWord = eWords[0];
        // this is an array of booleans to check whether a letter got updated. This array is useful in the backtracking 
        // step where we remove a word from the keyArray 
        boolean[] updatePattern = new boolean[eWord.length()];
        // get promising words that may match
        for (String word : words)
            if (word.length() == eWord.length()
                    && wordPattern(word).equals(wordPattern(eWord)))
                promisingWords.add(word);

        for (String word : promisingWords) {
            if (mapWord(eWord, word, keyArray, updatePattern)) {
                if (eWords.length > 1) {
                    // recursive call:
                    if (matchWords(words, Arrays.copyOfRange(eWords, 1, eWords.length), keyArray))
                        return true;
                    else {
                        // remove the word from the dictionary to try another one
                        for (int i = 0; i < eWord.length(); i++)
                            if (keyArray[1][eWord.charAt(i) - 97] == word.charAt(i) && updatePattern[i])
                                keyArray[1][eWord.charAt(i) - 97] = '*';
                    }
                }
                // if there are now decrypted words, then return true
                else
                    return true;
            }
        }
        // if there is no word mapped, then return false
        return false;
    }

    private static boolean mapWord(String eWord, String word, char[][] keyArray, boolean[] updatePattern) {
        // check one-to-one from the decrypted word to the dictionary word:
        for (int i = 0; i < eWord.length(); i++)
            if (keyArray[1][eWord.charAt(i) - 97] != word.charAt(i)
                    && keyArray[1][eWord.charAt(i) - 97] != '*')
                return false;
            
        // check the other way around    
        for(int i=0; i<word.length(); i++)
            if(!isLetterMapped(eWord.charAt(i), word.charAt(i), keyArray))
                return false;

        // update the key array:
        for(int i=0; i<eWord.length(); i++) {
            if (keyArray[1][eWord.charAt(i) - 97] == word.charAt(i))
                updatePattern[i] = false;
            else {
                keyArray[1][eWord.charAt(i) - 97] = word.charAt(i);
                updatePattern[i] = true;
            }
        }

//        System.out.println("eWord: " + eWord);
//        System.out.println("word: " + word);
//        System.out.println("this mapping is: " + isMapped);
//        if (isMapped)
//            for (char[] aKeyArray : keyArray) System.out.println(Arrays.toString(aKeyArray));
        return true;
    }

    private static boolean isLetterMapped(char eLetter, char letter, char[][] keyArray) {
        for (int i = 0; i < 26; i++)
            if (keyArray[1][i] == letter && keyArray[0][i] != eLetter)
                return false;
        return true;
    }

    // generate a word pattern
    private static String wordPattern(String word) {
        if (word.length() > 0) {
            StringBuilder mapped = new StringBuilder();
            int count = 0;
            HashMap<Character, Character> mapping = new HashMap<>();
            for (int i = 0; i < word.length(); i++)
                if (!mapping.containsKey(word.charAt(i)))
                    mapping.put(word.charAt(i), (char) (48 + count++));
            for (int i = 0; i < word.length(); i++)
                mapped.append(mapping.get(word.charAt(i)));
            return mapped.toString();
        } else {
            return "";
        }
    }
}