OJ Board

I haven't done equivalency classes, but I honestly don't see how they would help out much with my method. If you have 1000 words all of the same length and that have no repeated letters, and then a sentence of 10-15 words, you still have to check each dictionary word with each sentence word.

How do you do the search?

Well, when you say you compare with words having the same length, that IS equivalence classes. Of course, it depends how it is implemented : if you browse sequentially, that's awfully long.
Maybe using vectors (already avalaible in c++), or better, maps with the length, and then storing in it maps with the number of repeated letters, that might really help, I guess.
And I think that the case where you don't have any repeated letters is rare enough to still gain time by using that sort of equivalence class.

Ok, I was just talking about equivalency classes when it came to letter placement, not length. I can see how to improve my recursive function to a best time using this, but it will still time out on a case with lots of words of same length that have the same letter layout. And I don't want to spend my time writing all that in the hopes that the judge doesn't use an example like that to test it.

Larry to answer your question, I have an array of vectors each containing words that are all the same length - maps like what Julien said would be equivalent. Then the recursive function just checks the words sequentially from the vector that contains the words of the same length, moving forward to the next word in the sentence if the word doesn't contradict, on to the next word in the vector if it does contradict, and backwards if all the words in the vector contradict.

Hi,

I have a TLE too, and solve it deleting of my word's list repeated words.
Be careful with blank lines too...

Best regards,

Sebasti

That's what I do, and I get AC.. (the DFS..).. maybe you should use a simpler data structure ...?

Is it possible that there are repeated words in the dictionary?

I have lost some days trying to solve this problem. My code had minor errors, but I got trapped with the problem description, which in my opinion is far away from perfect. Now that I got AC, I decided to share my experience and alert others.

The problem description states:

A common but insecure method of encrypting text is to permute the letters of the alphabet. That is, in the text, each letter of the alphabet is consistently replaced by some other letter. So as to ensure that the encryption is reversible, no two letters are replaced by the same letter.

This means that an encoded text "zzz" should not be decoded as a dictionary word "abc", for example.

But now note that the problem does NOT state the opposite. The reader can think that an encoded text word "abc" CAN be decoded as a dictionary word "zzz", if there was one. This consideration does not make the code more complex, but makes it extremely slower. If you made this consideration, this is why you got TLE.

The description said that a text with T different letters should not be decoded using more than T different letters. This means the encoded text letters relate with dictionary letters in N to 1.
But, in fact, you should consider that the dictionary letters have a 1 to 1 relationship with the encoded text letters. This makes your program extremely faster.

In my case I just had to remove the "//" in the code below:
[cpp]if (Decode[TextC] != UNDEFINED && Decode[TextC] != DicC) break;
//if (Encode[DicC] != UNDEFINED && Encode[DicC] != TextC) break;[/cpp]

Any questions ?

Hello, I have tried to solve the Crypt Kicker using recursion, but I get TLE on inputs with number of dictionary words close to 1000 and lines that cannot be decoded, since it takes a lot of time to go through all the words. I've put the dictionary words in an array of ArrayLists based on word length. Could someone please give me a hint how to speed it up? Thank you.
Ondrej

[java]
import java.io.*;
import java.util.*;

class crypt {

public static void main (String[] args) {
crypt m = new crypt();
m.go();
}

// stores the answer
String ans = "";

void go()
{
try
{
BufferedReader in = new BufferedReader(new FileReader("d:\\java\\pc\\test.txt"));
int n = Integer.parseInt(in.readLine());
ArrayList[] words = new ArrayList[17];
for (int i = 0; i < words.length; i++)
words = new ArrayList();
for (int i = 0; i < n; i++)
{
// sort the dictionary words according to their length
String word = in.readLine();
if (!words[word.length()].contains(word))
words[word.length()].add(word);
}
String input = in.readLine();
while (input != null)
{
String[] code = split(input);
decode("", 0, 0, "", "", code, words);
System.out.println(ans);
ans = "";
input = in.readLine();
}
}
catch (IOException e)
{
System.out.println(e.toString());
}
}

// alfa1 and alfa2 store the found words; j is an index of a word in dictionary words, k is an index of a word in the sentence
void decode(String answer, int j, int k, String alfa1, String alfa2, String[] code, ArrayList[] words)
{
if (k == code.length)
{
// return the answer if end of the sentence
ans = answer.trim();
return;
}
if (k == 0 && j == words[code[k].length()].size())
{
// return stars if no solution
if (ans != "") return;
for (int m = 0; m < code.length; m++)
{
for (int n = 0; n < code[m].length(); n++)
ans += "*";
ans += " ";
}
ans = ans.trim();
return;
}
if (j == words[code[k].length()].size())
// go back to previous word in sentence if no match found for current word
return;

String temp1 = "";
String temp2 = "";
boolean finish = true;
for (int m = 0; m < code[k].length() && finish; m++)
{
// check matching of the structures of a word from dictionary and a word from the sentence
int ind1 = temp1.indexOf(code[k].charAt(m));
int ind2 = temp2.indexOf(((String)words[code[k].length()].get(j)).charAt(m));
if (ind1 == ind2)
{
temp1 += code[k].charAt(m);
temp2 += ((String)words[code[k].length()].get(j)).charAt(m);
}
else
finish = false;
}
if (finish)
{
// if structures match check if letters match with previously found words
for (int n = 0; n < code[k].length(); n++)
if (alfa1.indexOf(code[k].charAt(n)) != alfa2.indexOf(((String)words[code[k].length()].get(j)).charAt(n)))
{
finish = false;
break;
}
}
if (finish)
// if dictionary word fits move on to the next word in sentence
decode(answer + " " + (String)words[code[k].length()].get(j), 0, k + 1, alfa1 + temp1, alfa2 + temp2, code, words);
if (ans == "")
// if answer still not found move on to the next dictionary word
decode(answer, j + 1, k, alfa1, alfa2, code, words);
return;
}

String[] split(String s)
{
StringTokenizer st = new StringTokenizer(s);
String[] ret = new String[st.countTokens()];
for (int i = 0; st.hasMoreElements(); i++)
ret = st.nextToken();
return ret;
}
}[/java]

Hi,

My Java code wont compile can anyone help?
It compiles and passes on the programming challenges site.

Problem is 843 Crypt Kicker.

Code Follows:

[java]


import java.io.*;
import java.util.*;

class Main {

static boolean finished = false, solutionFound = false;
static String[] dictionary, dicFormat, encFormat;
static StringTokenizer stk;
static String encryptLine;
static String[] solution = null;
static String[] encryptWords = null;
static char[]transArrEnc;
static char[] transArrCand;

public static void main(String [] args){

// long start = System.currentTimeMillis();

Main myProg = new Main();
myProg.loadDictionary();

//Loop till EOF processing encrypted lines and outputing solution.
encryptLine = Main.readln(85);
while(encryptLine != null){

stk = new StringTokenizer(encryptLine);

while(stk.hasMoreTokens()){

word = (stk.nextToken().trim());
encryptWords[a]= word;

for(int loop=0; loop<word.length(); loop++){
word = word.replace( word.charAt(loop), (char)(loop+65) );
}//for
encFormat[a] = word;
a++;
}//while

//Pass in partial solution String Array, current location to be filled,
//total solution length.
finished = false;
solutionFound = false;
myProg.backTrack(solution, 0, solution.length-1);


encryptLine = Main.readln(256);

// if(encryptLine != null)
System.out.println();
}//while.

// long end = System.currentTimeMillis();
// System.out.println("\nTime: "+( (end-start)/1000.0)+" Seconds");
}//main.

void backTrack(String[] solution, int currentElement, int solutionLength){

String [] candidates = new String[dictionary.length];
Integer nextCandidatePos = new Integer(0);

if (isASolution(solution, currentElement, solutionLength)){
processSolution(solution, currentElement, solutionLength);
}else{
currentElement++;
nextCandidatePos = constructCandidates(solution, currentElement, solutionLength, candidates, nextCandidatePos);

for(int count =0; count<nextCandidatePos.intValue(); count++){
solution[currentElement] = candidates[count];

backTrack(solution, currentElement, solutionLength);

if (finished){
return;
}//if

}//for

}//else

}//Begin

Integer constructCandidates(String[] solution, int currentElement, int solutionLength, String[] candidates, Integer nextCandidatePos){

int index = 0;
int nCandPos = 0;
boolean translationOk = true;
transArrEnc = new char[123];
transArrCand = new char[123];


if(!translationOk){

continue;
}
//Add dictionary word to candidate list.
// System.out.println("new Cand = "+dictionary[count]);
candidates[nCandPos]= dictionary[count];
nCandPos++;


}//for

return new Integer(nCandPos);
}//construct

boolean isASolution(String[] solution, int currentElement, int solutionLength){
return (currentElement == solutionLength);
}//isASolution

void processSolution(String[] solution, int currentElement, int solutionLength){
finished = true;
solutionFound = true;
if ( solution.length != 1 ){
for(int loop=1; loop<=currentElement; loop++){
if (loop != currentElement){
System.out.print(solution[loop]+" ");
}else{
System.out.print(solution[loop]);
}
}//for
}//if
}//process

void loadDictionary(){

int count = 0;


//Get Dictionary.
while(count < wordNum){

word = (readln(18).trim());
if (count != 0 && word == dictionary[count-1] )
continue;


dictionary[count] = word;


count++;
}//while.

}//loadDic.

static String readln (int LEN)
{
byte lin[] = new byte [LEN];
int lg = 0, car = -1;
String line = "";

try {
while (lg < LEN)
{
car = System.in.read();
if ((car < 0) || (car == '\n')) break;
lin [lg++] += car;
}
} catch (IOException e){
return (null);
}
if ((car < 0) && (lg == 0)) return (null);
return (new String (lin, 0, lg));
}//ReadLn
}//Main.



[/java]

what is the compile error you get? You can see this in your e-mail.

If you don't receive an e-mail for every solution you send in, change your preferences or user options or something like that...

Hi,

My code passes on the Programming Challanges site but gets a compilier error here.
Could be the archaic version of Java on the server.

Here are the compiler error messages:

03092288_24.java: In class `Main':
03092288_24.java: In method `backTrack(java.lang.String[],int,int)':
03092288_24.java:73: Internal compiler error in `expand_expr', at expr.c:5844
Please submit a full bug report.
See <URL:http://www.gnu.org/software/gcc/bugs.html> for instructions.

Heres the BackTrack method:



[java]
void backTrack(String[] solution, int currentElement, int solutionLength){

String [] candidates = new String[dictionary.length];
Integer nextCandidatePos = new Integer(0);

if (isASolution(solution, currentElement, solutionLength)){
processSolution(solution, currentElement, solutionLength);
}else{
currentElement++;
nextCandidatePos = constructCandidates(solution, currentElement, solutionLength, candidates, nextCandidatePos);

for(int count =0; count<nextCandidatePos.intValue(); count++){
solution[currentElement] = candidates[count];

backTrack(solution, currentElement, solutionLength);

if (finished){
return;
}//if

}//for

}//else

}//Begin
[/java]

How did anyone solve something like this in less than 3 hours??

After coding and re-coding for some time I finally managed to write a C++ program that accepts the test cases from

http://plg.uwaterloo.ca/~acm00/S98-1/

But it takes about 15 MINUTES. My design is backtracking, so my code should be more or less the same as those who got AC in the previous posts. Is there a way to make my code faster?

I used the next_permuation function in STL, which is linear time. For combinations (i.e. when the # of encrypted words of length x is less than the # of dictionary words of length x) I used a boolean array, where T means a word is chosen. I then use next_permutation on the array to get different combinations. Is this method naive? Is there a better way?

I am new to UVa, so I am starting to feel overwhelmed whenever I see similar combination/permuation problems (e.g. Yahtzee, doublets etc.).

Can someone smart please point me in the right direction?

I used backtracking too (got Acc), but I can't understand, why do you use permutations ? In my opinion it isn't neccessary...

Best regards
DM

For permutation:

Dictionary:
dog
cat
web

Encrypted String:
xyz abc pqr

I need to try
dog->xyz cat->abc web->pqr
dog->xyz web->abc cat->pqr
cat->xyz web->abc dog->pqr
etc.. (so I need to permutate the dictionary words)

For combination:

Dictionary:
dog
cat
web
boy

Encrypted String:
xyz abc

I need to try
dog-> xyz cat->abc
cat->xyz web->abc
web->xyz boy->abc
etc.. (and for each combination I do a permutation e.g. for web->xyz boy->abc, I also try boy->xyz, web->abc)

Am I missing something important?