RussellAndrewEdson

public class HornersRule {

    public static int totalAdditions = 0;
    public static int totalMultiplications = 0;

    /**
     * Computes the value of the polynomial with the given coefficients
     * at the point x, using Horner's Rule.
     *
     * @param coefficients An array of coefficients: a_i = coefficients[i]

RussellAndrewEdson

public class Polynomial2 {
    
    public static int totalAdditions = 0;
    public static int totalMultiplications = 0;

    /**
     * Computes the value of the polynomial with the given coefficients
     * at the point x.
     *
     * @param coefficients An array of coefficients: a_i = coefficients[i]

RussellAndrewEdson

public class Polynomial1 {
    
    public static int totalAdditions = 0;
    public static int totalMultiplications = 0;

    /**
     * Computes the value of the polynomial with the given coefficients
     * at the point x.
     *
     * @param coefficients An array of coefficients: a_i = coefficients[i]

RussellAndrewEdson

# Given a list of MIU strings, this method generates more strings by taking
# each of the strings in the list and, if possible, applying each of the Rules
# 1, 2, 3, 4 to that string. The resulting collection of strings is then
# filtered for duplicates and returned. 
def generate_more_strings(miu_strings)
  # Helper method: applies all of the possible rules to a given string, and
  # returns an array of the results.
  def apply_all_rules(str)
    results = []
    results << apply_rule1(str) if can_apply_rule1?(str)

RussellAndrewEdson

# Returns true if we can apply Rule 4 to the given string.
# (Rule 4: If "UU" appears anywhere in our string, we can drop it.)
def can_apply_rule4?(str)
  !(str.match(/UU/).nil?)
end

# Returns an array of indices for the given string where Rule 4 can be applied.
def rule4_indices(str)
  # We find all of the places where we have 2 or more U's.
  matches_for_U = str.to_enum(:scan, /U{2,}/).map { Regexp.last_match }

RussellAndrewEdson

# Returns true if we can apply Rule 3 to the given string.
# (Rule 3: If our string contains an instance of "III", we can replace
# that instance with "U".)
def can_apply_rule3?(str)
  !(str.match(/III/).nil?)
end

# Returns an array of indices for the given string where Rule 3 can be applied.
def rule3_indices(str)
  # First, we find all of the places where we have 3 or more I's.

RussellAndrewEdson

# Returns true if we can apply Rule 2 to the given string.
# (Rule 2: If our string looks like Mx, we can change it to Mxx.)
def can_apply_rule2?(str)
  str.start_with?("M")
end

# Applies Rule 2: We replace the string Mx with Mxx.
def apply_rule2(str)
  str + str[1, str.length]
end

RussellAndrewEdson

# Returns true if we can apply Rule 1 to the given string.
# (Rule 1: If the string ends with an I, we can add on a U at the end.)
def can_apply_rule1?(str)
  str.end_with?("I")
end

# Applies Rule 1: We add a U to the end of the given string.
def apply_rule1(str)
  str + "U"
end

RussellAndrewEdson

# Returns true if the given string only contains the characters M, I, U.
def miu_string?(str)
  !(str.match(/[^MIU]/))
end

RussellAndrewEdson

/* Here we create the constraints for the "backward diagonals" where
 * we move along the last column.
 *   ie. x_i,n + the sum of x_i+m,n-m <= 1 for all i=1,...,n.
 */
double[][] columnBackwardConstraintsMatrix = new double[n][n*n];
for (int row = 0; row < n; row++) {
    for (int column = n*(row+1) - 1; column < n*n; column += (n-1)) {
        columnBackwardConstraintsMatrix[row][column] = 1;
    }
}