Set.java

package setgame;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;

/**
 * Set is the container for a game instance.
 * @author Paul A. Rubin (rubin@msu.edu)
 */
public final class Set {
  /** NCARDS is the number of cards in the game. */
  public static final int NCARDS = 81;
  /** NFEATURES is the number of features on a card. */
  public static final int NFEATURES = 4;
  /** NVALUES is the number of values a feature can have. */
  public static final int NVALUES = 3;
  /** SETSIZE is the number of cards in a set. */
  public static final int SETSIZE = 3;
  private final int[][] cards;  // the card deck
  private final HashMap<Integer, HashMap<Integer, HashSet<Integer>>>
    hasFeature;
  private int found;  // number of valid sets found

  /**
   * Constructor.
   */
  public Set() {
    cards = new int[NCARDS][NFEATURES];
    int[] divisors = new int[NFEATURES + 1];
    divisors[0] = 1;
    for (int i = 1; i <= NFEATURES; i++) {
      divisors[i] = NVALUES * divisors[i - 1];
    }
    // Fill in the cards.
    for (int c = 0; c < NCARDS; c++) {
      cards[c][0] = c % divisors[1];
      for (int f = 1; f < NFEATURES; f++) {
        cards[c][f] = (c % divisors[f + 1]) / divisors[f];
      }
    }
    // Fill in the feature possession map.
    hasFeature = new HashMap<>();
    for (int f = 0; f < NFEATURES; f++) {
      HashMap<Integer, HashSet<Integer>> m = new HashMap<>();
      for (int v = 0; v < NVALUES; v++) {
        HashSet<Integer> s = new HashSet<>();
        for (int c = 0; c < NCARDS; c++) {
          if (cards[c][f] == v) {
            s.add(c);
          }
        }
        m.put(v, s);
      }
      hasFeature.put(f, m);
    }
  }

  /**
   * Gets the set of cards with a particular value of a particular feature.
   * @param feature the feature
   * @param value the target value
   * @return the set of cards with that value
   */
  public Collection<Integer> findCards(final int feature, final int value) {
    return new HashSet<>(hasFeature.get(feature).get(value));
  }

  /**
   * Prints a set.
   * @param set the set to print
   */
  public void printSet(final Collection<Integer> set) {
    ArrayList<Integer> list = new ArrayList<>(set);
    Collections.sort(list);
    for (int c : list) {
      System.out.println(Arrays.toString(cards[c]) + " (" + c + ")");
    }
  }

  /**
   * Computes all valid sets by brute force (using recursion).
   * @return the number of sets found
   */
  public int findAllSets() {
    found = 0;
    HashMap<Integer, HashSet<Integer>> map = new HashMap<>();
    for (int f = 0; f < NFEATURES; f++) {
      map.put(f, new HashSet<>());
    }
    enumerate(1, 0, map);
    return found;
  }

  /**
   * Recursively enumerates all valid sets.
   * @param level the level (1 ... SETSIZE) at which the function is called
   * @param start the initial card index
   * @param values the accumulated values of all features
   */
  private void enumerate(final int level, final int start,
                         final HashMap<Integer, HashSet<Integer>> values) {
    // Check for vacuous cases (level or start index too high).
    if (level > SETSIZE || start == NCARDS) {
      return;
    }
    for (int c = start; c < NCARDS; c++) {
      // Clone the values map, adding the value of each feature in card c.
      HashMap<Integer, HashSet<Integer>> v = new HashMap<>();
      for (int f = 0; f < NFEATURES; f++) {
        HashSet<Integer> s = new HashSet<>(values.get(f));
        s.add(cards[c][f]);
        v.put(f, s);
      }
      if (level == SETSIZE) {
        // Final level: check for a valid set and if valid count it.
        boolean valid = true;
        for (int f = 0; f < NFEATURES; f++) {
          if (v.get(f).size() == 2) {
            valid = false;
            break;
          }
        }
        if (valid) {
          found += 1;
        }
      } else {
        // Call enumerate at the next level.
        enumerate(level + 1, c + 1, v);
      }
    }
  }

  /**
   * Gets the value of a particular feature for every card.
   * @param feature the feature
   * @return the vector of feature values
   */
  public int[] getValues(final int feature) {
    int[] v = new int[NCARDS];
    for (int c = 0; c < NCARDS; c++) {
      v[c] = cards[c][feature];
    }
    return v;
  }
}