Le Monde puzzle [#1158]

A weekly puzzle from Le Monde on umbrella sharing:

Four friends, Antsa, Cyprien, Domoina and Fy, are leaving school to return to their common housing. It is raining and they only have one umbrella with only room for two. Given walking times, x¹, x², x³ and x⁴, find the fastest time by which all of the four will be home, assuming they all agree to come back with the umbrella if need be.

A recursive R function produces the solution

bez=function(starz=rexp(4),finiz=rep(0,4),rtrn=F){
  if((!rtrn)&(sum(starz>0)==2)){return(max(starz))
    }else{
      tim=1e6
      if(rtrn){
        for(i in (1:4)[finiz>0]){
          nstart=starz;nstart[i]=finiz[i]
          nfini=finiz;nfini[i]=0
          targ=finiz[i]+bez(nstart,nfini,FALSE)
          if(targ<tim){tim=targ}} 
          }else{
          for(i in (1:4)[starz>0])
          for(j in (1:4)[starz>0]){
            if(i!=j){
              nstar=starz;nstar[i]=nstar[j]=0
              nfini=finiz;nfini[i]=starz[i];nfini[j]=starz[j]
              targ=max(starz[i],starz[j])+bez(nstar,nfini,TRUE)
              if (targ<tim){tim=targ}
            }}}
      return(tim)}

which gives for instance

> bez()
[1] 3.297975
> bez(1:4)
[1] 11
> bez(rep(3,4))
[1] 15