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

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



If you got this far, why not subscribe for updates from the site? Choose your flavor: e-mail, twitter, RSS, or facebook...

Comments are closed.

Search R-bloggers


Sponsors

Never miss an update!
Subscribe to R-bloggers to receive
e-mails with the latest R posts.
(You will not see this message again.)

Click here to close (This popup will not appear again)