Skip to content

Instantly share code, notes, and snippets.

@chochos
Created September 9, 2015 23:18
Show Gist options
  • Save chochos/d8f7398f756479e67395 to your computer and use it in GitHub Desktop.
Save chochos/d8f7398f756479e67395 to your computer and use it in GitHub Desktop.
Zurg
class Toy(shared String name, shared Integer time) {
string="``name`` (takes ``time``m)";
}
Comparison sortFast(Toy a, Toy b)
=> a.time<=>b.time;
Toy[2] fastestPair([Toy*] gang) {
assert(nonempty g=gang.sort(sortFast),
nonempty r=g.rest);
return [g.first, r.first];
}
Toy[2] slowestPair([Toy*] gang) {
assert(nonempty g=gang.sort((a, b) => b.time<=>a.time),
nonempty r=g.rest);
return [g.first, r.first];
}
[Toy*] remove([Toy*] toys, Toy[2] par)
=> toys.select((e) => !e in par);
shared void run() {
variable [Toy*] start = [ Toy("Buzz",5), Toy("Woody",10),
Toy("Hamm",25), Toy("Rex",20) ];
variable [Toy*] end = [];
variable value time = 0;
while (time<60, start.size > 0) {
value rapidos = fastestPair(start);
print("Cruzan: ``rapidos`` en ``rapidos[1].time``");
start = remove(start, rapidos);
end = end.withTrailing(rapidos[1]);
time += rapidos[1].time;
if (start.size > 0) {
start = start.withTrailing(rapidos[0]);
time += rapidos[0].time;
print("Regresa ``rapidos[0]`` llevamos ``time``");
value lentos = slowestPair(start);
time += lentos[0].time;
print("Cruzan: ``lentos`` en ``lentos[0].time`` llevamos ``time``");
end=end.append(lentos).sort(sortFast);
start=remove(start,lentos);
assert(nonempty e=end);
time += e.first.time;
print("Regresa ``e.first`` llevamos ``time``");
start = start.withTrailing(e.first);
end = end.rest;
} else {
end = end.withTrailing(rapidos[0]);
}
}
print("Tiempo: ``time``");
}
Buzz, Woody, Rex, and Hamm have to escape from Zurg. They merely have to cross one last bridge before they are free. However, the bridge is fragile and can hold at most two of them at the same time. Moreover, to cross the bridge a flashlight is needed to avoid traps and broken parts. The problem is that our friends have only one flashlight with one battery that lasts for only 60 minutes (this is not a typo: sixty). The toys need different times to cross the bridge (in either direction):
TOY TIME
Buzz 5 minutes
Woody 10 minutes
Rex 20 minutes
Hamm 25 minutes
Since there can be only two toys on the bridge at the same time, they cannot cross the bridge all at once. Since they need the flashlight to cross the bridge, whenever two have crossed the bridge, somebody has to go back and bring the flashlight to those toys on the other side that still have to cross the bridge.
The problem now is: In which order can the four toys cross the bridge in time (that is, in 60 minutes) to be saved from Zurg?
Add Comment Collapse
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment