Build an implied-volatility smile from quotes

An index options desk receives end-of-day quotes for 17 European calls with six months to expiry. Traders quote prices, but the risk system stores volatilities, so every quote has to be turned into an implied volatility.

Some quotes are stale or mistyped. A solver that diverges on them, or quietly returns a number anyway, corrupts the whole volatility surface.

Your task

1. Write implied_vol(price, S, K, T, r): the volatility at which bs_call equals the quoted price. Return None when no volatility can produce that price: below the no-arbitrage lower bound $\max(S - Ke^{-rT}, 0)$, or at or above the spot.
2. Make it robust. It must converge for deep out-of-the-money calls and for calls priced just above intrinsic value, where plain Newton's method misbehaves.
3. Write smile(quotes, S, T, r): a list of (strike, volatility) pairs, with None for quotes that fail the check.

The data

QUOTES holds the 17 (strike, price) pairs; SPOT, RATE and EXPIRY hold the market data. The code provides bs_call and vega. The quotes were generated from a known smile and rounded, with two quotes spoiled.

Hint: Where to start

Lesson 2.4.6 finds one implied volatility with Newton's method. Start from that, then make it safe.

Hint: Keeping Newton safe

The call price rises with volatility, so each price you compute tells you which side of the answer you are on. Keep a bracket around the root, and bisect whenever a Newton step would leave it (lesson 2.4.4).