The Santa Claus problem

“The Little Book of Semaphores” presents the following as the “Santa Claus problem”, and attributes it to William Stallings:

Stand Claus sleeps in his shop at the North Pole and can only be awakened by either (1) all nine reindeer being back from their vacation in the South Pacific, or (2) some of the elves having difficulty making toys; to allow Santa to get some sleep, the elves can only wake him when three of them have problems. When three elves are having their problems solved, any other elves wishing to visit Santa must wait for those elves to return. If Santa wakes up to find three elves waiting at his shop’s door, along with the last reindeer having come back from the tropics, Santa has decided that the elves can wait until after Christmas, because it is more important to get his sleigh ready. (It is assumed that the reindeer do not want to leave the tropics, and therefore they stay there until the last possible moment.) The last reindeer to arrive must get Santa while the others wait in a warming hut before being harnessed to the sleigh.

Santa is easy:

func (s SantaClaus) Run() {
	for {
		select {
		case <-s.ReindeerCh:
			log.Println("All the reindeer are here")
			return
		case <-s.ElfCh:
			log.Println("Enough elves are having trouble, woke up Santa")
			s.ElfCh <- Signal{}
		}
	}
}

this can be executed as a goroutine that is woken up when all the reindeer are back or when enough elves are having trouble. Santa doesn’t need to worry about counting either reindeer or elves. Following the specification, Santa needs to send a signal back when the elves’ problem has been dealt with, and then he does back to sleep.

The problem of figuring out if all the reindeer are back or if enough elves are having trouble is pushed back to another entity, which I’m calling Santa’s Helper:

func (h SantasHelper) Run() {
	var reindeer, elves int
	for {
		select {
		case <-h.ReindeerCh:
			reindeer++
			if reindeer == Reindeers {
				h.Santa.ReindeerCh <- Signal{}
			}
		case <-h.ElfCh:
			elves++
			if elves == Elves {
				h.Santa.ElfCh <- Signal{}
				elves = 0
				<-h.Santa.ElfCh
			}
		}
	}
}

whenever a reindeer arrives, the helper makes a note of it; whenever an elf arrives, the helper makes a note of it. When there are enough reindeer or elves, the helper sends a signal to wake Santa up. It is really this simple.

There is one subtle issue here: since Santa might take a non trivial amount of time helping elves, when the third elf arrives, the helper blocks waiting for Santa. In that case reindeer are going to pile up waiting for the helper to wake up, and when it does wake up, the helper might end up giving priority to the elves that arrived later instead of the reindeer that arrived first. This is not such a big problem though, as it is easily solved creating two helpers: one for reindeer and one for elves.

The full source is here.

Next week it’s time to build some water.