/**
* Created by matei on 22/05/16.
*/
import javax.sound.midi.Soundbank;
import javax.xml.bind.SchemaOutputResolver;
import java.io.*;
import java.util.*;
class Triple <T1,T2,T3> {
T1 v1;
T2 v2;
T3 v3;
public Triple(T1 v1, T2 v2, T3 v3){
this.v1 = v1; this.v2 = v2; this.v3 = v3;
}
public T1 fst(){ return v1;}
public T2 snd(){ return v2;}
public T3 thrd(){ return v3;}
}
class NFA {
/*
Convention for reading an automata:
n m
f1 f2 ... fk
s c sp
...
s c sp
n - number of states
m - number of symbols
f1 f2 ... fk - the final states
s c p - transition (state symbol state)
*/
private int state_no, symbol_no;
List<Integer> [][] m;
List<Integer> [][] invm;
List<Integer> final_states;
List<Integer> initial_states;
boolean isFinal (Integer s){
return final_states.contains(s);
}
public NFA (int state_no, int symbol_no){
init(state_no,symbol_no);
}
private void init (int state_no, int symbol_no){
this.state_no = state_no;
this.symbol_no = symbol_no;
m = new LinkedList[state_no][symbol_no];
invm = new LinkedList[state_no][symbol_no];
final_states = new LinkedList<Integer>();
initial_states = new LinkedList<Integer>();
initial_states.add(0);
}
public NFA(BufferedReader reader){
try
{
//BufferedReader reader = new BufferedReader(new FileReader(filename));
String line;
String[] toks;
line = reader.readLine(); // states and symbols
toks = line.split("\\s+");
init(Integer.parseInt(toks[0]), Integer.parseInt(toks[1]));
line = reader.readLine();
toks = line.split("\\s+");
for (String i:toks)
final_states.add(Integer.parseInt(i));
while (!(line = reader.readLine()).trim().equals(""))
{
toks = line.split("\\s+");
char c = toks[1].charAt(0);
Integer s = Integer.parseInt(toks[0]);
Integer sp = Integer.parseInt(toks[2]);
if (m[s][c-'a'] == null)
m[s][c - 'a'] = new LinkedList<Integer>();
if (invm[sp][c-'a'] == null)
invm[sp][c - 'a'] = new LinkedList<Integer>();
m[s][c - 'a'].add(sp);
invm[sp][c - 'a'].add(s);
}
}
catch (Exception e)
{
e.printStackTrace();
}
}
public NFA(String filename){
try
{
BufferedReader reader = new BufferedReader(new FileReader(filename));
String line;
String[] toks;
line = reader.readLine(); // states and symbols
toks = line.split("\\s+");
init(Integer.parseInt(toks[0]), Integer.parseInt(toks[1]));
line = reader.readLine();
toks = line.split("\\s+");
for (String i:toks)
final_states.add(Integer.parseInt(i));
while ((line = reader.readLine()) != null)
{
toks = line.split("\\s+");
char c = toks[1].charAt(0);
Integer s = Integer.parseInt(toks[0]);
Integer sp = Integer.parseInt(toks[2]);
if (m[s][c-'a'] == null)
m[s][c - 'a'] = new LinkedList<Integer>();
if (invm[sp][c-'a'] == null)
invm[sp][c - 'a'] = new LinkedList<Integer>();
m[s][c - 'a'].add(sp);
invm[sp][c - 'a'].add(s);
}
reader.close();
}
catch (Exception e)
{
System.err.format("Exception occurred trying to read '%s'.", filename);
e.printStackTrace();
}
}
public int size (){ return state_no;}
public int symbols () {return symbol_no;}
public int final_states(){return final_states.size();}
public List<Integer> get_nonfinal_states(){
List<Integer> r = new LinkedList<Integer>();
for (int i = 0; i<state_no; i++)
if (!isFinal(i))
r.add(i);
return r;
}
public List<Integer> get_final_states(){
return final_states;
}
// returns the list of states from which a state in S is reachable via symbol
public Set<Integer> inv (int symbol, Set<Integer> S){
Set<Integer> r = new HashSet<Integer>();
for (Integer s:S)
if (invm[s][symbol] != null)
r.addAll(invm[s][symbol]);
return r;
}
@Override
public String toString(){
String s = "# ";
for (int i=0; i<symbol_no; i++)
s += Character.toString((char)(i + 'a'))+" ";
s+="\n";
for (int i=0; i<state_no; i++){
s += Integer.toString(i)+" ";
for (int j = 0; j<symbol_no; j++) {
if (m[i][j] != null)
s += m[i][j].toString();
else
s += "[]";
}
s += "\n";
}
return s;
}
public Set<Integer> move(int c, Set<Integer> q) {
Set<Integer> r = new HashSet<Integer>();
for (Integer s:q)
if (m[s][c] != null)
r.addAll(m[s][c]);
return r;
}
public void add_transition(int s, int c, int sp){
if (m[s][c] == null)
m[s][c] = new LinkedList<Integer>();
if (invm[sp][c] == null)
invm[sp][c] = new LinkedList<Integer>();
m[s][c].add(sp);
invm[sp][c].add(s);
}
public void add_final_state(int s){
final_states.add(s);
}
}
public class Main {
public static <T> Set<T> setmin (Set<T> s1, Set<T> s2){
if (s1.size() > s2.size())
return s2;
return s1;
}
public static <T> boolean refine (Set<T> Y1, Set<T> Y2, Set<T> Y, Set<T> X){
for (T t:Y){
if (X.contains(t))
Y1.add(t);
else Y2.add(t);
}
if (Y1.size() == 0 || Y2.size() == 0)
return false;
return true;
}
public static NFA det (NFA A){
List<Triple<List<Integer>,Integer,List<Integer>>> delta = new LinkedList<Triple<List<Integer>,Integer,List<Integer>>>();
List<Set<Integer>> Q = new LinkedList<Set<Integer>>();
Set<Integer> q0 = new HashSet<Integer>();
for (Integer si:A.initial_states)
q0.add(si);
Q.add(q0);
List<Integer> F = new LinkedList<Integer>();
List<Set<Integer>> mark = new LinkedList<Set<Integer>>();
Set<Integer> q, qp;
ListIterator<Set<Integer>> it;
boolean flag = true;
while(flag) {
flag = false; // new traversal started
for (it = Q.listIterator(); it.hasNext(); ) {
//System.out.println("Q is " + Q);
q = it.next();
//System.out.println("Current q is " + q);
if (!mark.contains(q)) {
mark.add(q);
for (Integer c = 0; c < A.symbols(); c++) {
qp = A.move(c, q);
if (qp.isEmpty())
continue;
//System.out.println("Qp is:" + qp + " for " + (char) (c + 'a'));
if (!Q.contains(qp)) {
//System.out.println("Adding " + qp);
it.add(qp);
flag = true; // list modification. A new traversal is allowed0.
}
//System.out.println("Trans " + q + " " + (char) (c + 'a') + " " + qp);
delta.add(new Triple(q, c, qp));
}
}
}
} // end of while
NFA det = new NFA(Q.size(),A.symbols());
//System.out.println("Q is "+Q);
for (Triple<List<Integer>,Integer,List<Integer>> t:delta) { // the initial state is guaranteed to be the first
//System.out.println("Transition "+t.fst()+" "+(char)(t.snd()+'a')+" "+t.thrd());
det.add_transition(Q.indexOf(t.fst()), t.snd(), Q.indexOf(t.thrd()));
}
for(Set<Integer> qq:mark)
for (Integer s:qq)
if(A.isFinal(s))
det.add_final_state(mark.indexOf(qq));
return det;
}
public static NFA rev (NFA A){
NFA rev = new NFA(A.size(),A.symbols());
rev.final_states = A.initial_states;
rev.initial_states = A.final_states;
rev.m = A.invm;
rev.invm = A.m;
return rev;
}
public static boolean isTotal (NFA A){
for (int i=0; i<A.size(); i++)
for (int j=0; j<A.symbols(); j++)
if (A.m[i][j]== null || A.m[i][j].size()==0)
return false;
return true;
}
public static int hopcroft (NFA a){
List<Set<Integer>> P = new LinkedList<Set<Integer>>();
Set<Integer> sf = new HashSet(a.get_final_states());
Set<Integer> snf = new HashSet(a.get_nonfinal_states());
P.add(sf);
P.add(snf);
List<Set<Integer>> W = new LinkedList<Set<Integer>>();
W.add(setmin(sf, snf));
while (!W.isEmpty()){
Set<Integer> A = W.get(0);
W.remove(0);
for (int c = 0; c<a.symbols();c++) {
for (ListIterator<Set<Integer>> it = P.listIterator(); it.hasNext();) {
Set<Integer> Y = it.next();
Set<Integer> Y1 = new HashSet<Integer>(), Y2 = new HashSet<Integer>();
//System.out.println("[W="+W+"]Processing "+Y);
if (refine(Y1, Y2, Y, a.inv(c, A))) { // we have a partition
//System.out.println("Refining " + Y + " by " + Y1 + " and " + Y2);
it.remove();
it.add(Y1);
it.add(Y2);
if (W.contains(Y)) {
W.remove(Y);
W.add(Y1);
W.add(Y2);
} else
W.add(setmin(Y1, Y2));
}
}
}
}
//System.out.println(P);
return P.size();
}
//concatenation of two automata over the same alphabet
// it is assumed that a has a single final state having only sink-state transitions,
public static NFA concatenate (NFA a, NFA b){
NFA res = new NFA(a.size()+b.size()-1,a.symbols());
for (int i=0; i<a.size();i++){
for (int c=0; c<a.symbols(); c++){
if (a.isFinal(i)) {
if (b.m[0][c] != null && !b.m[0][c].isEmpty())
for (Integer next : b.m[0][c]) {
res.add_transition(i, c, a.size() + next - 1);
}
}
else
if (a.m[i][c] != null){
for (Integer next:a.m[i][c])
res.add_transition(i,c,next);
}
}
}
for (int i=1; i<b.size();i++){
for (int c=0; c<b.symbols(); c++){
if (b.m[i][c] != null)
for (Integer next:b.m[i][c])
res.add_transition(a.size()+i-1,c,a.size()+next-1);
}
if (b.isFinal(i))
res.add_final_state(a.size()+i-1);
}
return res;
}
public static String genOutput (NFA a){
String str = "";
str += a.size()+" "+a.symbols()+"\n";
for (Integer i:a.final_states)
str+=i+" ";
str+="\n";
for (int i=0; i<a.size(); i++)
for (int c=0; c<a.symbols(); c++)
if (a.m[i][c] != null && !a.m[i][c].isEmpty())
for (Integer next:a.m[i][c])
str+=i+" "+(char)(c+'a')+" "+next+"\n";
return str;
}
public static void run_tests(){
//String[] tests = {"a1.in", "a2.in", "a3.in", "a4.in", "a5.in", "a6.in", "a8.in"};
String[] tests = {"t.in"};
for (String test:tests) {
NFA a = new NFA(test);
long startTime = System.nanoTime();
int r = hopcroft(a);
long endTime = System.nanoTime();
long duration = (endTime - startTime)/1000000; //divide by 1000000 to get milliseconds.
//System.out.println(a);
//System.out.println(rev(a));
NFA min = det(rev(det(rev(a))));
int rp=0;
if (isTotal(min))
rp = min.size();
else rp = min.size()+1;
//System.out.println(det(rev(det(rev(a)))));
if (r == rp)
System.out.println("Test passed [" + duration + " ms] - min states="+r);
else
System.out.println("Test " + test + " failed ! r="+r+" vs "+rp);
}
}
public static void gen_tests () {
NFA a = new NFA("a2.in");
//System.out.println(a);
int rep = 10;
while (rep > 0){
a = concatenate(a,a);
rep--;
}
System.out.println(genOutput(a));
}
// final version
public static void acm (){
}
public static void main (String args[]) throws IOException {
BufferedReader reader = new BufferedReader(new FileReader("robo.in"));
Integer test_no = Integer.parseInt(reader.readLine());
PrintWriter out = new PrintWriter("robo.out");
while (test_no > 0){
out.println(hopcroft(new NFA(reader)));
test_no --;
}
reader.close();
out.close();
//run_tests();
//gen_tests();
}
}
/*
class DFA {
private int state_no, symbol_no;
int [][] m; // state per symbol,
HashMap<Integer,HashMap<Integer,List<Integer>>> invm; // invm is the inverse matrix
List<Integer> final_states;
boolean isFinal (Integer s){
return final_states.contains(s);
}
public DFA (int state_no, int symbol_no){
init(state_no,symbol_no);
}
private void init (int state_no, int symbol_no){
this.state_no = state_no;
this.symbol_no = symbol_no;
m = new int[state_no][symbol_no];
invm = new HashMap<Integer,HashMap<Integer,List<Integer>>>();
final_states = new LinkedList<Integer>();
}
public DFA(String filename){
try
{
BufferedReader reader = new BufferedReader(new FileReader(filename));
String line;
String[] toks;
line = reader.readLine(); // states and symbols
toks = line.split("\\s+");
init(Integer.parseInt(toks[0]), Integer.parseInt(toks[1]));
line = reader.readLine();
toks = line.split("\\s+");
for (String i:toks)
final_states.add(Integer.parseInt(i));
while ((line = reader.readLine()) != null)
{
toks = line.split("\\s+");
char c = toks[1].charAt(0);
Integer s = Integer.parseInt(toks[0]);
Integer sp = Integer.parseInt(toks[2]);
m[s][c - 'a'] = sp;
if (!invm.containsKey(sp)) // no container for symbol
invm.put(sp,new HashMap<Integer,List<Integer>>());
if(!invm.get(sp).containsKey(c - 'a')) // no reverse transition defined
invm.get(sp).put(c-'a',new LinkedList<Integer>());
invm.get(sp).get(c-'a').add(s);
}
reader.close();
}
catch (Exception e)
{
System.err.format("Exception occurred trying to read '%s'.", filename);
e.printStackTrace();
}
}
public int size (){ return state_no;}
public int symbols () {return symbol_no;}
public int final_states(){return final_states.size();}
public List<Integer> get_nonfinal_states(){
List<Integer> r = new LinkedList<Integer>();
for (int i = 0; i<state_no; i++)
if (!isFinal(i))
r.add(i);
return r;
}
public List<Integer> get_final_states(){
return final_states;
}
// returns the list of states from which a state in S is reachable via symbol
public List<Integer> inv (int symbol, List<Integer> S){
List<Integer> r = new LinkedList<Integer>();
for (Integer s:S) {
if (invm.containsKey(s))
if (invm.get(s).containsKey(symbol))
r.addAll(invm.get(s).get(symbol));
}
return r;
}
@Override
public String toString(){
String s = "# ";
for (int i=0; i<symbol_no; i++)
s += Character.toString((char)(i + 'a'))+" ";
s+="\n";
for (int i=0; i<state_no; i++){
s += Integer.toString(i)+" ";
for (int j = 0; j<symbol_no; j++)
s+= Integer.toString(m[i][j])+" ";
s += "\n";
}
return s;
}
}
*/
Stefan Ruseti stefanr