Archive for brute-force solution

Le Monde puzzle [#1155]

Posted in Books, Kids, R with tags , , , , , , , on September 26, 2020 by xi'an

The weekly puzzle from Le Monde is another Sudoku challenge:

Anahera and Wiremu play a game for T rounds. They successively pick a digit between 1 and 3, never repeating the previous one, and sum these digits. The last to play wins if the sum is a multiple of 3. Who is the winner for an optimal strategy?

By a simple dynamic programming of the optimal strategy at each step

N=3
A=matrix(-1,20,N)
A[1,1:N]=1:N
for (T in 2:20)
for (i in 1:N) A[T,i]=i+ifelse(!T%%2, #parity check
max((i+A[T-1,-i])%%3), #avoid zero
min((i+A[T-1,-i])%%3)) #seek zero

the first to play can always win the game. Not fun!

Le Monde puzzle [#1154]

Posted in Statistics with tags , , , , , , on August 25, 2020 by xi'an

The weekly puzzle from Le Monde is another Sudoku challenge:

An n by n grid contains all numbers from 1 till n². Is it possible for fill the grid so that every row and every column has an integer average, for n=5, 7 9?

By sheer random search

`?`=rowSums; `+`=sample 
o=function(n){
x=matrix(+(n^2),n) 
while(any(c(?x,?t(x))%%n))x=x/x*+x 
x}

I found solutions for n=3,4,5, quite easily,

     [,1] [,2] [,3] [,4] [,5]
[1,]   20   15   14   13    3
[2,]   21    4   25    6    9
[3,]    2    1   23   18   11
[4,]   17   12   22   24    5
[5,]   10    8   16   19    7

correction, for n=6 as well

     [,1] [,2] [,3] [,4] [,5] [,6]
[1,]    4   12   11   23    8   32
[2,]   17   15   14   33    5   30
[3,]   35   28   27    7   13   22
[4,]   31    1    6    2   21   29
[5,]   25   36   20   34   16   19
[6,]   26   10   24    3    9   18

but larger values of n require a less frontal attack… Simulated annealing maybe.

Le Monde puzzle [#1152]

Posted in Kids, R with tags , , , , , , on July 20, 2020 by xi'an

The weekly puzzle from Le Monde is a tournament classic:

An even number of teams play one another once a week with no tie allowed and have played all other teams. Four weeks into the tournament, A has won all its games, B,C, and D have won three games, the other teams have won at least one games. What is the minimum number of teams? Show an instance.

By sheer random search

tnmt=function(K=10,gamz=4){
 t1=t0=matrix(1,K,K)
tnmt=function(K=10,gamz=4){
 tnmt=t0=matrix(0,K,K)
 while (!prod(apply(tnmt^2,1,sum)==4)){
   tnmt=t0
   for (i in 1:(K-2)){
     if((a<-gamz-sum(tnmt[i,]^2))> K-i-1) break()
     if(a>0){
      j=sample((i+1):K,a)
      tnmt[i,j]=sample(c(-1,1),a,rep=TRUE)
      tnmt[j,i]=-tnmt[i,j]}}}
 tnmt}
chck=function(1,gamz=4){
    sumz=apply(tnmt,1,sum)
    max(sumz)==gamz&
    sum(sumz==2)>2&
    min(sumz)>-gamz}

I found that 8 teams were not producing an acceptable game out of 10⁶ tries. Here is a solution for 9 teams:

       [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9]
 [1,]             -1   -1         1             -1
 [2,]             -1         1        -1        -1
 [3,]    1    1                   1             -1
 [4,]    1                   1         1   -1     
 [5,]        -1        -1                   1   -1
 [6,]   -1        -1                  -1    1     
 [7,]         1        -1         1         1     
 [8,]                   1   -1   -1   -1     
 [9,]    1    1    1         1

where team 9 wins all four games, 7,4 and 3, win three games, and the other 4 teams win one game. Which makes sense since this is a zero sum game, with a value of 10 over the four top teams and 2(N-4)=10 if no team has two wins (adding an even number of such teams does not change the value of the game).

Le Monde puzzle [#1149]

Posted in Books, Kids, pictures, R with tags , , , , , , on July 1, 2020 by xi'an

The weekly puzzle from Le Monde is a leaking variant on an old puzzle:

Three buckets have capacities of 8, 5 and 3 litres, respectively. At the start of the game, the 8 litre bucket is full and both others are empty. Aiming at reaching exactly 4 litres in one bucket, water is transferred between buckets. However, a fraction 1/k is lost with each transfer. If k=9, it is possible to reach 4 litres in three operations? If k=7, is it at all possible to reach 4 litres?

By sheer random search

k=1/5
z=c(8,5,3)
m<-function(s){
  i=sample(1:3,2)
  s[i]=s[i]+ifelse(
   rep((a<-z[i[1]]-s[i[1]])<(b<-s[i[2]])*(1-k),2),
   a*c(1,-1-k),b*c(1-k,-1))
  s}

I found that most fractions allow to reach 4 litres starting with k=2. (And am unsure the missing ones, like 18 or 21 are not due to a lack of luck… In particular, for k=9, the shortest path is

 8.000    0 0
 2.375    5 0
 0.000    5 2.11
 0.000    4 3

Le Monde puzzle [#1147]

Posted in Books, Kids, R with tags , , , , , , on June 10, 2020 by xi'an

The weekly puzzle from Le Monde is not much, again:

A number A is such that (1) the difference between two digits is never 1 (2) two digits are equal to 2 (3) it only involves 3 different digits (4) it is a multiple of 4 (5)  the sum of two of the digits is 5 (6) the product of the digits is not a multiple of 6 (7) the digits are between 0 and 6. What are the values of A with no digit equal to 0? What is the smallest A containing a zero?

as brute force produced 2052 as the smallest number with a zero. But I could not find numbers without a zero which seems indeed impossible since (1) plus (2) excludes 1 and 3, then (5) implies 0 and 5 are the other digits. Did I misunderstood the wording?!

Rereading the puzzle pointed out a detail I had missed:

A digit 1<x<7 is part of the digits of A if and only if (x) is true.

Which of course reduces the number of constraints. Using the checking function (and possibly calling xor for the first time ever!)

rule<-function(A){
  xor(!1%in%outer(A,A,'-'),!1%in%A)&
    xor(sum(A==2)==2,!2%in%A)&
    xor(length(unique(A))==3,!3%in%A)&
    xor(!dig2num(A)%%4,!4%in%A)&
    xor(5%in%outer(A,A,'+'),!5%in%A)&
    xor(!!prod(A)%%6,!6%in%A)}

the first realisations of A are

  [1]   304   340   344  2452  2524  3004  3040  3044  3304  3340  3344
 [12]  3400  3404  3440  3444  4252  4300  4304  4340  4344  5224 20452
 [23] 20524 22335 22353 22355 22504 22533 22535 22540 22553 23235 23253
 [34] 23255 23325 23523 23525 24052 24520 25024 25204 25233 25235 25240
 [45] 25253 25323 25325 25420 25523 30004 30040 30044 30304 30340 30344
 [56] 30400 30404 30440 30444 32235 32253 32255 32325 32523 32525 33004
 [67] 33040 33044 33225 33304 33340 33400 33404 33440 33522 34000 34004
 [78] 34040 34044 34300 34304 34340 34400 34404 34440 35223 35225 35322
 [89] 35522 40252 40300 40304 40340 40344 42052 42520 43000 43004 43040
[100] 43044 43300 43304 43340 43400 43404 43440 44300 44304 44340 45220
[111] 50224 52024 52204 52233 52235 52240 52253 52323 52325 52420 52523
[122] 53223 53225 53322 53522 54220 55223 55322

with the first value containing 0 being 304. And no 6 ever appearing in the numbers!