-
Notifications
You must be signed in to change notification settings - Fork 8
/
Copy pathcrown-typewriter.html
177 lines (165 loc) · 9.61 KB
/
crown-typewriter.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
<!DOCTYPE html>
<html>
<head>
<link rel="canonical" href="https://hardmath123.github.io/crown-typewriter.html"/>
<link rel="stylesheet" type="text/css" href="/static/base.css"/>
<title>Tuning a Typewriter - Comfortably Numbered</title>
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8"/>
<meta charset="utf-8"/>
<meta name="viewport" content="width=device-width, initial-scale=1.0, maximum-scale=1.0, user-scalable=no" />
<link rel="alternate" type="application/rss+xml" title="Comfortably Numbered" href="/feed.xml" />
<!--
<script src="https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.1/MathJax.js?config=TeX-AMS-MML_HTMLorMML"></script>
<script>
MathJax.Hub.Config({
tex2jax: {inlineMath: [['$','$']]}
});
</script>
-->
<link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/[email protected]/dist/katex.min.css" integrity="sha384-Um5gpz1odJg5Z4HAmzPtgZKdTBHZdw8S29IecapCSB31ligYPhHQZMIlWLYQGVoc" crossorigin="anonymous">
<script defer src="https://cdn.jsdelivr.net/npm/[email protected]/dist/katex.min.js" integrity="sha384-YNHdsYkH6gMx9y3mRkmcJ2mFUjTd0qNQQvY9VYZgQd7DcN7env35GzlmFaZ23JGp" crossorigin="anonymous"></script>
<script defer src="https://cdn.jsdelivr.net/npm/[email protected]/dist/contrib/auto-render.min.js" integrity="sha384-vZTG03m+2yp6N6BNi5iM4rW4oIwk5DfcNdFfxkk9ZWpDriOkXX8voJBFrAO7MpVl" crossorigin="anonymous"></script>
<script>
document.addEventListener("DOMContentLoaded", function() {
renderMathInElement(document.body, {
// customised options
// • auto-render specific keys, e.g.:
delimiters: [
{left: '$$', right: '$$', display: true},
{left: '$', right: '$', display: false},
{left: '\\begin{align}', right: '\\end{align}', display: true},
{left: '\\(', right: '\\)', display: false},
{left: '\\[', right: '\\]', display: true}
],
// • rendering keys, e.g.:
throwOnError : false
});
});
</script>
</head>
<body>
<header id="header">
<script src="static/main.js"></script>
<div>
<a href="/"><span class="left-word">Comfortably</span> <span class="right-word">Numbered</span></a>
</div>
</header>
<article id="postcontent" class="centered">
<section>
<h1>Tuning a Typewriter</h1>
<center><em><p>A Markovian adventure in optimizing historical typewriter layouts</p>
</em></center>
<h4>Tuesday, November 20, 2018 · 3 min read</h4>
<p>I recently read this <a href="https://www.theatlantic.com/technology/archive/2016/11/chinese-computers/504851/">Atlantic
piece</a>
on input methods for computers, and it reminded me of a mathematical adventure
I had this summer that I should have blogged about at the time.</p>
<p>Back in July, I was exploring the City Museum of New York when I came across
this lovely Crown typewriter from the late 1800s. By our modern standards, it
uses a rather clunky input mechanism: you manually shift the pointer to the
character you want to type, press the button, rinse, repeat.</p>
<p><img src="static/crown-typewriter/crown-typewriter.png" alt="Crown Typewriter"></p>
<p>“What a waste of time,” you say. Ah, but even in the late 19th centure time was
the essential ingredient, and in the modern world there was no time. Notice,
then, that the designers of the Crown typewriter did not place the letters in
alphabetical order. Instead, the they placed commonly-together letters near
each other. You can type “AND” and “THE” rather quickly with just 2 shifts
apiece; “GIG,” on the other hand, takes 15 shifts from the G to the I, and 15
shifts back to the G.</p>
<p>The question, then, begs to be asked: is this the <em>most efficient</em> permutation
of letters? For example, Q and U are on opposite ends of the typewriter; surely
it would be better to put them together?</p>
<p>I have a doubly disappointing answer to this question: first, this is <em>not</em> the
most efficient permutation of letters (based on my digraph frequency map), but
I also don’t <em>know</em> what the most efficient permutation is! That is, I’ve found
permutations that are more efficient, but cannot prove that they are optimal
— after all, exploring all 26-factorial permutations is not an option.</p>
<p>My “cost” metric here is defined as “Ignoring non-alphabetic characters, how
many shifts does it take to type all of <em>Pride and Prejudice</em> followed by all
of <em>The Time Traveller</em> followed by all of <em>The Adventures of Sherlock
Holmes</em>?” (All three are classic 19th-century novels available from Project
Gutenberg.)</p>
<p>By this metric, the naive alphabetical order (<code>ABCDEFGHIJKLMNOPQRSTUVWXYZ</code>)
requires a whopping 9,630,941 shifts. In comparison, the Crown Typewriter
(<code>XQKGBPMCOFLANDTHERISUWYJVZ</code>) requires only 6,283,692 shifts. But the
ComfortablyNumbered typewriter (<code>ZKVGWCDNIAHTESROLUMFYBPXJQ</code>) requires a mere
5,499,341 shifts. This means we can save nearly one in eight shifts from the
Crown typewriter!</p>
<p>I found this permutation with the following algorithm: start with a random
permutation, then “optimize” it by repeatedly swapping characters such that the
post-swap permutation has a lower cost than the pre-swap permutation. Continue
“optimizing” until no further swaps can be made. Now, do this procedure for a
large number of random starting permutations, and pick the lowest-cost
optimized permutation.</p>
<p>Encouragingly, it turns out that many different random starts get optimized to
my solution. What do I mean by that? Well, the graph below shows two datasets:
the costs of 1,000 random permutations and the costs of those permutations once
optimized. Clearly, optimization is doing great good.</p>
<p><img src="static/crown-typewriter/typewriter-graph-1.png" alt="First graph"></p>
<p>But let’s zoom in on the optimized permutations. Notice that the two
lowest-cost bars are almost an order of magnitude more frequent than the
remaining bars. In fact, the lower-cost bar’s “bucket” in the histogram is
populated <em>only</em> with permutations of cost 5499341! This suggests that 5499341
is a “hard ceiling” for my optimizer, rather than the furthest point on the tip
of a long tail that my optimizer samples from.</p>
<p><img src="static/crown-typewriter/typewriter-graph-2.png" alt="Second graph"></p>
<p>Of course, this is no proof: there might be a single highly-efficient
permutation that is hard to reach by optimizing a random permutation. But that
<em>feels</em> unlikely!</p>
<p>So: I leave this as an open problem for readers to explore.</p>
<blockquote>
<p>Update (Dec 15): I found this <a href="https://yurichev.com/blog/cabling_Z3/">blog
post</a> by Dennis Yurichev that tackles
the same problem, but restated as “in what order do I mount these devices on
a rack if I want to minimize the total length of cables between them”? Dennis
finds an optimal solution for 8 devices with Z3… perhaps the solution
scales to 26 “devices”? Intriguingly, his post was published just weeks
before my visit to the City Museum!</p>
<p>Update (Jan 28): @rjp on Github has posted a <a href="http://rjp.is/blogging/posts/2019/01/linear-typewriters/">blog
post</a> with
<em>several</em> new approaches to this problem!</p>
<p>Update (May 21, 2020): I discovered that back at the end of 2018, a bunch of
optimization theory researchers wrote <em>several</em> blog posts inspired by this
problem. See <a href="https://www.theverge.com/2020/5/20/21262302/ap-test-fail-iphone-photos-glitch-email-college-board-jpeg-heic">Nathan
Brixius’s
post</a>
and a <a href="https://orinanobworld.blogspot.com/2018/12/of-typewriters-and-permutations-i.html">five-post series by Paul
Rubin</a>.
Amazing!</p>
<p>Update (July 3, 2020): I discovered that Peter Norvig <a href="https://github.com/norvig/pytudes/blob/master/ipynb/Gesture%20Typing.ipynb">spent some
time</a>
thinking about this question for 2D gesture-based keyboards (e.g. “Swype”).
Relatedly see <a href="https://jasmcole.com/2017/06/04/swype-right/">this</a> blog post
by Jason Cole.</p>
<p>Update (Sept 12, 2020): Found yet another
<a href="https://github.com/BenjaminPoilve/Typewriter-Optimisation">attack</a> on the
problem!</p>
</blockquote>
</section>
<div id="comment-breaker">◊ ◊ ◊</div>
</article>
<footer id="footer">
<div>
<ul>
<li><a href="https://github.com/kach">
Github</a></li>
<li><a href="feed.xml">
Subscribe (RSS feed)</a></li>
<li><a href="https://twitter.com/hardmath123">
Twitter</a></li>
<li><a href="https://creativecommons.org/licenses/by-nc/3.0/deed.en_US">
CC BY-NC 3.0</a></li>
</ul>
</div>
<script>
(function(i,s,o,g,r,a,m){i['GoogleAnalyticsObject']=r;i[r]=i[r]||function(){
(i[r].q=i[r].q||[]).push(arguments)},i[r].l=1*new Date();a=s.createElement(o),
m=s.getElementsByTagName(o)[0];a.async=1;a.src=g;m.parentNode.insertBefore(a,m)
})(window,document,'script','//www.google-analytics.com/analytics.js','ga');
ga('create', 'UA-46120535-1', 'hardmath123.github.io');
ga('require', 'displayfeatures');
ga('send', 'pageview');
</script>
</footer>
</body>
</html>