Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Some more progress in proving the optimality of the results for a number game; see http://math.stackexchange.com/questions/1341929
import java.math.BigInteger;
import java.util.HashSet;
import java.util.Set;
public class Question1341929Dynamic {
final static int maxn = 1000;
final static int maxslots = 2 * maxn + 1;
static class Record {
BigInteger left;
BigInteger right;
// List<Integer> moves;
public Record (BigInteger left,BigInteger right) {
this.left = left;
this.right = right;
// moves = new ArrayList<Integer> ();
}
public Record (Record r,int i) {
left = r.right.add (r.left);
right = r.right.add (values [i]);
// (moves = new ArrayList<Integer> (r.moves)).add (i - 1);
}
public Record (int i,Record r) {
right = r.left.add (r.right);
left = r.left.add (values [i]);
// (moves = new ArrayList<Integer> (r.moves)).add (i + 1);
}
public BigInteger value () {
return left.add (right);
}
public String toString () {
return "<" + left + "," + right + ">";
}
public boolean dominates (Record r) {
return left.compareTo (r.left) >= 0 && right.compareTo (r.right) >= 0;
}
}
static class RecordSet {
Set<Record> records = new HashSet<Record> ();
void add (Record r) {
if (!records.stream ().anyMatch (record -> record.dominates (r))) {
records.removeIf (record -> r.dominates (record));
records.add (r);
}
}
public BigInteger value () {
return records.stream ().map (Record::value).reduce (BigInteger.ZERO,(a,b) -> a.compareTo (b) > 0 ? a : b);
}
public String toString () {
return records.toString ();
}
}
// records [m] [n] contains the "best" ways to sum slots in [m,n]
static RecordSet [] [] records = new RecordSet [maxslots] [maxslots];
static BigInteger [] values = new BigInteger [maxslots];
public static void main (String [] args) {
for (int i = 0;i < maxslots;i++)
values [i] = BigInteger.valueOf (Math.abs (i - maxn) + 1);
for (int i = 0;i + 1 < maxslots;i++)
(records [i] [i + 1] = new RecordSet ()).add (new Record (values [i],values [i + 1]));
for (int delta = 2;delta <= 2 * maxn;delta++)
for (int i = 0;i + delta < maxslots;i++) {
RecordSet newRecords = new RecordSet ();
for (Record record : records [i] [i + delta - 1].records)
newRecords.add (new Record (record,i + delta));
for (Record record : records [i + 1] [i + delta].records)
newRecords.add (new Record (i,record));
records [i] [i + delta] = newRecords;
}
for (int n = 2;n <= maxn;n++)
System.out.println (n + " : " + records [maxn - (n - 1)] [maxn + (n - 1)].value ());
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.