## Le Monde puzzle [#1051]

Posted in Books, Kids, R with tags , , , , , , on May 18, 2018 by xi'an

A combinatoric Le Monde mathematical puzzle of limited size:
When the only allowed move is to switch two balls from adjacent boxes, what is the minimal number of moves to return all balls in the above picture to their respective boxes? Same question with six boxes and 12 balls.

The question is rather interesting to code as I decided to use recursion (as usual!) but wanted to gain time by storing the number of steps needed by any configuration to reach its ordered recombination. Meaning I had to update an external vector within the recursive function for each new configuration I met. With help from Julien Stoehr, who presented me with the following code, a simplification of a common R function

```v.assign <- function (i,value,...) {
temp <- get(i, pos = 1)
temp[...] <- value
assign(i, temp, pos = 1)}
```

which assigns one or several entries to the external vector i. I thus used this trick in the following R code, where cosz is a vector of size 5¹⁰, much larger than the less than 10! values I need but easier to code. While n≤5.

```n=5;tn=2*n
baz=n^(0:(tn-1))
cosz=rep(-1,n^tn)
swee <- function(balz){
indz <- sum((balz-1)*baz)
if (cosz[indz]==-1){
if (min(diff(balz))==0){ #ordered
v.assign("cosz",indz,value=1)}else{
val <- n^tn
for (i in 2:n)
for (j in (2*i-1):(2*i))
for (k in (2*i-3):(2*i-2)){
calz <- balz
calz[k] <- balz[j];calz[j] 0)
val <- min(val,1+swee(calz))}
v.assign("cosz",indz,value=val)
}}
return(cosz[indz])}
```

which returns 2 for n=2, 6 for n=3, 11 for n=4, 15 for n=5. In the case n=6, I need a much better coding of the permutations of interest. Which is akin to ranking all words within a dictionary with letters (1,1,…,6,6). After some thinking (!) and searching, I came up with a new version, defining

```parclass=rep(2,n)
rankum=function(confg){
n=length(confg);permdex=1
for (i in 1:(n-1)){
x=confg[i]
if (x>1){
for (j in 1:(x-1)){
if(parclass[j]>0){
parclass[j]=parclass[j]-1
permdex=permdex+ritpermz(n-i,parclass)
parclass[j]=parclass[j]+1}}}
parclass[x]=parclass[x]-1}
return(permdex)}

ritpermz=function(n,parclass){
return(factorial(n)/prod(factorial(parclass)))}
```

for finding the index of a given permutation, between 1 and (2n)!/2!..2!, and then calling the initial swee(p) with this modified allocation. The R code was still running when I posted this entry… and six days later, it returned the answer of 23.

## Le Monde puzzle [#875]

Posted in Kids, R, Statistics, University life with tags , , , , on July 12, 2014 by xi'an

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.)