import string

from collections import Counter

# Computed from "A Tale of Two Cities". Compare Table $1\mathrm{.}3$ in Hoffstein, Pipher, Silverman.

english$\_$freq $=\{$

$\text{'}$a$\text{'}$: $0\mathrm{.}0803,$

$\text{'}$b$\text{'}$: $0\mathrm{.}014,$

$\text{'}$c$\text{'}$: $0\mathrm{.}0232,$

$\text{'}$d$\text{'}$: $0\mathrm{.}0467,$

$\text{'}$e$\text{'}$: $0\mathrm{.}1247,$

$\text{'}$f$\text{'}$: $0\mathrm{.}0226,$

$\text{'}$g$\text{'}$: $0\mathrm{.}0209,$

$\text{'}$h$\text{'}$: $0\mathrm{.}065,$

$\text{'}$i$\text{'}$: $0\mathrm{.}0683,$

$\text{'}$j$\text{'}$: $0\mathrm{.}0012,$

$\text{'}$k$\text{'}$: $0\mathrm{.}008,$

$\text{'}$l$\text{'}$: $0\mathrm{.}0367,$

$\text{'}$m$\text{'}$: $0\mathrm{.}0255,$

$\text{'}$n$\text{'}$: $0\mathrm{.}0706,$

$\text{'}$o$\text{'}$: $0\mathrm{.}0776,$

$\text{'}$p$\text{'}$: $0\mathrm{.}0166,$

$\text{'}$q$\text{'}$: $0\mathrm{.}0011,$

$\text{'}$r$\text{'}$: $0\mathrm{.}0621,$

$\text{'}$s$\text{'}$: $0\mathrm{.}0626,$

$\text{'}$t$\text{'}$: $0\mathrm{.}0902,$

$\text{'}$u$\text{'}$: $0\mathrm{.}0279,$

$\text{'}$v$\text{'}$: $0\mathrm{.}0087,$

$\text{'}$w$\text{'}$: $0\mathrm{.}0236,$

$\text{'}$x$\text{'}$: $0\mathrm{.}0012,$

$\text{'}$y$\text{'}$: $0\mathrm{.}0203,$

$\text{'}$z$\text{'}$: $0\mathrm{.}0004$

$\}$

def only$\_$letters$($X$,$ case$=$None$)$:

$\text{'}\text{'}\text{'}$Returns the string obtained from X by removing everything but the letters.

If case$=$"upper" or case$=$"lower", then the letters are all

converted to the same case.$\text{'}\text{'}\text{'}$

X $=\text{'}\text{'}.$join$($c for c in X if c in string.ascii$\_$letters$)$

if len$($X$)==0$:

return None

if case is None:

return X

elif case $==$ "lower":

return X$.$lower$()$

elif case $==$ "upper":

return X$.$upper$()$

def shift$\_$char$($ch$,$ shift$\_$amt$)$:

$\text{'}\text{'}\text{'}$Shifts a specific character by shift$\_$amt.

Example:

shift$\_$char$("$Y$",3)$ returns $"$B$"$

$\text{'}\text{'}\text{'}$

if ch in string.ascii$\_$lowercase:

base $=\text{'}$a$\text{'}$

elif ch in string.ascii$\_$uppercase:

base $=\text{'}$A$\text{'}$

# It's not clear what shifting should mean in other cases

# so if the character is not upper or lower$-$case, we leave it unchanged

else:

return ch

return chr$(($ord$($ch$)-$ord$($base$)+$shift$\_$amt$)\%26+$ord$($base$))$

def shift$\_$string$($X$,$ shift$\_$amt$)$:

$\text{'}\text{'}\text{'}$Shifts all characters in X by the same amount.$\text{'}\text{'}\text{'}$

return $\text{'}\text{'}.$join$($shift$\_$char$($ch$,$ shift$\_$amt$)$ for ch in X$)$

def count$\_$substrings$($X$,$n$)$:

$\text{'}\text{'}\text{'}$Returns a Python Counter object of all n$-$grams in X$.\text{'}\text{'}\text{'}$

if not X:

return $\{\}$

X $=$ only$\_$letters$($X$)$

shifts $=[$X$[$i:$]$ for i in range$($n$)]$

grams $=[\text{'}\text{'}.$join$($chrs$)$ for chrs in zip$(*$shifts$)]$

return Counter$($grams$)$

def get$\_$freq$($X$)$:

$\text{'}\text{'}\text{'}$Returns the proportion that each letter occurs in $"$X$".$

I might change this later, but for now, it converts everything to lowercase.

The reason is to match what appears in the english$\_$freq dictionary.$\text{'}\text{'}\text{'}$

X $=$ only$\_$letters$($X$,$ case$=$"lower"$)$

n $=$ len$($X$)$

ctr $=$ count$\_$substrings$($X$,1)$

output $=\{\}$

for char in string.ascii$\_$lowercase:

output$[$char$]=$ ctr$[$char$]/$n

return output

def mut$\_$ind$\_$co$($d$1,$ d$2)$:

$\text{'}\text{'}\text{'}$For letter frequency dictionaries d$1$ and d$2,$ return the Mutual Index of Coincidence.

See Equation $(5\mathrm{.}9)$ on page $222$ in Hoffstein, Pipher, Silverman.$\text{'}\text{'}\text{'}$

s $=0$

for k in d$1.$keys$()$:

s $+=$ d$1.$get$($k$,0)*$d$2.$get$($k$,0)$

return s

Write a function $`$shift$\_$decrypt$`$ to automatically decrypt ciphertext that has been encrypted using a shift cipher. Use the following pseudocode as your template. $($Even if you have an alternate approach, for this assignment, you should follow this pseudocode. Or at least check with Chris first before using a different approach.$)$

Here is a template to help you with the syntax and strategy. In this template, rather than using the above strategy, we return the shift amount for which the frequency of the letter $`"$E$"`$ is highest. If you already are pretty comfortable with Python, try to see how far you can get without using this template.

$```$

import numpy as np

def naive$\_$decrypt$($Y$)$:

holder $=$ np$.$zeros$(26)$

for i in range$(26)$:

X $=$ shift$\_$string$($Y$,$ i$)$

holder$[$i$]=$ X$.$count$("$E$")$

# np$.$argmax finds the location of the maximum value.

# $($If the maximum is obtained multiple times, only the first index is returned.$)$

shift$\_$amt $=$ np$.$argmax$($holder$)$

X $=$ shift$\_$string$($Y$,$ shift$\_$amt$)$

return $($X$,$ shift$\_$amt$)$

$```$