Archive for codegolf

a new Monty Hall riddle

Posted in Books, Kids, Mountains, pictures, R, Statistics, Travel with tags , , , , , , , , , on May 22, 2020 by xi'an

The Riddler was sort of feeling the rising boredom of being under lockdown when proposing the following variant to the Monty Hall puzzle:

There are zero to three goats, with a probability ¼ each, and they are allocated to different doors uniformly among the three doors of the show. After the player chooses a door, Monty opens another door hidding a goat or signals this is impossible. Given that he did open a door, what is the probability that the player’s door does not hide a goat?

Indeed, a straightforward conditional probability computation considering all eight possible cases with the four cases corresponding to Monty opening a door leads to a probability of 3/8 for the player’s door. As confirmed by the following R code:

s=sample
m=c(0,0)
for(t in 1:1e6)m=m+(range(s(1:3,s(1:3,1)))>1)

Metropolis in 95 characters

Posted in pictures, R, Statistics, Travel with tags , , , , , , , , on January 2, 2020 by xi'an

Here is an R function that produces a Metropolis-Hastings sample for the univariate log-target f when the later is defined outside as another function. And when using a Gaussian random walk with scale one as proposal. (Inspired from a X validated question.)

m<-function(T,y=rnorm(1))ifelse(rep(T>1,T),
  c(y*{f({z<-m(T-1)}[1])-f(y+z[1])<rexp(1)}+z[1],z),y)

The function is definitely not optimal, crashes for values of T larger than 580 (unless one modifies the stack size), and operates the most basic version of a Metropolis-Hastings algorithm. But as a codegolf challenge (on a late plane ride), this was a fun exercise.

sampling the mean

Posted in Kids, R, Statistics with tags , , , , , on December 12, 2019 by xi'an

A challenge found on the board of the coffee room at CEREMADE, Université Paris Dauphine:

When sampling with replacement three numbers in {0,1,…,N}, what is the probability that their average is (at least) one of the three?

With a (code-golfed!) brute force solution of

mean(!apply((a<-matrix(sample(0:n,3e6,rep=T),3)),2,mean)-apply(a,2,median))

producing a graph pretty close to 3N/2(N+1)² (which coincides with a back-of-the-envelope computation):temp

Froebenius coin problem

Posted in pictures, R, Statistics with tags , , , , , , , , , , on November 29, 2019 by xi'an

A challenge from The Riddler last weekend came out as the classical Frobenius coin problem, namely to find the largest amount that cannot be obtained using only n coins of specified coprime denominations (i.e., with gcd equal to one). There is always such a largest value. For the units a=19 and b=538, I ran a basic R code that returned 9665 as the largest impossible value, which happens to be 19×538-538-19, the Sylvester solution to the problem when n=2. A recent paper by Tripathi (2017) manages the case n=3, for “almost all triples”, which decomposes into a myriad of sub-cases. (As an aside, Tripathi (2017) thanks a PhD student, Prof. Thomas W. Cusick, for contributing to the proof, which constitutes a part of his dissertation, but does not explain why he did not join as co-author.) The specific case when a=19, b=101, and c=538 suggested by The Riddler happens to fall in one of the simplest categories since, as ⌊cb⁻¹⌋ and ⌊cb⁻¹⌋ (a) are equal and gcd(a,b)=1 (Lemma 2), the solution is then the same as for the pair (a,b), namely 1799. As this was quite a light puzzle, I went looking for a codegolf challenge that addressed this problem and lo and behold! found one. And proposed the condensed R function

function(a)max((1:(b<-prod(a)))[-apply(combn(outer(a,0:b,"*"),sum(!!a))),2,sum)])

that assumes no duplicate and ordering in the input a. (And learned about combn from Robin.) It is of course very inefficient—to the point of crashing R—to look at the upper bound

\prod_{i=1}^n a_i \ \ \ \ \ \ \ (1)

for the Frobenius number since

\min_{(i,j);\text{gcd}(a_i,a_j)=1} (a_i-1)(a_j-1)\ \ \ \ \ \ \ (2)

is already an upper bound, by Sylvester’s formula. But coding (2) would alas take much more space…

R puzzle

Posted in Statistics with tags , , on September 12, 2019 by xi'an

Can you guess the meaning of the following R code

"?"=`u\164f8ToI\x6Et`;'!'=prod;!{
    y<-xtabs(~?readLines())}%in%{
     z<-y[1]}&z>T##&[]>~48bEfILpu

If not (!), the explanation is provided in Robin’s answer to a codegolf puzzle.