Archive for brute-force solution

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!

Le Monde puzzle [#1146]

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

The weekly puzzle from Le Monde is once more disappointing.

Everyday of the month, take 0, 1 or 2 units. If one unit taken past day, next day none can be taken. If two units taken two day ago, none can be taken the current day. What is the strategy maximising the number of units  for February? March? April? Generalise to 0,..,3 units taken each day with 0 compulsory three days after taking 3 units.

as taking 2-1-0 (or 3-2-1-0) sounds like the optimal strategy. Except at the final step when 2, 2-2, 2-2-0, and 1-0-2-2 are best. But then why would one distinguish between the three months..?! Because the outcome differ, as 30, 32, and 33, resp. (or 45, 48 and 51). With an average increase of 1 in the first case and 1.5 in the second.

Another puzzle took too much of my time, namely a code golf challenge to devise a code taking as input a matrix of moves over an n x x grid and returning as input the number of nodes and transient tributaries for each loop (or irreducible set) of the moves. Which I solved by running Markov chains from each starting point long enough to reach stationarity. Entering the moves as

n=3;M=matrix(sample(1:4,n^2,rep=T),n)

and returning the result via 390 bytes

j=cbind;l=sum;a=apply
m=l(!!M);n=m^.5
g=function(A,r=M[A])A+c((r<2)*(1-n*(A[,1]==n))-(r==2)*(1-n*(A[,1]<2)),
(r==3)*(1-n*(A[,2]==n))-(r>3)*(1-n*(A[,2]<2)))
I=c()
for(i in d<-1:n)I=rbind(I,j(i*d/d,d))
for(t in b<-1:m)I=g(I)
p=function(i)i[,1]+n*i[,2]-n-1
K=matrix(0,m,m)
for(t in b)K[b+m*p(I<-g(I))]=1
s=o=a(u<-unique(K),1,l)
for(k in 1:l(!!s))s[k]=l(!a(!!sweep(K,2,u[k,],'-'),1,l))
j(o,s-o)

which could be much shorter if only matrices could be indexed from 0 as in C.

Le Monde puzzle [#1144]

Posted in Books, Kids with tags , , , , , , on May 19, 2020 by xi'an

The weekly puzzle from Le Monde is again using 2020 but not R!

Two teams involve a prime total number m of participants, with each player getting between 0 and 100 points. The total score for both teams is 2020, with team B less than team A on average. A single transfer from A to B increases the average scores for both A and B by 1/2. What is the difference of the averages? The transfer(ed) player, Camélia, had 5 points less  than the average score for A. What was the score of Camélia?

but I could not find a brute force solution and ended up finding that 2×2020=2x2x5x101 is a multiple of m, which leaves only

m=101

as the possible number of players. Which almost immediately leads to a difference of m/2 between the average scores. And then almost as immediately to Camélia’s score being 60. If one really needed an R function

k=function(a){((C<-71-a)>0)&(C+(a-1)/2<102)
              &(C-((102-a)/2)>0)&(C+5==(C+(a-1)/2))}

does return a=11 but this is 100% useless!

more games of life

Posted in Books, Kids, R with tags , , , , on May 5, 2020 by xi'an

Another puzzle in memoriam of John Conway in The Guardian:

Find the ten digit number, abcdefghij. Each of the digits is different, and

  • a is divisible by 1
  • ab is divisible by 2
  • abc is divisible by 3
  • abcd is divisible by 4
  • abcde is divisible by 5
  • abcdef is divisible by 6
  • abcdefg is divisible by 7
  • abcdefgh is divisible by 8
  • abcdefghi is divisible by 9
  • abcdefghij is divisible by 10

Which brute force R coding by checking over random permutations of (1,2,…,9) [since j=0] solves within seconds:

while(0<1)
  if (prod(!(x<-sum(10^{0:8}*sample(1:9)))%/%10^{7:0}%%2:9))break()

into x=3816547290. And slightly less brute force R coding even faster:

while(0<1){
e=sample(c(2,6,8))#even
o=sample(c(1,3,7,9))#odd
if((!(o[1]+e[1]+o[2])%%3)&
(!(10*o[2]+e[2])%%4)&
(!(o[1]+e[1]+o[2]+e[2]+5+4)%%3)&
(!sum(10^{6:0}*c(o[1],e[1],o[2],e[2],5,4,o[3]))%%7)&
(!(10*o[3]+e[3])%%8)&
(!(sum(o)+sum(e))%%9)){
print(sum(10^{9:0}*c(o[1],e[1],o[2],e[2],4,5,o[3],e[3],o[4],0)));break()}}