######################################################################
##GetMicrosoftJob: Save this file as GetMicrosoftJob. To use it,     #
#stay in the                                                         #
##same directory, get into Maple (by typing: maple <Enter> )         #
##and then type:  read GetMicrosoftJob : <Enter>                     #
##Then follow the instructions given there                           #
##                                                                   #
##Written by Doron Zeilberger, Temple University ,                   #
#zeilberg@math.temple.edu.                                           # 
#######################################################################
 
#Created: Sept. 25, 1998
#This version: Sept. 28, 1998
#GetMicrosoftJob: A Maple package to study the Generalized
#Microsoft recruiting puzzle
#Please report bugs to zeilberg@math.temple.edu
 
print(`GetMicrosoftJob: A Maple package to study the Generalized`):
print(`Microsoft recruiting puzzle.`):
print(`It is a companion of the paper by S.B. Ekhad and D. Zeilberger`):
print(`Entitled:The Generalized U2-Flashlight Microsoft 5-Minute Puzzle`):
print(`Please report bugs to zeilberg@math.temple.edu`):
 
print(``):
print(`This Maple package was inspired by the following riddle`):
print(`allegdly posed to Microsoft job candidates, who are`):
print(`required to solve it in less than five minutes`):
print(``):
print(`The four members of the U2 band have to cross a bridge at night`):
print(`equipped with a flashlight. At most two people can cross the`):
print(`bridge at one time. The times it takes them are: 1,2,5, and 10.`):
print(`When two people walk together, the faster one has to slow down`):
print(`and walk at the pace of the slower one`):
print(`How to arrange the crossings in such a way`):
print(`that the total time to cross all members is 17 minutes?`):
print(``):
print(`In order to get hired at Microsoft, put the package below on `):
print(` a micro-chip (say on your watch), and type`):
print(` "Bill(1,2,5,10);", or whatever times they would give you`):
print(``):
print(`Created: Sept. 25, 1998.`):
print(`This version: 9/25/1999`):
lprint(``):
print(`Written by Doron Zeilberger, zeilberg@math.temple.edu`):
lprint(``):
print(`Please report bugs to zeilberg@math.temple.edu`):
lprint(``):
 print(`The most current version of this  package and paper`):
 print(` are  available from`):
 print(`http://www.math.temple.edu/~zeilberg`):
 print(`For a list of the procedures type ezra(), for help with`):
 print(`a specific procedure, type ezra(procedure_name)`):
 print(``):
ezra:=proc()
if args=NULL then
 print(`Contains the following procedures:Bill, CheapestPaths, BillGates`):
 print(`  Gates, GatesT, Leonardo, Win95, Win98 `):
fi:
 
if nops([args])=1 and op(1,[args])=Leonardo then
print(`Leonardo(a,n): The set of expressions, in terms`):
print(`of the times a[1]<...<a[n], whose minimum gives`):
print(`the minimal times of crossing n people across`):
print(`the bridge`):
fi:
 
 
if nops([args])=1 and op(1,[args])=nape then
print(`nape(bitu,kv,L,a): Given an expression in the a[i]s`):
print(` 1<=i<=L `):
print(`with integer coefficients, and a set of expressions`):
print(`decides whether there is an expression in kv `):
print(`that is smaller than bitu `):
fi:
 
if nops([args])=1 and op(1,[args])=Win95 then
print(`Win95(L,a): Solves the Microsoft problem`):
print(`symbolically, where L is the number of people`):
print(` and we assume that the times it takes them is`):
print(`a[1]<a[2]<...<a[L] . The output consists of two parts`):
print(`The first part is the set of dominant expressions, incomparable`):
print(`expressions, that may be the minimal-crossing time`):
print(`The second is  table, showing for each winning possibility`):
print(` all the possible ways to cross with this minimal-total time`):
print(`For example, try Win95(4,a) `):
fi:
 
 
if nops([args])=1 and op(1,[args])=Win98 then
print(`Win98(time1,time2,...timek): Solves the generalized Microsoft problem`):
print(`numerically, using the fast recurrence in the paper`):
print(`by Zeilberger`):
print(`To solve the original problem, type: Win98(1,2,5,10); `):
fi:
 
 
if nops([args])=1 and op(1,[args])=Gates then
print(`Gates(time1,time2,...timek): Solves the generalized Microsoft problem`):
print(`numerically, using the explicit formula in the paper`):
print(`by Ekhad and Zeilberger`):
print(`To solve the original problem, type: Win98(1,2,5,10); `):
print(`Verbose version`):
fi:
 
 
if nops([args])=1 and op(1,[args])=GatesT then
print(`Gates(time1,time2,...timek): Solves the generalized Microsoft problem`):
print(`numerically, using the explicit formula in the paper`):
print(`by Ekhad and Zeilberger`):
print(`To solve the original problem, type: Win98(1,2,5,10); `):
print(`Terse version`):
fi:
 
if nops([args])=1 and op(1,[args])=Nathan then
print(`Nathan(L,Flashlight): Given L guys, 1,2, ..., L`):
print(`crossing the bridge, finds all the possible ways`):
print(`of doing it (with a flashlight Flashlight)`):
fi:
 
 
if nops([args])=1 and op(1,[args])=Mhyrvold then
print(`Mhyrvold(U2Guys,Flashlight): Given a set of distinct times for`):
print(`crossing the bridge, finds the shortest way of`):
print(`doing it`):
fi:
 
if nops([args])=1 and op(1,[args])=BillGates then
print(`BillGates(TIMES): Given a set of distinct times for`):
print(`crossing the bridge, finds the shortest way of`):
print(`doing it; For example, to solve the original version`):
print(` type: BillGates(1,2,5,10); `):
print(``):
print(`This is the slow version. The fast version is Gates `):
fi:
 
 
if nops([args])=1 and op(1,[args])=Bill then
print(`Verbose version of BillGates`):
print(`Slow version, (from scratch, so to speak) using CheapestPaths`):
print(``):
print(`Bill(TIMES): Given a set of distinct times for`):
print(`crossing the bridge, finds the shortest way of`):
print(`doing it; For example, to solve the original puzzle `):
print(` type: Bill(1,2,5,10); `):
 
fi:
 
 
if nops([args])=1 and op(1,[args])=CheapestPaths then
 
print(`CheapestPaths(Vertices,DiGraph,Cost,Start,Finish,K):`):
print(`Given a directed graph, with the data structure:`):
print(`set of Vertices, table of set outgoing neigbors for each`):
print(`vertex, DiGraph, a table of the Cost, a Start`):
print(`vertex and a Finish vertex, finds the cheapest`):
print(`path ; K is like infinity`):
 
fi:
 
end:
 
ezra1:=proc():print(` nape `):end:
 
#CheapestPaths(Vertices,DiGraph,Cost,Start,Finish,K):
#Given a directed graph, with the data structure:
#set of Vertices, table of set outgoing neigbors for each
#vertex, DiGraph, a table of the Cost, a Start
#vertex and a Finish vertex, finds the cheapest
#path ; K is like infinity
 
CheapestPaths:=proc(Vertices,DiGraph,Cost,Start,Finish,K)
local gu,skhenim,shi,j,mu,i,lu,sakhen:
option remember:
 
if Start=Finish then
RETURN({[[],0]}):
fi:
 
 
skhenim:=DiGraph[Start]:
 
if skhenim={} then
RETURN({}):
fi:
 
shi:=K:
gu:={}:
 
for i from 1 to nops(skhenim) do
sakhen:=op(i,skhenim):
mu:=CheapestPaths(Vertices,DiGraph,Cost,sakhen,Finish,K):
for j from 1 to nops(mu) do
lu:=op(j,mu):
 
if lu[2]+Cost[Start,sakhen]<shi then
 shi:=lu[2]+Cost[Start,sakhen]:
 gu:={[ [[Start,sakhen],op(lu[1])],shi]}:
elif lu[2]+Cost[Start,sakhen]=shi then
 gu:=gu union {[ [[Start,sakhen],op(lu[1])],shi]}:
fi:
 
od:
 
od:
 
gu:
 
end:
 
 
 
 
#Mhyrvold(U2Guys,Flashlight): Given the distinct times for
#crossing the bridge, finds the shortest way of
#doing it
Mhyrvold:=proc(U2Guys,Fl)
local Vertices,DiGraph,Cost,Start,Finish,K,guys,i,j,k,gu1,sakhen:
with(combinat):
K:=0:
 
Vertices:=powerset(U2Guys union {Fl}):
Start:=U2Guys union {Fl}:
Finish:={}:
 
for i from 1 to nops(Vertices) do
 
guys:=op(i,Vertices):
 
if guys={} then
DiGraph[guys]:={}:
fi:
 
if member(Fl,guys) then
gu1:=guys minus {Fl}:
 
if nops(gu1)=1 then
DiGraph[guys]:={}:
Cost[guys,{}]:=guys[1]:
K:=K+guys[1]:
fi:
 
DiGraph[guys]:={}:
for j from 1 to nops(gu1) do
for k from j+1 to nops(gu1) do
sakhen:=gu1 minus {op(j,gu1),op(k,gu1)}:
DiGraph[guys]:= DiGraph[guys] union 
{sakhen}:
 
Cost[guys,sakhen]:=max(op(j,gu1),op(k,gu1)):
K:=K+Cost[guys,sakhen]:
od:
od:
 
else
gu1:=U2Guys minus guys:
 
DiGraph[guys]:={}:
for j from 1 to nops(gu1) do
sakhen:=guys union {Fl, op(j,gu1)}:
DiGraph[guys]:= DiGraph[guys] union 
{sakhen}:
Cost[guys,sakhen]:=op(j,gu1):
K:=K+Cost[guys,sakhen]:
od:
fi:
od:
CheapestPaths(Vertices,DiGraph,Cost,Start,Finish,K):
end:
 
#BillGates(TIMES): Solves the Microsoft problem
BillGates:=proc()
local Fl1,gu,i,mu,mu1,gu1,j,gu2:
gu:=Mhyrvold({args},Fl1):
mu:={}:
 
for i from 1 to nops(gu) do
gu1:=op(i,gu)[1]:gu2:=op(i,gu)[2]:
mu1:=[]:
for j from 1 to nops(gu1)/2 do
mu1:=[op(mu1),gu1[2*j-1][1] minus gu1[2*j-1][2] minus {Fl1},
gu1[2*j][2] minus gu1[2*j][1] minus {Fl1}]:
od:
if nops(gu1) mod 2=1 then
j:=nops(gu1):
mu1:=[[op(mu1),gu1[j][1] minus gu1[j][2] minus {Fl1}],gu2]:
fi:
mu:=mu union {mu1}:
od:
mu:
end:
 
 
#sipur(mu)
sipur:=proc(mu)
local i,mu1,mu11:
mu1:=mu[1]:
 
for i from 1 to nops(mu1)/2 do
mu11:=mu1[2*i-1]:
print(` Let `, mu11[1], `and `, mu11[2], `walk forward with the flashlight`):
mu11:=mu1[2*i]:
print(` Let `, mu11[1], `walk back with the flashlight`):
od:
if nops(mu1) mod 2=1 then
i:=nops(mu1):
mu11:=mu1[i]:
print(` Let `, mu11[1], `and `, mu11[2], `walk forward with the flashlight`):
fi:
print(`Now they are all on the other side (flashlight included)`):
end:
 
#Bill(TIMES): Solves the Microsoft problem
Bill:=proc(TIMES)
local gu,i:
gu:=BillGates(args):
 
print(`The shortest time that the crossings can take is`, gu[1][2]):
print(` minutes `):
print(``):
print(`The number of ways to achieve this is`, nops(gu)):
print(``):
print(`Here there are`):
 
for i from 1 to nops(gu) do
print(`The Number`, i, `Way `):
sipur(gu[i]):
od:
end:
 
 
##################################
 
 
 
 
 
#Nathan(L,Flashlight): Given L guys, 1,2, ..., L
#crossing the bridge, finds all the possible ways
#of doing it (with a flashlight Flashlight)
Nathan:=proc(L,Fl)
local Vertices,DiGraph,Cost,Start,Finish,K,guys,i,j,k,gu1,sakhen,U2guys:
with(combinat):
K:=0:
 
U2guys:={seq(i,i=1..L)}:
Vertices:=powerset(U2guys union {Fl}):
Start:=U2guys union {Fl}:
Finish:={}:
 
for i from 1 to nops(Vertices) do
 
guys:=op(i,Vertices):
 
if guys={} then
DiGraph[guys]:={}:
fi:
 
if member(Fl,guys) then
gu1:=guys minus {Fl}:
 
if nops(gu1)=1 then
DiGraph[guys]:={}:
Cost[guys,{}]:=1:
K:=K+guys[1]:
fi:
 
DiGraph[guys]:={}:
for j from 1 to nops(gu1) do
for k from j+1 to nops(gu1) do
sakhen:=gu1 minus {op(j,gu1),op(k,gu1)}:
DiGraph[guys]:= DiGraph[guys] union 
{sakhen}:
 
Cost[guys,sakhen]:=1:
K:=K+Cost[guys,sakhen]:
od:
od:
 
else
gu1:=U2guys minus guys:
 
DiGraph[guys]:={}:
for j from 1 to nops(gu1) do
sakhen:=guys union {Fl, op(j,gu1)}:
DiGraph[guys]:= DiGraph[guys] union 
{sakhen}:
Cost[guys,sakhen]:=1:
K:=K+Cost[guys,sakhen]:
od:
fi:
od:
CheapestPaths(Vertices,DiGraph,Cost,Start,Finish,K):
end:
 
 
 
#Win95(L,a): Solves the Microsoft problem
#symbolically
Win95:=proc(L,a)
local Fl1,gu,i,mu,mu1,gu1,j,gu2,Mu,Gu,Gu1,T,T1:
gu:=Nathan(L,Fl1):
mu:={}:
 
for i from 1 to nops(gu) do
gu1:=op(i,gu)[1]:gu2:=op(i,gu)[2]:
mu1:=[]:
for j from 1 to nops(gu1)/2 do
mu1:=[op(mu1),gu1[2*j-1][1] minus gu1[2*j-1][2] minus {Fl1},
gu1[2*j][2] minus gu1[2*j][1] minus {Fl1}]:
od:
if nops(gu1) mod 2=1 then
j:=nops(gu1):
mu1:=[[op(mu1),gu1[j][1] minus gu1[j][2] minus {Fl1}],gu2]:
fi:
mu:=mu union {mu1}:
od:
mu:
Mu:={}:
Gu:={}:
for i from 1 to nops(mu) do
mu1:=op(i,mu)[1]:
Mu:=Mu union {[mu1,sleazeball(mu1,a)]}:
Gu:=Gu union {sleazeball(mu1,a)}:
od:
 
for i from 1 to nops(Gu) do
T[op(i,Gu)]:={}:
od:
 
for i from 1 to nops(Mu) do
T[op(i,Mu)[2]]:=T[op(i,Mu)[2]] union {op(i,Mu)[1]}:
od:
 
Gu1:=Gu:
 
for  i from 1 to nops(Gu) do
if nape(op(i,Gu),Gu minus {op(i,Gu)},L,a) then
Gu1:=Gu1 minus {op(i,Gu)}:
fi:
od:
 
for i from 1 to nops(Gu1) do
T1[op(i,Gu1)]:=T[op(i,Gu1)]:
od:
Gu1,T1:
end:
 
#sleazeball(mu,a): Given a list of sets, finds the
#sum of the a[max(set)]
sleazeball:=proc(mu,a)
local i,gu:
gu:=0:
for i from 1 to nops(mu) do
gu:=gu+a[max(op(mu[i]))]:
od:
gu:
end:
 
 
 
 
if nops([args])=1 and op(1,[args])=KM then
print(`KM(Exp,L,a): Given an expression in a[1], ..., a[L]`):
print(`with a[1]<a[2]<...<a[L]`):
fi:
 
 
 
 
#KM(Exp,L,a): Given an expression in a[1], ..., a[L]
#with a[1]<a[2]<...<a[L]
KM:=proc(Exp,L,a)
local i,Exp1,b:
Exp1:=Exp:
for i from L by -1 to 2 do
Exp1:=subs(a[i]=b[i]+a[i-1],Exp1):
od:
Exp1:=-subs(a[1]=b[1],Exp1):
 
for i from 1 to L do
if coeff(Exp1,b[i])<0 then
RETURN(false):
fi:
od:
 
true:
 
end:
 
 
#nape(bitu,kv,L,a): Given an expression in the a[i]'s
#with integer coefficients, and a set of expressions
#decides whether there is an expression in kv
#that is smaller than bitu 
nape:=proc(bitu,kv,L,a)
local gu,i:
for i from 1 to nops(kv) do
gu:=op(i,kv):
 
if KM(gu-bitu,L,a) then
RETURN(true):
fi:
od:
 
false:
end:
 
 
Win98:=proc(): F12(sort([args])):end:
 
F12:=proc(gu)
local gu1,gu2,n,Mu1,Mu2,ku:
option remember:
n:=nops(gu):
if n=1 then
RETURN([{op(gu)}], gu[1]):
elif n=2 then
RETURN([{op(gu)}], max(op(gu))):
elif n=3 then 
RETURN([{gu[1],gu[2]}, {gu[1]}, {gu[1],gu[3]}],gu[1]+gu[2]+gu[3]):
else
gu1:=[op(1..n-1,gu)]:
gu2:=[op(1..n-2,gu)]:
Mu1:=F12(gu1):
Mu2:=F12(gu2):
ku:=min(gu[n]+gu[1]+Mu1[2],gu[n]+2*gu[2]+gu[1]+Mu2[2]):
if ku=gu[n]+gu[1]+Mu1[2] then
RETURN([{gu[1],gu[n]},{gu[1]}, op(Mu1[1])],ku):
else
RETURN([{gu[1],gu[2]},{gu[1]},{gu[n-1],gu[n]}, {gu[2]}, op(Mu2[1])],ku):
fi:
 
fi:
end:
 
 
#Leonardo(a,n): The set of expressions, in terms
#of the times a[1]<...<a[n], whose minimum gives
#the minimal times of crossing n people across
#the bridge
Leonardo:=proc(a,n)
local i,gu1,gu2,gu:
option remember:
 
 
if n<1 then
RETURN({}):
fi:
if n=1 then
RETURN({a[1]}):
elif n=2 then
RETURN({a[2]}):
elif n=3 then
RETURN({a[1]+a[2]+a[3]}):
else
gu1:=Leonardo(a,n-1):
gu2:=Leonardo(a,n-2):
gu:={}:
 
for i from 1 to nops(gu1) do
gu:=gu union {op(i,gu1)+a[1]+a[n]}:
od:
 
for i from 1 to nops(gu2) do
gu:=gu union {op(i,gu2)+a[1]+2*a[2]+a[n]}:
od:
 
RETURN(gu):
#RETURN(Nake(gu,n,a)):
fi:
 
end:
 
 
 
#Nake1(kv,L,a): Given a set of expressions in the a[i]'s
#i=1,..., L
#with integer coefficients, deletes one,
#if possible
Nake1:=proc(kv,L,a)
local i:
 
for i from 1 to nops(kv) do
if nape(kv[i],kv minus {kv[i]},L,a) then
RETURN(kv minus {kv[i]}):
fi:
od:
kv:
end:
 
 
 
#Nake(kv,L,a): Given a set of expressions in the a[i]'s
#i=1,..., L
#with integer coefficients, deletes one,
#if possible
Nake:=proc(kv,L,a)
local gu1,gu:
gu:=kv:
gu1:=Nake1(gu,L,a):
 
if gu=gu1 then
RETURN(gu):
else
while gu<>gu1 do
gu:=gu1:
gu1:=Nake1(gu1,L,a):
od:
fi:
gu1:
end:
 
 
Pisa:=proc()
local a,gu,mu,i:
gu:=sort([args]):
mu:=Leonardo(a,nops(gu)):
for i from 1 to nops(gu) do
mu:=subs(a[i]=gu[i],mu):
od:
min(op(mu)):
end:
 
 
##################
 
 
 
#Leonardo1(a,n): The set of expressions, in terms
#of the times a[1]<...<a[n], whose minimum gives
#the minimal times of crossing n people across
#the bridge
Leonardo1:=proc(a,n)
local i,gu1,gu2,gu:
option remember:
 
 
if n<1 then
RETURN({}):
fi:
if n=1 then
RETURN({a[1]}):
elif n=2 then
RETURN({a[2]}):
elif n=3 then
RETURN({a[1]+a[2]+a[3]}):
else
gu1:=Leonardo1(a,n-1):
gu2:=Leonardo1(a,n-2):
gu:={}:
 
for i from 1 to nops(gu1) do
gu:=gu union {op(i,gu1)+a[1]+a[n]}:
od:
 
for i from 1 to nops(gu2) do
gu:=gu union {op(i,gu2)+a[1]+2*a[2]+a[n]}:
od:
 
RETURN(Nake(gu,n,a)):
fi:
 
end:
 
 
Pisa1:=proc()
local a,gu,mu,i:
gu:=sort([args]):
mu:=Leonardo1(a,nops(gu)):
for i from 1 to nops(gu) do
mu:=subs(a[i]=gu[i],mu):
od:
print(mu):
min(op(mu)):
end:
 
 
yafe:=proc(a,n)
local mu,gu,i,mu1,j,gu1:
 
mu:=Leonardo1(a,n):
gu:={}:
 
for i from 1 to nops(mu) do
mu1:=op(i,mu):
gu1:=[]:
 
for  j from 1 to n do
gu1:=[op(gu1),coeff(mu1,a[j],1)]:
od:
gu:=gu union {gu1}:
od:
gu:
end:
 
 
 
#Leonardo2(a,n): The set of expressions, in terms
#of the times a[1]<...<a[n], whose minimum gives
#the minimal times of crossing n people across
#the bridge. VERY FAST, using the explicit formula
Leonardo2:=proc(a,n)
local gu,r,i,mu:
gu:=[]:
for r from 0 to trunc(n/2)-1 do
mu:=(n-2-r)*a[1]+(2*r+1)*a[2]:
for i from 3 to n-2*r do
mu:=mu+a[i]:
od:
for i from 0 to r-1 do
mu:=mu+a[n-2*i]:
od:
gu:=[op(gu),mu]:
od:
gu:
end:
 
 
 
 
 
 
#GatesT(time1,time2, ..., timer): finds the shortest possible
#time and how to do it, terse version
GatesT:=proc()
local a,n,gu,mu,i,r,Mini:
gu:=sort([args]):
n:=nops(gu):
mu:=Leonardo2(a,nops(gu)):
 
for i from 1 to nops(gu) do
mu:=subs(a[i]=gu[i],mu):
od:
Mini:=min(op(mu)):
for r while mu[r]<>Mini do
od:
r:=r-1:
mu:=[]:
 
for i from 0 to r-1 do
mu:=[op(mu),{gu[1],gu[2]},{gu[1]},{gu[n-2*i],gu[n-2*i-1]},{gu[2]}]:
od:
 
for i from 0 to n-2*r-3 do
mu:=[op(mu),{gu[1],gu[n-2*r-i]},{gu[1]}]:
od:
mu:=[op(mu),{gu[1],gu[2]}]:
mu,Mini:
 
end:
 
Gates:=proc()
local mu:
mu:=GatesT(args):
print(`The shortest total time is`, mu[2]):
print(`One way of doing it is`):
sipur([mu])
end: