Page 5 of 6
Re: 429 - Word Transformation
Posted: Thu Sep 25, 2014 5:05 pm
by sreka11
Can you please see my code and tell me why I am getting Runtime Error ?
Code: Select all
import java.util.*;
import java.io.*;
class Main
{
static TreeMap<String, Integer> map;
static Vector<Vector<Integer>> vect;
static int[] dist;
static Vector<String> names;
static Queue<Integer> q;
public static void main(String[] args) throws IOException
{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));
StringBuffer str = new StringBuffer();
String line = br.readLine();
line = br.readLine();
line = br.readLine();
while(line != null)
{
names = new Vector<String>();
map = new TreeMap<String, Integer>();
line = br.readLine();
int c = 0;
while(!line.equals("*"))
{
names.add(line);
map.put(line, c);
c++;
line = br.readLine();
}
int n = map.size();
vect = new Vector<Vector<Integer>>(n);
for(int j = 0; j < n; j++)
{
Vector<Integer> v = new Vector<Integer>();
vect.add(v);
}
for(int j = 0; j < n; j++)
{
for(int k = j+1; k < n; k++)
{
String s1 = names.get(j);
String s2 = names.get(k);
int d = dist(s1,s2);
if(d == 1)
{
vect.get(map.get(s1)).add(map.get(s2));
vect.get(map.get(s2)).add(map.get(s1));
}
}
}
String[] total = br.readLine().split(" ");
int src;
int d;
while(true)
{
src = map.get(total[0]);
d = map.get(total[1]);
dist = new int[n];
Arrays.fill(dist, -1);
dist[src] = 0;
q = new LinkedList<Integer>();
q.add(src);
boolean check = false;
while(!q.isEmpty())
{
int v = q.poll();
Iterator it = vect.get(v).iterator();
while(it.hasNext())
{
int u = (int)it.next();
if(dist[u] == -1 && u == d)
{
dist[u] = dist[v] + 1;
check = true;
break;
}
else if(dist[u] == -1)
{
dist[u] = dist[v] + 1;
q.add(u);
}
}
if(check)
break;
}
str.append(total[0] + " " + total[1] + " " + dist[d] + "\n");
line = br.readLine();
if(line == null)
break;
else if(line.length() == 0)
break;
else
total = line.split(" ");
}
str.append("\n");
if(line == null)
break;
}
str.deleteCharAt(str.length()-1);
out.write(str.toString());
out.flush();
}
public static int dist(String s1, String s2)
{
if(s1.length() != s2.length())
return -1;
else
{
int d = 0;
for(int i = 0; i < s1.length(); i++)
{
if(s1.charAt(i) != s2.charAt(i))
{
d++;
}
}
return d;
}
}
}
Re: 429 - Word Transformation
Posted: Thu Sep 25, 2014 10:45 pm
by brianfry713
Instead of filling up a StringBuffer with all of the output try writing directly to the BufferedWriter or at least between test cases.
Re: 429 - Word Transformation
Posted: Thu Sep 25, 2014 11:16 pm
by sreka11
Still Runtime Error, even if did what you suggested
Code: Select all
import java.util.*;
import java.io.*;
class Main
{
static TreeMap<String, Integer> map;
static Vector<Vector<Integer>> vect;
static int[] dist;
static Vector<String> names;
static Queue<Integer> q;
public static void main(String[] args) throws IOException
{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));
String line = br.readLine();
line = br.readLine();
line = br.readLine();
while(line != null)
{
names = new Vector<String>();
map = new TreeMap<String, Integer>();
line = br.readLine();
int c = 0;
while(!line.equals("*"))
{
names.add(line);
map.put(line, c);
c++;
line = br.readLine();
}
int n = map.size();
vect = new Vector<Vector<Integer>>(n);
for(int j = 0; j < n; j++)
{
Vector<Integer> v = new Vector<Integer>();
vect.add(v);
}
for(int j = 0; j < n; j++)
{
for(int k = j+1; k < n; k++)
{
String s1 = names.get(j);
String s2 = names.get(k);
int d = dist(s1,s2);
if(d == 1)
{
vect.get(map.get(s1)).add(map.get(s2));
vect.get(map.get(s2)).add(map.get(s1));
}
}
}
String[] total = br.readLine().split(" ");
int src;
int d;
while(true)
{
src = map.get(total[0]);
d = map.get(total[1]);
dist = new int[n];
Arrays.fill(dist, -1);
dist[src] = 0;
q = new LinkedList<Integer>();
q.add(src);
boolean check = false;
while(!q.isEmpty())
{
int v = q.poll();
Iterator it = vect.get(v).iterator();
while(it.hasNext())
{
int u = (int)it.next();
if(dist[u] == -1 && u == d)
{
dist[u] = dist[v] + 1;
check = true;
break;
}
else if(dist[u] == -1)
{
dist[u] = dist[v] + 1;
q.add(u);
}
}
if(check)
break;
}
out.write(total[0] + " " + total[1] + " " + dist[d] + "\n");
line = br.readLine();
if(line == null)
break;
else if(line.length() == 0)
break;
else
total = line.split(" ");
}
out.write("\n");
if(line == null)
break;
}
out.flush();
}
public static int dist(String s1, String s2)
{
if(s1.length() != s2.length())
return -1;
else
{
int d = 0;
for(int i = 0; i < s1.length(); i++)
{
if(s1.charAt(i) != s2.charAt(i))
{
d++;
}
}
return d;
}
}
}
Re: 429 - Word Transformation
Posted: Fri Oct 03, 2014 1:30 am
by brianfry713
The first line of the input is an integer N, indicating the number of test set that your correct program should test.
Re: 429 - Word Transformation
Posted: Sun Nov 23, 2014 8:10 pm
by mhsn06
Just for future newbie:
You can handle the last part input like below in c or c++ only
Code: Select all
char s[40], *s1, *s2;
while(gets(s) && strlen(s)){
s1 = strtok(s, " ");
s2 = strtok(NULL, " ");
// do whatever need to do
}
Re: 429 - Word Transformation
Posted: Fri Dec 26, 2014 12:08 pm
by messiNayan
Please Somebody help me.I am getting timelimit exit.
Code: Select all
#define _CRT_SECURE_NO_WARNINGS
#define MAX 200
#include<stdio.h>
#include<string.h>
#include<iostream>
#include<utility>
#include<vector>
#include<queue>
using namespace std;
int bfs(int source, int destinition, vector<int> map[]);
bool oneDiff(char *a, char * b);
int find(char *word, char book[][11]);
int main(void)
{
//freopen("in.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
int caseNo = 0;
int t,i;
vector<int> map[MAX];
char pair[25];
char source[11], dest[11];
char dictionary[200][11];
char blank[10];
scanf("%d",&t);
gets(blank);
gets(blank);
while (t--)
{
if (caseNo)
printf("\n");
memset(map, 0, sizeof(map));
memset(dictionary,0,sizeof(dictionary));
i = 0;
while (1)
{
scanf("%s",dictionary[i]);
if (!strcmp(dictionary[i], "*"))
break;
i++;
}
gets(blank);
for (int p = 0; p < i; p++)
{
for (int q = 0; q < i; q++)
{
if (p != q && oneDiff(dictionary[p], dictionary[q]))
{
map[p].push_back(q);
map[q].push_back(p);
}
}
}
while (1)
{
memset(source, 0, sizeof(source));
memset(dest,0,sizeof(dest));
gets(pair);
sscanf(pair,"%s %s", source, dest);
if (strlen(source) == 0)
break;
int srcIndex = find(source,dictionary);
int destIndex = find(dest,dictionary);
int step = bfs(srcIndex,destIndex,map);
printf("%s %s %d\n",source,dest,step);
}
caseNo++;
}
//fclose(stdin);
//fclose(stdout);
return 0;
}
bool oneDiff(char *a, char * b)
{
int p = strlen(a);
int q = strlen(b);
int cnt = 0;
if (p != q)
return false;
else
{
for (int i = 0; i < p; i++)
{
if (a[i] != b[i])
cnt++;
if (cnt > 1)
return false;
}
if (cnt == 1)
return true;
}
}
int find(char *word, char book[][11])
{
for (int i = 0; i < 200; i++)
{
if (!strcmp(word, book[i]))
return i;
}
}
int bfs(int source, int destinition,vector<int> map[])
{
if (source == destinition)
return 0;
int dis[200];
bool visited[200];
memset(visited, false, sizeof(visited));
memset(dis,0,sizeof(dis));
queue<int> q;
q.push(source);
visited[source] = true;
while (!q.empty())
{
int u = q.front();
for (int i = 0; i < map[u].size(); i++)
{
int v = map[u][i];
if (!visited[v])
{
visited[v] = true;
dis[v] = dis[u] + 1;
if (v == destinition)
return dis[v];
q.push(v);
}
}
q.pop();
}
}
Re: 429 - Word Transformation
Posted: Fri Dec 26, 2014 12:48 pm
by lighted
Use code blocks. Change your code to
Code: Select all
while (gets(pair))
{
memset(source, 0, sizeof(source));
memset(dest, 0, sizeof(dest));
sscanf(pair, "%s %s", source, dest);
Re: 429 - Word Transformation
Posted: Mon Feb 09, 2015 6:23 pm
by PromeNabid
I got TLE. Can not figure out the bug.
I used BFS to find shortest path to trasnform from source to destination. If the query strings are not of same length or both are same, then just printed 0.
Source code: ac
Re: 429 Word Transformation
Posted: Mon Feb 09, 2015 11:27 pm
by brianfry713
brianfry713 wrote:Compare each pair of words once before you start the BFS.
Re: 429 - Word Transformation
Posted: Tue Feb 10, 2015 1:44 pm
by PromeNabid
I used this comparison..
Code: Select all
// check length, if not same no need to run bfs
solved
Re: 429 - Word Transformation
Posted: Tue Feb 10, 2015 1:46 pm
by PromeNabid
Re: 429 - Word Transformation
Posted: Tue Feb 10, 2015 11:50 pm
by brianfry713
Before you run BFS, create a graph: bool [200][200] that is a 1 if there is an edge between the two strings and a 0 otherwise.
If you do that inside the BFS you are repeating a lot of comparisons.
Re: 429 - Word Transformation
Posted: Thu Feb 12, 2015 11:24 am
by ssaha22
Dont knwo why WA??? tested with various inputs..bt it gives correcct ans.. anyone please help
here is the code
..............
Code: Select all
#include <cstdio>
#include <cstring>
#include <string>
#include <vector>
#include <map>
#include <iostream>
#include <queue>
using namespace std;
vector<int>v[210];
int test[210];
int dd[210];
map<string,int>m;
map<int,string>ms;
queue<int>q;
struct as{
string a;
string b;
int an;
};
typedef struct as ans;
vector<ans>g;
int main(){
string h,A,B;
int a,b,c,d,n,T,source,dest;
a=1;
cin>>T;
map<string,int>::iterator it;
map<string,int>::iterator it2;
getchar();
while(a<=T){
if(a!=1){
cout<<endl;
}
g.clear();
memset(test,0,sizeof(test));
m.clear();
b=3;
while(1){
cin>>h;
if(h[0]=='*' && h.length()==1){
break;
}
if(m[h]==0){
m[h]=b;
ms[b]=h;
b++;
}
}
for(it=m.begin();it!=m.end();it++){
for(it2=m.begin();it2!=m.end();it2++){
if(it==it2){
continue;
}
else{
if(it->first.length()==it2->first.length()){
int count=0;
for(c=0;c<it->first.length();c++){
if(it->first[c]!=it2->first[c]){
count++;
}
else{
continue;
}
}
if(count==1){
v[it->second].push_back(it2->second);
}
}
}
}
}
getchar();
string k;
while(getline(cin,k)){
if(k==""){
break;
}
for(c=0;c<k.length();c++){
if(k[c]==' '){
break;
}
}
B="\0";
A="\0";
for(d=0;d<c;d++){
A=A+k[d];
}
for(d=c+1;d<k.length();d++){
B=B+k[d];
}
if((A.length()!=B.length()) || (A==B)){
cout<<A<<" "<<B<<" "<<0<<endl;
}
else{
memset(dd,0,sizeof(dd));
source=m[A];
dest=m[B];
q.push(source);
dd[source]=0;
memset(test,0,sizeof(test));
while(!(q.empty())){
int u=q.front();
for(c=0;c<v[u].size();c++){
if(test[v[u][c]]==0){
q.push(v[u][c]);
dd[v[u][c]]=dd[u]+1;
test[v[u][c]]=1;
}
}
q.pop();
}
dd[source]=0;
cout<<A<<" "<<B<<" "<<dd[dest]<<endl;
}
}
a++;
}
return 0;
}
Re: 429 - Word Transformation
Posted: Thu Feb 12, 2015 11:14 pm
by brianfry713
You're not clearing v between test cases.
Input:
Code: Select all
2
aa
bb
ac
*
aa ac
aa
ab
bb
*
aa bb
AC output:
Re: 429 - Word Transformation
Posted: Sat Feb 14, 2015 11:07 pm
by ssaha22
thankz brianfry
tht really helped me..and i dnt knw how i missed tht
thankz again