It's feeding time in the pig pen, where a trough is divided into n
stalls to accommodate n piglets. The rude piglets immediately rush to
the trough and distribute themselves arbitrarily among the stalls. After
them come the fastidious piglets one at a time, at one-minute intervals.
A fastidious piglet doesn't want to feed in just any stall, since he
doesn't like to be sandwiched between two piglets. As the trough
fills up, however, a piglet who hasn't managed to occupy an end stall will
eventually have a neighbor on each side. It is the fastidious
piglet's goal to delay this sandwiching as long as possible.
Among multiple stalls that afford the same delay, he prefers
the leftmost. He makes his selection in the knowledge that all subsequent piglets
arriving at the trough will choose a stall according to the same criteria.
Given a String describing a trough configuration such that '-'
represents an empty stall and 'p' represents an occupied stall, return the
zero-based index of the stall chosen by the next piglet. Return -1 if every
stall is occupied.
|