solution to http://infinitesearchspace.dyndns.org/primesums

BoundedConcurrentSortedSet.java

import java.util.BitSet;
import java.util.NavigableSet;
import java.util.NoSuchElementException;
import java.util.concurrent.ConcurrentSkipListSet;

/**
 * A concurrent sorted set with a fixed bound
 */
public class BoundedConcurrentSortedSet {

  private final NavigableSet<Grid> set = new ConcurrentSkipListSet<Grid>();   //todo: try mapdb library?
  public int size;            // set.size is not O(1) for skiplists

  private final int CACHE_SIZE = (int) 1e9;
  private final BitSet polled = new BitSet(CACHE_SIZE);           //todo: static?

  final int LIMIT;

  public BoundedConcurrentSortedSet(int limit) {
    LIMIT = limit;
  }

  public void add(Grid g) {
    if (willAdd(g) && !polled.get(hash(g)) && set.add(new Grid(g))) {
      if (size < LIMIT) {
        size++;
      } else {
        set.pollFirst();
      }
    }
  }

  private boolean willAdd(Grid g) {
    return size < LIMIT || (size >= LIMIT && g.compareTo(set.first()) > 0);
  }

  public Grid pollLast() {
    size--;
    Grid g = set.pollLast();
    if (g != null) {
      polled.set(hash(g));
    }
    return g;
  }

  public Grid last() {
    try {
      return set.last();
    } catch (NoSuchElementException e) {
      return null;
    }
  }

  private int hash(Grid g) {
    return (CACHE_SIZE + (g.hashCode()%CACHE_SIZE))%CACHE_SIZE;
  }

  public void clear() {
    size = 0;
    set.clear();
  }
}

Grid.java

import java.util.Arrays;
import java.util.Random;

/**
 * Represents a grid
 */
public class Grid implements Comparable {
  private short[] grid;  // the grid

  // all these can be recomputed given a grid
  private int[] sums;
  private byte[] primes;
  private int primeSum;
  private short totalPrimes;
  private short uniquePrimes;
  private long quickHash;  //quick hash is sum i xor grid[i]

  private final Record r;

  /**
   * copy constructor
   */
  public Grid(Grid copy) {
    this.grid = copy.grid.clone();
    this.sums = copy.sums.clone();
    this.primes = copy.primes.clone();
    this.totalPrimes = copy.totalPrimes;
    this.uniquePrimes = copy.uniquePrimes;
    this.primeSum = copy.primeSum;
    this.quickHash = copy.quickHash;
    this.r = copy.r;
  }

  /**
   * random grid
   */
  public Grid(Record r) {
    this(getRandomGrid(r), r);
  }

  public Grid(short[] grid, Record r) {
    this.grid = grid;
    this.r = r;
    this.primes = new byte[r.N* r.N* r.N];
    this.sums = new int[4* r.N];
    for(int i = 0; i < this.grid.length; i++) {
      add(i, this.grid[i]);
      quickHash += i^ this.grid[i];
    }
  }

  private static short[] getRandomGrid(Record r) {
    short[] grid = new short[r.S];
    for(short i = 1; i <= r.S; i++) {
      grid[i-1] = i;
    }

    Random rnd = new Random();

    for (int i=r.S; i>1; i--) {
      short t = grid[i-1];
      int j = rnd.nextInt(i);
      grid[i-1] = grid[j];
      grid[j] = t;
    }
    return grid;
  }

  /**
   * Add "add" to cell[p/N][p%N]
   */
  private void add(int p, int add) {
    final int N = r.N, n = p/N, d = p%N;
    updatePrimes(n, add);        // row sum
    updatePrimes(N + d, add);        // col sum
    updatePrimes(2 * N + (n + d) % N, add);        // broken diagonal 1 sum
    updatePrimes(3 * N + (N + n - d) % N, add);        // broken diagonal 2 sum
  }

  /**
   * Helps the add() in updating primes
   */
  private void updatePrimes(int p, int add) {
    int i = isPrime[sums[p]];
    if(i>=0 && primes[i] > 0) {
      totalPrimes--;
      if(--primes[i] == 0) {
        primeSum -= sums[p];
        uniquePrimes--;
      }
    }
    sums[p] += add;
    i = isPrime[sums[p]];
    if (i>=0) {
      totalPrimes++;
      if(++primes[i] == 1) {
        primeSum += sums[p];
        uniquePrimes++;
      }
    }
  }

  /**
   * swap x,y in grid in O(1)
   * Heavily optimized to be O(1) as it takes 80% of execution time still
   */
  public void swap(int x, int y) {
    final short X = grid[x], Y = grid[y];
    final int diff = X-Y;
    add(x, -diff);
    add(y, diff);
    quickHash -= x^X;
    quickHash -= y^Y;
    quickHash += x^Y;
    quickHash += y^X;
    grid[x] = Y;
    grid[y] = X;
  }

  @Override
  public int compareTo(Object obj) {
    final Grid that = (Grid) obj;
    final int ret, p1 = this.primesNeeded(), p2 = that.primesNeeded(), p = p1*p2;

    if (p < 0) {
      ret = p1 < 0 ? 1 : -1;
    } else if(p > 0) {
      if(p1 != p2) {
        ret = p1<0 ? p1 - p2 : p2 - p1;
      } else if(this.totalPrimes != that.totalPrimes) {
        ret = p1<0 ? this.totalPrimes - that.totalPrimes : that.totalPrimes - this.totalPrimes;
      } else {
        ret = detailedCompare(that);
      }
    } else if (p1 == 0 && p2 == 0) {
      ret = detailedCompare(that);
    } else {
      ret = p1 == 0 ? 1 : -1;
    }

    return ret;
  }

  private int detailedCompare(Grid that) {
    final int ret;
    if (this.primeSum != that.primeSum) {
      ret = r.SOLVING_FOR_MAX ? this.primeSum - that.primeSum : that.primeSum - this.primeSum;
    } else if(this.totalPrimes != that.totalPrimes) {
      ret = this.totalPrimes - that.totalPrimes;  // most primes wins
    } else if(this.quickHash != that.quickHash) {
      ret = (int) (this.quickHash - that.quickHash);  // makes sure we don't discard solutions
    } else {
      int x = -1;
      for(int i = 0; i < r.S; i++) {
        if(this.grid[i] != that.grid[i]) {
          x = i;
          break;
        }
      }
      if(x == -1) {
        ret = 0;    // equals
      } else {
        ret = -1; // todo: arbitrarily break ties
      }
    }
    return ret;
  }

  /**
   * Score this grid
   * Higher the score, the better
   * Positive score denotes 2N unique primes
   * Otherwise having more primes is "better" than having less
   */
  public int score() {
    final int primesNeeded = primesNeeded();
    if (primesNeeded == 0) {
      return r.SOLVING_FOR_MAX ? primeSum : 1000000-primeSum;
    }
    return primesNeeded > 0 ? -2*primesNeeded : primesNeeded;
  }

  private int primesNeeded() {
    return 2* r.N - uniquePrimes;
  }

  public boolean isSolution() {
    return primesNeeded() == 0;
  }

  @Override
  public int hashCode() {
    return (int) quickHash;
  }

  @Override
  public boolean equals(Object obj) {
    return obj instanceof Grid && Arrays.equals(grid, ((Grid) obj).grid);
  }

  @Override
  public String toString() {
    String str = Arrays.toString(grid);
    return str.substring(1, str.length()-1);
  }

  public int getPrimeSum() {
    return primeSum;
  }

  /**
   * Prime code down here
   */
  private static final int LOG_MAX_PRIME_SIEVE = 15;
  private static short[] isPrime = new short[1<<LOG_MAX_PRIME_SIEVE];
  // isPrime[i] < 0 if i is not prime or index of that prime e.g. isPrime[2] = 1, isPrime[5] = 3 etc
  private static short PRIMES = 0;
  static {
    // pre fill primes sieve using sieve
    isPrime[0] = isPrime[1] = -1;
    for(int i  = 2; i < isPrime.length; i++) {
      if (isPrime[i] == 0) {
        isPrime[i] = ++PRIMES;
        for (int j = i * i; j < isPrime.length; j += i) {
          isPrime[j] = -1;
        }
      }
    }
  }
}

Main.java

import java.util.ArrayList;
import java.util.Date;

public class Main {

  private static final int CORES = Runtime.getRuntime().availableProcessors()-1;

  public static void main(String[] args) {
    // todo: exploit hard current sols OR exploit submitted OR branch off - my scoring function does not take into account next of kin
    ArrayList<Record> records = new ArrayList<Record>();

    records.add(compute(-28, 800));

    System.out.println("FINAL");
    for(Record r : records) {
      System.out.println(r);
    }
    System.out.println("Submit: ");
    for(Record r : records) {
      System.out.print(r.best);
      System.out.print(';');
    }
  }

  /**
   * Main entry point - call compute(8) to calculate max-8 for call(-8) for min-8
   */
  public static Record compute(int n, final int MINUTES) {
    final Record record = new Record(n);

    final long end = System.currentTimeMillis() + MINUTES * 60 * 1000;
    for(int tries = 0; System.currentTimeMillis() < end; tries++) {
      BoundedConcurrentSortedSet q = next(record, record.N <= 10 ? 50000 : 1000);
      assert q.last().isSolution();
      System.out.printf("Starting round %d with %d(%d) ", tries, q.last().getPrimeSum(), q.size);
      run(getExploiters(q, record, 10));
      Grid last = q.last();
      if(last == null) {
        System.out.print("Finished exploit queue ");
      } else {
        System.out.print("Timeout exploit [q.size=" + q.size + ", record=" + (last.isSolution() ? last.getPrimeSum() : null) + "] ");
      }
      System.out.println(new Date() + ": " + record);
    }

    return record;
  }

  private static BoundedConcurrentSortedSet next(Record r, int maxSize) {
    Swapper[] s = getExplorers(r, maxSize);
    run(s);
    BoundedConcurrentSortedSet q = new BoundedConcurrentSortedSet(maxSize);
    for(Swapper e : s) {
      if(e.q.last().isSolution()) {
        q.add(e.q.last());
      }
    }
    assert q.size>0;
    return q;
  }

  private static Swapper[] getExplorers(Record r, int maxSize) {
    Swapper[] s = new Swapper[CORES];
    for(int i = 0; i < s.length; i++) {
      s[i] = Swapper.newExplorer(r, maxSize);
    }
    return s;
  }

  private static Swapper[] getExploiters(BoundedConcurrentSortedSet q, Record r, int wait) {
    Swapper[] s = new Swapper[CORES];
    int[] waitRef = new int[]{wait};
    for(int i = 0; i < s.length; i++) {
      s[i] = Swapper.newExploiter(q, r, waitRef);
    }
    return s;
  }

  private static void run(Runnable... r) {
    Thread[] t = new Thread[r.length];
    for(int i = 0; i < r.length; i++) {
      t[i] = new Thread(r[i]);
      t[i].start();
    }

    for(Thread i : t) {
      try {
        i.join();
      } catch (InterruptedException e) {
        e.printStackTrace();
      }
    }
  }
}

Record.java

/**
 * Stored a record for given N and (min vs max)
 * Can be shared by multiple swappers
 */
public class Record {
  public final int N, S;
  public final boolean SOLVING_FOR_MAX;

  Grid best;

  public Record(int n) {
    N = Math.abs(n);
    S = n*n;
    SOLVING_FOR_MAX = n>0;
  }

  @Override
  public synchronized String toString() {
    return String.format("[%2d%s, record:%7d]: %s", N, SOLVING_FOR_MAX ? "max" : "min", best.getPrimeSum(), best);
  }
}

Swapper.java

public abstract class Swapper implements Runnable {

  protected final BoundedConcurrentSortedSet q;
  protected final Record r;

  protected Swapper(BoundedConcurrentSortedSet q, Record r) {
    this.q = q;
    this.r = r;
  }

  @Override
  public final void run() {
    for(Grid g; (g = next()) != null; ) {
      if (g.isSolution()) {
        handleSolution(g);
      }

      for(int i = 0; i < r.S; i++) {
        for(int j = i+1; j < r.S; j++) {
          g.swap(i, j);
          q.add(g);
          g.swap(j, i);
        }
      }
    }
  }

  protected abstract void handleSolution(Grid g);

  protected abstract Grid next();

  public static Swapper newExplorer(Record r, int maxSize) {
    final BoundedConcurrentSortedSet q = new BoundedConcurrentSortedSet(maxSize);
    return new Swapper(q, r) {

      @Override
      protected void handleSolution(Grid g) {
        throw new IllegalStateException("should not get here");
      }

      @Override
      protected Grid next() {
        return q.size == 0 ? new Grid(r) : q.last().isSolution() ? null : q.pollLast();
      }
    };
  }

  // problem - quickly abandon crappy hills

  public static Swapper newExploiter(BoundedConcurrentSortedSet q, Record r, final int[] waitSecond) {
    return new Swapper(q, r) {
      private int bestScore = -1;
      private long lastBeatTime = System.currentTimeMillis();
      private int[] wait = waitSecond;

      @Override
      protected void handleSolution(Grid g) {
        if (r.best == null || g.score() > r.best.score()) {
          r.best = new Grid(g);
          wait[0] = 20;
          System.out.println(q.size + " " + r);
        }
        if(g.score() > bestScore) {
          bestScore = g.score();
          lastBeatTime = System.currentTimeMillis();
        }
        // todo if q.size < 100, increase q.limit?
      }

      @Override
      protected Grid next() {
        return System.currentTimeMillis() - lastBeatTime > wait[0] * 1000 ? null : q.pollLast();
      }
    };
  }
}