Le Monde puzzle [#1061]

lemondapariA griddy Le Monde mathematical puzzle:

  1. On a 4×5 regular grid, find how many nodes need to be turned on to see all 3×4 squares to have at least one active corner in case of one arbitrary node failing.
  2.  Repeat for a 7×9 grid.

The question is open to simulated annealing, as in the following R code:

n=3;m=4;np=n+1;mp=m+1

cvr=function(grue){
  grud=grue
  obj=(max(grue)==0)
  for (i in (1:length(grue))[grue==1]){
   grud[i]=0
   obj=max(obj,max((1-grud[-1,-1])*(1-grud[-np,-mp])*
       (1-grud[-np,-1])*(1-grud[-1,-mp])))
   grud[i]=1}
  obj=99*obj+sum(grue)
  return(obj)}

dumban=function(grid,T=1e3,temp=1,beta=.99){
   obj=bez=cvr(grid)
   sprk=grid
   for (t in 1:T){
     grue=grid
     if (max(grue)==1){ grue[sample(rep((1:length(grid))[grid==1],2),1)]=0
      }else{ grue[sample(1:(np*mp),np+mp)]=1}
     jbo=cvr(grue)
     if (bez>jbo){ bez=jbo;sprk=grue}
     if (log(runif(1))<(obj-jbo)/temp){
        grid=grue;obj=cvr(grid)}
     temp=temp*beta
     }
   return(list(top=bez,sol=sprk))}

leading to

>  dumban(grid,T=1e6,temp=100,beta=.9999)
$top
[1] 8
$sol
     [,1] [,2] [,3] [,4] [,5]
[1,]    0    1    0    1    0
[2,]    0    1    0    1    0
[3,]    0    1    0    1    0
[4,]    0    1    0    1    0

which sounds like a potential winner.

2 Responses to “Le Monde puzzle [#1061]”

  1. […] article was first published on R – Xi'an's Og, and kindly contributed to […]

  2. […] 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 on topics such as: Data […]

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.