# Le Monde puzzle [#1051]

**R – Xi'an's Og**, and kindly contributed to R-bloggers]. (You can report issue about the content on this page here)

Want to share your content on R-bloggers? click here if you have a blog, or here if you don't.

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

**T**he 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] <- balz[k] if (max(balz[k]-calz[k],calz[j]-balz[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 is still running…

**leave a comment**for the author, please follow the link and comment on their blog:

**R – Xi'an's Og**.

R-bloggers.com offers

**daily e-mail updates**about R news and tutorials about learning R and many other topics. Click here if you're looking to post or find an R/data-science job.

Want to share your content on R-bloggers? click here if you have a blog, or here if you don't.