#http://www.reddit.com/r/askscience/comments/35uljq/if_i_wanted_to_randomly_find_someone_in_an/cr89r0o

#options:

options(error=debug)
#initialize:




simulate=function(move2=F,verbose=F,moveA="random"){
    die=function(x=1){floor(runif(x,1,11))}
    coords=function(who){pos=grep(who,park);y=ceiling(pos/10);x=pos%%10;if(x==0)x=10;return(c(x,y))}
    gridAstatus="placeholder" # this var is used to remember what we're doing when we're walking a grid

    park= matrix(data="0",nrow=10,ncol=10,byrow=T)

    #place A
    posA=die(2)
    park[posA[1],posA[2]]="A0"

    #place B
    overlap=T
    while(overlap){
        posB=die(2)
        if(! all(posB==posA)){overlap=F}
        }
    park[posB[1],posB[2]]="B0"


    #plotpark=function(){for(i in 1:10){for(j in 1:10){cat(park[park$x==i & park$y==j,"who"], " ") };print("")}}#print()
    plotpark=function(){print(park)}
    if(verbose)plotpark()

    found=FALSE
    counter=0
    if(all(posB==posA)){
        warning("+++ REDO FROM START +++               >> collision")
        found=T
        }

    while(!found){
        counter=counter+1
        if(verbose==2)cat("\n\n\n~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\nCounter: ",counter,"\n")

        # ####  A
        #get pos:
        pos=coords("A")
        x=pos[1]
        y=pos[2]
        if(verbose==2)cat("A: ",x,y,"\n")
        park[x,y]=as.numeric(gsub("([a-zA-Z])([[:digit:]]*)","\\2",park[pos[1],pos[2]] ))+1 #or counter

        #valid moves:
        if(moveA=="random"){
        dirs=c("U","UR","R","DR","D","DL","L","UL")
        if(y==1)dirs=grep("[^L]$",dirs,value=T)
        if(y==10)dirs=grep("[^R]$",dirs,value=T)
        if(x==1)dirs=grep("^[^U]",dirs,value=T)
        if(x==10)dirs=grep("^[^D]",dirs,value=T)

        if(verbose==2)print(dirs)

        dirs=sample(dirs,1)
        if(verbose==2)print(dirs)

        if(length(grep("D",dirs))==1) x=x+1
        if(length(grep("U",dirs))==1) x=x-1
        if(length(grep("R",dirs))==1) y=y+1
        if(length(grep("L",dirs))==1) y=y-1
        }
        if(moveA=="grid"){
        if(verbose==2)cat("A: grid: ",gridAstatus,"\n")
            switch(gridAstatus,
                down={
                if(x<10)
                    x=x+1
                    else {
                    if(y<10){
                        y=y+1
                        gridAstatus="up"
                        }else{
                        gridAstatus="left"
                        }
                    }
                }, # end "right"
                up={
                    if(x>1)
                    x=x-1
                    else {
                        if(y<10){
                        y=y+1
                        gridAstatus="down"
                        }else{
                        gridAstatus="left"
                        }
                    }
                }, #end "left"
                left={
                    if(y>1) y=y-1
                    else{
                        if(x==10){ #we are at top left
                            x=x-1
                            gridAstatus="down"
                            }
                        else{ #we are at top right
                            x=x+1
                            gridAstatus="up"
                            }
                    }
                }, #end "up"
                { #DEFAULT: we are just starting out, gotta pick a direction.
                    if(x<10){
                        x=x+1
                        gridAstatus="up"
                        }
                    else{
                        x=x-1
                        gridAstatus="down"
                        }
                    }# end default selection
                )#end switch(gridAstatus)
            if(verbose==2)cat("A: grid: ",gridAstatus,"\n")
            }#end if move=grid



        if(verbose==2)cat("A: ",x,y,"\n")

        newA=c(x,y)

        # ####  B
        #get pos:
        pos=coords("B")
        x=pos[1]
        y=pos[2]
        if(verbose==2)cat("B: ",x,y,"\n")
        park[x,y]=as.numeric(gsub("([a-zA-Z])([[:digit:]]*)","\\2",park[pos[1],pos[2]]))+1 #or counter


        #valid moves:
        dirs=c("U","UR","R","DR","D","DL","L","UL")
        if(y==1)dirs=grep("[^L]$",dirs,value=T)
        if(y==10)dirs=grep("[^R]$",dirs,value=T)
        if(x==1)dirs=grep("^[^U]",dirs,value=T)
        if(x==10)dirs=grep("^[^D]",dirs,value=T)

        if(verbose==2)print(dirs)

        dirs=sample(dirs,1)

        if(verbose==2)print(dirs)

        if(length(grep("D",dirs))==1) x=x+1
        if(length(grep("U",dirs))==1) x=x-1
        if(length(grep("R",dirs))==1) y=y+1
        if(length(grep("L",dirs))==1) y=y-1

        if(verbose==2)cat(x,y,"\n")

        newB=c(x,y)


        if(all(newA==newB))
            {
            found=T
            #park[x,y]="X"
            }
            else{
            park[newA[1],newA[2]]=paste("A",park[newA[1],newA[2]],sep="")
            park[newB[1],newB[2]]=paste("B",park[newB[1],newB[2]],sep="")
            }

        #Search nieghbouring squares

        if(verbose==2)plotpark()
    }
    if(verbose)plotpark()
    if(verbose)cat("\n\nFound in: ",counter)
return(c(counter,summary(as.numeric(park[park!=0]))))
}

#simulate()
#simulate(verbose=T)
simulate(moveA="grid",verbose=2)

nruns=1e5

if(F){
pb=txtProgressBar(min=0,max=nruns,style=3)

a=rep(0,nruns)
dataA=data.frame(steps=a,min=a,q1=a,md=a,me=a,q3=a,max=a)
dataAB=data.frame(steps=a,min=a,q1=a,md=a,me=a,q3=a,max=a)
dataAgB=data.frame(steps=a,min=a,q1=a,md=a,me=a,q3=a,max=a)
for(i in 1:nruns){dataA[i,]=simulate(F); setTxtProgressBar(pb, i)}
for(i in 1:nruns){dataAB[i,]=simulate(T); setTxtProgressBar(pb, i)}
for(i in 1:nruns){dataAgB[i,]=simulate(T,moveA="grid"); if(!(x%%1000))setTxtProgressBar(pb, i)}

print(summary(dataA));print(sd(dataA$steps))
print(summary(dataAB));print(sd(dataAB$steps))
print(summary(dataAgB));print(sd(dataAgB$steps))
}