IOIOI Solver (v16, most recent one) [738]

!7

import java.text.DecimalFormat;


public class main {
  sinterface Function {
    public Object process(Object in);
    public void toJava_process(Code code);
  }
  
  sinterface ReversibleFunction extends Function {
    public Object unprocess(Object in);
    public void toJava_unprocess(Code code);
  }
  
  // generic learner (works on objects)
  sinterface Learner {
    public void processInOut(Object in, Object out);
    public Object processIn(Object in);
    public void toJava(Code code);
    public void tryAgain();
  }
  
  abstract sclass Base {
    void printVars() {
      new StringBuilder buf;
      Field[] fields = getClass().getDeclaredFields();
      for (Field field : fields) {
        if ((field.getModifiers() & Modifier.STATIC) != 0)
          continue;
        Object value;
        try {
          value = field.get(this);
        } catch (Exception e) {
          value = "?";
        }
        
        if (main.nempty(buf)) buf.append(", ");
        buf.append(field.getName() + "=" + value);
      }
      System.out.println(buf.toString());
    }
    
    String name() {
      return getClass().getName().replaceAll("^main\\$", "");
    }
    
    void debug(String s) {
      System.out.println(name() + ": " + s);
    }
  }
  
  abstract sclass LearnerImpl extends Base implements Learner {
    public void tryAgain() {
      throw new RuntimeException("No try again");
    }
    
    public void toJava(Code code) {
      main.todo();
    }
  }
  
  abstract sclass FunctionImpl extends Base implements Function {
    public void toJava_process(Code code) {
      main.todo();
    }
  }
  
  abstract sclass ReversibleFunctionImpl extends FunctionImpl implements ReversibleFunction {
    public void toJava_unprocess(Code code) {
      main.todo();
    }
  }
  
  sclass Code {
    new StringBuilder buf;
    String var = "in";
    String indent = "";
    new List<String> translators;
    new List<String> varStack;
    int varCounter;
    
    *() {
      translators.add("!636");
    }
    
    void line(String line) {
      buf.append(indent).append(line).append('\n');
    }
    
    void indent() {
      indent += "  ";
    }
    
    void unindent() {
      indent = indent.substring(0, indent.length()-2);
    }
    
    void translators(String... ids) {
      for (String id : ids)
        if (! translators.contains(id)) // space is needed otherwise translator 636 is fooled :)
          translators.add(id);
    }
    
    String getTranslators() {
      // TODO: We should really fix the "standard functions" translator
      // to properly find the main class.
      //
      // As a hack, we move it upwards (before classes adding)
      int i = translators.indexOf("!standard functions");
      if (i >= 0) {
        translators.remove(i);
        translators.add(0, "!standard functions");
      }
      
      return main.fromLines(translators);
    }
  
    String s() {
      return "((String) " + var + ")";
    }
    
    String list() {
      return "((List) " + var + ")";
    }
    
    void assign(String exp) {
      line(var + " = " + exp + ";");
    }
    
    void newVar() {
      varStack.add(var);
      var = "_v" + (++varCounter);
      line("Object " + var + ";");
    }
    
    void oldVar() {
      var = varStack.get(varStack.size()-1);
      varStack.remove(varStack.size()-1);
    }
  }

  // The following field is filled by JavaX.
  static Object androidContext;
  
  static final String ALL = "#681";
  static final String DEFAULT_STRATEGY = "#1000464";
  static int maxCaseSize = 100000;
  
  static boolean classic = false;
  
  static new List<Case> cases;
  static new HashMap<String, Case> casesByID;
  static boolean testJava = false, showFails, execTasks = false;
  static boolean collectClosest = false; // saves time
  static boolean verboseMonitor = false, extensiveMode = false;
  static boolean verbose;
  static new (Hash)Set<String> parseErrors;
  static int caseIdx;
  static new (Hash)Set<Class> debuggedClasses;
  static new List<Throwable> strategyParseErrors;
  static Learner trying;
  static String user, pass;
  static boolean edit, stayAlive, printStrategy;
  static new List<String> strategies;
  static new List<String> backStrategies;
  
  static {
    strategies.add(DEFAULT_STRATEGY);
    // need to do here because there are multiple entry points,
    // such as quickSolve()
  }

  psvm {
   try {
    keepAlive();
    setOpt(getJavaX(), "androidContext", androidContext);
    long startTime = System.currentTimeMillis();
    
    new List<String> snippetIDs;
    new List<String> inputs;
    new List<String> inputDocs;
    new List<Case> userCases;
    
    for (int i = 0; i < args.length; i++) {
      String arg = args[i];
      if (arg.equals("debug"))
        debugOn(args[++i]);
      else if (arg.equals("user"))
        user = args[++i];
      else if (arg.equals("pass")) {
        pass = args[++i];
        args[i] = "hidden";
      } else if (arg.equals("edit"))
        edit = true;
      else if (arg.equals("in")) {
        String in = args[++i];
        //System.out.println("in=" + quote(in));
        String quoteUnquote = unquote("\"" + in + "\"");
        //System.out.println("now in=" + quote(quoteUnquote));
        inputs.add(quoteUnquote);
      } else if (arg.equals("in-doc"))
        inputDocs.add(args[++i]);
      else if (arg.equals("-notestjava"))
        testJava = false;
      else if (arg.equals("-testjava"))
        testJava = true;
      else if (arg.equals("verbose"))
        verbose = true;
      else if (arg.equals("closest"))
        collectClosest = true;
      else if (arg.equals("-withexec"))
        execTasks = true;
      else if (arg.equals("-showfails"))
        showFails = true;
      else if (arg.equals("-classic"))
        classic = true;
      else if (arg.equals("-stayalive"))
        stayAlive = true;
      else if (arg.equals("-printstrategy"))
        printStrategy = true;
      else if (arg.equals("strategy"))
        strategies.add(args[++i]);
      else if (arg.equals("backstrategy"))
        backStrategies.add(args[++i]);
      else if (arg.equals("onlystrategy")) {
        strategies.clear();
        strategies.add(args[++i]);
      } else if (arg.equals("extensive") || arg.equals("-extensive"))
        extensiveMode = true;
      else if (arg.equals("big"))
        maxCaseSize = Integer.MAX_VALUE;
      else if (arg.equals("all"))
        snippetIDs.add(ALL);
      else if (isSnippetID(arg))
        snippetIDs.add(arg);
      else
        System.err.println("Unknown argument: " + arg + ", ignoring");
    }
    
    strategies.addAll(backStrategies);
    backStrategies.clear();
    
    if (snippetIDs.isEmpty()) {
      String s = loadTextFile("input/input.txt", null);
      if (s != null)
        parse(s);
      else
        parse(ALL);
    }
    
    for (String snippetID : snippetIDs)
      try {
        Case case = parse(snippetID);
        if (case != null) {
          case.halfExamples.addAll(inputs);
          for (String docID : inputDocs)
            case.halfExamples.add(loadSnippet(docID));
          userCases.add(case);
        }
      } catch (Throwable e) {
        e.printStackTrace();
        parseErrors.add(snippetID);
      }
    
    int solved = 0, n = cases.size(), goodJava = 0;
    for (caseIdx = 0; caseIdx < n; caseIdx++) {
      Case case = cases.get(caseIdx);
      try {
        calculate(case);
      } catch (Throwable e) {
        e.printStackTrace();
      }
      if (case.winner != null)
        ++solved;
      if (case.goodJava)
        ++goodJava;
      if (caseIdx+1 == solved)
        System.out.println((caseIdx+1) + " case(s) processed & solved.");
      else
        System.out.println((caseIdx+1) + " case(s) processed, " + solved + " solved.");
      if (testJava && goodJava < solved)
        System.out.println((solved-goodJava) + " case(s) with BAD JAVA.");
    }

    print ""    
    print "----"

    List<Case> sorted = casesSortedByID();
    boolean allSolved = solved == n;
    if (!allSolved) {
      System.out.println();
      System.out.println("Unsolved:");
      for (Case case : sorted)
        if (case.winner == null)
          System.out.println("  " + case.id + (case.name == null ? "" : " - " + case.name));
    }
    if (solved != 0) {
      System.out.println();
      System.out.println("Solved:");
      for (Case case : sorted)
        if (case.winner != null)
          System.out.println("  " + case.id + (case.name == null ? "" : " - " + case.name));
    }
    if (testJava && solved > goodJava) {
      System.out.println();
      System.out.print("Bad Java: ");
      for (Case case : sorted)
        if (case.winner != null && !case.goodJava)
          System.out.print(case.id + " ");
      System.out.println();
    }
    if (!parseErrors.isEmpty()) {
      System.out.print("\nParse errors: ");
      for (String id : parseErrors)
          System.out.print(id + " ");
      System.out.println();
    }
    if (!strategyParseErrors.isEmpty())
      System.out.println("Strategy parse errors!");
    System.out.println();
    if (allSolved && testJava && goodJava < solved)
      System.out.println("ALL SOLVED (" + solved + "), but some BAD JAVA.");
    else {
      System.out.println(allSolved ? "ALL SOLVED (" + solved + ")" : "Solved " + solved + " out of " + n + ".");
      if (testJava)
        if (goodJava == solved)
          System.out.println("All Java code OK" + (allSolved ? "" : " (for solved cases)") + ".");
        else
          System.out.println("Some bad Java.");
      else
        System.out.println("Java not tested.");
    }
    print ""

    if (edit) {
      if (userCases.size() != 1) fail("Edit: More than one user case, confused");
      Case case = userCases.get(0);
      for (String docID : inputDocs) {
        Object _out = case.processIn(loadSnippet(docID));
        if (!(_out instanceof String))
          fail("Case did not generate a string: " + structure(_out));
        String out = cast _out;
        String editInfo = "Solver #" + programID() + " " + join(" ", args);
        editSnippetText(docID, out, editInfo);
      }
    }

    /*long time = getUserTime();
    if (time >= 0)
      System.out.println("User time: " + formatDouble(time/1e9, 3) + "s");*/
      
    long time = System.currentTimeMillis()-startTime;
    System.out.println("Real time: " + formatDouble(time/1e3, 3) + "s");
    System.gc();
    Runtime runtime = Runtime.getRuntime();
    System.out.println("Used memory: "
            + (runtime.totalMemory() - runtime.freeMemory()+1024*1024-1) / (1024*1024) + " MB" + ", total: " + (runtime.totalMemory()+1024*1024-1)/(1024*1024) + " MB");
            
    if (stayAlive) {
      System.out.println("Staying alive.");
      Thread.sleep(1000*60*60*24); // for VisualVM and such
    }
   } catch (Throwable e) {
    e.printStackTrace();
   }
  } // end of main method
  
  public static String formatDouble(double d, int digits) {
    String format = "0.";
    for (int i = 0; i < digits; i++) format += "#";
    String s = new DecimalFormat(format).format(d);
    return s.replace(',', '.'); // hack german -> english
  }
  
  /** Get user time in nanoseconds. */
  public static long getUserTime( ) {
    ThreadMXBean bean = ManagementFactory.getThreadMXBean();
    return bean.isCurrentThreadCpuTimeSupported() ?
      bean.getCurrentThreadUserTime() : -1L;
  }
  
  static class Case {
    String id, name;
    new List<Object[]> fullExamples;
    new List<Object> halfExamples;
    List<Object[]> examples1, examples2;
    Learner winner;
    RunnersUp runnersUp = collectClosest ? new RunnersUp() : null;
    boolean goodJava;
    List<Case> combined;
    int splitPoint = -1;
    
    // stats
    int learnersTried, retries;

    void split() {    
      if (examples1 != null)
        return; // already done
      if (fullExamples.isEmpty())
        throw new RuntimeException("No full examples");
      if (splitPoint < 0)
        splitPoint = fullExamples.size()-1;
      System.out.println("Full examples: " + fullExamples.size() + ", splitPoint: " + splitPoint + (halfExamples.isEmpty() ? "" : ", half examples: " + halfExamples.size()));
      examples1 = fullExamples.subList(0, splitPoint);
      examples2 = fullExamples.subList(splitPoint, fullExamples.size());
    }
    
    void add(Case case) {
      combined.add(case);
      fullExamples.addAll(case.fullExamples);
      halfExamples.addAll(case.halfExamples);
    }
    
    Object processIn(Object in) {
      return winner.processIn(in);
    }
    
    int size() {
      return structureSize(fullExamples);
    }
    
    static int structureSize(Object o) {
      if (o == null) return 0;
      if (o instanceof String) return ((String) o).length();
      int size = 0;
      if (o instanceof Collection)
        for (Object x : (Collection) o)
          size += structureSize(x);
      else if (o.getClass().isArray()) {
        int n = Array.getLength(o);
        for (int i = 0; i < n; i++)
          size += structureSize(Array.get(o, i));
      }
      return size;
    }

    void checkSize() {    
      int size = size();
      if (size > maxCaseSize)
        fail("Ignoring case - too big: " + id);
    }
    
    bool solved() {
      ret winner != null;
    }
  }

  static Case parse(String arg) tex {
   try {
    if (arg == null) return null;
    arg = arg.trim();
    if (arg.length() == 0) return null;
    new Case case;
    String text;
    
    if (casesByID.containsKey(arg))
      return casesByID.get(arg);
      
    if (arg.startsWith("Combine")) {
      case.id = "Combine";
      case.combined = new ArrayList<Case>();
      List<String> tok = javaTok(arg);
      new List<String> ids;
      for (int i = 5; i < tok.size(); i += 6) { // skip # and "and"
        if (verbose)
          System.out.println("Combine: Parsing " + tok.get(i));
        Case case2 = parse("#" + tok.get(i));
        case.id += " #" + tok.get(i);
        cases.remove(case2);
        case.add(case2);
      }
      addCase(case);
      return case;
    }
    
    if (verbose)
      System.out.println("parse: testing snippet ID");
      
    if (isSnippetID(arg)) {
      case.id = arg;
      String[] x = loadSnippetAndTitle(arg);
      text = x[0];
      case.name = x[1];
    } else {
      case.id = "direct (" + shorten(arg, 10) + ")";
      text = arg;
    }

    if (verbose)
      System.out.println("parse: testing snippet ID done " + quote(text));
      
    // it's a collection of cases!
    if (text.trim().startsWith("#") || text.trim().startsWith("Combine")) {
      for (String line : toLines(text))
        if (isSnippetID(line))
          parse(line);
        else if (line.trim().length() != 0)
          fail("Unknown line: " + line);
      return null;
    }
    
    // it's a "Continue:" task - transform to I/O format
    if (text.trim().startsWith("Continue:")) {
      List<String> lines = toLines(text);
      new StringBuilder buf;
      for (int i = 1; i < lines.size(); i++) {
        buf.append("In: " + quote("" + i) + "\n");
        buf.append("Out: " + quote(lines.get(i)) + "\n");
      }
      int numAsking = 3;
      for (int i = lines.size(); i < lines.size()+numAsking; i++)
        buf.append("In: " + quote("" + i) + "\n");
      text = buf.toString();
    }
      
    // it's an "Execute." task - run Java(X) and transform to I/O format
    if (text.trim().startsWith("Execute.")) {
      if (!execTasks) return null;
      List<String> tok = javaTok(text);
      new StringBuilder buf;
      for (int i = 5; i < tok.size(); i += 2) {
        if (tok.get(i).equals("-") && tok.get(i+2).equals("-")) {
          i += 2;
          buf.append("--\n");
        } else {
          String code = unquote_fixSpaces(tok.get(i));
          String result = execute("!636\n" + code);
          buf.append("In: " + quote(code) + "\n");
          buf.append("Out: " + quote(result) + "\n");
        }
      }
      text = buf.toString();
    }

    if (text.trim().startsWith("Marking.")) {
      List<String> tok = javaTok(text);
      new StringBuilder buf;
      if (verbose)
        System.out.println("Is marking.");
      for (int i = 5; i < tok.size(); i += 2) {
        if (tok.get(i).equals("-") && tok.get(i+2).equals("-")) {
          i += 2;
          buf.append("--\n");
        } else if (tok.get(i).equals("Doc") && tok.get(i+2).equals(":") && tok.get(i+4).equals("#")) {
          if (verbose)
            System.out.println("Loading subsnippet: " + tok.get(i+6));
          String out = loadSnippet(tok.get(i+6));
          i += 6;
          String in = out.replace("[[", "").replace("]]", "");
          buf.append("In: " + quote(in) + "\n");
          buf.append("Out: " + quote(out) + "\n");
        } else {
          String out = unquote_fixSpaces(tok.get(i));
          String in = out.replace("[[", "").replace("]]", "");
          buf.append("In: " + quote(in) + "\n");
          buf.append("Out: " + quote(out) + "\n");
        }
      }
      text = buf.toString();
    }
 
    //System.out.println(text);
    String in = null;
    
    if (verbose)
      System.out.println("parse: JavaToking " + quote(text));
    
    // parse a standard IOIOI document (Ins and Outs)
    
    List<String> tok = javaTok(text);
    for (int i = 1; i < tok.size(); i += 2) {
      String t = tok.get(i), t2 = i+2 < tok.size() ? tok.get(i+2) : "";
      
       if (t.equalsIgnoreCase("Cmd") && t2.equals("-") && tok.get(i+4).equalsIgnoreCase("Hint") && tok.get(i+6).equals(":")) { // "Cmd-Hint:"
        i += 8;
        int j = findNextLine(tok, i);
        String cmdHint = unquote_fixSpaces(join(tok.subList(i, j-1))); // result unused as of now
        i = j-2;
      } else if (t.equals("-") && t2.equals("-")) {
        i += 2;
        case.splitPoint = case.fullExamples.size();
        //System.out.println("t=" + t + ", t2= " + t2);
      } else if (t.toUpperCase().startsWith("I") && t2.equals("-") && tok.get(i+4).toUpperCase().equals("DOC") && tok.get(i+6).equals(":")) { // "In-Doc:"
        if (in != null)
          case.halfExamples.add(in);
        i += 8;
        int j = findNextLine(tok, i);
        String inID = unquote_fixSpaces(join(tok.subList(i, j-1)));
        in = loadSnippet(inID);
        i = j-2;
      } else if (t.toUpperCase().startsWith("I") && t2.equals(":")) { // "In:" or "I:"
        if (in != null)
          case.halfExamples.add(in);
        i += 4;
        int j = findNextLine(tok, i);
        in = unquote_fixSpaces(join(tok.subList(i, j-1)));
        i = j-2;
      } else if ((swic(t, "O") || eqic(t, "Expect")) && t2.equals(":")) { // "Out: " or "O: " or "Expect: "
        i += 4;
        int j = findNextLine(tok, i);
        String out = unquote_fixSpaces(join(tok.subList(i, j-1)));
        i = j-2;
        if ((in + out).indexOf('\t') >= 0)
          System.err.println("WARNING: Tab character used!");
          
        System.out.println(shorten(quote(in), 80) + " => " + shorten(quote(out), 80));
        case.fullExamples.add(new Object[] {in, out});
        case.checkSize();
        in = null;
      } else if (t.toUpperCase().startsWith("O") && t2.equals("-") && tok.get(i+4).toUpperCase().equals("LIST") && tok.get(i+6).equals(":")) { // "Out-List:"
        i += 8;
        if (!tok.get(i).equals("{")) fail("Syntax error in Out-List");
        i += 2;
        new List<String> outList;
        while (!tok.get(i).equals("}")) {
          if (tok.get(i).equals(",")) i += 2;
          if (tok.get(i).equals("}")) break;
          String listEntry = unquote(tok.get(i));
          outList.add(listEntry);
          i += 2;
        }
        System.out.println(shorten(quote(in), 80) + " => list of " + outList.size());
        case.fullExamples.add(new Object[] {in, outList});
        case.checkSize();
        in = null;
      } else {
        int j = findNextLine(tok, i);
        String line = join(tok.subList(i, j-1));
        i = j-2;
        System.out.println("-- Ignoring line: " + line);
      }
    }
    
    if (in != null)
      case.halfExamples.add(in);
    addCase(case);
    return case;
   } catch (Throwable e) {
    parseErrors.add(arg);
    e.printStackTrace();
    return null;
   }
  }
  
  static String unquote_fixSpaces(String s) {
    String _ = unquote(s);
    if (s.startsWith("[["))
      _ = fixSpaces(_);
    return _;
  }
  
  // remove invisible spaces at end of line - this will otherwise confuse the engine(s) greatly...
  static String fixSpaces(String s) {
    System.out.println(quote(s));
    s = s.replaceAll("[\t ]+(\r?\n)", "$1");
    s = s.replaceAll("[\t ]+$", "");
    //System.out.println("_fixSpaces => " + quote(s));
    return s;
  }
  
  // i is a code-token (odd index)
  // return value is also a code token, or end of list
  static int findNextLine(List<String> tok, int i) {
    while (i < tok.size() && tok.get(i-1).indexOf('\n') < 0)
      i += 2;
    return i;
  }
  
  static void addCase(Case case) {
    cases.add(case);
    casesByID.put(case.id, case);
  }
  
  static void calculate(Case case) tex {
    System.out.println("\n== CASE " + newLinesToBars(case.id) + " ==");
    
    case.split();
    Learner learner = findOKLearner(case);
    if (learner == null) {
      String stat = "";
      if (case.retries != 0) stat = " + " + case.retries + " retries";
      System.out.println("\nProblem not solved (" + case.learnersTried + " learners tried" + stat + ")");
      RunnersUp ru = case.runnersUp;
      if (ru != null && ru.winner != null)
        System.out.println("Closest result: " + quote(ru.bestResult) + " instead of " + quote(ru.expected) + " (score " + ru.bestScore + ") by " + structure(ru.winner));
    } else {
      print "\nSolved!"
      new structure_Data data;
      data.stringSizeLimit = 40;
      print("  " + structure(learner, data) + "\n");
      case.winner = learner;
      String java = null;
      new Code code;
      if (testJava) try {
        learner.toJava(code);

        if (testJava)
          testJava(case, code); // prints "GOOD JAVA" or "BAD JAVA"
        else
          print "Java:"
          
        java = code.getTranslators() + code.buf.toString();
        System.out.println(indent("  ", java));
      } catch (Throwable e) {
        print "BAD JAVA"
      }
      
      if (isSnippetID(case.id))
        updateMyCommentOnSnippet(case.id, "Solved!\n\nDetails:\n" + structure(learner) + (java == null ? "" : "\n\nJava:\n" + indent("  ", java)));
        
      for (Object in : case.halfExamples) {
        Object out = learner.processIn(in);
        System.out.println(structure(in) + " =>! " + structure(out));
      }
    }
  }

  static void choice_orderList(List l) {
  }
  
  static Learner findOKLearner(Case case) tex {
    List<Learner> list = makeLearners(case);
    choice_orderList(list);
    for (Learner learner : list) try {
      if (learnerOK(learner, case))
        return learner;
    } catch (Throwable e) {
      if (showFails)
        e.printStackTrace();
    }
    
    if (case.combined != null) {
      Case switchCase = makeSwitchCase(case);
      calculate(switchCase);
      Learner learner = switchCase.winner;
      if (learner != null)
        return new LSwitch(case, learner);
    }
    
    return null;
  }
  
  static Case makeSwitchCase(Case case) {
    int i = 0;
    Case s = new Case();
    s.id = "Switch " + case.id;
    s.examples1 = new ArrayList<Object[]>();
    s.examples2 = new ArrayList<Object[]>();
    for (Case c : case.combined) {
      ++i;
      for (Object[] e : c.examples1)
        s.examples1.add(new Object[] {e[0], String.valueOf(i)});
      for (Object[] e : c.examples2)
        s.examples2.add(new Object[] {e[0], String.valueOf(i)});
      for (Object[] e : c.fullExamples)
        s.fullExamples.add(new Object[] {e[0], String.valueOf(i)});
    }
    return s;
  }
  
  static boolean learnerOK(Learner learner, Case case) {
    trying = learner;
    
    try {
      Object[] _e = null;
      try {
        if (case.examples1 == null)
          fail("Case not calculated: " + case.id);
          
        ++case.learnersTried;
        for (Object[] e : case.examples1) {
          _e = e;
          learner.processInOut(e[0], e[1]);
        }
        
        // full validation against all examples - but starting with the unknown ones to make coding easier for learners
        int retry = 0;
        retryLoop: while (true) {
          int n = case.fullExamples.size();
          for (int i = 0; i < n; i++) {
            Object[] e = case.fullExamples.get((i+case.examples1.size()) % n);
            _e = e;
            Object out = learner.processIn(e[0]);
            if (!resultsEqual(e[1], out)) {
            
              if (case.runnersUp != null && e[1] instanceof String && out instanceof String)
                case.runnersUp.add((String) e[1], (String) out, leven((String) out, (String) e[1]), learner);
                
              if (debuggedClasses.contains(learner.getClass()) || showFails) {
                System.out.println("[fail] " + structure(learner) + " on " + structure(e[0]) + " - got: " + structure(out) + " rather than: " + structure(e[1]));
                if (e[1] instanceof String && out instanceof String)
                  System.out.println("Leven distance: " + leven((String) e[1], (String) out)); 
              }
              ++retry;
              ++case.retries;
              if (retry % 1000 == 0)
                System.err.println("Retry " + retry);
              learner.tryAgain();
              continue retryLoop;
            }
          }
          return true;  // all test examples passed
        }
      } catch (Throwable e) {
        if (debuggedClasses.contains(learner.getClass()) || showFails) {
          e.printStackTrace();
          System.err.println("[fail] " + structure(learner) + " on " + (_e == null ? "?" : structure(_e[0])) + " - " + e);
        }
        return false;
      }
    } finally {
      trying = null;
    }
  }
  
  static boolean resultsEqual(Object a, Object b) {
    if (a instanceof String && b instanceof String)
      return ((String) a).replace("\r", "").equals(((String) b).replace("\r", ""));
    else return a.equals(b);
  }
  
  static boolean validate(String[] example, Learner learner) {
    try {
      String out = (String) learner.processIn(example[0]);
      if (!example[1].equals(out)) {
          //System.out.println("[fail] " + learner + " on " + quote(e[0]) + " - got: " + quote(out) + " rather than: " + quote(e[1]));
          return false;
        }
      return true;
    } catch (Throwable e) {
      silentException(e);
      return false;
    }
  }
  
  static void silentException(Throwable e) {
  }
  
  static List<Learner> makeLearners() {
    ret makeLearners(null);
  }
  
  static List<Learner> makeLearners(Case case) ctex {
    new List<Learner> list;
    
    // process hints in comments on IOIOI snippet
    
    if (case != null && isSnippetID(case.id)) {
      List<Comment> comments = getSnippetComments(case.id);
      System.out.println(case.id + ": " + comments.size() + " comment(s).");
      for (Comment c : comments) try {
        if (verbose)
          System.out.println("Processing hint: " + c.text);
        processHint(c.text, list);
      } catch (Throwable e) {
        e.printStackTrace();
      }
    }
    
    // apply strategies
    for (String strategy : strategies) {
      String s = isSnippetID(strategy) ? loadSnippet(strategy) : strategy;
      s += "\n" + combineClasses();
      
      if (printStrategy)
        System.out.println("Strategy:\n" + s);
        
      list.addAll(parseStrategy(s));
      if (classic)
        list.addAll(classicLearners()); // Endlosschleife!?
    }
    
    // return list
    return list;
  }
  
  static void processHint(String text, List<Learner> list) {
    List<String> tok = javaTok(text);
    if (tok.size() > 5)
      if (tok.get(1).equals("try") && tok.get(3).equals("regexp")) {
        String re = unquote(tok.get(5));
        System.out.println("re: " + re);
        list.add(new LUse(new FRegExp(re)));
      }
      
    Matcher m = Pattern.compile("(?:LHotwire\\(programID=\"||hotwire\\s+)(#\\d+)").matcher(text);
    if (m.find()) {
      String programID = m.group(1);
      if (isJavaxSafe(programID))
        list.add(new LHotwire(programID));
    }
  }
  
  static String[] extensiveLearners = {
    "LFunctionPlusPrevious",
    "LCombineTwoFunctions",
    "LCombineTwoFunctions2"
  };
  
  static List<Class> extensiveLearnerClasses;
  
  static boolean isExtensive(Class c) {
    if (extensiveLearnerClasses == null) {
      extensiveLearnerClasses = new ArrayList<Class>();
      for (String s : extensiveLearners) {
        Class cc = findClassFlex(s);
        if (cc != null)
          extensiveLearnerClasses.add(cc);
      }
    }
    return extensiveLearnerClasses.contains(c);
  };
  
  static boolean extensiveOK(Class c) {
    return extensiveMode || !isExtensive(c);
  }
  
  static String combineClasses() {
    new StringBuilder buf;
    for (Class c : myNonAbstractClassesImplementing(Learner)) {
      continue unless extensiveOK(c);
      //System.out.println("combineClasses: " + c);
      if (hasConstructor(false, c))
        buf.append(getName(c) + "\n");
      for (String s2 : myInnerClasses())  {
        Class c2 = findClass(s2);
        if (c2 == null) continue;
        if (isAbstract(c2) || !hasConstructor(false, c2)) continue; // no default constructor
        boolean ctr = hasConstructor(false, c, c2);
        /*if (c == LUse.class)
          System.out.println("combineClasses: Checking LUse " + c2+ ", ctr=" + ctr);*/
        if (c2 != null && ctr && extensiveOK(c2))
          buf.append(getName(c) + " " + getName(c2) + "\n");
      }
    }
    return buf.toString();
  }
  
  static List<Learner> parseStrategy(String strategyText) ctex {
    List <String> lines = toLines(strategyText);
    new List<Learner> list;
    for (String s : lines) try {
      s = s.trim();
      L<S> parts = javaTok(s);
      if (parts.size() == 1) continue;
      
      new Stack<Object> stack;
      for (int i = parts.size()-2; i >= 1; i -= 2) {
        String p = parts.get(i);
        if (p.startsWith("\"")) {
          stack.add(unquote(p));
          continue;
        }
        
        if (isInteger(p)) {
          if (i > 1 && parts.get(i-2).equals("#")) {
            i -= 2;
            p = "#" + p;
          }
          stack.add(p);
          continue;
        }

        Class c = findClassFlex(p);
        if (c == null)
          fail("Strategy element " + p + " not known");
        
        Constructor ctr = c.getDeclaredConstructors()[0];
        makeAccessible(ctr);
        Class[] types = ctr.getParameterTypes();
        try {
          if (types.length == 0)
            stack.add(ctr.newInstance());
          else if (types.length == 1) {
            if (stack.isEmpty())
              fail("Too few arguments for " + c.getName());
            stack.add(ctr.newInstance(stack.pop()));
          } else if (types.length == 2) {
            if (stack.size() < 2)
              fail("Too few arguments for " + c.getName());
            Object a = stack.pop();
            Object b = stack.pop();
            stack.add(ctr.newInstance(a, b));
          } else
            fail("bla");
        } on fail {
          print("Was calling constructor: " + ctr);
        }
      }
      
      list.add((Learner) stack.peek());
    } catch (Throwable e) {
      print("Strategy parse error.");
      printIndent("STRAT> ", strategyText);
      e.printStackTrace();
      strategyParseErrors.add(e);
    }
    return list;
  }

  static List<Learner> classicLearners() {
    new List<Learner> list;
    list.addAll(level1());
    list.add(new LBox(new LMulti(level1())));
    list.add(new LBox2(new LMulti(level1())));
    
    list.add(new LChange(new FCommonPrefix(), new LOutPattern()));
    list.add(new LChange(new FCommonSuffix(), new LOutPattern()));
    
    list.add(new LEmptyBox(new LMulti(level1())));
    
    list.add(new LChange(new RFToLines(), new LFixedFunction(new FLength())));
    
    // for #1000455
    list.add(new LFindOutInIn(new LFixedSubstring()));
   
    for (int I = 1; I <= 2; I++)
    // for #1000457
    list.add(new LChange(new FDropFirstLines(I), new LMulti(
      new LFixWhitespace(l1()), level1())));

    // for #1000458
    list.add(new LFixWhitespace(l1()));

    return list;
  }

  static Learner l1() {
    return new LMulti(level1());
  }
  
  static List<Learner> level1() {
    new List<Learner> list;
    list.add(new LId()); // always good to have as included learner
    list.add(new LPrefixSuffix());
    list.add(new LSplitInput(new LOutPattern()));
    list.add(new LInputPattern());
    list.add(new LFixed());
    list.add(new LWrap(new RFJavaTok(), new LEach(new LFixedFunction(new EscapeCase()))));
    list.add(new LCharShift());
    list.add(new LOutSuffix(new LFirst(new LCharShift())));
    
    list.add(new LChange(new RFJavaTok(), new LMulti(
      new LChange(new FStringsOnly(), new LGetListElement()),
      new LChange(new FNumbersOnly(), new LMath()),
      new LChange(new FNumbersOnly(), new LMath2())
    )));
    
    // TODO - for #1000378
    list.add(new LChange(new RFJavaTok(), new LDistinguishList(new FIsString())));
    
    list.add(new LFixedSubstring());
    
    return list;
  }
  
  static void debugOn(String name) {
    try {
      Class c = findClassFlex(name);
      debuggedClasses.add(c);
      Field field;
      while (true)
        try {
          field = c.getDeclaredField("debug");
          break;
        } catch  (NoSuchFieldException e) {
          c = c.getSuperclass();
        }
      field.setBoolean(null, true);
    } catch (Exception e) {
      e.printStackTrace();
      System.err.println("Cannot debug class " + name);
    }
  }

static int choice(String text, int i) {
  return i;
}
  
  // splits the input at some point, takes only one part
  static class LSplitInput extends LearnerImpl {
    int splitIdx = 1; // split after first character
    Learner baseLearner;
    
    LSplitInput(Learner baseLearner) {
      this.baseLearner = baseLearner;
      splitIdx = choice("LSplitInput.i", splitIdx);
    }
    
    public void processInOut(Object _in, Object _out) {
      String in = (String) _in, out = (String) _out;
      in = in.substring(splitIdx);
      baseLearner.processInOut(in, out);
    }
    
    public Object processIn(Object _in) {
      String in = (String) _in;
      in = in.substring(splitIdx);
      return baseLearner.processIn(in);
    }
    
    public void toJava(Code code) {
      if (splitIdx != 0)
        code.line(code.var + " = ((String) " + code.var + ").substring(" + splitIdx + ");");
      baseLearner.toJava(code);
    }
  }

  static class FDropFirstLines implements Function {
    int n;
    *(int *n) {}

    public Object process(Object _in) {
      String in = (String)_in;
      for (int I=0; I < n; I++)
        in = in.substring(in.indexOf('\n')+1);
      return in;
    }
    
    public void toJava_process(Code code) {
      todo();
    }
  }
  
  // removes common suffix from out, delegates to base learner
  // just demo (only removes "!")
  static class LOutSuffix extends LearnerImpl {
    String suffixOut = "";
    Learner baseLearner;
    
    LOutSuffix(Learner baseLearner) {
      this.baseLearner = baseLearner;
    }
    
    public void processInOut(Object _in, Object _out) {
      String in = (String) _in, out = (String) _out;
      if (out.endsWith("!"))
        suffixOut = "!";
      if (out.endsWith(suffixOut))
        out = out.substring(0, out.length()-suffixOut.length());
      
      baseLearner.processInOut(in, out);
    }
    
    public Object processIn(Object _in) {
      String in = (String) _in;
      return baseLearner.processIn(in) + suffixOut;
    }
    
    public void toJava(Code code) {
      baseLearner.toJava(code);
      if (suffixOut.length() != 0)
        code.line(code.var + " = " + code.s() + "+" + quote(suffixOut) + ";");
    }
  }
  
  // if input appears in output in fixed pattern
  static class LOutPattern extends LearnerImpl {
    static boolean debug;
    String pattern = "%!%";

    public void processInOut(Object _in, Object _out) {
      String in = (String) _in, out = (String) _out;
      pattern = out.replace(in, "%!%");
      if (debug)
        System.out.println("LOutPattern: in=" + quote(in) + ", out=" + quote(out) + ", pattern=" + quote(pattern));
    }
    
    public String processIn(Object _in) {
      String in = (String) _in;
      return pattern.replace("%!%", in);
    }
    
    public void toJava(Code code) {
      code.line(code.var + " = " + quote(pattern) + ".replace(" + quote("%!%") + ", (String) " + code.var + ");");
    }
  }
  
  // simplets learner - only knows the "id" function
  static class LId extends LearnerImpl {
    public void processInOut(Object in, Object out) {
    }
    
    public Object processIn(Object in) {
      return in;
    }
    
    public void toJava(Code code) {
    }
  }
  
  !include #1000584 // LInputPattern
  
  static class LFixed extends LearnerImpl {
    static boolean debug;
    Object value;
    
    public void processInOut(Object in, Object out) {
      value = out;
      if (debug)
        printVars();
    }
    
    public Object processIn(Object in) {
      return value;
    }
    
    public void toJava(Code code) {
      code.line(code.var + " = " + quote((String) value) + ";");
    }
  }
  
  static void assertSameSize(List a, List b) {
    if (a.size() != b.size())
      fail("wrong list sizes");
  }

  // process lists in parallel
  // (in and out must be a list of same length)
  static class LEach extends LearnerImpl {
    static boolean debug;
    Learner base;
    
    LEach(Learner base) {
      this.base = base;
    }
    
    public void processInOut(Object _in, Object _out) {
      List in = (List) _in, out = (List) _out;
      assertSameSize(in, out);
      for (int i = 0; i < in.size(); i++)
        base.processInOut(in.get(i), out.get(i));
      if (debug)
        printVars();
    }
    
    public Object processIn(Object _in) {
      List in = (List) _in;
      List out = new ArrayList();
      for (Object x : in)
        out.add(base.processIn(x));
      return out;
    }
    
    public void toJava(Code code) {
      code.line("List out = new ArrayList();");
      code.line("for (Object x : (List) in) {");
      code.indent();
      code.line("in = x;");
      base.toJava(code);
      code.line("out.add(in);");
      code.unindent();
      code.line("}");
      code.line("in = out;");
    }
  }
  
  static class LChange extends LearnerImpl {
    Function f;
    Learner base;
    
    LChange(Function f, Learner base) {
      this.f = f;
      this.base = base;
    }
    
    public void processInOut(Object in, Object out) {
      in = f.process(in);
      base.processInOut(in, out);
    }
    
    public Object processIn(Object in) {
      in = f.process(in);
      return base.processIn(in);
    }
    
    public void toJava(Code code) {
      f.toJava_process(code);
      base.toJava(code);
    }
  }
  
  static class LFindOutInIn extends LearnerImpl {
    static boolean debug;
    Learner base;
    String findMarker1 = "{{", findMarker2 = "}}";
    
    *(Learner *base) {}
    
    public void processInOut(Object _in, Object _out) {
      String in = (String) _in, out = (String) _out;
      if (out.length() == 0)
        out = in;
      else {
        int i = in.indexOf(out);
        if (i < 0) throw new RuntimeException("error");
        int j = i+out.length();
        out = in.substring(0, i) + findMarker1 + in.substring(i, j) + findMarker2 + in.substring(j);
        if (debug)
          System.out.println("LFindOutInIn: index=" + i);
      }
      
      base.processInOut(in, out);
      
      if (debug)
        System.out.println("LFindOutInIn: Base learned. " + base);
    }
    
    public Object processIn(Object _in) {
      if (debug)
        System.out.println("LFindOutInIn: processIn");
      String in = (String) _in;
      String out = (String) base.processIn(in);
      int i = out.indexOf(findMarker1), j = out.indexOf(findMarker2, i)-2;
      String result = i < 0 ? "" : in.substring(i, j);
      if (debug)
        System.out.println("LFindOutInIn: processIn " + i + " " + j + " " + quote(result));
      return result;
    }
    
    public void tryAgain() {
      base.tryAgain();
    }
  }
  
  static class RFJavaTok implements ReversibleFunction {
    public Object process(Object in) {
      return javaTok((String) in);
    }
    
    public Object unprocess(Object in) {
      return join((List) in);
    }
    
    public void toJava_process(Code code) {
      code.translators("!636", "!class JavaTok");
      code.line(code.var + " = javaTok((String) " + code.var + ");");
    }
    
    public void toJava_unprocess(Code code) {
      code.translators("!636", "!class JavaTok");
      code.line(code.var + " = join((List) " + code.var + ");");
    }
  }
  
  static class RFToLines implements ReversibleFunction {
    public Object process(Object in) {
      return toLines((String) in);
    }
    
    public Object unprocess(Object in) {
      return fromLines((List) in);
    }
    
    public void toJava_process(Code code) {
      code.translators("!636", "!standard functions");
      code.assign("toLines(" + code.s() + ");");
    }
    
    public void toJava_unprocess(Code code) {
      code.translators("!636", "!standard functions");
      code.assign("fromLines(" + code.list() + ");");
    }
  }
  
  // works on a token list - makes a list of only the string constants (unquoted)
  static class FStringsOnly implements Function {
    static boolean debug;
    
    public Object process(Object _in) {
      new List<String> tok;
      for (String s : (List<String>) _in) {
        boolean isString = s.startsWith("\"") || s.startsWith("[[");
        if (isString)
          tok.add(unquote(s));
        if (debug)
          System.out.println("FStringsOnly - isString: " + isString + " - " + s);
      }
      return tok;
    }
    
    public void toJava_process(Code code) {
      code.translators("!standard functions");
      code.line("List<String> tok = new ArrayList<String>();");
      code.line("for (String s : (List<String>) " + code.var + ")");
      code.line("  if (s.startsWith(\"\\\"\") || s.startsWith(\"[[\")) tok.add(unquote(s));");
      code.assign("tok");
    }
  }
  
  // works on a token list - makes a list of only the number constants
  static class FNumbersOnly implements Function {
    static boolean debug;
    
    public Object process(Object _in) {
      new List<String> tok;
      for (String s : (List<String>) _in) {
        boolean isNumber = s.length() != 0 && (Character.isDigit(s.charAt(0)) || (s.charAt(0) == '-' && s.length() > 1));
        if (isNumber)
          tok.add(s);
        if (debug)
          System.out.println("FNumbersOnly - isNumber: " + isNumber + " - " + s);
      }
      return tok;
    }
    
    public void toJava_process(Code code) {
      code.line("List<String> tok = new ArrayList<String>();");
      code.line("for (String s : (List<String>) " + code.var + ")");
      code.line("  if (s.length() != 0 && (Character.isDigit(s.charAt(0)) || (s.charAt(0) == '-' && s.length() > 1))) tok.add(s);");
      code.assign("tok");
    }
  }
  
  static class FLength implements Function {
    static boolean debug;
    
    public Object process(Object in) {
      Object result = String.valueOf(in instanceof List ? ((List) in).size() : ((String) in).length());
      if (debug)
        System.out.println("FLength: " + result);
      return result;
    }
    
    public void toJava_process(Code code) {
      code.assign("String.valueOf(" + code.var + " instanceof List ? " + code.list() + ".size() : " + code.s() + ".length())");
    }
  }
  
  static class LFixedFunction extends LearnerImpl {
    Function f;
    
    LFixedFunction(Function f) {
      this.f = f;
    }
    
    public void processInOut(Object in, Object out) {
    }
    
    public Object processIn(Object in) {
      return f.process(in);
    }
    
    public void toJava(Code code) {
      f.toJava_process(code);
    }
  }
  
  // trivial stuff like taking the one element out of a 1-element list
  static class LTrivial extends LearnerImpl {
    public void processInOut(Object in, Object out) {
    }
    
    public Object processIn(Object in) {
      return ((List) in).get(0);
    }
    
    public void toJava(Code code) {
      code.assign(code.list() + ".get(0)");
    }
  }
  
  // get element of a list at fixed index
  static class LGetListElement extends LearnerImpl {
    static boolean debug;
    int i;
    
    public void processInOut(Object _in, Object out) {
      List in = (List) _in;
      i = in.indexOf(out);
      if (debug)
        System.out.println("LGetListElement: " + i + " " + out);
    }
    
    public Object processIn(Object in) {
      return ((List) in).get(i);
    }
    
    public void toJava(Code code) {
      code.assign(code.list() + ".get(" + i + ")");
    }
  }
  
  !include #1005157 // LMath
  !include #1005160 // LMath2
  
  static class EscapeCase implements Function {
    static boolean debug;
    
    public Object process(Object _in) {
      if (debug)
        System.out.println("EscapeCase: " + _in);
      String in = (String) _in;
      return in.equals("case") ? "_case" : in;
    }
    
    public void toJava_process(Code code) {
      code.line("if (\"case\".equals(" + code.var + ")) " + code.var + " = " + quote("_case") + ";");
    }
  }
  
  static class LCharShift extends LearnerImpl {
    int shift;
    
    public void processInOut(Object _in, Object _out) {
      String in = (String) _in, out = (String) _out;
      shift = (int) out.charAt(0) - (int) in.charAt(0);
    }
    
    public Object processIn(Object _in) {
      String in = (String) _in;
      char[] c = new char[in.length()];
      for (int i = 0; i < c.length; i++)
        c[i] = (char) ((int) in.charAt(i) + shift);
      return new String(c);
    }
    
    public void toJava(Code code) {
      code.line("char[] c = new char[((String) " + code.var + ").length()];");
      code.line("for (int i = 0; i < c.length; i++)");
      code.line("  c[i] = (char) ((int) ((String) " + code.var + ").charAt(i)" + (shift < 0 ? "" + shift : "+" + shift) + ");");
      code.line(code.var + " = new String(c);");
    }
  }
  
  // applies base learner to first char of string
  // (or first element of list, TODO)
  static class LFirst extends LearnerImpl {
    Learner baseLearner;
    
    *(Learner baseLearner) {
      this.baseLearner = baseLearner;
    }
    
    public void processInOut(Object _in, Object _out) {
      String in = (String) _in, out = (String) _out;
      if (in.length() == 0)
        return;
      String firstIn = in.substring(0, 1), firstOut = out.substring(0, 1);
      baseLearner.processInOut(firstIn, firstOut);
    }
    
    public Object processIn(Object _in) {
      String in = (String) _in;
      if (in.length() == 0)
        return in;
      String firstIn = in.substring(0, 1);
      return baseLearner.processIn(firstIn) + in.substring(1);
    }
    
    public void toJava(Code code) {
      code.line("if (" + code.s() + ".length() != 0) {");
      code.indent();
      code.line("String rest = " + code.s() + ".substring(1);");
      code.line(code.var + " = " + code.s() + ".substring(0, 1);");
      baseLearner.toJava(code);
      code.line(code.var + " = " + code.s() + "+rest;");
      code.unindent();
      code.line("}");
    }
  }
  
  static Method findMainMethod(Class<?> theClass) {
    for (Method method : theClass.getMethods())
      if (method.getName().equals("main") && method.getParameterTypes().length == 1)
        return method;
    throw new RuntimeException("Method 'main' with 1 parameter not found in " + theClass.getName());
  }
  
  static Method compileJavaInToOut(Code code) {
    try {
      String java = code.buf.toString();
      String prelude = /*"import java.util.*;\n\n" +*/
        "public class main { public static Object main(Object in) throws Exception {\n";
      String postlude = "\nreturn in;\n}}";
      String src = code.getTranslators() + "\n" + prelude + java + postlude;
      Class<?> mainClass = compileAndLoadMainClass(src);
      return findMainMethod(mainClass);
    } catch (Exception e) {
      throw new RuntimeException(e);
    }
  }
  
  static Method findCalcMethod(Class<?> theClass) {
    for (Method method : theClass.getMethods())
      if (method.getName().equals("calc"))
        return method;
    throw new RuntimeException("Method 'calc' not found in " + theClass.getName());
  }
  
  // for simplejava stuff (execute tasks)
  static String execute(String src) {
    try {
      Class<?> mainClass = compileAndLoadMainClass(src);
      Method m = findCalcMethod(mainClass);
      return String.valueOf(m.invoke(null));
    } catch (Exception e) {
      throw new RuntimeException(e);
    }
  }
  
  static void testJava(Case case, Code code) {
    try {
      Method m = compileJavaInToOut(code);
      
      for (Object[] e : case.fullExamples) {
        String out = (String) m.invoke(null, e[0]);
        
        if (!e[1].equals(out)) {
          throw new RuntimeException("[fail] Java code on " + structure(e[0]) + " - got: " + structure(out) + " rather than: " + structure(e[1]));
        }
      }
      
      System.out.println("\nGOOD JAVA.");
      case.goodJava = true;
    } catch (Throwable e) {
      if (showFails)
        e.printStackTrace();
      System.out.println("\nBAD JAVA.");
    }
  }
  
  static class LSwitch extends LearnerImpl {
    Case case;
    Learner switcher;
    
    *(Case case, Learner switcher) {
      this.case = case;
      this.switcher = switcher;
    }
    
    public void processInOut(Object in, Object out) {
    }
   
    public Object processIn(Object in) {
      int i = Integer.parseInt((String) switcher.processIn(in));
      return case.combined.get(i-1).winner.processIn(in);
    }
   
    public void toJava(Code code) {
      todo();
    }
  }
 
  static class LMulti extends LearnerImpl {
    static boolean debug;
    new List<Learner> candidates;
    
    *(Learner... learners) {
      for (Learner l : learners)
        candidates.add(l);
    }
    
    *(L<Learner> learners) {
      for (Learner l : learners)
        candidates.add(l);
    }

    *(Learner l, L<Learner> ll) {
       candidates.add(l);
      candidates.addAll(ll);
    }
    
    public void processInOut(Object in, Object out) {
      if (debug)
        System.err.println("LMulti candidates: " + candidates.size());
      for (ListIterator<Learner> i = candidates.listIterator(); i.hasNext(); ) {
        Learner l = i.next();
        try {
          l.processInOut(in, out);
        } catch (Throwable e) {
          if (debug) {
            e.printStackTrace();
            System.err.println("Removing candidate: " + structure(l));
          }
          silentException(e);
          i.remove();
        }
      }
      if (debug)
        System.err.println("LMulti candidates now: " + candidates.size());
      if (candidates.isEmpty())
        fail("no candidates left");
    }
    
    public Object processIn(Object in) {
      while (true) { // fails or returns eventually
        Learner l = candidates.get(0);
        if (debug)
          System.err.println("Using candidate: " + structure(l) + ", " + candidates.size() + " left");
        try {
          return l.processIn(in);
        } catch (Throwable e) {
          if (debug) {
            e.printStackTrace();
            System.err.println("Removing candidate: " + structure(l));
          }
          silentException(e);
          candidates.remove(0);
        }
      }
    }
    
    public void tryAgain() {
      candidates.remove(0);
    }
    
    public void toJava(Code code) {
      candidates.get(0).toJava(code);
    }
  }
  
  static class FIsString implements Function {
    static boolean debug;
    
    public Object process(Object _in) {
      String in = (String) _in;
      return in.startsWith("\"") || in.startsWith("[[") ? "1" : "0";
    }
    
    public void toJava_process(Code code) {
      code.assign(code.s() + ".startsWith(\"\\\"\") || " + code.s() + ".startsWith(\"[[\") ? \"1\" : \"0\"");
    }
  }
  
  static class FCommonPrefix implements Function {
    static boolean debug;

    public Object process(Object _in) {
      String in = (String) _in, prefix = null;
      for (String line : toLines(in))
        if (line.length() != 0) {
          prefix = prefix == null ? line : commonPrefix(prefix, line);
          if (debug)
            System.out.println("FCommonPrefix: line=" + quote(line) + ", prefix=" + quote(prefix));
        }
      return prefix;
    }
    
    public void toJava_process(Code code) {
      todo();
    }
  }
  
  static class FCommonSuffix implements Function {
    static boolean debug;

    public Object process(Object _in) {
      String in = (String) _in, suffix = null;
      for (String line : toLines(in))
        if (line.length() != 0) {
          suffix = suffix == null ? line : commonSuffix(suffix, line);
          if (debug)
            System.out.println("FCommonSuffix: line=" + quote(line) + ", suffix=" + quote(suffix));
        }
      return suffix;
    }
    
    public void toJava_process(Code code) {
      todo();
    }
  }
  
  /*static class Pair {
    Object a, b;
    
    public boolean equals(Object o) {
      return o instanceof Pair && a.equals(((Pair) o).a) && b.equals((Pair) o).b);
    }
    
    public int hashCode() {
      return a.hashCode()+b.hashCode()*2;
    }
  }*/
  
  static class Matrix {
    new HashMap<Object, Map> dataByCol;
    
    void put(Object col, Object row, Object value) {
      //data.put(new Pair(col, row), value);
      getCol(col).put(row, value);
    }
    
    Map getCol(Object col) {
      Map map = dataByCol.get(col);
      if (map == null)
        dataByCol.put(col, map = new HashMap());
      return map;
    }
    
    Object get(Object col, Object row) {
      //return data.get(new Pair(col, row));
      return getCol(col).get(row);
    }
    
    Set cols() {
      return dataByCol.keySet();
    }
    
    Set rowsFor(Object col) {
      return getCol(col).keySet();
    }
  }
  
  static class LDistinguishList extends LearnerImpl {
    static boolean debug;
    Function helper;
    int idx;
    new Matrix matrix;

    *(Function helper) {
      this.helper = helper;
    }
    
    public void processInOut(Object _in, Object out) {
      List in = (List) _in;
      for (int i = 0; i < in.size(); i++) {
        Object y = helper.process(in.get(i));
        matrix.put(i, y, out);
      }
    }
    
    public Object processIn(Object _in) {
      // find idx
      
      for (Object i : matrix.cols()) {
        Collection ys = matrix.rowsFor(i);
        if (ys.size() > 1) {
          idx = (Integer) i;
          break;
        }
      }
      
      List in = (List) _in;
      Object y = helper.process(in.get(idx));
      return matrix.get(idx, y);
    }
    
    public void toJava(Code code) {
      List ys = new ArrayList(matrix.rowsFor(idx));
      //String v = code.var;
      //code.newVar();
      //String vy = code.var;
      //code.oldVar();
      code.assign(code.list() + ".get(" + idx + ")");
      helper.toJava_process(code);
      
      for (int i = 0; i < ys.size(); i++) {
        Object y = ys.get(i);
        if (i < ys.size())
          code.line((i == 0 ? "" : "else ") + "if (" + quote((String) y) + ".equals(" + code.var + "))");
        else
          code.line("else");
        code.line("  " + code.var + " = " + quote((String) matrix.get(idx, y)) + ";");
      }
    }
  }
  
  static class RunnersUp {
    String expected;
    int bestScore = -1;
    String bestResult;
    Learner winner;
    
    void add(String expected, String result, int score, Learner learner) {
      if (!expected.equals(this.expected) || bestScore == -1 || score < bestScore) {
        bestScore = score;
        bestResult = result;
        winner = learner;
      }
      this.expected = expected;
    }
  }
  
  static List<Case> casesSortedByID() {
    new (Tree)Map<Long, Case> map;
    new List<Case> rest;
    for (Case c : cases)
      if (isSnippetID(c.id))
        map.put(parseSnippetID(c.id), c);
      else
        rest.add(c);
    List<Case> list = new ArrayList<Case>(map.values());
    list.addAll(rest);
    return list;
  }
  
  !include #1000382 // Box learners
  !include #1000387 // Empty box learner
  
  // for "find" tasks (e.g. "abcde" to "[[abc]]de")
  static class LFixedSubstring extends LearnerImpl {
    static boolean debug;
    String findMarker1 = "{{", findMarker2 = "}}";
    int i, j;
    
    public void processInOut(Object _in, Object _out) {
      String in = (String) _in, out = (String) _out;
      i = out.indexOf(findMarker1);
      j = out.indexOf(findMarker2, i)-2;
      if (debug && j >= 0) {
        boolean correct = in.substring(i, j).equals(out.substring(i+2, j+2));
        System.out.println("LFixedSubstring: i, j = " + i + ", " + j + " " + correct + " " + quote(in.substring(i, j)));
      }
    }
    
    public String processIn(Object _in) {
      String in = (String) _in;
      return in.substring(0, i) + findMarker1 + in.substring(i, j) + findMarker2 + in.substring(j);
    }
  }

  !include #1000459 // LFixWhiteSpace

  static Object newInstance(Class c, Object... args) ctex {
    Constructor m = findConstructor(c, args);
    m.setAccessible(true);
    return m.newInstance(args);
  }
  
  static boolean hasConstructor(boolean debug, Class c, Class... args) {
    for (Constructor m : c.getDeclaredConstructors()) {
      if (!checkArgs(m.getParameterTypes(), args, debug))
        continue;
      return true;
    }
    return false;
  }
  
  static boolean hasConstructor(boolean debug, Class c, Object... args) {
    for (Constructor m : c.getDeclaredConstructors()) {
      if (!checkArgs(m.getParameterTypes(), args, debug))
        continue;
      return true;
    }
    return false;
  }
  
  static Constructor findConstructor(Class c, Object... args) {
    for (Constructor m : c.getDeclaredConstructors()) {
      if (!checkArgs(m.getParameterTypes(), args, false))
        continue;
      return m;
    }
    throw new RuntimeException("Constructor with " + args.length + " matching parameter(s) not found in " + c.getName());
  }
  
  static Class findClass(String name) {
    for (String c : myInnerClasses())
      if (c.equalsIgnoreCase(name))
        try {
          return Class.forName("main$" + c);
        } catch (ClassNotFoundException e) {
          return null;
        }
    return null;
  }
  
  static boolean isSubclass(Class a, Class b) {
    return b.isAssignableFrom(a);
  }
  
  static boolean checkArgs(Class[] types, Object[] args, boolean debug) {
    if (types.length != args.length) {
      if (debug)
        System.out.println("Bad parameter length: " + args.length + " vs " + types.length);
      return false;
    }
    for (int i = 0; i < types.length; i++)
      if (!(args[i] == null || types[i].isInstance(args[i]))) {
        if (debug)
          System.out.println("Bad parameter " + i + ": " + args[i] + " vs " + types[i]);
        return false;
      }
    return true;
  }
  
  static boolean checkArgs(Class[] types, Class[] args, boolean debug) {
    if (types.length != args.length) {
      if (debug)
        System.out.println("Bad parameter length: " + args.length + " vs " + types.length);
      return false;
    }
    for (int i = 0; i < types.length; i++)
      if (!(args[i] == null || isSubclass(args[i], types[i]))) {
        if (debug)
          System.out.println("Bad parameter " + i + ": " + args[i] + " vs " + types[i]);
        return false;
      }
    return true;
  }
  
  !include #1000465 // LCertainElement
  
  static Class findClassFlex(String p) {
    Class c = findClass(p);
    if (c == null) c = findClass("L" + p);
    if (c == null) c = findClass("F" + p);
    if (c == null) c = findClass("RF" + p);
    return c;
  }
  
  !include #1000468 // LOneWordChanged
  !include #1000470 // LBla
  
  static String shorten(String s, int max) {
    return s.length() <= max ? s : s.substring(0, Math.min(s.length(), max)) + "...";
  }
  
  !include #1000481 // LIntersperse
  
  static String getName(Class c) {
    return c.getName().replaceAll("^main\\$", "");
  }
  
  static void keepAlive() {
    daemon {
      Object printed = null;
      while (true) {
        Object t = trying;
        Thread.sleep(1000);
        if (t != null && (verboseMonitor || (t == trying && printed != t))) { // still trying
          System.err.println("* "+ shorten(structure(t), 200));
          printed = t;
        } else printed = null;
      }
    }
  }
  
  !include #1000485 // LFixedPositions
  !include #1000486 // LMap
  !include #1000492 // LPrefixSuffix
  !include #1000493 // LRemoveInputSuffix
  
  static <T> T overwrite(T existing, T newValue) {
    if (existing != null && !existing.equals(newValue))
      fail("Overwrite");
    return newValue;
  }
  
  static void getPass() ctex {
    if (user != null) {
      File pwFile = new File(userHome(), ".javax/pw-" + user);
      if (pass == null) {
        List<String> lines = toLines(readTextFile(pwFile, ""));
        if (!lines.isEmpty())
          pass = lines.get(0).trim();
        if ("".equals(pass)) pass = null;
        //System.out.println("Pass: " + quote(pass));
        if (pass != null)
          System.out.println("Password read from " + pwFile.getAbsolutePath());
      }
      if (pass == null)
        System.out.println("You can put your password in: " + pwFile.getAbsolutePath());
    }
  }
  
  static void editSnippetText(String docID, String newText, String editInfo) ctex {
    getPass();
    System.out.println("Editing " + docID);
    URL url = new URL(tb_mainServer() + "/tb-int/auto-edit.php");
    String postData =
        "user=" + urlencode(user)
      + "&pass=" + urlencode(pass)
      + "&id=" + urlencode(docID)
      + "&text=" + urlencode(newText)
      + "&editinfo=" + urlencode(editInfo);
    System.out.println(postData);
    String result = doPost(postData, url.openConnection(), url);
    System.out.println("Edit result: " + result);
  }
  
  !include #1000498 // FBeforeColon
  !include #1000505 // FAfterColon
  !include #1000499 // FUnquote
  !include #1000500 // LCombineTwoFunctions
  !include #1000506 // LCombineTwoFunctions2
  
  static List<Function> allFunctions() {
    new List<Function> list;
    for (String s : myInnerClasses()) {
      Class c = findClass(s);
      if (c == null) continue;
      if (isSubclass(c, Function.class) && hasConstructor(false, c)) {
        //System.out.println("allFunctions: " + c);
        list.add((Function) newInstance(c));
      }
    }
    return list;
  }
  
  static List<Case> solvedCases() {
    new List<Case> list;
    for (int i = caseIdx-1; i >= 0; i--)
      if (cases.get(i).winner != null)
        list.add(cases.get(i));
    return list;
  }
  
  static O tryProcess(Function f, O in) null on exception {
    ret f.process(in);
  }
  
  static O tryProcess(Learner l, Object in) null on exception {
    return l.processIn(in);
  }  
  
  !include #1000509 // LFunctionPlusPrevious
  !include #1000510 // FNonMarkedAsList
  !include #1000511 // LWrap
  !include #1000512 // LPost
  !include #1000513 // FJoin
  !include #1000531 // FStringAsChars
  !include #1000532 // LUse
  !include #1000622 // FRegExp
  !include #1000640 // LHotwire
  
  !include #2000521 // XX - new unquote function
  
  // makes a case from ioioi lines (just the raw i/o strings),
  // solves and returns it.
  // nice for embedding (hotwiring)
  static Case quickSolve(String[] ioioi) ctex {
    Case case = produceCase(ioioi);
    calculate(case);
    return case;
  }
  
  static Case produceCase(S[] ioioi) ctex {
    new StringBuilder buf;
    for (int i = 0; i < ioioi.length; i++) {
      buf.append((i % 2) == 0 ? "In: " : "Out: ");
      buf.append(quote(ioioi[i]) + "\n");
    }
    ret parse(buf.toString());
  }
  
  static class FToUpper extends FunctionImpl {
    public O process(O _in) {
      String in = cast _in;
      ret upper(in);
    }
  }
}
Travelled to 18 computer(s): aoiabmzegqzx, bhatertpkbcr, cbybwowwnfue, cfunsshuasjs, ddnzoavkxhuk, gwrvuhgaqvyk, ishqpsrjomds, jtubtzbbkimh, lpdgvwnxivlt, mqqgnosmbjvj, onxytkatvevr, pyentgdyhuwx, pzhvpgtvlbxg, teubizvjbppd, tslmcundralx, tvejysmllsmz, vouqrxazstgt, xrpafgyirdlv
ID	Author/Program	Comment	Date
526	#1000610 (pitcher)		2015-08-20 15:30:54
525	#1000604 (pitcher)		2015-08-20 15:30:54
Snippet ID:	#738
Snippet name:	IOIOI Solver (v16, most recent one)
Eternal ID of this version:	#738/24
Text MD5:	be731444a79321867f2c502100989855
Transpilation MD5:	cb6889db283c7a84d9df6d96173e331c
Author:	stefan
Category:
Type:	JavaX source code
Public (visible to everyone):	Yes
Archived (hidden from active list):	No
Created/modified:	2020-01-26 15:52:51
Source code size:	66693 bytes / 2146 lines
Pitched / IR pitched:	No / No
Views / Downloads:	2270 / 3534
Version history:	23 change(s)
Referenced in:	[show references]
< > BotCompany Repo | #738 // IOIOI Solver (v16, most recent one)

JavaX source code [tags: use-pretranspiled] - run with: x30.jar

Author comment

Comments [hide]
