SP LAB 2

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
/////////////////////////////lab2.java

package lab2SP;

import java.io.File;
import java.io.FileNotFoundException;
import java.util.Scanner;
import java.util.*;



public class lab2 {
    public static void main(String[] args) {
        Automata<Integer> a1 = Scan("input1.in");
        Automata<Integer> a2 = Scan("input2.in");
        Automata<Pair<Integer , Integer> > m = Multiply(a1 , a2);
    //  System.out.println(m.s.first() + " " + m.s.second());
        for(Pair<Integer , Integer> i: m.S){
            //System.out.println(i.first() + " " + i.second());
        }
        ArrayList<Pair<Integer , Integer> > path = m.Solve();

        if(path.size() > 1){
            for(int i = 0 ; i < path.size() - 1; ++i){
                for(Pair<Pair<Integer, Integer>, Pair<Integer, Integer>> j : m.inverse_f.keySet()){
                    if(j.first().first() == path.get(i).first()
                      && j.first().second() == path.get(i).second()
                      && j.second().first() == path.get(i + 1).first()
                      && j.second().second() == path.get(i + 1).second())
                    {
                        System.out.print(m.inverse_f.get(j));
                    }
                }
            }
        }

    }
    static Automata<Integer> Scan(String file){
        Automata<Integer> a1 = null;
        try{
            Scanner in = new Scanner(new File(file));
            int A , S1 , s;
            A = in.nextInt();
            S1 = in.nextInt();
            s = in.nextInt();
            Set<Integer> S = new HashSet<Integer>();
            for(int i = 0 ; i < S1 ; ++i)S.add(i);
            int t;
            t = in.nextInt();
            Set<Integer> F = new HashSet<Integer>();
            for(int i = 0 ; i < t ; ++i){
                F.add(in.nextInt());
            }

            Map<Pair<Integer , Character> , Integer> f = new HashMap<Pair<Integer , Character> , Integer>();
            while(in.hasNextLine()){
                int u , v;
                char c;
                u = in.nextInt();
                c = in.next().charAt(0);
                v = in.nextInt();
                Pair<Integer , Character> pr = new Pair<Integer , Character>(u , c);
                f.put(pr , v);
            }

            a1 = new Automata<Integer>(A , S , s , F , f);
            in.close();
        }catch(FileNotFoundException e){
            System.out.print("File input1.in not found :( ");
        }
        return a1;
    }

    static <T> Automata<Pair<T , T> > Multiply (Automata<T> a , Automata<T> b){
        int new_A = Math.max(a.A, b.A);
        Set<Pair<T , T> > new_S = new HashSet<Pair<T , T> >();
        for(T i: a.S){
            for(T j: b.S){
                Pair<T , T> pr = new Pair<T, T>(i , j);
                new_S.add(pr);
            }
        }
        Set<Pair<T , T> > new_F = new HashSet<Pair<T , T> >();
        for(T i: a.F){
            for(T j: b.F){
                Pair<T , T> pr = new Pair<T , T>(i , j);
                new_F.add(pr);
            }
        }
        Pair<T , T> new_s = new Pair<T , T>(a.s , b.s);
        Map<Pair<Pair<T , T> , Character> , Pair<T , T> > new_f = new HashMap<Pair<Pair<T , T> , Character> , Pair<T , T> >();

        for(Pair<T , Character> i : a.f.keySet()){
            for(Pair<T , Character> j : b.f.keySet()){
                if(i.second() != j.second())continue;
                for(Pair<T , T> k : new_S){
                    if(i.first() == k.first() && j.first() == k.second()){
                        Pair<Pair<T , T> , Character> pr = new Pair<Pair<T , T> , Character>(k , (char)i.second());
                        Pair<T , T> put_pair = new Pair<T, T>(a.f.get(i) , b.f.get(j));
                        new_f.put(pr, put_pair);
                    }
                }
            }
        }
        Automata<Pair<T , T> > res = new Automata<Pair<T , T> >(new_A , new_S , new_s , new_F , new_f);
        return res;
    }
}

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////Automata.java

package lab2SP;

import java.io.File;
import java.io.FileNotFoundException;
import java.util.Scanner;
import java.util.*;

public class Automata<T> {
    int A;
    T s;
    Set<T> S = new HashSet<T>();
    Set<T> F = new HashSet<T>();
    Map<Pair<T , Character> , T> f = new HashMap<Pair<T , Character> , T>();
    Map<Pair<T , T> , Character> inverse_f = new HashMap<Pair<T , T> , Character>();

    Automata(int _A , Set<T> _S , T _s , Set<T> _F , Map<Pair<T , Character> , T> _f){
        A = _A;
        s = _s;
        S = _S;
        F = _F;
        f = _f;
        for(Map.Entry<Pair<T , Character> , T> i : f.entrySet()){
            Pair<T , T> pr = new Pair<T , T>(i.getKey().first() , i.getValue());
            inverse_f.put(pr , i.getKey().second());
        }
    }

    T bfs(Map<T , Integer> d , Map<T , T> p , Map<T , Boolean> used){
    //  Queue<T> q = new PriorotyQueue<T>();
        Set<T> q = new HashSet<T>();
        q.add(s);
        used.put(s ,  true);
        T ret = s;
        p.put(s , s);
        d.put(s ,  0);
        boolean flag = false;
        while(q.size() > 0){
            T v = q.iterator().next();//q.poll();
            q.remove(v);
        //  q.peek();
            for(Pair<T , Character> i: f.keySet()){
                //System.out.println(((Pair)(i.first())).first() + " " + ((Pair)(i.first())).second() + " and " + ((Pair)(v)).first() + " " + ((Pair)(v)).second());
                if(((Pair)(i.first())).first() == ((Pair)(v)).first() && ((Pair)(i.first())).second() == ((Pair)(v)).second()){
                //if(i.first().equals(v)){

                    T to = f.get(i);
                    try{
                        if(used.get(to) == false);
                    }catch(java.lang.NullPointerException e){
                        used.put(to , false);
                    }
                    if(used.get(to) == false){
                        used.put(to , true);
                        q.add(to);
                        d.put(to, d.get(v) + 1);
                        p.put(to, v);
                        for(T j : F){
                            if((int)((Pair)(to)).first() == (int)((Pair)(j)).first() && (int)((Pair)(to)).second() == (int)((Pair)(j)).second()){
                                ret = to;
                            //  System.out.println("We have found a finish vertex!");
                                flag = true;
                                break;
                            }
                        }
                    /*  if(F.contains(to)){
                            ret = to;
                            System.out.println("We have found a finish vertex!");
                            flag = true;
                            break;
                        }*/
                    }
                }
            }
            if(flag)break;
        }
        return ret;
    }

    ArrayList<T> Solve(){
        Map<T , Integer> d = new HashMap<T , Integer>();
        Map<T , T> p = new HashMap<T , T>();
        Map<T , Boolean> used = new HashMap<T , Boolean>();
        T need = bfs(d , p , used);

        ArrayList<T> path = new ArrayList<T>();
        if(need == s){
            System.out.println("Such word does not exist :(");
            return path;
        }
        boolean ck = true;
        for(T v = need ; ck && v != s ; v = p.get(v)){
            path.add(v);
            if(v == s)ck = false;
        }
        path.add(s);
        Collections.reverse(path);
        return path;
    }
}

////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////Pair.java

package lab2SP;

public class Pair<T1 , T2> {
    T1 x;
    T2 y;
    Pair(T1 _x , T2 _y){
        x = _x;
        y = _y;
    }
    T1 first(){
        return x;
    }
    T2 second(){
        return y;
    }

    boolean equals(Pair<T1 , T2> other){
        return ((Object)this.x == (Object)other.x && (Object)this.y == (Object)other.y);
    }
}

/////////////////////////////////////////////////////////////////////////////////////////////////////////
////////////////////INPUT EXAMPLE
/*
3
6
0
1 5
0 b 2
0 a 1
1 b 3
2 a 3
3 a 4
3 b 0
4 a 2
4 c 5
4 b 1



3
7
0
1 6
0 a 1
0 b 2
0 c 3
1 a 4
2 a 4
2 b 3
3 b 4
4 a 5
4 b 3
4 c 0
5 a 1
5 c 6
5 b 3
*/