/*
Copyright 2010 Ken Takusagawa
This program is free software: you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation, either version 3 of the License, or
(at your option) any later version.
This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
GNU General Public License for more details.
You should have received a copy of the GNU General Public License
along with this program. If not, see .
*/
import java.util.Iterator;
import java.util.HashSet;
import java.util.HashMap;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Scanner;
import java.util.Collections;
import java.util.AbstractMap;
import java.util.Set;
class Boardsize {
static final int size=5;
}
public class Dodgem {
public static void main(String argv[]){
DodgemExhaustiveSearch.doExhaustive();
}
}
class Value {
short win; //+1 or -1 or 0
short distance;
public Value(Value x){
win=x.win;
distance=x.distance;
}
public Value(int x){
//from Game Node
win=(short)x;
distance=0;
}
private Value(){
}
short shortValue(){
/*
if(win==0){
throw new RuntimeException("0 value to short");
}
*/
return (short)(win*distance);
}
static Value makeValueFromShort(short x){
Value v=new Value();
if(x>0){
v.distance=x;
v.win=1;
}
else if (x<0){
v.distance=(short)(-x);
v.win=-1;
}
//else throw new RuntimeException("0 makeValueFromShort");
return v;
}
static Value makeBetter(Value old, Value nother){
Value me=new Value(nother);
me.win=(short)(-me.win);
me.distance++;
if(old==null)return me;
//System.out.println("me="+me+" old="+old);
Value ret=old;
if(me.win==1){
if(old.win==1){
if(me.distanceold.distance){
ret=me; //arbitrary
}
} else if (old.win==-1){
ret=me;
} else {
//throw new RuntimeException("makeBetter");
}
} else if (me.win==-1){
if (old.win==1 || old.win==0){
} else {
if (me.distance>old.distance){
ret=me;
}
}
}
return ret;
}
@Override public String toString(){
return ""+win+" "+distance;
}
}
class Onenode{
static void p(String x){
//System.out.println(x);
}
static Value onenode(Node n, Map table){
if(n.isTerminal())return null;
if(table.get(n)!=null)return null;
boolean allChildrenFound=true;
Value best=null;
//p("starting iteration\n"+n);
List moves=n.moves();
if(moves.size()==0){
throw new RuntimeException("stalemate");
}
for(Iteratori=moves.iterator();i.hasNext();){
Node c=n.makeNode(i.next());
//p("node\n"+c);
Value v;
if (c.isTerminal()){
//p("terminal");
v=new Value(c.value());
}
else
v=table.get(c);
//p("value "+v);
if(v==null){
allChildrenFound=false;
} else {
best=Value.makeBetter(best,v);
}
//p("best "+best);
}
if(allChildrenFound || (best!=null && best.win==1)) {
//p("putting "+best+"\n"+n);
return best;
} else {
//p("fail "+allChildrenFound+" best "+best+"\n"+n);
}
return null;
}
}
interface Node {
//arraylist over list for convenience of random access.
ArrayList moves();
Node makeNode(Move m);
int value();
boolean isTerminal();
// hashCode and equals!
}
interface Move{};
class DodgemNode implements Node{
int[][] board;
//static final int[][] initboard={{0,1,1},{2,0,0},{2,0,0}};
int playerToMove;
int size;
static DodgemNode defaultDodgemNode(){
DodgemNode n=uninitialized();
n.size=Boardsize.size;
n.playerToMove=1;
n.board=makeboard(Boardsize.size);
return n;
}
DodgemNode(DodgemNode o){
playerToMove=o.playerToMove;
size=o.size;
board=new int[size][size];
for(int i=0;i=0;--i){
for(int j=0;j=0;--i){
for(int j=0;j children(){
//if(isTerminal()) throw new RuntimeException("terminal children");
ArrayList a=new ArrayList();
List moves=moves();
for(Iteratori=moves.iterator();i.hasNext();){
DodgemNode n=new DodgemNode(this);
n.playMove((DodgemMove)i.next());
a.add(n);
}
return a;
}
public Node makeNode(Move m){
DodgemNode n=new DodgemNode(this);
n.playMove((DodgemMove)m);
return n;
}
static final int[][] oneArr={{0,-1},{1,0},{0,1}};
static final int[][] twoArr={{-1,0},{0,1},{1,0}};
static final Coord[] oneDirs=makeDirs(oneArr);
static final Coord[] twoDirs=makeDirs(twoArr);
static final Coord[][] dirs={null,makeDirs(oneArr),makeDirs(twoArr)};
static Coord[] makeDirs(int[][] dirs){
Coord[] out=new Coord[dirs.length];
for(int i=0;i moves(){
ArrayList r=new ArrayList();
//System.out.println("gf "+findpieces()+" "+playerToMove);
List mypieces=findpieces().get(playerToMove);
for(Iterator i=mypieces.iterator();i.hasNext();){
Coord c=i.next();
for(int dir=0;dir<3;++dir){
DodgemMove xy=new DodgemMove(c,dirs[playerToMove][dir]);
Coord e=xy.finalLocation();
if(inBounds(e)){
if(board[e.x][e.y]==0)
r.add(xy);
} else if (playerToMove==1 && e.x==size ||
playerToMove==2 && e.y==size)
r.add(xy);
}
}
return r;
}
boolean inBounds(Coord c){
return coordInBounds(c.x)&&coordInBounds(c.y);
}
boolean coordInBounds(int q){
return (0<=q)&&(q > findpieces(){
ArrayList< List > pieces=new ArrayList >();
pieces.add(null);//waste the zero entry
pieces.add(new LinkedList());
pieces.add(new LinkedList());
for(int i=0;i {
public int x;
public int y;
public Coord(int a, int b){
x=a;
y=b;
}
public Coord(Coord c){
x=c.x;
y=c.y;
}
@Override public String toString(){
return "("+x+" "+y+")";
}
@Override public boolean equals(Object o){
Coord b=(Coord)o;
return (x==b.x)&&(y==b.y);
}
@Override public int compareTo(Coord o){
if(x!=o.x) return (x-o.x);
return (y-o.y);
}
void flip(){
int temp=x;
x=y;
y=temp;
}
}
class DodgemMove implements Move{
Coord origin;
Coord direction;
public Coord finalLocation(){
return new Coord(origin.x+direction.x,origin.y+direction.y);
}
public DodgemMove(Coord a,Coord b){
origin=a;
direction=b;
}
@Override public String toString(){
return""+origin+"+"+direction;
}
}
class CompressedBoard {
int a;
short b;
static final int modulus=1+Boardsize.size*Boardsize.size;
CompressedBoard(long l){
a=(int)l;
b=(short)(l>>32);;
}
long get64(){
long c=b;
//c may be negative...
c &= 0xffff;
c <<= 32;
//System.err.println("c1 = "+c);
long longa=a;
longa &= 0xffffffffl;
//System.err.println("longa = "+longa);
c |= longa;
return c;
}
DodgemListNode pos(){
DodgemListNode b=DodgemListNode.empty();
long l=get64();
for(int i=0;i<2*(Boardsize.size-1);++i){
List p=b.pieces.get(1+i/(Boardsize.size-1));
//System.err.println("l="+l);
int r=(int)(l%modulus);
l/=modulus;
//v.add(Integer.valueOf(r));
if (r!=0){
r--;
int x=r%Boardsize.size;
int y=r/Boardsize.size;
p.add(new Coord(x,y));
}
}
b.canonicalize();
return b;
}
DodgemNode getNode(){
return pos().makeBoard();
}
@Override public String toString(){
return "long short "+a+" "+b;
}
@Override public boolean equals(Object o){
CompressedBoard other=(CompressedBoard)o;
return (a==other.a)&&(b==other.b);
}
@Override public int hashCode(){
return a+7*b;
}
}
class DodgemListNode {
//always stored from the POV of player 0 to move.
//we waste the 0 entry.
ArrayList< List> pieces;
private DodgemListNode(){
}
void flip(){
flipside(pieces.get(1));
flipside(pieces.get(2));
List temp=pieces.get(1);
pieces.set(1,pieces.get(2));
pieces.set(2,temp);
canonicalize();
}
static void flipside(List v){
for(Iterator i=v.iterator();i.hasNext();){
i.next().flip();
}
}
void canonicalize(){
Collections.sort(pieces.get(1));
Collections.sort(pieces.get(2));
}
DodgemNode makeBoard(){
DodgemNode d=DodgemNode.uninitialized();
d.size=Boardsize.size;
d.board=new int[d.size][d.size];
d.playerToMove=1;
for(int player=1;player<=2;++player){
for(Iterator i=pieces.get(player).iterator();
i.hasNext();){
Coord c=i.next();
d.board[c.x][c.y]=player;
}
}
return d;
}
CompressedBoard makeCompressedBoard(){
long sum=0;
long multiplier=1;
for(int player=1;player<=2;++player){
for(int i=0;i());
n.pieces.add(new ArrayList());
return n;
}
static DodgemListNode uninitialized(){
return new DodgemListNode();
}
static DodgemListNode semiinitialized(){
DodgemListNode n=new DodgemListNode();
n.pieces=new ArrayList>();
//not an array because of weirdness of java generic Array creation
n.pieces.add(null);//waste the zero entry
return n;
}
@Override public String toString(){
return "("+pieces.get(1).toString()+" & "+pieces.get(2).toString()+")";
}
}
class DodgemPieceState {
Coord c; //null implies off
@Override public String toString(){
return "ps "+c;
}
@Override public boolean equals(Object o){
if(c==null) return false;
DodgemPieceState p=(DodgemPieceState)o;
if (p.c==null) return false;
return (c.equals(p.c));
}
}
class DodgemPieceIterator implements Iterator{
boolean dispensed;
DodgemPieceState preparedNext;
@Override public void remove(){
throw new UnsupportedOperationException();
}
@Override public DodgemPieceState next(){
if(dispensed) throw new RuntimeException("already dispensed");
dispensed=true;
return preparedNext;
}
@Override public boolean hasNext(){
DodgemPieceState p=preparedNext;//shorthand
if(!dispensed)return true;
if(p.c==null) return false;
//in place might be bad.
if (p.c.y pieces;
@Override public String toString(){
return pieces.toString();
}
ArrayList getpieces(){
ArrayList r=new ArrayList();
for(Iterator i=pieces.iterator();i.hasNext();){
DodgemPieceState p=i.next();
if(p.c==null)break;
r.add(p.c);
}
// System.out.println("before "+r);
//Collections.sort(r);
//System.out.println("after "+r);
return r;
}
}
class DodgemSideIterator implements Iterator{
boolean dispensed;
DodgemSideState n;
ArrayList c;
@Override public void remove(){
throw new UnsupportedOperationException();
}
@Override public DodgemSideState next(){
//if(dispensed) throw new RuntimeException("already dispensed");
//hasNext must be called first;
dispensed=true;
return n;
}
@Override public boolean hasNext(){
if(!dispensed)return true;
for(;;){
if(!findIncrement()) return false;
if(isOk())break;
}
dispensed=false;
return true;
}
boolean findIncrement(){
for(int i=0;i(Boardsize.size-1);
n=new DodgemSideState();
n.pieces=new ArrayList(Boardsize.size-1);
for(int i=0;i state;
@Override public String toString(){
return state.toString();
}
DodgemListNode getlist(){
DodgemListNode n=DodgemListNode.semiinitialized();
n.pieces.add(state.get(0).getpieces());
n.pieces.add(state.get(1).getpieces());
return n;
}
boolean triviallyTerminal(){
return state.get(0).pieces.isEmpty();
}
boolean isTerminal(){
if(triviallyTerminal())return true;
return getlist().makeBoard().isTerminal();
}
}
class DodgemBothSideIterator implements Iterator {
boolean dispensed;
DodgemBothSideState n;
ArrayList c;
@Override public void remove(){
throw new UnsupportedOperationException();
}
@Override public DodgemBothSideState next(){
//if(dispensed) throw new RuntimeException("already dispensed");
//hasNext must be called first;
dispensed=true;
return n;
}
@Override public boolean hasNext(){
if(!dispensed)return true;
for(;;){
if(!findIncrement()) return false;
if(isOk())break;
}
dispensed=false;
return true;
}
boolean findIncrement(){
for(int i=0;i();
n=new DodgemBothSideState();
n.state=new ArrayList();
for(int i=0;i<2;++i){
DodgemSideIterator si=new DodgemSideIterator();
c.add(si);
n.state.add(si.next());
}
dispensed=true;// knowing initial state is bad
hasNext();
}
}
class Doublehash{
long[] h;
HashMap pcz;
Doublehash(){
h=new long[size];
pcz=new HashMap();
}
int mysize=0;
static final int size=200000000-9;//prime
short gethh(int hash1, int hash2, long target){
//System.out.println("gethh "+hash1+" "+hash2+" "+target);
for(int i=hash1;;i=(i+hash2)%size){
if (h[i]>>16==target){
return (short)h[i];
} else if(h[i]==0){
return NOTFOUND;
}
}
}
void puthh(int hash1, int hash2, long x){
//if(x==0)throw new RuntimeException("bad insert 0");
// cannot reinsert!
int pcount=1;
mysize++;
for(int i=hash1;;i=(i+hash2)%size){
if(h[i]==0){
h[i]=x;
Integer ipct=new Integer(pcount);
Integer pold=pcz.get(ipct);
int old;
if(pold==null)
old=0;
else
old=pold.intValue();
old++;
pcz.put(ipct,new Integer(old));
return;
}
pcount++;
}
}
static final short NOTFOUND=32100;
short getcb(CompressedBoard cb){
long c=cb.get64();
//System.out.println("c `= "+c+" @ "+cb);
long a=c%size;
long b=1+c%(size-1);
return gethh((int)a,(int)b,c);
}
void putcb(CompressedBoard cb, short x){
long c=cb.get64();
long a=c%size;
long b=1+c%(size-1);
c<<=16;
c|=(0xffff&(long)x);
puthh((int)a,(int)b,c);
}
void dump(){
int count=0;
for(int i=0;i>16);
//System.out.println(""+i+" "+cb.pos());
}
}
System.out.println(count);
for(Iterator> i=
pcz.entrySet().iterator();
i.hasNext();){
Map.Entry v=i.next();
System.out.println(v);
}
}
}
class CompressedMap extends AbstractMap implements Map{
Doublehash table;
CompressedMap(){
table=new Doublehash();
}
@Override public Value get(Object n){
CompressedBoard cb=((DodgemNode)n).mkdodgemlistnode().makeCompressedBoard();
//System.out.println("canonical of "+n+" is "+cb.pos().makeBoard());
short s=table.getcb(cb);
Value ret;
if (s==Doublehash.NOTFOUND)
ret=null;
else
ret=Value.makeValueFromShort(s);
//System.out.println("fetched "+cb.pos().makeBoard()+" = "+ret);
return ret;
}
@Override public int size(){
return table.mysize;
}
@Override public Value put(Node n, Value v){
//cant overwrite!
//System.out.println("now inserting value "+v+" into\n"+n);
//if(get(n)!=null) throw new RuntimeException("reinsert");
table.putcb(((DodgemNode)n).mkdodgemlistnode().makeCompressedBoard(),v.shortValue());
return null;
}
@Override public Set> entrySet(){
return null;
}
}
class NodeValue{
CompressedBoard n;
short v;
@Override public String toString(){
return ""+n+" "+v;
}
}
class DodgemExhaustiveSearch {
static void doExhaustive(){
CompressedMap map=new CompressedMap();
for(int iteration=0;;++iteration){
//System.out.println("special "+map.get(special));
ArrayList q=new ArrayList();
for(DodgemBothSideIterator i=new DodgemBothSideIterator();
i.hasNext();){
DodgemBothSideState s=i.next();
if(!s.triviallyTerminal()){
DodgemListNode ln=s.getlist();
Node n=ln.makeBoard();
Value v=Onenode.onenode(n,map);
if(v!=null){
NodeValue nv=new NodeValue();
nv.n=ln.makeCompressedBoard();
nv.v=v.shortValue();
System.out.println(nv);
q.add(nv);
}
}
}
System.err.println("iteration "+iteration+" size="+q.size());
for(Iterator i=q.iterator();i.hasNext();){
NodeValue nv=i.next();
//System.out.println("nv "+((DodgemNode)nv.n).compact()+" "+nv.v);
//map.put(nv.n,nv.v);
map.table.putcb(nv.n,nv.v);
}
if(q.size()==0)break;
}
System.out.println("final "+map.size());
}
}
/*
size4
iteration 0 size=696
iteration 1 size=2300
iteration 2 size=2285
iteration 3 size=4655
iteration 4 size=4320
iteration 5 size=8906
iteration 6 size=7518
iteration 7 size=14542
iteration 8 size=11949
iteration 9 size=17929
iteration 10 size=13166
iteration 11 size=19442
iteration 12 size=12854
iteration 13 size=18269
iteration 14 size=11572
iteration 15 size=15288
iteration 16 size=9616
iteration 17 size=12387
iteration 18 size=7636
iteration 19 size=9502
iteration 20 size=6495
iteration 21 size=7665
iteration 22 size=5099
iteration 23 size=5996
iteration 24 size=3514
iteration 25 size=3989
iteration 26 size=2219
iteration 27 size=2551
iteration 28 size=1303
iteration 29 size=1426
iteration 30 size=794
iteration 31 size=876
iteration 32 size=468
iteration 33 size=483
iteration 34 size=293
iteration 35 size=298
iteration 36 size=147
iteration 37 size=159
iteration 38 size=63
iteration 39 size=70
iteration 40 size=26
iteration 41 size=14
iteration 42 size=2
iteration 43 size=0
*/