429 - Word Transformation

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

Moderator: Board moderators

sreka11
New poster
Posts: 15
Joined: Fri Aug 15, 2014 8:06 pm

Re: 429 - Word Transformation

Post by sreka11 » Thu Sep 25, 2014 5:05 pm

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



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

Re: 429 - Word Transformation

Post by brianfry713 » Thu Sep 25, 2014 10:45 pm

Instead of filling up a StringBuffer with all of the output try writing directly to the BufferedWriter or at least between test cases.
Check input and AC output for thousands of problems on uDebug!

sreka11
New poster
Posts: 15
Joined: Fri Aug 15, 2014 8:06 pm

Re: 429 - Word Transformation

Post by sreka11 » Thu Sep 25, 2014 11:16 pm

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




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

Re: 429 - Word Transformation

Post by brianfry713 » Fri Oct 03, 2014 1:30 am

The first line of the input is an integer N, indicating the number of test set that your correct program should test.
Check input and AC output for thousands of problems on uDebug!

mhsn06
New poster
Posts: 16
Joined: Tue Apr 01, 2014 7:36 pm

Re: 429 - Word Transformation

Post by mhsn06 » Sun Nov 23, 2014 8:10 pm

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
   }
:)

messiNayan
New poster
Posts: 7
Joined: Thu Feb 20, 2014 7:07 pm

Re: 429 - Word Transformation

Post by messiNayan » Fri Dec 26, 2014 12:08 pm

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

}
Last edited by brianfry713 on Tue Jan 06, 2015 5:27 am, edited 1 time in total.
Reason: Added code blocks

lighted
Guru
Posts: 585
Joined: Wed Jun 11, 2014 9:56 pm
Location: Kyrgyzstan, Bishkek

Re: 429 - Word Transformation

Post by lighted » Fri Dec 26, 2014 12:48 pm

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);
A person who sees the good in things has good thoughts. And he who has good thoughts receives pleasure from life... Bediuzzaman

PromeNabid
New poster
Posts: 21
Joined: Mon Jun 18, 2012 12:52 am
Location: Dhaka, Bangladesh.
Contact:

Re: 429 - Word Transformation

Post by PromeNabid » Mon Feb 09, 2015 6:23 pm

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
Last edited by PromeNabid on Sun Feb 15, 2015 4:37 pm, edited 1 time in total.

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

Re: 429 Word Transformation

Post by brianfry713 » Mon Feb 09, 2015 11:27 pm

brianfry713 wrote:Compare each pair of words once before you start the BFS.
Check input and AC output for thousands of problems on uDebug!

PromeNabid
New poster
Posts: 21
Joined: Mon Jun 18, 2012 12:52 am
Location: Dhaka, Bangladesh.
Contact:

Re: 429 - Word Transformation

Post by PromeNabid » Tue Feb 10, 2015 1:44 pm

I used this comparison..

Code: Select all

// check length, if not same no need to run bfs
solved
Last edited by PromeNabid on Sun Feb 15, 2015 4:37 pm, edited 1 time in total.

PromeNabid
New poster
Posts: 21
Joined: Mon Jun 18, 2012 12:52 am
Location: Dhaka, Bangladesh.
Contact:

Re: 429 - Word Transformation

Post by PromeNabid » Tue Feb 10, 2015 1:46 pm

Source code:

Code: Select all

ac
Last edited by PromeNabid on Sun Feb 15, 2015 4:38 pm, edited 1 time in total.

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

Re: 429 - Word Transformation

Post by brianfry713 » Tue Feb 10, 2015 11:50 pm

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.
Check input and AC output for thousands of problems on uDebug!

ssaha22
New poster
Posts: 5
Joined: Sat Dec 14, 2013 10:00 am

Re: 429 - Word Transformation

Post by ssaha22 » Thu Feb 12, 2015 11:24 am

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;
}
Last edited by brianfry713 on Thu Feb 12, 2015 9:01 pm, edited 1 time in total.
Reason: Added code blocks

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

Re: 429 - Word Transformation

Post by brianfry713 » Thu Feb 12, 2015 11:14 pm

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:

Code: Select all

aa ac 1

aa bb 2
Check input and AC output for thousands of problems on uDebug!

ssaha22
New poster
Posts: 5
Joined: Sat Dec 14, 2013 10:00 am

Re: 429 - Word Transformation

Post by ssaha22 » Sat Feb 14, 2015 11:07 pm

thankz brianfry :) tht really helped me..and i dnt knw how i missed tht :P
thankz again :)

Post Reply

Return to “Volume 4 (400-499)”