the large half now

The little half puzzle proposed a “dumb’ solution in that players play a minimax strategy. There are 34 starting values less than 100 guaranteeing a sure win to dumb players. If instead the players maximise their choice at each step, the R code looks like this:

solveO=function(n){
if (n<3){ solve=(n==2)}else{
  solve=(!(solveO(n-1)))||(!solveO(ceiling(n/2)))}
solve}

and there are now 66 (=100-34, indeed!) starting values for which the starting player can win.

Incidentally, I typed

> solveO(1113)
Error: evaluation nested too deeply: infinite recursion / options(expressions=)?

which shows R cannot handle heavy recursion without further programming. Testing for the upper limit, I found that the largest acceptable value is 555 (which takes forever to return a value, predicted at more than one hour by a linear regression on the run times till 300…).

One Response to “the large half now”

  1. Yup, too much overhead in R to do heavy recursion well. On the other hand, that’s probably not a very efficient way to code it anyways (too many duplicate calculations). Something like this is much speedier (apologies for inconsistent format):

    temps <- rep(NA, 10000)

    solveO<-function(n){
    if (is.na(temps[[n]]))
    { if (n<=3){ solve=(n==2)}else{
    solve=(!(solveO(n-1)))||(!solveO(ceiling(n/2)))}
    temps[n] <<- solve
    solve
    } else
    { temps[n]
    }
    }

    sum(mapply(solveO, 1:10000))

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 717 other followers