Crack the Caesar Cipher

A Caesar cipher moves every letter the same number of places forward in the alphabet, wrapping from Z to A: with shift 3, A becomes D and Y becomes B. Upper and lower case letters move the same way and keep their case, and every other character stays as it is. You have intercepted a message, but you do not know the shift.

Write crack_caesar(cipher) that finds the most likely shift by scoring how English each possible decryption looks, and returns a tuple (shift, plaintext). For every shift s from 0 to 25:

• decrypt the message by moving every letter s places backward (wrapping from A to Z);
• score that decryption: for each letter in it, upper or lower case, add the letter's weight from the table below.

The shift with the highest score wins, and if several shifts tie, the smallest of them wins. The weights are how common each letter is in English, in tenths of a percent (your starter code has them as the dictionary WEIGHTS, with capital letters as keys):

A 82   B 15   C 28   D 43   E 127  F 22   G 20
H 61   I 70   J 2    K 8    L 40   M 24   N 67
O 75   P 19   Q 1    R 60   S 63   T 91   U 28
V 10   W 24   X 2    Y 20   Z 1

Examples

crack_caesar("Wkh txlfn eurzq ira.")  # returns (3, 'The quick brown fox.')
crack_caesar("Uryyb, Jbeyq!")         # returns (16, 'Ebiil, Tloia!')
crack_caesar("2 + 2 = 4")             # returns (0, '2 + 2 = 4')

The second example is "Hello, World!" moved by 13, but on a message this short another decryption happens to score higher, and the rule picks it: frequency analysis needs enough text to work. With no letters at all, every shift scores 0 and the smallest, 0, wins.

Constraints

• cipher has 0 to 100,000 characters.