TradeMaximizer.java

// TradeMaximizer.java
// Created by Chris Okasaki (cokasaki)
// Version 1.3a
// $LastChangedDate: 2008-03-07 09:08:08 -0500 (Fri, 07 Mar 2008) $
// $LastChangedRevision: 28 $

import java.io.*;
import java.util.*;
import java.text.*;

public class TradeMaximizer {
  public static void main(String[] args) { new TradeMaximizer().run(); }

  final String version = "Version 1.3a";

  // This function is executed by main() at startup
  void run() {
    System.out.println("TradeMaximizer " + version);

    // Read in the want options, usernames, and want lists
    List< String[] > wantLists = readWantLists();
    if (wantLists == null) return;

    // Display custom options, if they exist
    if (options.size() > 0) {
      System.out.print("Options:");
      for (String option : options) System.out.print(" "+option);
      System.out.println();
    }
    System.out.println();

    // Create the graph by parsing the want lists and other input
    buildGraph(wantLists);

    // Display more info if requested by options
    if (showMissing && officialNames != null && officialNames.size() > 0) {
      for (String name : usedNames) officialNames.remove(name);
      List<String> missing = new ArrayList<String>(officialNames);
      Collections.sort(missing);
      for (String name : missing) {
        System.out.println("**** Missing want list for official name " +name);
      }
      System.out.println();
    }
    if (showErrors && errors.size() > 0) {
      Collections.sort(errors);
      System.out.println("ERRORS:");
      for (String error : errors) System.out.println(error);
      System.out.println();
    }

    // Input parsing is completed. Before we start processing, we'll take a
    // timestamp so we can later report the total processing time
    long startTime = System.currentTimeMillis();

    // Remove unusable entries and edges from the graph
    graph.removeImpossibleEdges();

    // Perform the actual search
    List<List<Graph.Vertex>> bestCycles = graph.findCycles();
    int bestSumSquares = sumOfSquares(bestCycles);

    // Repeat the search for each iteration
    if (iterations > 1) {
      graph.saveMatches();
      for (int i = 0; i < iterations-1; i++) {
        // Shuffle the receiver order around
        graph.shuffle();
        // Perform the actual search again
        List<List<Graph.Vertex>> cycles = graph.findCycles();

        // Determine if we have a better solution this time
        int sumSquares = sumOfSquares(cycles);
        if (sumSquares < bestSumSquares) {
          // Save off info on the new find
          bestSumSquares = sumSquares;
          bestCycles = cycles;
          graph.saveMatches();
          // Prepare some display information for the user
          int[] groups = new int[cycles.size()];
          for (int j = 0; j < cycles.size(); j++)
            groups[j] = cycles.get(j).size();
          Arrays.sort(groups);
          // Display stats on the new find
          System.out.print("[ "+sumSquares + " :");
          for (int j = groups.length-1; j >= 0; j--)
            System.out.print(" " + groups[j]);
          System.out.println(" ]");
        }
      }
      System.out.println();
      // Restore info regarding our best matching solution
      graph.restoreMatches();
    }
    long stopTime = System.currentTimeMillis();
    displayMatches(bestCycles);

    if (showElapsedTime)
      System.out.println("Elapsed time = " + (stopTime-startTime) + "ms");
  }

  // Find the sum of the squared cycle (loop) sizes. Used in determining
  // which solution has the largest loops.
  int sumOfSquares(List<List<Graph.Vertex>> cycles) {
    int sum = 0;
    for (List<Graph.Vertex> cycle : cycles) sum += cycle.size()*cycle.size();
    return sum;
  }

  boolean caseSensitive = false;
  boolean requireColons = false;
  boolean requireUsernames = false;
  boolean showErrors = true;
  boolean showRepeats = true;
  boolean showLoops = true;
  boolean showSummary = true;
  boolean showNonTrades = true;
  boolean showStats = true;
  boolean showMissing = false;
  boolean sortByItem = false;
  boolean allowDummies = false;
  boolean showElapsedTime = false;

  static final int NO_PRIORITIES = 0;
  static final int LINEAR_PRIORITIES = 1;
  static final int TRIANGLE_PRIORITIES = 2;
  static final int SQUARE_PRIORITIES = 3;
  static final int SCALED_PRIORITIES = 4;
  static final int EXPLICIT_PRIORITIES = 5;

  int priorityScheme = NO_PRIORITIES;
  int smallStep = 1;
  int bigStep = 9;
  long nonTradeCost = 1000000000L; // 1 billion

  int iterations = 1;

  //////////////////////////////////////////////////////////////////////

  List<String> options = new ArrayList<String>();
  HashSet<String> officialNames = null;
  List<String> usedNames = new ArrayList<String>();

  List<String[]> readWantLists() {
    try {
      BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
      List<String[]> wantLists = new ArrayList<String[]>();
      boolean readingOfficialNames = false;

      for (int lineNumber = 1;;lineNumber++) {
        String line = in.readLine();
        if (line == null) return wantLists;

        line = line.trim();
        if (line.length() == 0) continue; // skip blank link

        // Handle options
        if (line.matches("#!.*")) {
          if (wantLists.size() > 0)
            fatalError("Options (#!...) cannot be declared after first real want list", lineNumber);
          if (officialNames != null)
            fatalError("Options (#!...) cannot be declared after official names", lineNumber);
          for (String option : line.toUpperCase().substring(2).trim().split("\\s+")) {
            if (option.equals("CASE-SENSITIVE"))
              caseSensitive = true;
            else if (option.equals("REQUIRE-COLONS"))
              requireColons = true;
            else if (option.equals("REQUIRE-USERNAMES"))
              requireUsernames = true;
            else if (option.equals("HIDE-ERRORS"))
              showErrors = false;
            else if (option.equals("HIDE-REPEATS"))
              showRepeats = false;
            else if (option.equals("HIDE-LOOPS"))
              showLoops = false;
            else if (option.equals("HIDE-SUMMARY"))
              showSummary = false;
            else if (option.equals("HIDE-NONTRADES"))
              showNonTrades = false;
            else if (option.equals("HIDE-STATS"))
              showStats = false;
            else if (option.equals("SHOW-MISSING"))
              showMissing = true;
            else if (option.equals("SORT-BY-ITEM"))
              sortByItem = true;
            else if (option.equals("ALLOW-DUMMIES"))
              allowDummies = true;
            else if (option.equals("SHOW-ELAPSED-TIME"))
              showElapsedTime = true;
            else if (option.equals("LINEAR-PRIORITIES"))
              priorityScheme = LINEAR_PRIORITIES;
            else if (option.equals("TRIANGLE-PRIORITIES"))
              priorityScheme = TRIANGLE_PRIORITIES;
            else if (option.equals("SQUARE-PRIORITIES"))
              priorityScheme = SQUARE_PRIORITIES;
            else if (option.equals("SCALED-PRIORITIES"))
              priorityScheme = SCALED_PRIORITIES;
            else if (option.equals("EXPLICIT-PRIORITIES"))
              priorityScheme = EXPLICIT_PRIORITIES;
            else if (option.startsWith("SMALL-STEP=")) {
              String num = option.substring(11);
              if (!num.matches("\\d+"))
                fatalError("SMALL-STEP argument must be a non-negative integer",lineNumber);
              smallStep = Integer.parseInt(num);
            }
            else if (option.startsWith("BIG-STEP=")) {
              String num = option.substring(9);
              if (!num.matches("\\d+"))
                fatalError("BIG-STEP argument must be a non-negative integer",lineNumber);
              bigStep = Integer.parseInt(num);
            }
            else if (option.startsWith("NONTRADE-COST=")) {
              String num = option.substring(14);
              if (!num.matches("[1-9]\\d*"))
                fatalError("NONTRADE-COST argument must be a positive integer",lineNumber);
              nonTradeCost = Long.parseLong(num);
            }
            else if (option.startsWith("ITERATIONS=")) {
              String num = option.substring(11);
              if (!num.matches("[1-9]\\d*"))
                fatalError("ITERATIONS argument must be a positive integer",lineNumber);
              iterations = Integer.parseInt(num);
            }
            else if (option.startsWith("SEED=")) {
              String num = option.substring(5);
              if (!num.matches("[1-9]\\d*"))
                fatalError("SEED argument must be a positive integer",lineNumber);
              graph.setSeed(Long.parseLong(num));
            }
            else
              fatalError("Unknown option \""+option+"\"",lineNumber);

            options.add(option);
          }
          continue;
        }
        if (line.matches("#.*")) continue; // skip comment line
        if (line.indexOf("#") != -1) {
          if (readingOfficialNames) {
            if (line.split("[:\\s]")[0].indexOf("#") != -1) {
              fatalError("# symbol cannot be used in an item name",lineNumber);
            }
          }
          else
            fatalError("Comments (#...) cannot be used after beginning of line",lineNumber);
        }

        // Handle official name
        if (line.equalsIgnoreCase("!BEGIN-OFFICIAL-NAMES")) {
          if (officialNames != null)
            fatalError("Cannot begin official names more than once", lineNumber);
          if (wantLists.size() > 0)
            fatalError("Official names cannot be declared after first real want list", lineNumber);

          officialNames = new HashSet<String>();
          readingOfficialNames = true;
          continue;
        }
        if (line.equalsIgnoreCase("!END-OFFICIAL-NAMES")) {
          if (!readingOfficialNames)
            fatalError("!END-OFFICIAL-NAMES without matching !BEGIN-OFFICIAL-NAMES", lineNumber);
          readingOfficialNames = false;
          continue;
        }
        if (readingOfficialNames) {
          if (line.charAt(0) == ':')
            fatalError("Line cannot begin with colon",lineNumber);
          if (line.charAt(0) == '%')
            fatalError("Cannot give official names for dummy items",lineNumber);

          String[] toks = line.split("[:\\s]");
          String name = toks[0];
          if (!caseSensitive) name = name.toUpperCase();
          if (officialNames.contains(name))
            fatalError("Official name "+name+"+ already defined",lineNumber);
          officialNames.add(name);
          continue;
        }

        // Handle wants
        // check parens for user name preceding wants
        if (line.indexOf("(") == -1 && requireUsernames)
          fatalError("Missing username with REQUIRE-USERNAMES selected",lineNumber);
        if (line.charAt(0) == '(') {
          if (line.lastIndexOf("(") > 0)
            fatalError("Cannot have more than one '(' per line",lineNumber);
          int close = line.indexOf(")");
          if (close == -1)
            fatalError("Missing ')' in username",lineNumber);
          if (close == line.length()-1)
            fatalError("Username cannot appear on a line by itself",lineNumber);
          if (line.lastIndexOf(")") > close)
            fatalError("Cannot have more than one ')' per line",lineNumber);
          if (close == 1)
            fatalError("Cannot have empty parentheses",lineNumber);

          // temporarily replace spaces in username with #'s
          if (line.indexOf(" ") < close) {
            line = line.substring(0,close+1).replaceAll(" ","#")+" "
                    + line.substring(close+1);
          }
        }
        else if (line.indexOf("(") > 0)
          fatalError("Username can only be used at the front of a want list",lineNumber);
        else if (line.indexOf(")") > 0)
          fatalError("Bad ')' on a line that does not have a '('",lineNumber);


        // Check wants for semicolons, which indicate a large step in rank
        // value between two wants
        line = line.replaceAll(";"," ; "); // place extra space around semicolons
        int semiPos = line.indexOf(";");
        if (semiPos != -1) {
          if (semiPos < line.indexOf(":")) // Semicolons can only appear between wants
            fatalError("Semicolon cannot appear before colon",lineNumber);
          String before = line.substring(0,semiPos).trim();
          if (before.length() == 0 || before.charAt(before.length()-1) == ')')
            fatalError("Semicolon cannot appear before first item on line", lineNumber);
        }

        // Check and remove colon, which should occur just after the item whose
        // wants are being specified
        int colonPos = line.indexOf(":");
        if (colonPos != -1) {
          if (line.lastIndexOf(":") != colonPos)
            fatalError("Cannot have more that one colon on a line",lineNumber);
          String header = line.substring(0,colonPos).trim();
          if (!header.matches("(.*\\)\\s+)?[^(\\s)]\\S*"))
            fatalError("Must have exactly one item before a colon (:)",lineNumber);
          line = line.replaceFirst(":"," "); // remove colon
        }
        else if (requireColons) {
          fatalError("Missing colon with REQUIRE-COLONS selected",lineNumber);
        }

        if (!caseSensitive) line = line.toUpperCase();
        // Add an array of each item on the list to wantLists. The first item is
        // the username, if present. The next item (or the first, if no username)
        // is the item whose wants are specified in the remaining items.
        wantLists.add(line.trim().split("\\s+"));
      }
    }
    catch(Exception e) {
      fatalError(e.getMessage());
      return null;
    }
  }

  void fatalError(String msg) {
    System.out.println();
    System.out.println("FATAL ERROR: " + msg);
    System.exit(1);
  }
  void fatalError(String msg,int lineNumber) {
    fatalError(msg + " (line " + lineNumber + ")");
  }

  //////////////////////////////////////////////////////////////////////

  Graph graph = new Graph();

  List< String > errors = new ArrayList< String >();

  final long INFINITY = 100000000000000L; // 10^14
  // final long NOTRADE  = 1000000000L; // replaced by nonTradeCost
  final long UNIT     = 1L;

  int ITEMS; // the number of items being traded (including dummy items)
  int DUMMY_ITEMS; // the number of dummy items

  String[] deleteFirst(String[] a) {
    assert a.length > 0;
    String[] b = new String[a.length-1];
    for (int i = 0; i < b.length; i++) b[i] = a[i+1];
    return b;
  }

  void buildGraph(List< String[] > wantLists) {

    HashMap< String,Integer > unknowns = new HashMap< String,Integer >();

    // create the nodes
    for (int i = 0; i < wantLists.size(); i++) {
      String[] list = wantLists.get(i);
      assert list.length > 0; // Every array of strings should be a formatted want list
      String name = list[0]; // The item to be traded (whose wants are specified here)
      String user = null;
      int offset = 0; // Note: this is unused

      // Check whether a name is present as the first string
      if (name.charAt(0) == '(') {
        user = name.replaceAll("#"," "); // restore spaces in username
        list = deleteFirst(list); // remove the username from the list
          // was Arrays.copyOfRange(list,1,list.length);
          // but that caused problems on Macs
        wantLists.set(i,list);
        name = list[0]; // set the current item to be traded to the next string
      }

      // Check whether this item is a dummy item
      boolean isDummy = (name.charAt(0) == '%');
      if (isDummy) {
        if (user == null)
          errors.add("**** Dummy item " + name + " declared without a username.");
        else if (!allowDummies)
          errors.add("**** Dummy items not allowed. ("+name+")");
        else {
          name += " for user " + user;
          list[0] = name;
        }
      }

      // Check whether the item exists in the list of official item names, if present
      if (officialNames != null && !officialNames.contains(name) && name.charAt(0) != '%') {
        errors.add("**** Cannot define want list for "+name+" because it is not an official name.  (Usually indicates a typo by the item owner.)");
        wantLists.set(i,null);
      }
      else if (graph.getVertex(name) != null) {
        errors.add("**** Item " + name + " has multiple want lists--ignoring all but first.  (Sometimes the result of an accidental line break in the middle of a want list.)");
        wantLists.set(i, null);
      }
      else {
        ITEMS++; // increment the number of items being offered
        if (isDummy) DUMMY_ITEMS++; // keep track of how many offered items are dummy items

        // Add sender and receiver vertices (nodes) to the graph
        Graph.Vertex vertex = graph.addVertex(name,user,isDummy);

        // Mark this item's name as added to the graph
        if (officialNames != null && officialNames.contains(name))
          usedNames.add(name);

        // Keep track of the longest name+entry length for output formatting purposes
        if (!isDummy) width = Math.max(width, show(vertex).length());
      }
    }

    // Create the edges
    for (String[] list : wantLists) {
      if (list == null) continue; // skip the duplicate lists
      String fromName = list[0];
      Graph.Vertex fromVertex = graph.getVertex(fromName);

      // Add the "no-trade" edge to itself (from receiver to sender node)
      graph.addEdge(fromVertex,fromVertex.twin,nonTradeCost);

      // Evaluate each want for this item
      long rank = 1;
      for (int i = 1; i < list.length; i++) {
        String toName = list[i]; // focus on this want

        // A single semicolon represents a large step in rank value between
        // two items
        if (toName.equals(";")) {
          rank += bigStep;
          continue;
        }

        // Perform entry error checking on the current want
        if (toName.indexOf('=') >= 0) {
          // Handle explicit priorities (e.g., ThisWant=100)
          if (priorityScheme != EXPLICIT_PRIORITIES) {
            errors.add("**** Cannot use '=' annotation in item "+toName+" in want list for item "+fromName+" unless using EXPLICIT_PRIORITIES.");
            continue;
          }
          if (!toName.matches("[^=]+=[0-9]+")) {
            errors.add("**** Item "+toName+" in want list for item "+fromName+" must have the format 'name=number'.");
            continue;
          }
          String[] parts = toName.split("=");
          assert(parts.length == 2);
          long explicitCost = Long.parseLong(parts[1]);
          if (explicitCost < 1) {
            errors.add("**** Explicit priority must be positive in item "+toName+" in want list for item "+fromName+".");
            continue;
          }
          rank = explicitCost;
          toName = parts[0];
        }

        // Handle dummy items
        if (toName.charAt(0) == '%') {
          // Make sure this item has an associated username if it wants a dummy item
          if (fromVertex.user == null) {
            errors.add("**** Dummy item " + toName + " used in want list for item " + fromName + ", which does not have a username.");
            continue;
          }

          // Append the username to the dummy item to prevent confusion in cases
          // where multiple users have dummy items with the same name.
          toName += " for user " + fromVertex.user;
        }

        Graph.Vertex toVertex = graph.getVertex(toName); // grab the vertex (node) for this want
        if (toVertex == null) {
          if (officialNames != null && officialNames.contains(toName)) {
            // this is an official item whose owner did not submit a want list
            rank += smallStep;
          }
          else {
            // there is no offical item list; track number of uknown items
            int occurrences = unknowns.containsKey(toName) ? unknowns.get(toName) : 0;
            unknowns.put(toName,occurrences + 1);
          }
          continue;
        }

        toVertex = toVertex.twin; // adjust to the sending vertex
        if (toVertex == fromVertex.twin) {
          errors.add("**** Item " + toName + " appears in its own want list.");
        }
        else if (graph.getEdge(fromVertex,toVertex) != null) {
          if (showRepeats)
            errors.add("**** Item " + toName + " is repeated in want list for " + fromName + ".");
        }
        else if (!toVertex.isDummy &&
                 fromVertex.user != null &&
                 fromVertex.user.equals(toVertex.user)) {
          errors.add("**** Item "+fromVertex.name +" contains item "+toVertex.name+" from the same user ("+fromVertex.user+")");
        }
        else {
          long cost = UNIT;
          switch (priorityScheme) {
            case LINEAR_PRIORITIES:   cost = rank; break;
            case TRIANGLE_PRIORITIES: cost = rank*(rank+1)/2; break;
            case SQUARE_PRIORITIES:   cost = rank*rank; break;
            case SCALED_PRIORITIES:   cost = rank; break; // assign later
            case EXPLICIT_PRIORITIES: cost = rank; break;
          }

          // All edges out of a dummy node have the same cost because
          // they are usually considered to be the same item for
          // duplicate protection.
          if (fromVertex.isDummy) cost = nonTradeCost;

          // Add a connection from the listed item's receiver node to
          // the wanted item's sender node.
          graph.addEdge(fromVertex,toVertex,cost);

          // Increase the rank for calculating the priority of the next want
          rank += smallStep;
        }
      }

      // Update costs for those priority schemes that need information such as
      // number of wants
      if (!fromVertex.isDummy) {
        switch (priorityScheme) {
          case SCALED_PRIORITIES:
            int n = fromVertex.edges.size()-1;
            for (Graph.Edge edge : fromVertex.edges) {
              if (edge.sender != fromVertex.twin)
                edge.cost = 1 + (edge.cost-1)*2520/n;
            }
            break;
        }
      }
    }

    // "Freeze" the graph, declaring that we have finished adding things to it
    // and readying it for cleanup and analysis
    graph.freeze();

    // If any unknown items were added as wants, display those to the user now
    for (Map.Entry< String,Integer > entry : unknowns.entrySet()) {
      String item = entry.getKey();
      int occurrences = entry.getValue();
      String plural = occurrences == 1 ? "" : "s";
      errors.add("**** Unknown item " + item + " (" + occurrences + " occurrence" + plural + ")");
    }

  } // end buildGraph

  String show(Graph.Vertex vertex) {
    if (vertex.user == null || vertex.isDummy) return vertex.name;
    else if (sortByItem) return vertex.name + " " + vertex.user;
    else return vertex.user + " " + vertex.name;
  }

  //////////////////////////////////////////////////////////////////////

  void displayMatches(List<List<Graph.Vertex>> cycles) {
    int numTrades = 0;
    int numGroups = cycles.size();
    int totalCost = 0;
    int sumOfSquares = 0;
    List< Integer > groupSizes = new ArrayList< Integer >();

    List< String > summary = new ArrayList< String >();
    List< String > loops = new ArrayList< String >();

    for (List<Graph.Vertex> cycle : cycles) {
      int size = cycle.size();
      numTrades += size;
      sumOfSquares += size*size;
      groupSizes.add(size);
      for (Graph.Vertex v : cycle) {
        assert v.match != v.twin;
        loops.add(pad(show(v)) + " receives " + show(v.match.twin));
        summary.add(pad(show(v)) + " receives " + pad(show(v.match.twin)) + " and sends to " + show(v.twin.match));
        totalCost += v.matchCost;
      }
      loops.add("");
    }
    if (showNonTrades) {
      for (Graph.Vertex v : graph.RECEIVERS) {
        if (v.match == v.twin && !v.isDummy)
          summary.add(pad(show(v)) + "             does not trade");
      }
      for (Graph.Vertex v : graph.orphans) {
        if (!v.isDummy)
          summary.add(pad(show(v)) + "             does not trade");
      }
    }

    if (showLoops) {
      System.out.println("TRADE LOOPS (" + numTrades + " total trades):");
      System.out.println();
      for (String item : loops) System.out.println(item);
    }

    if (showSummary) {
      Collections.sort(summary);
      System.out.println("ITEM SUMMARY (" + numTrades + " total trades):");
      System.out.println();
      for (String item : summary) System.out.println(item);
      System.out.println();
    }


    System.out.print("Num trades  = " + numTrades + " of " + (ITEMS-DUMMY_ITEMS) + " items");
    if (ITEMS-DUMMY_ITEMS == 0) System.out.println();
    else System.out.println(new DecimalFormat(" (0.0%)").format(numTrades/(double)(ITEMS-DUMMY_ITEMS)));

    if (showStats) {
      System.out.print("Total cost  = " + totalCost);
      if (numTrades == 0) System.out.println();
      else System.out.println(new DecimalFormat(" (avg 0.00)").format(totalCost/(double)numTrades));
      System.out.println("Num groups  = " + numGroups);
      System.out.print("Group sizes =");
      Collections.sort(groupSizes);
      Collections.reverse(groupSizes);
      for (int groupSize : groupSizes) System.out.print(" " + groupSize);
      System.out.println();
      System.out.println("Sum squares = " + sumOfSquares);

//      System.out.println("Orphans     = " + graph.orphans.size());
    }
  }

  // Keep track of name widths for formatting purposes
  int width = 1;
  // Pad a name with trailing spaces so they align nicely
  String pad(String name) {
    while (name.length() < width) name += " ";
    return name;
  }

} // end TradeMaximizer