Archive for June, 2015

Introducing Quimby: Context sensitive keyboard chording in a GTK input method

June 21st, 2015

A number of years ago, I found myself wanting to be able to use a greater variety of compose sequences than were generally available for Linux users. Compose sequences are great, and let you enter lots of different accented characters that occur in various languages that use the Latin alphabet. For example, you could type [compose] + e + ‘ to get “é”, and [compose] + c + , to get “ç”. But if you wanted to type “ǫ” you were out of luck. (It’s used in Old Icelandic, and I actually did want to type it once, to input a song title.)

The way to I found to fix this problem was to write a GTK input method module. This is the chunk of code that takes input from the keyboard handler system (xkb) and performs alchemy upon it to produce the characters that show up on the screen when you enter some text in a box. Not every Linux application would use my module. GTK is just one of a number of GUI toolkits used by Linux applications, but it’s a very common one, and it’s the one used by all of the applications I use frequently.

Over time the stock GTK input method has improved somewhat in the range of compose sequences it supports, but since I had input method code of my own, from time to time I found features to add to it. For example, it annoyed me that there was no keyboard shortcut for directly pasting selected text, so I made [compose] + [insert] do just that. (In Linux you can paste selected text (without explicitly copying it) with a middle mouse button click, but in GTK apps you can’t normally do that with the keyboard.)

More recently, I was trying to think of a way to do something about the problem of the inefficiency of typing English. One spends quite a bit of time typing common words. For example, whenever you type “the”, it takes four keystrokes, counting the space after the word. Stenography allows users to reach much faster speeds of text input by pressing multiple buttons at the same time. Most common words can be input using a single chord of button presses.

People who have mastered stenography are typically able to input text at three times their typing speed. The downside is that stenography has an extremely steep learning curve. One can spend months or years in intensive study to reach that plateau, and it can take quite a while just to break even. It’s also a system that has been designed for natural language text input, but computer keyboards have been designed to perform other sorts of tasks as well, like performing commands in applications, and writing code, where punctuation is used in a very different way from how it is used in natural language. (I should note that some efforts have been made to remedy this situation in Plover, an open source stenography implementation.)

Intrigued as I was by the possibilities of stenography, I felt rather daunted by the learning curve, and the expense and/or trouble required to buy or make the specialized hardware required. But what if there were some way to use chorded strokes on a regular keyboard to represent the most common words? Then we could have a system where the learning curve could be relatively modest, as normal typing would always be available. The ceiling of the speed increase would be modest as well, but it looked like an increase of about 10% to 15% might be possible. That’s not nothing. And my GTK input method was just the place to put the code that was needed to make it happen.

The space bar, being the easiest key on the keyboard to hit, was very tempting to use to signify that we are typing a chord that we want expanded. For example, we could use [space] + t to expand to “the “, saving two keystrokes. Since those keystrokes occur simultaneously, it’s almost as good as saving a third. Conveniently, we normally type [space] once per word anyway, so this should feel fairly natural. But simply expanding chorded keystrokes wouldn’t work. The problem is that in normal typing, it will frequently happen that the key press event for one key will occur before the key release event for the previously pressed key. You could be typing “hat rack”, and get “hathe rack” if you typed too quickly.

Fortunately, there was a simple solution. The key insight was that the only time you want a chord to expand into a whole word is when you are at the start of typing a word. And you can detect that, through the context that the input method supplies: GTK input methods allow you to access the text around the cursor. If the cursor is after a space, you are at the beginning of a word. (It’s more complicated than that; you can also be at the start of a word after certain punctuation, and sometimes you are at the start of a sentence, and we should detect that, and automatically capitalize the word we are expanding. But that was enough to get me started.) The problem of mistaken expansions wasn’t entirely banished. You could type “a tree”, and accidentally chord a + [space] + t, which expands to “at “. That’s unfortunate, but if you train yourself to always type the word “a” with an “a” + [space] chord, you can avoid the problem.

The choice of chords to represent common words is an intriguing puzzle in itself, and a matter for a future post. If you run GTK apps, (which means you are probably running Linux) and are interested in trying out Quimby, (short for “Questionably Useful Input Method? But Yes.”) the code is available on GitHub. I make no guarantees about its stability. It’s quite possible that it will crash and make you lose data! But the current iteration has been stable for me of late, and I used it to write this very post. The available chords aren’t documented yet and are still very much in flux; to see what they are currently, read the source. (src/chording.c) Eventually, I want to have the chord list be user extensible, but I’m not there yet. There is still more work to be done, adding more chords, detecting better when we are at the start of a word or a sentence, and supplying a few more features that will make using chording more convenient. But it’s ready to be shown off, and I am interested in hearing what people think about it.

This is how I roll: Sicherman dice with doubles

June 12th, 2015

Here are a few mostly functionally equivalent things:

2d6x3

The first is a pair of perfectly normal dice. The second is a “Merged d6”, a 36-sided die I bought through a crowdfunding campaign. Each of the sides is labeled with a sum of the results of rolling two normal dice. One of each of the even numbers between two and twelve is colored green. These let you simulate rolling doubles, as is required for games like Monopoly: each roll of two of the same number is represented. (The small print size of the numbers and the fact that it takes a moment to figure out which number is on top make this somewhat less practical than the normal dice, but I collect dice for mathematical interest rather than practicality.)

The blue and green dice are Sicherman dice. They are numbered a bit oddly. One of them has faces numbered 1, 2, 2, 3, 3, 4. The other’s faces are numbered 1, 3, 4, 5, 6, 8. The distribution of sums of die rolls is nevertheless the same as that of a normal pair of dice. In fact, it is the only non-standard numbering for a pair of dice with this property where the numbers are all positive integers.

Unfortunately, Sicherman dice don’t work for games that distinguish doubles rolls. Could we design a version of the Sicherman dice that does work for such games? The specially colored faces of the Merged d6 suggested a direction to take. We might color the faces of the Sicherman dice differently, and call a roll a doubles roll if the colors match. How many different ways are there to color the faces so as to produce exactly one match for every even number between two and twelve?

I posed this question on Google+. Joe DeVincentis found that there are sixteen essentially different solutions, of which two are the most interesting to me for designs that I might be interested in having made at some point:

1 2 2 3 3 41 3 4 5 6 8

This has the advantage of only requiring three colors, and all of the faces that never match are on the same die. It also has an easy mnemonic that you could use even without coloring the faces: one on low die, odd on high die; four on low die, even on high die. Variations where some subset of the never-matching faces are a different color from the others are considered essentially similar here.

1 2 2 3 3 41 3 4 5 6 8

Here the colors can be ordered from low to high, and have the same order on each die.

The rest of the solutions follow. For clarity, I’ve colored all of the numbers that never match black even when they exist on both dice. We may define a rule that black is not considered to match itself.

1 2 2 3 3 41 3 4 5 6 8

1 2 2 3 3 41 3 4 5 6 8

1 2 2 3 3 41 3 4 5 6 8

1 2 2 3 3 41 3 4 5 6 8

1 2 2 3 3 41 3 4 5 6 8

1 2 2 3 3 41 3 4 5 6 8

1 2 2 3 3 41 3 4 5 6 8

1 2 2 3 3 41 3 4 5 6 8

1 2 2 3 3 41 3 4 5 6 8

1 2 2 3 3 41 3 4 5 6 8

1 2 2 3 3 41 3 4 5 6 8

1 2 2 3 3 41 3 4 5 6 8

1 2 2 3 3 41 3 4 5 6 8

1 2 2 3 3 41 3 4 5 6 8