Le Monde puzzle [#1130]
Want to share your content on R-bloggers? click here if you have a blog, or here if you don't.
A two-player game as Le weekly Monde current mathematical puzzle:
Abishag and Caleb fill in alternance a row of N boxes in a row by picking one then two then three &tc. consecutive boxes. When a player is unable to find enough consecutive boxes, the player has lost. Who is winning when N=29? When N=30?
Using a basic recursive search for the optimal strategy, with the status of the row and the number of required boxes as entries,
f<-function(b=!1:N,r=0){ for(i in 1:(N-r)){ if(p<-!max(b[j<-i+r:0])){ q=b;q[j]=1 if(p<-!f(q,r+1))break}} p}
returns Abishag as the winner for N=29 (as well as for N=1,2,7,…,13,19,…,29) and Caleb as the winner for N=30 (as well as for N=3,…,6,14,…,18). I am actually surprised that the recursion operates that deep, even though this means a √N depth for the recursion. While the code took too long to complete, the function operates for N=100. A side phenomenon is the apparent special case of N=47, which makes Abishag the looser, while N=46 and N=48 do not.This is an unusual pattern as otherwise (up to N=59), there are longer and longer stretches of adjacent wins and looses as N increases.
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.