# Le Monde puzzle [#887bis]

**Xi'an's Og » R**, 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.

**A**s mentioned in the previous post, an alternative consists in filling the permutation of {1,…,N} by adding squares left and right until the permutation is complete or no solution is available. While this sounds like the dual of the initial solution, it brings a considerable increase in computing time, as shown below. I thus redefined the construction of the solution by initialising the permutation at random (it could be 1 as well)

perfect=(1:trunc(sqrt(2*N)))^2 perm=friends=(1:N) t=1 perm[t]=sample(friends,1) friends=friends[friends!=perm[t]]

and then completing only with possible neighbours, left

out=outer(perfect-perm[t],friends,"==") if (max(out)==1){ t=t+1 perm[t]=sample(rep(perfect[apply(out,1, max)==1],2),1)-perm[t-1] friends=friends[friends!=perm[t]]}

or right

out=outer(perfect-perm[1],friends,"==") if (max(out)==1){ t=t+1 perf=sample(rep(perfect[apply(out,1, max)==1],2),1)-perm[1] perm[1:t]=c(perf,perm[1:(t-1)]) friends=friends[friends!=perf]}

(If you wonder about the rep in the sample step, it is a trick I just found to avoid the insufferable feature that sample(n,1) is equivalent to sample(1:n,1)! It costs basically nothing but bypasses reprogramming sample() each time I used it…) The gain in computing time is amazing:

> system.time(for (i in 1:50) pick(15)) utilisateur systÃ¨me Ã©coulÃ© 5.397 0.000 5.395 > system.time(for (i in 1:50) puck(15)) utilisateur systÃ¨me Ã©coulÃ© 0.285 0.000 0.287

An unrelated point is that an interesting (?) alternative problem consists in adding a toroidal constraint, namely to have the first and the last entries in the permutation to also sum up to a perfect square. Is it at all possible?

Filed under: Kids, R, Statistics, University life Tagged: Le Monde, mathematical puzzle, sample

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

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

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.