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

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

Re: 429 - Word Transformation

Post by PromeNabid » Sun Feb 15, 2015 4:39 pm

If you do that inside the BFS you are repeating a lot of comparisons.
Thanks a lot brianfry, I missed that optimization.

richatibrewal
New poster
Posts: 49
Joined: Mon Jun 16, 2014 7:40 pm

Re: 429 - Word Transformation

Post by richatibrewal » Sun Mar 08, 2015 12:44 pm

Hii, I am getting WA for this problem. Following is my code :-

Code: Select all

#include<cstdio>
#include<string>
#include<map>
#include<iostream>
#include<vector>
#include<climits>
#include<queue>
#include<sstream>
#define MAXLEN 210
using namespace std;

map<string,int> mp;
vector<vector<int> > graph;
int dist[MAXLEN];
bool visited[MAXLEN];

int find_diff(string a,string b)
{
    int d=0,i,j;

    if(a.size()!=b.size())
        return -1;

    for(i=0;i<a.size();i++)
    {
        if(a[i]!=b[i])
            d++;
    }
    return d;
}

void make_graph(int n,int m)
{
    graph[n].push_back(m);
    graph[m].push_back(n);
}

void shortest_path(int a,int b)
{
    int i,u,v;

    dist[a]=0;

    queue<int> q;
    q.push(a);

    while(!q.empty())
    {
        u=q.front();
        visited[u]=true;

        q.pop();

        for(i=0;i<graph[u].size();i++)
        {
            v=graph[u][i];

            if(dist[v]>dist[u]+1 && !visited[v])
            {
                dist[v]=dist[u]+1;

               // printf("%d %d %d\n",u,v,dist[v]);
                q.push(v);
            }
        }
    }
}

int main()
{
    int i,j,l,n,node,diff,x,y;
    string str,a,b;

    scanf("%d",&n);
    getchar();
    getchar();
    while(n--)
    {
        node=0;

        vector<int > v;
        graph.push_back(v);

         while(1)
         {
             cin>>str;

             if(str[0]=='*')
                break;

             if(!mp[str])
                mp[str]=++node;

            map<string,int>::iterator it;

            i=0;

            vector<int > v;
            graph.push_back(v);
            // make_graph(0,node);
            for(it=mp.begin();it!=mp.end();it++)
            {
                i++;
                diff=find_diff(it->first,str);
                if(diff==1)
                    make_graph(i,node);
            }


         }

         /* map<string,int>::iterator it;

         for(it=mp.begin();it!=mp.end();it++)
            cout<<it->first<<"  "<<it->second<<endl;

         for(i=0;i<graph.size();i++)
            {
                printf("%d---",i);
                for(j=0;j<graph[i].size();j++)
                    printf("%d  ",graph[i][j]);

                printf("\n");
            }*/

        getchar();
        //printf("yoo");


        getline(cin,str);

        //cout<<str;

        while(!str.empty())
        {
           // printf("ff");

            for(i=0;i<=node;i++)
            {
                dist[i]=INT_MAX;
                visited[i]=false;
            }

            stringstream ss(str);
            ss>>a>>b;

            x=mp[a];
            y=mp[b];

           // printf("\n%d %d",x,y);

            shortest_path(x,y);

            cout<<a<<" "<<b<<" "<<dist[y]<<endl;

            getline(cin,str);
        }
        if(n!=0)
            printf("\n");

        mp.clear();
        graph.clear();
    }

    return 0;
}

shauqi
New poster
Posts: 3
Joined: Fri Jan 02, 2015 1:51 pm

429-Word Tranformation

Post by shauqi » Tue Apr 07, 2015 8:57 pm

getting wa...
tried some critical input..

Code: Select all

#include<bits/stdc++.h>
using namespace std;

map<string,int>visited;
map<string,int>level;

int bfs(string src,string des,map< string,vector<string> >Graph)
{
    queue<string>Q;
    Q.push(src);
    visited[src]=0;
    level[src]=0;
    while(!Q.empty())
    {
        string u=Q.front();
        for(int i=0;i<Graph[u].size();i++)
        {
            string v=Graph[u][i];
            if(!visited[v])
            {
                level[v]=level[u]+1;
                visited[v]=1;
                Q.push(v);
            }
        }
        Q.pop();
    }
    return level[des];
}

bool compare(string s1,string s2)
{
    int count=0;
    for(int i=0;i<max(s1.size(),s2.size());i++)
    {
        if(s1[i]!=s2[i])
        {
            if(count>1) break;
            count++;
        }
    }
    if(count==1) return true;
    else return false;
}

int main()
{
    //freopen("Input.txt","r",stdin);
    //freopen("Output.txt","w",stdout);
    int TestCase,cnt=0;
    cin>>TestCase;
    while(TestCase--)
    {
        if(cnt>0) cout<<endl;
        map< string,vector<string> >Graph;
        vector<string>v;
        string s;
        cin>>s;
        while(s[0]!='*')
        {
            if(s[0]=='*') break;
            for(int i=0;i<v.size();i++)
            {
                if(compare(s,v[i]))
                {
                    Graph[s].push_back(v[i]);
                    Graph[v[i]].push_back(s);
                    visited[s]=0;
                    visited[v[i]]=0;
                    level[s]=0;
                    level[v[i]]=0;
                }
            }
            v.push_back(s);
            cin>>s;
        }
        string s1,s2;
        string line;
        getline(cin,line);
        getline(cin,line);
        while(line !="")
        {
            int pos=0;
            pos=line.find(" ");
            s1=line.substr(0,pos);
            s2=line.substr(pos+1,line.size());
            cout<<s1<<" "<<s2<<" "<<bfs(s1,s2,Graph)<<endl;
            if(!getline(cin,line))
            break;
        }
        cnt++;
    }
    return 0;
}

atul_pust
New poster
Posts: 3
Joined: Thu Mar 26, 2015 12:14 pm

Re: 429 - Word Transformation Getting WA. Please help

Post by atul_pust » Thu Apr 09, 2015 4:47 pm

Code: Select all

#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <cstring>
#include <cstring>
#include <map>
using namespace std;

map<string, int> M;
string source, destination;
int dist[300];
int visited[300];
vector<string> P[300];
vector<int> G[300];

bool compare(string s, string str){
    int times = 0;
    for(int i = 0; i < s.size(); i++){
        if(s[i] != str[i])
            ++times;
    }
    if(times == 1)
        return true;
    else
        return false;
}

int BFS(int source, int destination){
    queue<int> q;
   // cout << source << " " << destination << endl;
    dist[source] = 0;
    visited[source] = 1;
    q.push(source);
    while(!q.empty()){
        int u = q.front();
        q.pop();
        if(u == destination)
            return dist[u];
        for(int i = 0; i < G[u].size(); i++){
            int v = G[u][i];
            if(visited[v] == 0){
                visited[v] = 1;
                dist[v] = dist[u] + 1;
                q.push(v);
                if(v == destination)
                    return dist[v];
            }
        }
    }
    return 0;
}

int main()
{
  
    int t;
    cin >> t;
    getchar();

    for(int i = 1; i <= t; i++){
        for(int h = 0; h < 201; h++)
        {
            G[h].clear();
            P[h].clear();
        }
        if(i > 1)
            cout << endl;
        memset(visited, 0, sizeof(visited));
        memset(dist, 0, sizeof(dist));
        M.clear();
        string s;
        char c[20];
        int cnt = 0;
        getchar();
        while(gets(c)){
            if(c[0] == '*')
                break;
            string s(c);
            int len = s.size();
            if(M[s] == 0){
                M[s] = cnt + 1;
                cnt += 1;
                P[len].push_back(s);
            }
            for(int k = 0; k < P[len].size(); k++){
                string str = P[len][k];
                if(compare(s, str)){
                    G[M[s]].push_back(M[str]);
                    G[M[str]].push_back(M[s]);
                    //cout << s << " gg " << str;
                }
            }
        }
        while(gets(c)){
            if(c[0] == '\0')
                break;
            int l = strlen(c);
            bool flag = false;
            string d = "", s = "";
            for(int i = 0; i < l; i++){
                if(c[i] == ' ')
                    flag = true;
                else if(flag)
                    d += c[i];
                else
                    s += c[i];
            }
            int ans;
            source = s; destination = d;
            if(s.size() != d.size())
                ans = 0;
            else
            ans = BFS(M[source], M[destination]);

            cout << s << " " << d << " " << ans << endl;
            memset(visited, 0, sizeof(visited));
            memset(dist, 0, sizeof(dist));
        }
    }
    return 0;
}
Last edited by brianfry713 on Mon Apr 13, 2015 11:45 pm, edited 1 time in total.
Reason: Added code block

lusho
New poster
Posts: 4
Joined: Fri Jan 16, 2015 11:41 pm

Re: 429 - Word Transformation WA helpppppppp

Post by lusho » Mon May 18, 2015 11:45 pm

Code: Select all

#include <cstdio>
#include <map>
#include <vector>
#include <queue>
#include <iostream>
#include <sstream>
#include <set>
using namespace std;
struct word
{
	string pal;
	int step;
};

int main()
{
	int n;
	scanf("%d",&n);
	string dic;
	cin.ignore();
	getline(cin,dic);
	bool primera=true;
	while(n--)
	{
		bool com=true;
		map<string, set<string> > ma;
		map<string,bool> visi;
		set<string> v;
		if(!primera)
			printf("\n");
		primera=false;
		while(getline(cin,dic) && dic.size()!=0)
		{
			if(dic=="*")
				com=false;
			if(com)
			{
				set<string>:: iterator it=v.begin();
				visi[dic]=false;
				for(;it!=v.end();it++)
				{
					if(dic.size()==(*it).size())
					{
						int c=0;
						for(int j=0;j<dic.size() && c<2;j++)
						{
							if(dic[j] != (*it)[j])
								c++;
						}
						if(c==1)
						{
							ma[dic].insert((*it));
							ma[(*it)].insert(dic);
						}
					}
				}
				v.insert(dic);
			}
			else
			{
				istringstream S(dic);
				string a,b;
				S>>a>>b;
				queue<word> Q;
				word u;
				u.pal=a;
				u.step=0;
				Q.push(u);
				visi[a]=true;
				while(!Q.empty())
				{
					u=Q.front();
					if(u.pal==b)
					{
						//cout<<a<<" "<<b<<" "<<u.step<<endl;
						printf("%s %s %d\n",a.c_str(),b.c_str(),u.step);
						break;
					}
					Q.pop();
					set<string> ::iterator it=ma[u.pal].begin();

					for(;it!=ma[u.pal].end();it++)
					{
						word v;
						v.pal=(*it);
						v.step=u.step+1;
						if(visi[v.pal]==false)
						{
							Q.push(v);
							visi[v.pal]=true;
						}
					}
				}
			}
		}
	}
}
//why it gives me WA , somebody help me pleaseeeeeeeeeeeee
Last edited by brianfry713 on Fri Jun 19, 2015 6:30 am, edited 1 time in total.
Reason: Added code blocks

lusho
New poster
Posts: 4
Joined: Fri Jan 16, 2015 11:41 pm

Re: 429 - Word Transformation

Post by lusho » Mon May 18, 2015 11:49 pm

Code: Select all

#include <cstdio>
#include <map>
#include <vector>
#include <queue>
#include <iostream>
#include <sstream>
#include <set>
using namespace std;
struct word
{
	string pal;
	int step;
};

int main()
{
	int n;
	scanf("%d",&n);
	string dic;
	cin.ignore();
	getline(cin,dic);
	bool primera=true;
	while(n--)
	{
		bool com=true;
		map<string, set<string> > ma;
		map<string,bool> visi;
		set<string> v;
		if(!primera)
			printf("\n");
		primera=false;
		while(getline(cin,dic) && dic.size()!=0)
		{
			if(dic=="*")
				com=false;
			if(com)
			{
				set<string>:: iterator it=v.begin();
				visi[dic]=false;
				for(;it!=v.end();it++)
				{
					if(dic.size()==(*it).size())
					{
						int c=0;
						for(int j=0;j<dic.size() && c<2;j++)
						{
							if(dic[j] != (*it)[j])
								c++;
						}
						if(c==1)
						{
							ma[dic].insert((*it));
							ma[(*it)].insert(dic);
						}
					}
				}
				v.insert(dic);
			}
			else
			{
				istringstream S(dic);
				string a,b;
				S>>a>>b;
				queue<word> Q;
				word u;
				u.pal=a;
				u.step=0;
				Q.push(u);
				visi[a]=true;
				while(!Q.empty())
				{
					u=Q.front();
					if(u.pal==b)
					{
						//cout<<a<<" "<<b<<" "<<u.step<<endl;
						printf("%s %s %d\n",a.c_str(),b.c_str(),u.step);
						break;
					}
					Q.pop();
					set<string> ::iterator it=ma[u.pal].begin();

					for(;it!=ma[u.pal].end();it++)
					{
						word v;
						v.pal=(*it);
						v.step=u.step+1;
						if(visi[v.pal]==false)
						{
							Q.push(v);
							visi[v.pal]=true;
						}
					}
				}
			}
		}
	}
}
helppppppppp please it gives me WA

nander
New poster
Posts: 1
Joined: Wed Nov 11, 2015 4:51 am

Re: 429 - Word Transformation

Post by nander » Wed Nov 11, 2015 5:01 am

Hi,

I think I almost have a solution (in Java). However, it states Runtime Error. I've been looking at my code for quite a while now and can't find the problem.

Code: Select all

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;


/**
 * Created by nander on 10-11.
 */
public class Main {
    public static boolean neighbours(String w1, String w2)
    {
        int diff = 0;
        if(w1.length() != w2.length()) {
            return false;
        }
        for(int i=0;i<w1.length();i++)
            if(w1.charAt(i) != w2.charAt(i)) {
                diff++;
                if (diff > 1) {
                    return false;
                }
            }
        return true;
    }
    public static void main (String[] args) {
        Scanner s = new Scanner(System.in);


        int cases = s.nextInt();
        while (cases-- > 0) {
            String word;
            HashMap<String,Integer> dict = new  HashMap<>();
            int N=0;
            while( !(word = s.next()).equals( "*"))
            {
                dict.put(word,N);
                N++;
            }
            boolean[][] conversions = new boolean[N][N];
            for(String word1 : dict.keySet())
                for(String word2 : dict.keySet())
                    if(neighbours(word1,word2))
                    {
                        conversions[dict.get(word1)][dict.get(word2)] = true;
                    }
            String line;
            s.nextLine();

            while(!( line = s.nextLine()).equals(""))
            {
                String[] l = line.split(" ");
                String word1 = l[0];
                String word2 = l[1];
                int w1 = dict.get(word1);
                int w2 = dict.get(word2);
                int[] ans = new int[N+1];
                Queue<Integer> Q = new LinkedList<>();
                Q.offer(w1);
                int final_ans = -1;
                if( w1 == w2)
                    final_ans = 0;
                for(int i=0;i<N;i++)
                    ans[i]=-1;
                while(!Q.isEmpty())
                {
                    int el = Q.poll();
                    for(int ii=0;ii<N; ii++)
                    {
                        if(conversions[el][ii] && ans[ii]==-1 )
                        {

                            ans[ii] = ans[el]+ 1;
                            Q.offer(ii);
                            if(ii == w2) {
                                final_ans = ans[ii];
                                break;
                            }
                        }
                    }
                    if(final_ans != -1)
                        break;
                }
                System.out.println(word1+" "+ word2+ " "+final_ans);
            }

            if(cases > 0)
                System.out.println("");
        }
    }
}

anacharsis
Learning poster
Posts: 69
Joined: Mon Feb 09, 2015 1:56 am

Re: 429 - Word Transformation

Post by anacharsis » Sun Nov 29, 2015 8:58 pm

Some I/O

In:

Code: Select all

1

axe
axi
bxi
cxi
dxi
dli
dlx
dls
cls
clx
*
axe axi
axe clx
axi cls
axi dli
dli cls
cxi cls
AC out:

Code: Select all

axe axi 1
axe clx 5
axi cls 4
axi dli 2
dli cls 2
cxi cls 4

Post Reply

Return to “Volume 4 (400-499)”