## Le Monde puzzle [#1051]

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

## Leave a Reply