32
N children, with no two sharing their exact size, are lined up in some order. Each can only compare heights with their immediate neighbours. When the teacher shouts "raise hands if you are the tallest", they do so if they are taller than both their neighbours, and they do so simultaneously. If only one raises their hand, he wins. If more than one raise their hands, they are all eliminated from the row (preserving the order of the rest of the children) and they repeat the process.
Write a program, which takes an array of distinct integers (you can assume they are strictly positive) and outputs the winner of this game. This is code-golf, so the shortest code wins.
Examples (with intermediate stages shown):
5 3 9 8 7 → 3 8 7 → 8
1 2 9 4 → 9
9 3 8 7 4 12 5 → 3 7 4 5 → 3 4 → 4
Current leaders:
- Jelly: 17 bytes [by Dennis♦]
- MATL: 20 bytes [by Luis Mendo]
- APL: 28 bytes [voidhawk]
- k: 40 bytes [by Paul Kerrigan]
There's also a battle of Pythons going on. Still waiting for more golfing languages to show up.
I currently accepted Dennis♦'s answer - if there are new winners, I'll update the selection.
2sounds more like "who might be the tallest, or might not?" - to actually find "who is the tallest" you'd have to eliminate the ones that keep their hands down – Alnitak – 2016-12-01T17:42:24.313
4I drew similarity to kids' games, where one person shouts some signature phrase after which the game is named. Funnily enough, the tallest is least likely to win (by a huge margin). Asymptotically, out of N! permutations, only in 2^(N-1) cases he wins. – orion – 2016-12-01T21:03:24.577