Ask HN: Well-known algorithm to describe the balloons in hallway scenario? | Hacker News Reader

Ask HN: Well-known algorithm to describe the balloons in hallway scenario?

2 pointsbyoung25 comments

Is there a well-known sorting algorithm that fits the scenario described below?

A wise teacher once brought balloons to school, told her pupils to blow them up and write their name on one. After the children tossed their balloons into the hall, the teacher moved through the hall mixing them all up. The kids were given five minutes to find the balloon with their name on it, but though they searched frantically, no one found their own balloon.

Then the teacher told them to take the balloon closest to them and give it to the person whose name was on it. In less than two minutes, everyone was holding their own balloon.

The teacher said to the children, “These balloons are like happiness. We won’t find it when we’re only searching for our own. But if we care about someone else’s happiness … it will ultimately help us find our own.”

View on HN

Consider the balloon arrangement as a permutation, where balloons every balloon has a person and every person has a balloon. If you know the permutation, then you can invert it to send each balloon to its person.

You're assuming it's easier to find people than balloons, otherwise you don't know the permutation. If several people share a name, you need multiple passes.

I used a form of this, where every processor in an array wanted to request something from another processor in some permutation. If they all know the permutation, then you can skip the request part and send the reply directly to the one who wants it.

Is this actually sorting? It sounds more like a one-to-one mapping function.

In Lisp, you would use mapcar or a related map* function to do this.

Sending the kids in to search for their own balloons sounds like a (poor) sorting algorithm. But having pairs right from the get-go sounds like consing.

Sending the kids in to search for their own balloons sounds like a (poor) sorting algorithm

Haha true, I think that was the lesson. But sending kids to search for anyone's balloon and then assign it to the correct person seemed to be more efficient.

> assign it to the correct person ...

That's the mapping function in action. It's not really sorting.

It's a good story for teaching cooperation. If you wanted to apply it to an algorithm, it would look a lot like multi-agent modeling where you have a dozen kids, a dozen balloons, and each kid doing a single mapping function. In the inefficient model, each kid was doing a search function. In the efficient model, each kid was doing a map function.

Also: It reminds me of statistical analysis. An example of that is, if a PIN number fails at 3 attempts in a certain time frame, and you have hundreds of accounts, you are more likely to succeed if you use 1 pin for all accounts, and then increment the pin attempts each round, versus trying all pins on each account and getting locked out on the third attempt before you increment accounts each time. Statistically you'll get more hits faster one way over the other by the time the algorithm completes.

Makes sense!

Reply on news.ycombinator.com