/// [0/0/9] ## [:house:](/projects) [1/1/0] #### [**Home**](/) #### [__**Projects**__](/projects) #### [**Other**](/other) [3/4/9] ###### Monday, January 28th 2019 ## **Typewriter Optimisation** ##### @benjaminpoilve A few days ago, I read in [this blog post](https://hardmath123.github.io/crown-typewriter.html) about @hardmath123 effort to solve an interesting optimisation problem. He was inspired by a Crown typewriter from the late 1800s, which worked by shifting the pointer of a linear slide containing all the letter before pressing the button.  As a result, writing on this king of typewriter is terribly cumbersome! As a corollary, the order of the letters on the slide is very important. For exemple in English the T-H digraph is very common, so it is smart to have put them next to each other on the slide. But is the global choice the best one possible? To determine that, we need a metric. His choosen metric was the total shift number needed to type a couple of litterature classics. With a genetic algorithm, he managed to find a far less costly arrangement of letters, but did not manage to prove it was the best arrangement. Could I find a better one? He suggested trying to use constraint solvers, so that's what I tried #### Reproducing the result But first, let's make sure we have the right problem by re-implementing the whole thing in Python. You can find the notebook for this article [here](https://github.com/BenjaminPoilve/Typewriter-Optimisation/blob/master/main.ipynb) First thing first, let's make sure that we have results consistent with @hardmath123 article ``` def cost_typewriter(a,b,string): #index because we want to know if it is not found return abs(string.index(a)-string.index(b)) def test_permutation(string_permutation,cost_function): distance_matrix=np.empty([len(string_permutation), len(string_permutation)]) for index_1,letter_1 in enumerate(alphabet): for index_2,letter_2 in enumerate(alphabet): distance_matrix[index_1][index_2]=cost_function(letter_1,letter_2,string_permutation) score_matrix=np.multiply(distance_matrix, diag_digraph) return score_matrix.sum() test_permutation("ABCDEFGHIJKLMNOPQRSTUVWXYZ",cost_typewriter) ``` The result, 9630941 is consistent with the article. The genetic algorithm in himself is not too hard to implement. Once we have functions both for letter swapping and random arrangement generation, it is simply ``` def genetic_force(seed_size,number_test,stop_cutoff,cost_function): #generate seed family= [random_permutation() for x in range(seed_size)] stop_counter=0 while stop_counter=0, var