843 - Crypt Kicker

[hackfox]

I don't go through Onko's source code but I use the same method to Onko's. I *sort* the array and find if I compare words with long lenth first, then there are much less recursion than short length. Try sort when your think your speed is not good enoght. There are often miracles happen:)

[Zaspire]

In this problem I sort line (first goes more length words).
This action increace speed more then 1000%.

[Schultz]

I wrote the problem, ok. It works for every test I have tried but not for the one in the site. Can anybody check what is wrong with my code?

Code: Select all

/*
	------------
	ACM UVA 843
	Schultz
	
	Crypt Kicker
	------------
*/

/*	imports	*/
#include<stdio.h>
#include<string.h>

#include<vector>
#include<algorithm>
using namespace std;

/*	word list	*/
int	words;
char	W[128][32];
int	WL[128];

/*	blanks	*/
bool	isblank(char c) {return c == ' ' || c == '\t' || c == '\n';}
bool	isblank(char* str) {
	while (*str != '\0') {
		if (!isblank(*str)) return false;
		str++;
	}
	return true;
}

/*	reading word list	*/
void	read_words(char* str) {
	words = 0;
	for (;;) {
		while (isblank(*str)) str++;
		if (*str == '\0') break;
		
		sscanf(str, "%s", W[words]);
		WL[words] = strlen(W[words]);
		while (!isblank(*str)) str++;
		
		words++;
	}	
}

/*	matching words	*/
vector<int> M[128];

/*	match checks (word x dict)	*/
bool	match(char* A, int m, char* B, int n) {
	if (n != m) return false;
	else {
		static char M[32];
		for (int i = 0; i < 26; i++) M[i] = '*';
		
		for (int i = 0; i < n; i++) {
			if (M[A[i]-'a'] == '*' || M[A[i]-'a'] == B[i]) M[A[i]-'a'] = B[i];
			else return false;
		}
		return true;
	}
}

/*	dictionary	*/
int	dict;
char	D[1024][32];
int	DL[1024];

/*	reading dictionary	*/
void	read_dict() {
	scanf("%d", &dict);
	for (int i = 0; i < dict; i++) {scanf("%s", D[i]); DL[i] = strlen(D[i]);}
}

/*	making matches	*/
void	make_matches() {
	for (int i = 0; i < words; i++) {
		M[i].clear();
		for (int j = 0; j < dict; j++) if (match(W[i], WL[i], D[j], DL[j])) M[i].push_back(j);
	}
}

/*	schwarzian transform	*/
struct	schwartz {
	int word;
	
	bool operator <(schwartz const& s) const {return WL[word] > WL[s.word];}
	bool operator ==(schwartz const& s) const {return WL[word] == WL[s.word];}
};

schwartz	S[128];
int	R[128];

void	transform() {
	for (int i = 0; i < words; i++) S[i].word = i;
	sort(S, S+words);
	for (int i = 0; i < words; i++) R[S[i].word] = i;
}

/*	comparison (word x dict)	*/
bool	compare(char* A, int m, char* B, int n, char table[32]) {
	if (n != m) return false;
	else {	
		static char T[32];
		for (int i = 0; i < 26; i++) T[i] = table[i];
			
		for (int i = 0; i < n; i++) {
			if (T[A[i]-'a'] == '*' || T[A[i]-'a'] == B[i]) T[A[i]-'a'] = B[i];
			else return false;
		}
		for (int i = 0; i < 26; i++) table[i] = T[i];
		return true;
	}
}

/*	backtracking	*/
int	B[128];

bool	backtrack(int b, char table[32]) {
	if (b == words) return	true;
	else {
		char T[32], C[32];
		for (int i = 0; i < 26; i++) T[i] = C[i] = table[i];
		
		for (int i = 0; i < M[S[b].word].size(); i++) {
			if (compare(W[S[b].word], WL[S[b].word], D[M[S[b].word][i]], DL[M[S[b].word][i]], C)) {
				B[b] = M[S[b].word][i];
				if (backtrack(b+1, C))	return true;
				for (int i = 0; i < 26; i++) C[i] = T[i];
			}
		}
		
		return false;
	}
}

/*	main	*/
int	main() {

	read_dict();
	
	static char line[128];
	gets(line);
	while (fgets(line, 127, stdin)) {
		if (isblank(line)) {
			putchar('\n');
			continue;
		}
		
		read_words(line);
		transform();
		make_matches();
		
		static char table[32];
		for (int i = 0; i < 26; i++) table[i] = '*';
		
		if (backtrack(0, table)) {
			for (int i = 0; i < words; i++) printf("%s%c", D[B[R[i]]], i < words-1 ? ' ' : '\n');
		}
		else {
			for (int i = 0; i < words; i++) {
				for (int j = 0; j < WL[i]; j++) putchar('*');
				putchar(i < words-1 ? ' ' : '\n');
			}
		}
	}
		
	return	0;
}

Thanks in advance.[/code]

[Schultz]

Ah, the decoding function. Must it be injective?

[andysoft]

Hey!
I really don't understand the reason of my WRONG ANSWER...
I coded my solution both in C++ and Pascal and it fails at ~0.110 sec.

My solution is backtracking with optimizations. It passes the big test from Waterloo within 1 second, so it is time-efficient.

I think the reason is in empty-lines handling. Can you advice me something about reading input and about empty lines and outputting "\n" (empty lines) to the problem output... Any info would be great.

THANK YOU!

I don't think it may help, but here is my code:

Code: Select all

program uva843;
{$B-}{$R-}{$S-}{$Q-}
type
    stringArray = array [1..1000] of string;
    cryptArray = array [char] of char;
var
    words,sent: stringArray;
    crypt: cryptArray;
    foundSolution: boolean;
    i,n,sentn: integer;
    s,t,inp: string;

procedure slowsort (var a: stringArray; const n: integer);
var
    i,j: integer;
    t: string;
begin
    for i:=1 to n-1 do
        for j:=i+1 to n do
            if length(a[j])>length(a[i]) then
            begin
                t := a[j];
                a[j] := a[i];
                a[i] := t
            end;
end;

procedure clearCrypt;
var
    c: char;
begin
    for c:=#0 to #255 do
        crypt[c] := #0;
end;

function nextWord (var s: string): string;
var
    i,j: integer;
begin
    while (length(s)>0) and (s[1]=' ') do delete(s,1,1);
    j := pos(' ',s);
    if j<1 then j := length(s)+1;
    nextWord := copy(s,1,j-1);
    delete (s,1,j-1);
end;

procedure backtrack (index: integer);
var
    i,j: integer;
    could: boolean;
    cryptStack: cryptArray;
begin
    if foundSolution then exit;
    if index>sentn then
    begin
        foundSolution := true;
        for i:=1 to length(inp) do
            if inp[i]=' ' then
                write (' ')
            else
                write (crypt[inp[i]]);
        writeln; //REALLY ??
        exit;
    end;

    for i:=1 to n do
    begin
        if length(words[i])>length(sent[index]) then continue;
        if length(words[i])<length(sent[index]) then break;

        cryptStack := crypt;
        could := true;
        for j:=1 to length(words[i]) do
        begin
            if (crypt[sent[index][j]]=#0) or (crypt[sent[index][j]]=words[i][j]) then
                crypt[sent[index][j]] := words[i][j]
            else
            begin
                could := false;
                break
            end;
        end;
        if could then
            backtrack(index+1);
        crypt := cryptStack;

    end;


end;

begin

    readln (n);

    for i:=1 to n do
        readln (words[i]);

    while not eof do
    begin
        sentn := 0;

        readln (s);
        inp := s;
        while true do
        begin
            t := nextWord(s);
            if t='' then break;
            inc (sentn);
            sent[sentn] := t;
        end;

        slowsort(words,n);
        slowsort(sent,sentn);

        clearCrypt;
        foundSolution := false;

        backtrack (1);

        if not foundSolution then
        begin
            for i:=1 to length(inp) do
                if inp[i]=' ' then
                    write (' ')
                else
                    write ('*');
            writeln
        end;

    end;

end.

[andysoft]

oh, and also a question.
for example if we have line of input like this:
__crhhi___
(where "_" stands for usual space)
should we output:
__hello___
or just
hello

thank you!!

or if you don't want to waste your time on explaining to me, you can send your working .exe or maybe source code to my andysoft@tut.by e-mail, because my number of wrong submissions is getting really high.

[Lars Magnus]

hi, I got very WA, but I'm sure that my code is right, because I even tested with the testcase that bluebird put here and the answer of my program was right.
But I don't have any idea why I got WA.
Could you help me ?

Code: Select all

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

using namespace std;

typedef struct No{
	No* next;
	string source;
	string word;
	bool marked;
	int size;
}* NoPtr;

void insert(NoPtr &list,string word,int size);

int main(){
	NoPtr dictionary=NULL,aux=NULL;
	int count;
	string word,pieces,result,asterisk,alphabet[26],temp;
	bool init,found;
	bool confirmed[26];
	scanf("%d",&count);
	for (int i=0;i<count;i++){
		cin>>word;
		insert(dictionary,word,word.length());
	}
	for (int i=0;i<26;i++){
		alphabet[i]="0";
		confirmed[i]=false;
	}
	getline(cin,word);
	while(getline(cin,word)){
		stringstream buffer(word);
		result="";
		init=false;
		while(buffer>>pieces){
			found=false;
			asterisk="";
			if (init)
				result+=" ";
				
			for (int i=0;i<pieces.length();i++)
				asterisk+="*";
				
			aux=dictionary;
			int k=0;
			while(aux!=NULL){
				count=0;
				temp="";
				if (pieces.length()==aux->word.length()){
					if (aux->marked==true){
						if (aux->source.compare(pieces)==0){
							temp+=aux->word;
							found=true;
							break;
						}
					}
					else{
						for(int i=0;i<pieces.length();i++){
							string str=aux->word;
							string p=pieces;
							p=p[i];
							if (alphabet[str[i]-97].compare("0")==0){
								temp+=str[i];
								alphabet[str[i]-97]=pieces[i];
								count++;
							}
							else if ((alphabet[str[i]-97]).compare(p)==0){
								temp+=str[i];
								count++;
							}
						}
						if (count==pieces.length()){
							for (int i=0;i<pieces.length();i++){
								string str=aux->word;
								alphabet[str[i]-97]=pieces[i];
								confirmed[str[i]-97]=true;
							}
							aux->source=pieces;
							aux->marked=true;
							found=true;
							break;
						}
						else{
							for (int i=0;i<pieces.length();i++){
								string str=aux->word;
								if (confirmed[str[i]-97]==false)
									alphabet[str[i]-97]="0";
							}
						}
						
					}
					
				}
				aux=aux->next;
			}
			if (found)
				result+=temp;
			else
				result+=asterisk;
			init=true;
		}
		
	      cout<<result<<endl;

		
		
	}
	return 0;
}

void insert(NoPtr &list,string word,int size){
	NoPtr atual=list,ant=NULL;
	NoPtr aux;
	while(atual!=NULL){
		ant=atual;
		atual=atual->next;
	}
	aux=new No;
	aux->size=size;
	aux->source="0";
	aux->word=word;
	aux->next=NULL;
	aux->marked=false;
	
	if(ant!=NULL)
		ant->next=aux;
	else
		list=aux;
		
	return;
}

[psychic]

Hi all!
I get RTE even though my code runs the example case test fine.
I browsed this thread and only noticed one link to test cases which doesn't work anymore.
Could anyone point me to some test cases that I can run my code on?

Big thanks for any help, as I've been breaking my head on this.

[ajeet.singh82]

Hi All

Can anybody clarify my doubt about the decoding of below lines -
6
and
dick
jane
puff
spot
yertle
bjvg xsb hxsn xsb qymm xsb rqat xsb pnetfn
xxsb xsb zzsz www yyyy aaa bbbb ccc dddssd

According to uvatoolkit the output are as follows -

dick and jane and puff and spot and yertle
**** *** **** *** **** *** **** *** ******

But according to my understanding the red line can be decoded as -
aand and **n* *** **** *** dddd *** ***nn*

It is possible to decode xsb in the second line since there is only and only one three letter analogous word in dictionary so it has to be and. Now since we know the mapping x->a, s->n, b->d we can decode these letter of line wherever they occur.

But according to uvatoolkit it shouldn't be decoded, what is the judge requirement?

Even if I presume that all the decoded word must belong to dictionary even then output should be -

**** and **** *** **** *** **** *** ******

But which is not , Please clarify me with your understanding.

-A

[ajeet.singh82]

Here is what Carlos clarifies -

"If there is no solution, replace every letter of the alphabet by an asterisk."

It's not that those particular words can't be decoded, it's that we're
only interested in the whole sentence. If it's not possible, then we
don't want anything at all.

See you!
Carlos.


Makes the problem even more simpler
Thanks,

[Yusif]

I'm getting tl.
I classify the input by length and number of repeated letters and sort the dictionary accordingly
then do a complete search.

Is this algorithm inefficient or my implementation poor?

Code: Select all

#include <iostream>
#include <stdio.h>
#include <vector>
#include <string>
#include <algorithm>
#include <bitset>
using namespace std;

struct word{
	string s;
	int clas;
};
bool operator<(const word &a, const word &b){
	return a.clas<b.clas;
}
bool operator==(const word &a, const word &b){
	return a.clas==b.clas;
}

typedef vector <word> vw;
typedef vector <char> vc;

word dic[1010];
int n;
bool found;
vc cryptab(26);

bool apps (vc &tab2, word &liner, word &dicter){
	int nn=liner.s.size();
	for (int i=0; i<nn; ++i){
		if (tab2[liner.s[i]-'a']==0){
			tab2[liner.s[i]-'a']=dicter.s[i];
		}
		else if(tab2[liner.s[i]-'a']!=dicter.s[i]){
			return false;
		}
	}
	return true;
}

void decryp (vw &line, int ci, int lsize, vc table ){
	if (found) return;
	vc tab2(26);
	
	int i= lower_bound(dic, dic+n, line[ci]) - dic;
	while (line[ci]==dic[i]){
		tab2=table;
		if (apps(tab2, line[ci], dic[i])){
			if (ci==lsize-1){
				cryptab=tab2;
				found=true;
				return;
			}
			else{
				decryp(line, ci+1, lsize, tab2);
			}
		}
		
		++i;
	}
}

int main(){
	bitset <'z'+5> rep;
	int ssize;
	cin>>n;
	for (int i=0; i<n; ++i){
		cin>>dic[i].s;
		dic[i].clas=dic[i].s.size();
		rep.reset();
		ssize=dic[i].clas;
		dic[i].clas*=100;
		for (int j=0; j<ssize; ++j){
			if (rep[dic[i].s[j]]){
				++dic[i].clas;
			}
			else{
				rep.set(dic[i].s[j]);
			}
		}
	}
		
	sort(dic, dic+n);
	
	word temp;
	while (cin>>temp.s){
		temp.clas=temp.s.size();
		rep.reset();
		ssize=temp.clas;
		temp.clas*=100;
		for (int i=0; i<ssize; ++i){
			if (rep[temp.s[i]]){
				++temp.clas;
			}
			else{
				rep[temp.s[i]]=1;
			}
		}
		
		
		vw line;
		line.push_back(temp);
		while (true){
			while (cin.peek()==' ') getchar();
			if (cin.peek()=='\n') break;
			cin>>temp.s;
			temp.clas=temp.s.size();
			rep.reset();
			ssize=temp.clas;
			temp.clas*=100;
			for (int i=0; i<ssize; ++i){
				if (rep[temp.s[i]]){
					++temp.clas;
				}
				else{
					rep[temp.s[i]]=1;
				}
			}
			line.push_back(temp);
		}
		
		int lsize=line.size();
		vc table(26);
		fill(table.begin(), table.end(), 0);
		found=false;
		decryp (line, 0, lsize,  table );
		if (found){
			for (int i=0; i<lsize; ++i){
				int ss=line[i].s.size();
				for (int j=0; j<ss; ++j){
					printf("%c", cryptab[line[i].s[j]-'a']);
				}
				if (i<lsize-1) printf(" ");
			}
			printf("\n");
		}
		else {
			for (int i=0; i<lsize; ++i){
				int ss=line[i].s.size();
				for (int j=0; j<ss; ++j){
					printf("*");
				}
				if (i<lsize-1) printf(" ");
			}
			printf("\n");
		}
	}
	return 0;
}

[brianfry713]

I got AC in 0.062 sec using recursive backtracking. My function takes a position in the encrypted line, an array of what each letter that has been decrypted maps to, and an array of which decrypted letters have been mapped to.

I try every dictionary word of the same size as the current encrypted word to see if each letter in the encrypted word has not already been decrypted to a different letter then in that dictionary word. Also check that two encrypted letters don't map to the same decrypted letter.

[Yusif]

I guess I did the same at first, but I got tl
then I changed it slightly; I traverse through every input word in order to prune the search space

[brianfry713]

Try changing your input parsing. If the last line has a word, a space, and then no newline before EOF, your code gets stuck.

[Yusif]

According to a friend I'd been assuming that EOF is always preceded by a newline, thanks for mentioning that!
However it is still TL after fixing that.