import java.io.IOException;
import java.nio.file.Files;
import java.nio.file.Paths;
import java.nio.file.StandardOpenOption;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map.Entry;
import java.util.TreeSet;
import java.util.concurrent.ExecutionException;
import java.util.concurrent.atomic.AtomicBoolean;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

/**
 * @author Two
 */
public class Grammar {

  static final Pattern replacePattern = Pattern.compile("\\p{IsAlphabetic}+\\->\\p{IsAlphabetic}+");

  public static Grammar fromInputLines(final String mapping, final String target) {
    final HashMap<String, String> replacements = new HashMap<>();
    final Matcher matcher = replacePattern.matcher(mapping);
    while (matcher.find()) {
      final String replacement = matcher.group();
      final int delimiter = replacement.indexOf("->");
      final String from = replacement.substring(0, delimiter);
      final String to = replacement.substring(delimiter + 2);
      replacements.put(to, from);
    }
    return new Grammar(replacements, target);
  }
  protected final HashMap<String, String> reversedRules;
  protected final String root;

  public Grammar(final HashMap<String, String> reversedRules, final String root) {
    this.reversedRules = reversedRules;
    this.root = root;
  }

  public boolean verifyWord(final String word) {
    TreeSet<String> wordConstructs = new TreeSet<>();
    wordConstructs.add(word);

    final AtomicBoolean found = new AtomicBoolean(false);
    while ((found.get() == false) && (wordConstructs.isEmpty() == false)) {
      wordConstructs = wordConstructs.parallelStream()
              .collect(TreeSet::new,
                      (list, wordConstruct) -> {
                        if (root.equals(wordConstruct)) {
                          found.set(true);
                        } else {
                          for (final Entry<String, String> entry : reversedRules.entrySet()) {
                            final String variable = entry.getKey();
                            int pos = wordConstruct.indexOf(variable);
                            while (pos >= 0) {
                              list.add(new StringBuilder().append(wordConstruct).replace(pos, pos + variable.length(), entry.getValue()).toString());
                              pos = wordConstruct.indexOf(variable, pos + 1);
                            }
                          }
                        }
                      },
                      TreeSet::addAll);
    }
    return found.get();
  }

  public static void main(String[] args) throws IOException, InterruptedException, ExecutionException {
    if (args.length < 1) {
      System.err.println("Usage: Grammar <inputFile>");
    } else {
      final List<String> resultLines = new LinkedList<>();
      final List<String> lines = Files.readAllLines(Paths.get(args[0]));
      int offset = 0;
      for (int i = lines.size() / 5; i > 0; --i) {
        final Grammar grammar = fromInputLines(lines.get(offset + 2), lines.get(offset + 3));
        final StringBuilder resultBuilder = new StringBuilder();
        for (final String word : lines.get(offset + 4).split(",")) {
          resultBuilder.append(word).append(":").append(grammar.verifyWord(word)).append("; ");
        }
        resultLines.add(resultBuilder.toString());
        offset += 5;
      }
      Files.write(Paths.get("output.txt"), resultLines, StandardOpenOption.CREATE, StandardOpenOption.TRUNCATE_EXISTING);
    }
  }
}