# Le Monde puzzle [#887bis]

November 15, 2014
By

(This article was first published on Xi'an's Og » R, and kindly contributed to R-bloggers)

As 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))
5.397       0.000       5.395
> system.time(for (i in 1:50) puck(15))
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

R-bloggers.com offers daily e-mail updates about R news and tutorials on topics such as: Data science, Big Data, R jobs, visualization (ggplot2, Boxplots, maps, animation), programming (RStudio, Sweave, LaTeX, SQL, Eclipse, git, hadoop, Web Scraping) statistics (regression, PCA, time series, trading) and more...