import javax.imageio.*; import java.awt.image.*; import java.awt.event.*; import java.awt.*; import java.security.NoSuchAlgorithmException; import java.security.MessageDigest; import java.lang.management.*; import java.lang.reflect.*; import java.net.*; import java.io.*; import javax.swing.text.*; import javax.swing.event.*; import javax.swing.*; import java.util.concurrent.atomic.*; import java.util.concurrent.*; import java.util.regex.*; import java.util.List; import java.util.zip.*; import java.util.*; public class main { static List sentences = toLinesFullTrim("\n \n \"0\" is a digit.\n \"1\" is a digit.\n \"2\" is a digit.\n \"3\" is a digit.\n \"4\" is a digit.\n \"5\" is a digit.\n \"6\" is a digit.\n \"7\" is a digit.\n \"8\" is a digit.\n \"9\" is a digit.\n These are all the digits that exist.\n A number is a concatenation of digits.\n\n "); static List questions = toLinesFullTrim("\n \n Is \"5\" a digit?\n Is \"your mama\" a digit?\n \n "); static class Concept { List stringExamples = new ArrayList(); List descriptions = new ArrayList(); boolean closed; void addStringExample(String s) { if (!stringExamples.contains(s)) // yes it's inefficient... who cares right now :)))))) stringExamples.add(s); } void addDescription(String s) { if (!descriptions.contains(s)) descriptions.add(s); } } static class Concepts { Map map = new TreeMap(); Concept get(String s) { Concept c = map.get(s); if (c == null) map.put(s, c = new Concept()); return c; } } static Concepts concepts = new Concepts(); public static void main(String[] args) throws Exception { for (String s : concatLists(sentences, questions)) { List tok = javaTok(s); String[] bla = match("* is a *.", tok); if (bla != null && bla[0].startsWith("\"")) { print(bla[0] + " is a " + bla[1] + "!"); concepts.get(bla[1]).addStringExample(unquote(bla[0])); continue; } bla = match("These are all the * that exist.", tok); if (bla != null) { String c = bla[0].replaceAll("s$", ""); concepts.get(c).closed = true; print("Closed concept " + c + "."); continue; } bla = match("A * is ... .", tok); if (bla != null) { String desc = joinRest(bla, 1); concepts.get(bla[0]).addDescription(desc); print(bla[0] + ": " + desc); continue; } // process questions on knowledge base bla = match("Is * a *?", tok); if (bla != null) { print("? " + s); String answer = "Dunno."; Concept c = concepts.get(bla[1]); if (bla[0].startsWith("\"") && c.closed) { answer = c.stringExamples.contains(unquote(bla[0])) ? "Yes." : "No."; } print("! " + answer); continue; } print("Unknown line: " + s); } print("Number of concepts: " + concepts.map.size() + " (" + structure(concepts.map.keySet()) + ")"); } static String joinRest(String[] bla, int i) { return join(" ", Arrays.asList(bla).subList(i, bla.length)); } static String[] match(String pat, List tok) { Matches m = new Matches(); return match3(pat, join(tok), m) ? m.m : null; } static List concatLists(List a, List b) { List l = new ArrayList(a); l.addAll(b); return l; } static class Matches { String[] m; } static boolean match3(String pat, String s) { return match3(pat, s, null); } static boolean match3(String pat, String s, Matches matches) { List tokpat = parse3(pat), toks = parse3(s); String[] m = match2(tokpat, toks); //print(structure(tokpat) + " on " + structure(toks) + " => " + structure(m)); if (m == null) return false; else { if (matches != null) matches.m = m; return true; } } // replacement for class JavaTok // maybe incomplete, might want to add floating point numbers // todo also: extended multi-line strings static List javaTok(String s) { List tok = new ArrayList(); int l = s.length(); int i = 0; while (i < l) { int j = i; char c; String cc; // scan for whitespace while (j < l) { c = s.charAt(j); cc = s.substring(j, Math.min(j+2, l)); if (c == ' ' || c == '\t' || c == '\r' || c == '\n') ++j; else if (cc.equals("/*")) { do ++j; while (j < l && !s.substring(j, Math.min(j+2, l)).equals("*/")); j = Math.min(j+2, l); } else if (cc.equals("//")) { do ++j; while (j < l && "\r\n".indexOf(s.charAt(j)) < 0); } else break; } tok.add(s.substring(i, j)); i = j; if (i >= l) break; c = s.charAt(i); // cc is not needed in rest of loop body cc = s.substring(i, Math.min(i+2, l)); // scan for non-whitespace if (c == '\'' || c == '"') { char opener = c; ++j; while (j < l) { if (s.charAt(j) == opener) { ++j; break; } else if (s.charAt(j) == '\\' && j+1 < l) j += 2; else ++j; } } else if (Character.isJavaIdentifierStart(c)) do ++j; while (j < l && Character.isJavaIdentifierPart(s.charAt(j))); else if (Character.isDigit(c)) do ++j; while (j < l && Character.isDigit(s.charAt(j))); else if (cc.equals("[[")) { do ++j; while (j+1 < l && !s.substring(j, j+2).equals("]]")); j = Math.min(j+2, l); } else ++j; tok.add(s.substring(i, j)); i = j; } if ((tok.size() % 2) == 0) tok.add(""); return tok; } static void print() { System.out.println(); } static void print(Object o) { System.out.println(o); } static void print(long i) { System.out.println(i); } static List toLinesFullTrim(String s) { List l = toLines(s); for (ListIterator i = l.listIterator(); i.hasNext(); ) { String line = i.next().trim(); if (line.length() == 0) i.remove(); else i.set(line); } return l; } public static String unquote(String s) { if (s.startsWith("[")) { int i = 1; while (i < s.length() && s.charAt(i) == '=') ++i; if (i < s.length() && s.charAt(i) == '[') { String m = s.substring(1, i); if (s.endsWith("]" + m + "]")) return s.substring(i+1, s.length()-i-1); } } if (s.startsWith("\"") && s.endsWith("\"") && s.length() > 1) { String st = s.substring(1, s.length()-1); StringBuilder sb = new StringBuilder(st.length()); for (int i = 0; i < st.length(); i++) { char ch = st.charAt(i); if (ch == '\\') { char nextChar = (i == st.length() - 1) ? '\\' : st .charAt(i + 1); // Octal escape? if (nextChar >= '0' && nextChar <= '7') { String code = "" + nextChar; i++; if ((i < st.length() - 1) && st.charAt(i + 1) >= '0' && st.charAt(i + 1) <= '7') { code += st.charAt(i + 1); i++; if ((i < st.length() - 1) && st.charAt(i + 1) >= '0' && st.charAt(i + 1) <= '7') { code += st.charAt(i + 1); i++; } } sb.append((char) Integer.parseInt(code, 8)); continue; } switch (nextChar) { case '\\': ch = '\\'; break; case 'b': ch = '\b'; break; case 'f': ch = '\f'; break; case 'n': ch = '\n'; break; case 'r': ch = '\r'; break; case 't': ch = '\t'; break; case '\"': ch = '\"'; break; case '\'': ch = '\''; break; // Hex Unicode: u???? case 'u': if (i >= st.length() - 5) { ch = 'u'; break; } int code = Integer.parseInt( "" + st.charAt(i + 2) + st.charAt(i + 3) + st.charAt(i + 4) + st.charAt(i + 5), 16); sb.append(Character.toChars(code)); i += 5; continue; } i++; } sb.append(ch); } return sb.toString(); } else return s; // return original } public static String join(String glue, Iterable strings) { StringBuilder buf = new StringBuilder(); Iterator i = strings.iterator(); if (i.hasNext()) { buf.append(i.next()); while (i.hasNext()) buf.append(glue).append(i.next()); } return buf.toString(); } public static String join(String glue, String[] strings) { return join(glue, Arrays.asList(strings)); } public static String join(Iterable strings) { return join("", strings); } public static String join(String[] strings) { return join("", strings); } static Object get(Object o, String field) { if (o instanceof Class) return get((Class) o, field); try { Field f = get_findField(o.getClass(), field); f.setAccessible(true); return f.get(o); } catch (Exception e) { throw new RuntimeException(e); } } static Object get(Class c, String field) { try { Field f = get_findStaticField(c, field); f.setAccessible(true); return f.get(null); } catch (Exception e) { throw new RuntimeException(e); } } static Field get_findStaticField(Class c, String field) { for (Field f : c.getDeclaredFields()) if (f.getName().equals(field) && (f.getModifiers() & Modifier.STATIC) != 0) return f; throw new RuntimeException("Static field '" + field + "' not found in " + c.getName()); } static Field get_findField(Class c, String field) { for (Field f : c.getDeclaredFields()) if (f.getName().equals(field)) return f; throw new RuntimeException("Field '" + field + "' not found in " + c.getName()); } static String structure(Object o) { return structure(o, 0); } static String structure(Object o, int stringSizeLimit) { if (o == null) return "null"; String name = o.getClass().getName(); StringBuilder buf = new StringBuilder(); if (o instanceof Collection) { for (Object x : (Collection) o) { if (buf.length() != 0) buf.append(", "); buf.append(structure(x, stringSizeLimit)); } return "[" + buf + "]"; } if (o instanceof Map) { for (Object e : ((Map) o).entrySet()) { if (buf.length() != 0) buf.append(", "); buf.append(structure(((Map.Entry) e).getKey(), stringSizeLimit)); buf.append("="); buf.append(structure(((Map.Entry) e).getValue(), stringSizeLimit)); } return "{" + buf + "}"; } if (o.getClass().isArray()) { int n = Array.getLength(o); for (int i = 0; i < n; i++) { if (buf.length() != 0) buf.append(", "); buf.append(structure(Array.get(o, i), stringSizeLimit)); } return "{" + buf + "}"; } if (o instanceof String) return quote(stringSizeLimit != 0 ? shorten((String) o, stringSizeLimit) : (String) o); // Need more cases? This should cover all library classes... if (name.startsWith("java.") || name.startsWith("javax.")) return String.valueOf(o); String shortName = o.getClass().getName().replaceAll("^main\\$", ""); // TODO: go to superclasses too Field[] fields = o.getClass().getDeclaredFields(); int numFields = 0; String fieldName = ""; for (Field field : fields) { if ((field.getModifiers() & Modifier.STATIC) != 0) continue; Object value; try { field.setAccessible(true); value = field.get(o); } catch (Exception e) { value = "?"; } fieldName = field.getName(); // put special cases here... if (value != null) { if (buf.length() != 0) buf.append(", "); buf.append(fieldName + "=" + structure(value, stringSizeLimit)); } ++numFields; } String b = buf.toString(); if (numFields == 1) b = b.replaceAll("^" + fieldName + "=", ""); // drop field name if only one String s = shortName; if (buf.length() != 0) s += "(" + b + ")"; return s; } static String quote(String s) { if (s == null) return "null"; return "\"" + s.replace("\\", "\\\\").replace("\"", "\\\"").replace("\r", "\\r").replace("\n", "\\n") + "\""; } static String quote(long l) { return quote("" + l); } static List parse3(String s) { return dropPunctuation(javaTokPlusPeriod(s)); } // match2 matches multiple "*" (matches a single token) wildcards and zero or one "..." wildcards (matches multiple tokens) static String[] match2(List pat, List tok) { // standard case (no ...) int i = pat.indexOf("..."); if (i < 0) return match2_match(pat, tok); pat = new ArrayList(pat); // We're modifying it, so copy first pat.set(i, "*"); while (pat.size() < tok.size()) { pat.add(i, "*"); pat.add(i+1, ""); // doesn't matter } return match2_match(pat, tok); } static String[] match2_match(List pat, List tok) { List result = new ArrayList(); if (pat.size() != tok.size()) { /*if (debug) print("Size mismatch: " + structure(pat) + " vs " + structure(tok));*/ return null; } for (int i = 1; i < pat.size(); i += 2) { String p = pat.get(i), t = tok.get(i); /*if (debug) print("Checking " + p + " against " + t);*/ if ("*".equals(p)) result.add(t); else if (!p.equalsIgnoreCase(t)) return null; } return result.toArray(new String[result.size()]); } public static List toLines(String s) { List lines = new ArrayList(); int start = 0; while (true) { int i = toLines_nextLineBreak(s, start); if (i < 0) { if (s.length() > start) lines.add(s.substring(start)); break; } lines.add(s.substring(start, i)); if (s.charAt(i) == '\r' && i+1 < s.length() && s.charAt(i+1) == '\n') i += 2; else ++i; start = i; } return lines; } private static int toLines_nextLineBreak(String s, int start) { for (int i = start; i < s.length(); i++) { char c = s.charAt(i); if (c == '\r' || c == '\n') return i; } return -1; } static String shorten(String s, int max) { return s.length() <= max ? s : s.substring(0, Math.min(s.length(), max)) + "..."; } static List dropPunctuation(List tok) { tok = new ArrayList(tok); for (int i = 1; i < tok.size(); i += 2) { String t = tok.get(i); if (t.length() == 1 && !Character.isLetter(t.charAt(0)) && !Character.isDigit(t.charAt(0)) && !t.equals("*")) { tok.set(i-1, tok.get(i-1) + tok.get(i+1)); tok.remove(i); tok.remove(i); i -= 2; } } return tok; } // javaTok extended with "..." token. static List javaTokPlusPeriod(String s) { List tok = new ArrayList(); int l = s.length(); int i = 0; while (i < l) { int j = i; char c; String cc; // scan for whitespace while (j < l) { c = s.charAt(j); cc = s.substring(j, Math.min(j+2, l)); if (c == ' ' || c == '\t' || c == '\r' || c == '\n') ++j; else if (cc.equals("/*")) { do ++j; while (j < l && !s.substring(j, Math.min(j+2, l)).equals("*/")); j = Math.min(j+2, l); } else if (cc.equals("//")) { do ++j; while (j < l && "\r\n".indexOf(s.charAt(j)) < 0); } else break; } tok.add(s.substring(i, j)); i = j; if (i >= l) break; c = s.charAt(i); // cc is not needed in rest of loop body cc = s.substring(i, Math.min(i+2, l)); // scan for non-whitespace if (c == '\'' || c == '"') { char opener = c; ++j; while (j < l) { if (s.charAt(j) == opener) { ++j; break; } else if (s.charAt(j) == '\\' && j+1 < l) j += 2; else ++j; } } else if (Character.isJavaIdentifierStart(c)) do ++j; while (j < l && Character.isJavaIdentifierPart(s.charAt(j))); else if (Character.isDigit(c)) do ++j; while (j < l && Character.isDigit(s.charAt(j))); else if (cc.equals("[[")) { do ++j; while (j+1 < l && !s.substring(j, j+2).equals("]]")); j = Math.min(j+2, l); } else if (s.substring(j, Math.min(j+3, l)).equals("...")) j += 3; else ++j; tok.add(s.substring(i, j)); i = j; } if ((tok.size() % 2) == 0) tok.add(""); return tok; } }