843 - Crypt Kicker

All about problems in Volume 8. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 843 - Crypt Kicker

Post by brianfry713 » Wed Aug 14, 2013 11:57 pm

Yes usually there is a newline right before EOF but I wouldn't count on it.

Try simplifying your code as I described before. Also try changing your input parsing to just use C I/O. I only used scanf, getchar, gets, and printf in my AC code, no cin.
Check input and AC output for thousands of problems on uDebug!

saadtaame
New poster
Posts: 2
Joined: Tue Oct 29, 2013 1:32 pm

Crypt Kicker Judging Problem

Post by saadtaame » Tue Oct 29, 2013 1:53 pm

Is the judge misjudging the problem crypt kicker, i've tested my solution over and over but the judge keeps telling me its wrong, I even copied a correct solution and submitted it but still wrong answer. Here is my solution. If you can test my solution or find a problem with it please do.

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;
}

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: Crypt Kicker Judging Problem

Post by brianfry713 » Tue Oct 29, 2013 10:18 pm

On problem 843, if there is a blank line in the output, my AC code would print that line and any spaces it had to the output.
Check input and AC output for thousands of problems on uDebug!

saadtaame
New poster
Posts: 2
Joined: Tue Oct 29, 2013 1:32 pm

Re: Crypt Kicker Judging Problem

Post by saadtaame » Wed Oct 30, 2013 10:46 pm

I figured out the problem. I was using the globals map, mapinv where I should have been using the locals m_, minv_ in the funciton search. It got accepted.

fresher96
New poster
Posts: 25
Joined: Wed Sep 03, 2014 8:50 am

Crypt Kicker :Mis_Judging

Post by fresher96 » Tue Sep 30, 2014 5:31 pm

Mr.
saadtaame
you ignored part of the problem description it says
To ensure that the encryption is reversible, no two letters are
replaced by the same letter.
adding this to your "is_solution()" function you would get AC

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;

Master
brianfry713
i think there is another problem with the judge
for the program written by
saadtaame
after fixing
the judge accepted it but it's wrong try the input

Code: Select all

1
and
zxc cxz
the previous program prints

Code: Select all

and dna
but it's wrong because "dna" isn't mentioned in the dictionary
and the output should be

Code: Select all

*** ***
you can check it in your http://www.udebug.com/UVa/843

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 843 - Crypt Kicker

Post by brianfry713 » Tue Sep 30, 2014 9:19 pm

I don't have access to the judge's I/O.

If the judge accepts wrong code it doesn't really mean that there is a problem with it, just that it doesn't test that case.
Check input and AC output for thousands of problems on uDebug!

Maged_Saeed
New poster
Posts: 1
Joined: Sat Aug 18, 2018 7:54 pm

Re: 843 - Crypt Kicker

Post by Maged_Saeed » Sun Aug 19, 2018 12:45 pm

Hi everyone
I am really stuck in this problem. I did a Java solution for it. The code seems non erroneous passing the test cases proposed by uDebug site. However, I got WA verdict on the uva. Can anyone identify the problem in the code?
Here is the code:

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 "";
        }
    }
}

Post Reply

Return to “Volume 8 (800-899)”