!636
!quickmain
!auto-import
!standard functions
!quicknew
!1000346 // use "case" as a variable name
!688 // buf.isEmpty
!class JavaTok
!1000381 // L<S>

import java.lang.reflect.*;
import java.math.*; // BigInteger

!include #2000470 // class _x16

interface Function {
  public Object process(Object in);
  public void toJava_process(Code code);
}

interface ReversibleFunction extends Function {
  public Object unprocess(Object in);
  public void toJava_unprocess(Code code);
}

// generic learner (works on objects)
interface Learner {
  public void processInOut(Object in, Object out);
  public Object processIn(Object in);
  public void toJava(Code code);
}

interface Retry {} // marker interface for learners that want to retry

abstract class 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 (!buf.isEmpty()) buf.append(", ");
      buf.append(field.getName() + "=" + value);
    }
    System.out.println(buf.toString());
  }
}

abstract class LearnerImpl extends Base implements Learner {
}

class Code {
  new StringBuilder buf;
  String var = "in";
  String indent = "";
  new List<String> translators;
  new List<String> varStack;
  int varCounter;
  
  Code() {
    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);
  }
}

main {
  static new List<Case> cases;
  static new HashMap<String, Case> casesByID;
  static boolean testJava = true, showFails;
  static new (Hash)Set<String> parseErrors;
  static int caseIdx;
  
  psvm {
    new List<String> snippetIDs;
    new List<String> inputs;
    
    for (int i = 0; i < args.length; i++) {
      String arg = args[i];
      if (arg.equals("debug"))
        debugOn(args[++i]);
      else if (arg.equals("in"))
        inputs.add(args[++i]);
      else if (arg.equals("-notestjava"))
        testJava = false;
      else if (arg.equals("-testjava"))
        testJava = true;
      else if (arg.equals("-showfails"))
        showFails = true;
      else if (isSnippetID(arg))
        snippetIDs.add(arg);
      else
        System.err.println("Unknown argument: " + arg + ", ignoring");
    }
    
    if (snippetIDs.isEmpty())
      parse(null);
    
    for (String snippetID : snippetIDs)
      try {
        Case case = parse(snippetID);
        case.halfExamples.addAll(inputs);
      } 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;
      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 "----"

    boolean allSolved = solved == n;
    if (solved != 0) {
      System.out.println();
      System.out.print("Solved: ");
      for (Case case : cases)
        if (case.winner != null)
          System.out.print(case.id + " ");
      System.out.println();
    }
    if (testJava && solved > goodJava) {
      System.out.println();
      System.out.print("Bad Java: ");
      for (Case case : cases)
        if (case.winner != null && !case.goodJava)
          System.out.print(case.id + " ");
      System.out.println();
    }
    if (!allSolved) {
      System.out.println();
      System.out.print("Unsolved: ");
      for (Case case : cases)
        if (case.winner == null)
          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();
    }
    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 ""
  }
  
  static class Case {
    String id;
    new List<String[]> fullExamples;
    new List<String> halfExamples;
    List<String[]> examples1, examples2;
    Learner winner;
    boolean goodJava;
    List<Case> combined;
    int splitPoint = -1;

    void split() {    
      if (examples1 != null)
        return; // already done
      if (fullExamples.size() < 2)
        throw new RuntimeException("Too few examples (" + fullExamples.size() + ")");
      if (splitPoint < 0)
        splitPoint = fullExamples.size()-1;
      System.out.println("Full examples: " + fullExamples.size() + ", splitPoint: " + splitPoint + ", 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);
    }
  }

  static Case parse(String arg) tex {
    new Case case;
    String text;
    if (arg != null) {
      if (casesByID.containsKey(arg))
        return casesByID.get(arg);
        
      if (arg.startsWith("Combine")) {
        case.id = "Combine";
        case.combined = new ArrayList<Case>();
        List<String> tok = JavaTok.split(arg);
        new List<String> ids;
        for (int i = 5; i < tok.size(); i += 6) { // skip # and "and"
          Case case2 = parse("#" + tok.get(i));
          case.id += " #" + tok.get(i);
          cases.remove(case2);
          case.add(case2);
        }
        addCase(case);
        return case;
      } else {
        case.id = arg;
        text = loadSnippet(arg);
      }
    } else {
      case.id = "input.txt";
      text = loadTextFile("input/input.txt", null);
      if (text == null) {
        //case.id = "#2000455";  // example input
        case.id = "#681"; // a collection of "all cases"!
        text = loadSnippet(case.id);
      }
    }
    
    // it's a collection of cases!
    if (text.trim().startsWith("#") || text.trim().startsWith("Combine")) {
      for (String line : toLines(text))
        parse(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 a "Execute." task - run Java(X) and transform to I/O format
    if (text.trim().startsWith("Execute.")) {
      List<String> tok = JavaTok.split(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(tok.get(i));
          String result = execute("!636\n" + code);
          buf.append("In: " + quote(code) + "\n");
          buf.append("Out: " + quote(result) + "\n");
        }
      }
      text = buf.toString();
    }
      
    System.out.println(text);
    String in = null, out = null;
    
    List<String> tok = JavaTok.split(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.equals("-") && t2.equals("-")) {
        i += 2;
        case.splitPoint = case.fullExamples.size();
      } 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(JavaTok.join(tok.subList(i, j-1)));
        i = j-2;
        out = null;
      } else if (t.toUpperCase().startsWith("O") && t2.equals(":")) { // "Out: " or "O: "
        i += 4;
        int j = findNextLine(tok, i);
        out = unquote(JavaTok.join(tok.subList(i, j-1)));
        i = j-2;
        System.out.println(quote(in) + " => " + quote(out));
        case.fullExamples.add(new String[] {in, out});
        in = out = null;
      } else {
        int j = findNextLine(tok, i);
        String line = JavaTok.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;
  }
  
  // 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+2;
  }
  
  static void addCase(Case case) {
    cases.add(case);
    casesByID.put(case.id, case);
  }
  
  static void calculate(Case case) tex {
    System.out.println("\n== CASE " + case.id + " ==");
    
    case.split();
    Learner learner = findOKLearner(case);
    if (learner == null)
      print "\nProblem not solved"
    else {
      print "\nSolved!"
      case.winner = learner;
      new Code code;
      try {
        learner.toJava(code);

        if (testJava)
          testJava(case, code); // prints "GOOD JAVA" or "BAD JAVA"
        else
          print "Java:"
          
        System.out.println(indent("  ", code.getTranslators()));
        System.out.println(indent("  ", code.buf.toString()));
      } catch (Throwable e) {
        print "BAD JAVA"
      }
        
      for (String in : case.halfExamples) {
        Object out = learner.processIn(in);
        System.out.println(quote(in) + " =>! " + quote((String) out));
      }
    }
  }
  
  static Learner findOKLearner(Case case) tex {
    for (Learner learner : makeLearners()) 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<String[]>();
    s.examples2 = new ArrayList<String[]>();
    for (Case c : case.combined) {
      ++i;
      for (String[] e : c.examples1)
        s.examples1.add(new String[] {e[0], String.valueOf(i)});
      for (String[] e : c.examples2)
        s.examples2.add(new String[] {e[0], String.valueOf(i)});
      for (String[] e : c.fullExamples)
        s.fullExamples.add(new String[] {e[0], String.valueOf(i)});
    }
    return s;
  }
  
  static boolean learnerOK(Learner learner, Case case) {
    String[] _e = null;
    try {
      if (case.examples1 == null)
        fail("Case not calculated: " + case.id);
      for (String[] e : case.examples1) {
        _e = e;
        learner.processInOut(e[0], e[1]);
      }
      
      // full validation against all examples
      int retry = 0;
      retryLoop: while (true) {
        for (String[] e : case.fullExamples) {
          _e = e;
          String out = (String) learner.processIn(e[0]);
          if (!e[1].equals(out)) {
            if (showFails)
              System.out.println("[fail] " + structure(learner) + " on " + quote(e[0]) + " - got: " + quote(out) + " rather than: " + quote(e[1]));
            if (!(learner instanceof Retry))
              return false;
            else {
              ++retry;
              System.err.println("Retry " + retry);
              continue retryLoop;
            }
          }
        }
        return true;  // all test examples passed
      }
    } catch (Throwable e) {
      if (showFails) {
        e.printStackTrace();
        System.err.println("[fail] " + learner + " on " + (_e == null ? "?" : quote(_e[0])) + " - " + e);
      }
      return false;
    }
  }
  
  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) {
  }
  
  /* XXX - important part */
  static Iterable<Learner> makeLearners() {
    new List<Learner> list;
    list.addAll(level1());
    list.add(new LBox(new LMulti(level1())));
    return list;
  }
  
  static List<Learner> level1() {
    new List<Learner> list;
    //list.add(new LId()); // subsumed by trivial case of PrefixSuffix
    list.add(new LPrefixSuffix());
    list.add(new LSplitInput(new LOutPattern()));
    list.add(new LInputPattern());
    list.add(new LFixed());
    list.add(new LBoth(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()))
    ));
    
    // TODO - for #1000378
    list.add(new LChange(new RFJavaTok(), new LDistinguishList(new FIsString())));

    // of no use now it seems
    // list.add(new LTryPrevious());
    
    return list;
  }
  
  public static String unquote(String s) {
    if (s.startsWith("[[") && s.endsWith("]]"))
      return s.substring(2, s.length()-2);
    else if (s.startsWith("\"") && s.endsWith("\"") && s.length() > 1)
      return s.substring(1, s.length()-1).replace("\\\"", "\"").replace("\\\\", "\\"); // SHOULD work...
    else
      return s; // return original
  }
  
  public static String quote(String s) {
    if (s == null) return "null";
    return "\"" + s.replace("\\", "\\\\").replace("\"", "\\\"") + "\"";
  }
  
  static String indent(String indent, String s) {
    return indent + s.replace("\n", "\n" + indent);
  }
  
  static void debugOn(String name) {
    try {
      Class c = Class.forName("main$" + name);
      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);
    }
  }
  
  // splits the input at some point, takes only one part
  static class LSplitInput implements Learner {
    int splitIdx = 1; // split after first character
    Learner baseLearner;
    
    LSplitInput(Learner baseLearner) {
      this.baseLearner = baseLearner;
    }
    
    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);
    }
  }
  
  // removes common suffix from out, delegates to base learner
  static class LOutSuffix implements Learner {
    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 implements Learner {
    String pattern = "%!%";

    public void processInOut(Object _in, Object _out) {
      String in = (String) _in, out = (String) _out;
      pattern = out.replace(in, "%!%");
    }
    
    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 + ");");
    }
  }
  
  // learns to exchange common prefixes and suffixes
  static class LPrefixSuffix extends LearnerImpl {
    static boolean debug;
    String prefixIn, suffixIn, prefixOut, suffixOut;
    
    public void processInOut(Object _in, Object _out) {
      String in = (String) _in, out = (String) _out;
      updateIn(in);
      prefixOut = prefixOut == null ? out : commonPrefix(prefixOut, out);
      suffixOut = suffixOut == null ? out : commonSuffix(suffixOut, out);
      if (debug)
        printState("processInOut(" + quote(in) + ", " + quote(out) + ")");
    }
    
    void updateIn(String in) {
      prefixIn = prefixIn == null ? in : commonPrefix(prefixIn, in);
      suffixIn = suffixIn == null ? in : commonSuffix(suffixIn, in);
      if (debug)
        printState("updateIn(" + quote(in) + ")");
    }

    public String processIn(Object _in) {
      String in = (String) _in;
      //System.out.println("[before last info] " + quote(prefixIn) + " " + quote(suffixIn) + " " + quote(prefixOut) + " " + quote(suffixOut));
      //System.out.println("[last info] " + quote(in));
      
      // use latest information
      String p = prefixIn, s = suffixIn;
      updateIn(in);
      prefixOut = prefixOut.substring(0, prefixOut.length()-(p.length()-prefixIn.length()));
      suffixOut = suffixOut.substring(s.length()-suffixIn.length());
      
      //System.out.println("[after last info] " + quote(prefixIn) + " " + quote(suffixIn) + " " + quote(prefixOut) + " " + quote(suffixOut));
      String core = in.substring(prefixIn.length(), in.length()-suffixIn.length());
      return prefixOut + core + suffixOut;
    }
    
    public void toJava(Code code) {
      if (prefixIn.length() != 0 || suffixIn.length() != 0)
        code.line(code.var + " = ((String) " + code.var + ").substring(" + prefixIn.length() + ", " + code.s() + ".length()-" + suffixIn.length() + ");");
      if (prefixOut.length() != 0 || suffixOut.length() != 0)
        code.line(code.var + " = " + quote(prefixOut) + " + " + code.var + " + " + quote(suffixOut) + ";");
    }
    
    void printState(String text) {
      System.out.println(text);
      printVars();
    }
  }
  
  // for "find" tasks (e.g. "abcde" to "[[abc]]de")
  static class LInputPattern implements Learner {
    String regexp = "";
    
    public void processInOut(Object _in, Object _out) {
      String in = (String) _in, out = (String) _out;
      int i = out.indexOf("[["), j = out.indexOf("]]", i+1);
      if (j < 0) return;
      String s = out.substring(i+2, j);
      regexp = s.replaceAll("\\d+", Matcher.quoteReplacement("\\d+"));
      System.out.println("regexp: " + regexp);
    }
    
    public String processIn(Object _in) {
      String in = (String) _in;
      if (regexp.length() == 0)
        return in;
      else
        return in.replaceAll("(" + regexp + ")", "[[$1]]");
    }
    
    public void toJava(Code code) {
      code.line(code.var + " = ((String) " + code.var + ").replaceAll(" + quote("(" + regexp + ")") + ", \"[[$1]]\");");
    }
  }
  
  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 fail(String msg) {
    throw new RuntimeException(msg);
  }
  
  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 LBoth extends LearnerImpl {
    ReversibleFunction f;
    Learner base;
    
    LBoth(ReversibleFunction f, Learner base) {
      this.f = f;
      this.base = base;
    }
    
    public void processInOut(Object in, Object out) {
      in = f.process(in);
      out = f.process(out);
      base.processInOut(in, out);
    }
    
    public Object processIn(Object in) {
      in = f.process(in);
      in = base.processIn(in);
      in = f.unprocess(in);
      return in;
    }
    
    public void toJava(Code code) {
      f.toJava_process(code);
      base.toJava(code);
      f.toJava_unprocess(code);
    }
  }
  
  static class RFJavaTok implements ReversibleFunction {
    public Object process(Object in) {
      return JavaTok.split((String) in);
    }
    
    public Object unprocess(Object in) {
      return JavaTok.join((List) in);
    }
    
    public void toJava_process(Code code) {
      code.translators("!636", "!class JavaTok");
      code.line(code.var + " = JavaTok.split((String) " + code.var + ");");
    }
    
    public void toJava_unprocess(Code code) {
      code.translators("!636", "!class JavaTok");
      code.line(code.var + " = JavaTok.join((List) " + code.var + ");");
    }
  }
  
  // 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 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 + ")");
    }
  }
  
  // math operations
  static class LMath extends LearnerImpl {
    static boolean debug;
    String allOperations = "+ - * /";
    new (Tree)Set<String> possibleOperations;
    
    LMath() {
      possibleOperations.addAll(Arrays.asList(allOperations.split(" +")));
    }
    
    public void processInOut(Object _in, Object _out) {
      List in = (List) _in;
      String out = (String) _out;
      BigInteger[] inNumbers = getNumbers(in);
      BigInteger[] outNumbers = new BigInteger[] {getNumber(out)};
      findOperation(inNumbers, outNumbers);
      if (debug)
        System.out.println("Operations: " + possibleOperations);
    }
    
    public void findOperation(BigInteger[] in, BigInteger[] out) {
      filterOperations(in, out);
      if (possibleOperations.isEmpty())
        fail("tilt");
    }
      
    public void filterOperations(BigInteger[] in, BigInteger[] out) {
      for (Iterator<String> i = possibleOperations.iterator(); i.hasNext(); ) {
        String op = i.next();
        BigInteger[] out2 = doOperation(op, in);
        if (out2 == null || !arraysEqual(out, out2))
          i.remove(); // keep only matching operations
      }
    }
    
    public BigInteger[] doOperation(String op, BigInteger[] in) {
      op = op.intern();
      try {
        if (in.length == 2) {
          BigInteger a = in[0], b = in[1], x = null;
          if (op == "+")
            x = a.add(b);
          else if (op == "-")
            x = a.subtract(b);
          else if (op == "*")
            x = a.multiply(b);
          else if (op == "/")
            x = a.divide(b);
          return x != null ? new BigInteger[] {x} : null;
        }
        return null;
      } catch (Throwable e) {
        return null;
      }
    }
    
    public String processIn(Object _in) {
      List<String> in = (List<String>) _in;
      String op = possibleOperations.iterator().next();
      if (debug)
        System.out.println("op: " + op);
      BigInteger[] inNumbers = getNumbers(in);
      BigInteger[] outNumbers = doOperation(op, inNumbers);
      return outNumbers[0].toString();
    }
    
    String BI = BigInteger.class.getName();
    
    public void toJava(Code code) {
      String op = possibleOperations.iterator().next();
      String a = "new " + BI + "((String) " + code.list() + ".get(0))";
      String b = "new " + BI + "((String) " + code.list() + ".get(1))";
      if (op.equals("+"))
        code.assign(a + ".add(" + b + ").toString()");
      else
        todo();
    }
    
    static BigInteger[] getNumbers(List<String> in) {
      BigInteger[] big = new BigInteger[in.size()];
      for (int i = 0; i < in.size(); i++)
        big[i] = new BigInteger(in.get(i));
      return big;
    }
    
    static BigInteger getNumber(String s) {
      return new BigInteger(s);
    }
    
    static boolean arraysEqual(BigInteger[] a, BigInteger[] b) {
      if (a.length != b.length) return false;
      for (int i = 0; i < a.length; i++)
        if (!a[i].equals(b[i])) return false;
      return true;
    }
  }
  
  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 implements Learner {
    Learner baseLearner;
    
    LFirst(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());
  }
  
  // compile JavaX source and load main class
  static Class<?> loadMainClass(String src) tex {
    File srcDir = _x16.TempDirMaker_make();
    File classesDir = _x16.TempDirMaker_make();
    _x16.saveTextFile(new File(srcDir, "main.java").getPath(), src);
    new List<File> libraries;
    File transpiledDir = _x16.topLevelTranslate(srcDir, libraries);
    String javacOutput = _x16.compileJava(transpiledDir, libraries, classesDir);
    System.out.println(javacOutput);
    URL[] urls = {classesDir.toURI().toURL()};
    
    // make class loader
    URLClassLoader classLoader = new URLClassLoader(urls);

    // load main class
    Class<?> mainClass = classLoader.loadClass("main");
    return mainClass;
  }
      
  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 = loadMainClass(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 = loadMainClass(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 (String[] e : case.fullExamples) {
        String out = (String) m.invoke(null, e[0]);
        
        if (!e[1].equals(out)) {
          throw new RuntimeException("[fail] Java code on " + quote(e[0]) + " - got: " + quote(out) + " rather than: " + quote(e[1]));
        }
      }
      
      System.out.println("\nGOOD JAVA.");
      case.goodJava = true;
    } catch (Throwable e) {
      if (showFails)
        e.printStackTrace();
      System.out.println("\nBAD JAVA.");
    }
  }
  
  static void todo() {
    fail("todo");
  }
  
  static class LSwitch extends LearnerImpl {
    Case case;
    Learner switcher;
    
    LSwitch(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 LTryPrevious extends LearnerImpl {
    new List<Case> candidates;
    
    LTryPrevious() {
      for (int i = caseIdx-1; i >= 0; i--)
        candidates.add(cases.get(i));
    }

    public void processInOut(Object _in, Object _out) {
      String in = (String) _in, out = (String) _out;
      for (ListIterator<Case> i = candidates.listIterator(); i.hasNext(); ) {
        Case case = i.next();
        if (case.winner == null || !validate(new String[] {in, out}, case.winner))
          i.remove();
      }
      if (candidates.isEmpty())
        fail("no previous solution found");
    }
  
    public Object processIn(Object in) {
      return candidates.get(0).winner.processIn(in);
    }
  
    public void toJava(Code code) {
      candidates.get(0).winner.toJava(code);
    }
  }
  
  static class LMulti extends LearnerImpl implements Retry {
    static boolean debug;
    new List<Learner> candidates;
    
    LMulti(Learner... learners) {
      for (Learner l : learners)
        candidates.add(l);
    }
    
    LMulti(L<Learner> learners) {
      for (Learner l : learners)
        candidates.add(l);
    }
    
    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 toJava(Code code) {
      candidates.get(0).toJava(code);
    }
  }
  
  static String structure(Object o) {
    //if (!(o instanceof Base))
    if (!o.getClass().getName().startsWith("main$"))
      return String.valueOf(o);

    new StringBuilder buf;
    
    // TODO: go to superclasses too
    Field[] fields = o.getClass().getDeclaredFields();
    for (Field field : fields) {
      if ((field.getModifiers() & Modifier.STATIC) != 0)
        continue;
      Object value;
      try {
        value = field.get(o);
      } catch (Exception e) {
        value = "?";
      }
      
      if (!buf.isEmpty()) buf.append(", ");
      buf.append(field.getName() + "=" + structure(value));
    }
    String s = o.getClass().getName().replaceAll("^main\\$", "");
    if (!buf.isEmpty())
      s += "(" + buf + ")";
    return s;
  }
  
  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 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;

    LDistinguishList(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 LBox extends LearnerImpl {
    static boolean debug;
    Learner middleLearner;
    char topChar, bottomChar;
    
    LBox(Learner middleLearner) {
      this.middleLearner = middleLearner;
    }
    
    public void processInOut(Object _in, Object _out) {
      String in = (String) _in, out = (String) _out;
      L<S> l = toLines(out);
      String middle = l.get(2);
      middleLearner.processInOut(in, middle);
      topChar = l.get(1).charAt(0);
      bottomChar = l.get(3).charAt(0);
    }
    
    public Object processIn(Object in) {
      String middle = (String) middleLearner.processIn(in);
      return "\n" +
        repeat(topChar, middle.length()) + "\n" +
        middle + "\n" +
        repeat(bottomChar, middle.length()) + "\n";
    }
    
    static String repeat(char c, int n) {
      char[] chars = new char[n];
      for (int i = 0; i < n; i++)
        chars[i] = c;
      return new String(chars);
    }
    
    public void toJava(Code code) {
      todo();
    }
  }
}

Began life as a copy of #693