843 - Crypt Kicker
Moderator: Board moderators
-
- Experienced poster
- Posts: 145
- Joined: Sat Feb 23, 2002 2:00 am
- Location: Paris, France
- Contact:
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.
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.
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.
843 How-to
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:
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 ?
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 ?
I solve 4 problems per day, then I expend 4 days stuck in a single problem. But I think I'm doing well... ID 37180
843 - Crypt Kicker; speeding it up
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]
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]
Java code wont compile
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]
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]
Compiler Error - Crypt Kicker Problem - Any Suggestions?
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]
My code passes on the Programming Challanges site but gets a compilier error here.
Could be the archaic version of Java on the server.
![:D](./images/smilies/icon_biggrin.gif)
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]
843 Crypt Kicker OMG
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?
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?
-
- Guru
- Posts: 834
- Joined: Wed May 29, 2002 4:11 pm
- Location: Wroclaw, Poland
- Contact:
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
Best regards
DM
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)
Born from ashes - restarting counter of problems (800+ solved problems)
For permutation:
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:
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?
I need to tryDictionary:
dog
cat
web
Encrypted String:
xyz abc pqr
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:
I need to tryDictionary:
dog
cat
web
boy
Encrypted String:
xyz abc
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?