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
[sourcecode language=”r” gutter=”false”]
sole=function(n){
if (n>999){ return(TRUE)
}else{
return((!sole(3*n))&(!sole(4*n))&(!sole(n+1)))
}}
[/sourcecode]
which did not work because of too many calls to sole:
[sourcecode language=”r” gutter=”false”]
>sole(1)
Error: evaluation nested too deeply: infinite recursion
/ options(expressions=)?
[/sourcecode]
So I included a memory in the calls to sole so that good and bad entries of n were saved for later calls:
[sourcecode language=”r” gutter=”false”]
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)
}}}
[/sourcecode]
Trying frontal attack
[sourcecode language=”r” gutter=”false”]
>sole(1)
Error: evaluation nested too deeply: infinite recursion
/ options(expressions=)?
[/sourcecode]
did not work, but one single intermediary was sufficient:
[sourcecode language=”r” gutter=”false”]
> 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
[/sourcecode]
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:
[sourcecode language=”r” gutter=”false”]
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)
}}}
[/sourcecode]
From which we can deduce the next values chosen by A or B as
[sourcecode language=”r” gutter=”false”]
> best[1:10]
[1] 4 6 4 -1 6 -1 28 32 36 40
[/sourcecode]
(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.)
July 13, 2014 at 12:25 pm
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.
July 13, 2014 at 11:23 am
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?
July 13, 2014 at 12:38 pm
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…
July 12, 2014 at 5:02 pm
[…] Base from: Xi’an’s Og […]
July 12, 2014 at 11:07 am
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.
July 12, 2014 at 11:43 am
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.
July 12, 2014 at 2:30 pm
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!