package hidden; import java.util.Set; import edu.neu.ccs.demeterf.*; import edu.neu.ccs.demeterf.stackless.HeapTrav; import edu.neu.ccs.demeterf.demfgen.lib.List; import edu.neu.ccs.demeterf.demfgen.lib.ident; import gen.*; import edu.neu.ccs.evergreen.ir.Relation; import edu.neu.ccs.satsolver.*; /** Various Tools for the Generic Player and Friends */ public class Tools{ /** Skip the first of a list */ static Control skipFst = Control.bypass("edu.neu.ccs.demeterf.demfgen.lib.Cons.first"); /** Create a New Traversal */ //static HeapTrav newTrav(ID func){ return newTrav(func,Control.everywhere()); } static StaticTrav newTrav(ID func){ return newTrav(func,Control.everywhere()); } /** Create a New Traversal with Control */ //static HeapTrav newTrav(ID func, Control c){ return new HeapTrav(func,c); } static StaticTrav newTrav(ID func, Control c){ return new StaticTrav(func,c); } /** Create a symmetric formula using the given Relation numbers */ public static List<Constraint> symmetric(List<RelationNr> rs, int numVars, int rank){ final List<List<Variable>> vars = Tools.combs(numVars, rank, new List.Build<Variable>(){ public Variable build(int n){ return new Variable(new ident("v"+n)); } }); //** Create a list of Constraints for each Relation for all the variable lists List<Constraint> constrs = newTrav(new ID(){ List<Constraint> combine(){ return List.<Constraint>create(); } List<Constraint> combine(List l, final RelationNr r, final List<Constraint> rst){ return newTrav(new ID(){ List<Constraint> combine(){ return rst; } List<Constraint> combine(List<List<Variable>> v, List<Variable> vs, List<Constraint> rst){ return rst.push(new Constraint(new Weight(1), r, vs)); }},skipFst).<List<Constraint>>traverse(vars); } },skipFst).<List<Constraint>>traverseList_RelationNr_(rs); return constrs; } /** N choose K, the dynamic programming way! ;) */ public static <X> List<List<X>> combs(int n, int k, List.Build<X> b){ List<List<X>>[][] tbl = new List[n+1][k+1]; for(int ik = 0; ik <= k; ik++) for(int in = 0; in <= n; in++){ List<List<X>> newlst; if(ik == 0)newlst = List.create(List.<X>create()); else if(in < ik)newlst = List.create(); else newlst = tbl[in-1][ik].append(tbl[in-1][ik-1].map(new PushN<X>(b.build(in)))); tbl[in][ik] = newlst; } return tbl[n][k]; } /** Push the given number onto the front of each list */ private static class PushN<X> extends List.Map<List<X>,List<X>>{ X x; public PushN(X xx){ x = xx; } public List<X> map(List<X> l){ return l.push(x); } } /** Interest given back on the amount payed for a derivative */ static double INTEREST = 0; /** Incentive to produce a higher quality assignment */ static double INCENTIVE = 1; /** Compute the Payback for a given assignment of a Derivative */ public static double payback(Derivative d, Assignment a){ return payback(d, quality(d.optraw.inner().instance, a)); } /** Compute the Payback for a given quality */ public static double payback(Derivative d, double q){ if(d.isClassic())return q; // Else... new profit calculation double pr = d.price.val, sq = d.optraw.inner().instance.secret.inner().quality.val; boolean WIN = q >= sq*pr; double pay = pr * (1+INTEREST) + INCENTIVE*(q-pr*sq); return WIN?pay:0; } /** Compute the quality of an assignment == satRatio(reduce(rm,a)) */ public static double quality(final RawMaterialInstance rmi, Assignment a){ RawMaterial reduced = newTrav(new ID(){ RawMaterial combine(){ return new RawMaterial(rmi); } RawMaterial combine(List<Literal> a, Literal lit, RawMaterial r){ return reduce(r, lit); }},skipFst).<RawMaterial>traverseList_Literal_(a.literals); return satisfiedRatio(reduced); } /** Reduce a given RawMaterial based on a single Literal assignment */ public static RawMaterial reduce(RawMaterial s, final Literal lit){ return new RawMaterial(new RawMaterialInstance( newTrav(new Bc(){ public Constraint combine(Constraint c, Weight w, RelationNr r, List<Variable> vs){ int i = vs.index(lit.var); if(i < 0 || (r.v == 255))return c; return new Constraint(w, new RelationNr(new Relation(3, r.v) .reduce(i, lit.value.sign())), vs); }},Control.bypass(Constraint.class)).<List<Constraint>>traverseList_Constraint_(s.instance.cs))); } /** Accumulation for the satisfaction ratio */ static class R{ double top, bot; R(double t, double b){ top = t; bot = b; } R add(int t, int b){ return new R(top+t, bot+b); } double result(){ return bot==0.0?1.0:top/(double)bot; } } /** Calculate the satifaction ratio of a (reduced) RawMaterial */ public static double satisfiedRatio(RawMaterial rm){ return newTrav(new ID(){ R combine(){ return new R(0,0); } R combine(List<Constraint> cs, Constraint c, R r){ return r.add((c.r.v == 255)?c.w.v:0, c.w.v); }},skipFst).<R>traverseList_Constraint_(rm.instance.cs).result(); } /** Other tools for code generation and helpful stuff... */ static List<String> cmds = List.create("encode","test","prefs"); static void p(String s){ System.out.println(s); } static void usage(){ p(" ** usage : java Tools <cmd> <args...>\n"+ " Unfortunately the usage and passcode are secret! ;)"); System.exit(1); } static String MASTER = "009020548cf0d094"; /** The class file will be available, so I wanted to protect the Main method * from immediate tampering */ public static void main(String[] args){ if(args.length < 2 || !cmds.contains(args[0]) || !encode(args[1]).equals(MASTER)) usage(); switch(cmds.index(args[0])){ case 0: doEncode(args[1]); return; case 1: doTest(); return; case 2: createPreference(); return; default: usage(); } } static int LEN = 8; static String hex = "0123456789abcdef"; /** Print out the result of encoding the string... used to set the MASTER passcode */ static void doEncode(String passC){ p(" Result: \""+encode(passC)+"\""); } /** Encode a given passcode... then we can see if it's correct */ static String encode(String passC){ byte[] pass = (passC+passC).getBytes(); int [] res = new int[LEN]; for(int i = 0; i < LEN; i++) for(int j = 0; j < pass.length-LEN; j++) res[i] ^= pass[(i+j)%pass.length]<<2; String ret = ""; for(int i = 0; i < LEN; i++) ret += hex.charAt((res[i]>>4)&0xF)+""+ hex.charAt(res[i]&0xF); return ret; } /** Simple Password Test */ static void doTest(){ p(" * Password Correct!"); } /** For computing the break-even prices */ static class Input implements InputInitialI{ int rn; Input(int r){ rn = r; } public Set getPairs(){ Set<PairI> s = new java.util.HashSet<PairI>(); s.add(new PairI(){ /** The GenericPlayer only uses 1 relation (100%) */ public double getFraction(){ return 1; } public int getRelationNumber(){ return rn; } }); return s; } } /** Figure out what the best single constraint derivatives are so we can be a * little smarter about offering them */ static void createPreference(){ List<Pair<Integer,Double>> means = List.buildlist(new List.Build<Pair<Integer,Double>>(){ public Pair<Integer,Double> build(int i){ OutputI out = SATSolverUtil.calculateBias(new Input(i+1)); return new Pair<Integer,Double>(i+1, out.getPolynomial().eval(out.getMaxBias())); }}, 254).filter(new List.Pred<Pair<Integer,Double>>(){ public boolean huh(Pair<Integer,Double> p){ return p.b != 1.0; } }); System.out.println(means.sort(new List.Comp<Pair<Integer,Double>>(){ public boolean comp(Pair<Integer,Double> a, Pair<Integer,Double> b){ return a.b < b.b; } }).toString(new List.Stringer<Pair<Integer,Double>>(){ public String toString(Pair<Integer,Double> p, List<Pair<Integer,Double>> r){ return " new Pair<Integer, Double>("+p.a+","+p.b+"),\n"; } })); } /** GenericPlayer's TypeInstance offering preferences (in order) */ public static List<Pair<Integer,Double>> PREFS = List.create( new Pair<Integer, Double>(2,0.14814814814814814), new Pair<Integer, Double>(4,0.14814814814814814), new Pair<Integer, Double>(8,0.14814814814814814), new Pair<Integer, Double>(16,0.14814814814814814), new Pair<Integer, Double>(32,0.14814814814814814), new Pair<Integer, Double>(64,0.14814814814814814), new Pair<Integer, Double>(10,0.25), new Pair<Integer, Double>(12,0.25), new Pair<Integer, Double>(24,0.25), new Pair<Integer, Double>(34,0.25), new Pair<Integer, Double>(36,0.25), new Pair<Integer, Double>(48,0.25), new Pair<Integer, Double>(66,0.25), new Pair<Integer, Double>(68,0.25), new Pair<Integer, Double>(80,0.25), new Pair<Integer, Double>(6,0.2962962962962963), new Pair<Integer, Double>(18,0.2962962962962963), new Pair<Integer, Double>(20,0.2962962962962963), new Pair<Integer, Double>(40,0.2962962962962963), new Pair<Integer, Double>(72,0.2962962962962963), new Pair<Integer, Double>(96,0.2962962962962963), new Pair<Integer, Double>(14,0.38490017945975047), new Pair<Integer, Double>(26,0.38490017945975047), new Pair<Integer, Double>(28,0.38490017945975047), new Pair<Integer, Double>(38,0.38490017945975047), new Pair<Integer, Double>(50,0.38490017945975047), new Pair<Integer, Double>(52,0.38490017945975047), new Pair<Integer, Double>(70,0.38490017945975047), new Pair<Integer, Double>(82,0.38490017945975047), new Pair<Integer, Double>(84,0.38490017945975047), new Pair<Integer, Double>(42,0.3849001794597505), new Pair<Integer, Double>(44,0.3849001794597505), new Pair<Integer, Double>(56,0.3849001794597505), new Pair<Integer, Double>(74,0.3849001794597505), new Pair<Integer, Double>(76,0.3849001794597505), new Pair<Integer, Double>(88,0.3849001794597505), new Pair<Integer, Double>(98,0.3849001794597505), new Pair<Integer, Double>(100,0.3849001794597505), new Pair<Integer, Double>(112,0.3849001794597505), new Pair<Integer, Double>(104,0.4444444444444444), new Pair<Integer, Double>(22,0.4444444444444445), new Pair<Integer, Double>(46,0.5), new Pair<Integer, Double>(58,0.5), new Pair<Integer, Double>(60,0.5), new Pair<Integer, Double>(78,0.5), new Pair<Integer, Double>(90,0.5), new Pair<Integer, Double>(92,0.5), new Pair<Integer, Double>(102,0.5), new Pair<Integer, Double>(114,0.5), new Pair<Integer, Double>(116,0.5), new Pair<Integer, Double>(30,0.5281529477305951), new Pair<Integer, Double>(54,0.5281529477305951), new Pair<Integer, Double>(86,0.5281529477305951), new Pair<Integer, Double>(106,0.5281529477305951), new Pair<Integer, Double>(108,0.5281529477305951), new Pair<Integer, Double>(120,0.5281529477305951), new Pair<Integer, Double>(110,0.6311303094408988), new Pair<Integer, Double>(122,0.6311303094408988), new Pair<Integer, Double>(124,0.6311303094408988), new Pair<Integer, Double>(62,0.6311303094408989), new Pair<Integer, Double>(94,0.6311303094408989), new Pair<Integer, Double>(118,0.6311303094408989), new Pair<Integer, Double>(126,0.75)); }