Le Monde puzzle [#875]

I learned something in R today thanks to Le Monde mathematical puzzle:

A two-player game consists in A picking a number n between 1 and 10 and B and A successively choosing and applying one of three transforms to the current value of n

  • n=n+1,
  • n=3n,
  • n=4n,

starting with B, until n is larger than 999. Which value(s) of n should A pick if both players act optimally?

Indeed, I first tested the following R code

sole=function(n){
  if (n>999){ return(TRUE)
  }else{
     return((!sole(3*n))&(!sole(4*n))&(!sole(n+1)))
}}

which did not work because of too many calls to sole:

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

So I included a memory in the calls to sole so that good and bad entries of n were saved for later calls:

visit=rep(-1,1000) #not yet visited
sole=function(n){
  if (n>999){ return(TRUE)
  }else{
     if (visit[n]>-1){ return(visit[n]==1)
     }else{
       visit[n]<<-((!sole(3*n))&(!sole(4*n))&
    (!sole(n+1)))
       return(visit[n]==1)
  }}}

Trying frontal attack

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

did not work, but one single intermediary was sufficient:

> sole(500)
[1] FALSE
> for (i in 1:10)
+ print(sole(i))
[1] FALSE
[1] FALSE
[1] FALSE
[1] TRUE
[1] FALSE
[1] TRUE
[1] FALSE
[1] FALSE
[1] FALSE
[1] FALSE

which means that the only winning starters for A are n=4,6. If one wants the winning moves on top, a second counter can be introduced:

visit=best=rep(-1,1000)
sole=function(n){
  if (n>999){ return(TRUE)
  }else{
     if (visit[n]>-1){ return(visit[n]==1)
     }else{
       visit[n]<<-((!sole(3*n))&(!sole(4*n))&
       (!sole(n+1)))
       if (visit[n]==0) best[n]<<-max(
         3*n*(sole(3*n)),
         4*n*(sole(4*n)),
         (n+1)*(sole(n+1)))
       return(visit[n]==1)
  }}}

From which we can deduce the next values chosen by A or B as

> best[1:10]
 [1]  4  6  4 -1  6 -1 28 32 36 40

(where -1 means no winning choice is possible).

Now, what is the R trick I learned from this toy problem? Simply the use of the double allocation symbol that allows to change global variables within functions. As visit and best in the latest function. (The function assign would have worked too.)

7 Responses to “Le Monde puzzle [#875]”

  1. You could also probably use memoisation in this case (which is pretty much what you’re doing here) with Hadley Wickham’s package memoise.
    That way you don’t have to worry about bookkeeping.

  2. I am not sure I have understood who is the player that looses. Is the one that first applies a transformation that results to a n>999?

    • Yes, the first one to produce a number larger than 999 wins. So if A reaches 249, she wins because B cannot reach 1000 but
      produces a number that is at least 250…

  3. Your original function will work if you use “&&” instead of “&”. These two operators are slightly different. The “&” operator works on vectors and returns an element-wise logical comparison. In order to evaluate the outcome of “&” you must first evaluate both the left and right side arguments. The “&&” operator works on scalars and evaluates its arguments from left to right until it determines the outcome of the logical condition. It works more like a control flow operator.

    In your recursive function, these different behaviours can make a big difference to the call stack. With “&” your recursive function leaves some function calls on the call stack (the next call to sole() on the right hand side of “&”) and eventually exhausts the available space. With “&&” it does a depth-first search of the tree structure and the size of the stack is equal to the depth of recursion.

    • So once again I hit the “post comment” button and realise my explanation is wrong. The difference is that “&&” avoids redundant exploration fo the branch “sole(n+1)” which is the one that exhausts the call stack.

      • Thank you Martyn! Another special feature of R I had forgotten… I was actually thinking the other day of trying a sequential check and here is the trick! Thanks!

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 )

Google photo

You are commenting using your Google 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 )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.