Add option to use prefix-free hints so confirmation is not needed.

## **Current problem: Inconsistent flow when a hint is a prefix of another** When using the `hints` kitten ([live documentation](https://sw.kovidgoyal.net/kitty/kittens/hints/)/ documentation at the moment of writing [part 1](https://github.com/kovidgoyal/kitty/blob/c48111d92cba307f869dc1fd4ad0249b50502874/docs/kittens/hints.rst), [part 2](https://github.com/kovidgoyal/kitty/blob/c48111d92cba307f869dc1fd4ad0249b50502874/kittens/hints/main.py#L75)), the keyboard flow is disrupted when there is prefix ambiguity. Some hints are prefixes of other longer ones (for example, code `1` prefixes `10`, `11`, `1a`, etc.), If your collection of active hints has, for example: `[1, ..., 10, 11, ..., 1a, ..., a]` and so far you have already typed `1`, the terminal cannot immediately trigger the action that matches `1`, because there is still ambiguity on whether you intend to match `1` or something that starts with `1`. You to press a confirmation key (`Space`/`Enter` ) to resolve the ambiguity. In contrast, typing a code that is not a prefix of any other code (like `10`) always triggers immediately without confirmation. This disrupts the flow, in a multi-match scenario, with the hints collection described above,  you may have intended to match `1` and you are ready to start typing the next hint (let's say `a`), so you type `a` again and you now have matched `1a` instead of `1`, and `a`, as you intended. The flow is disrupted in that you have to remember to hit the confirmation key (but not all the time, because if there is no prefix, then the action triggers as soon as you finish the hint). Single match scenarios are also disrupted by requiring confirmation on cases where you have typed a prefix of another hint (you have to press one more key that was not explicitly shown in the hint initially) ## **Describe the solution you'd like** If hints where prefix-free confirmation would no longer be necessary and all matches would trigger as soon as you are done typing any hint, making the flow more consistent (today, you sometimes needs to confirm and sometimes you don't). ### On how to generate prefix-free hints: Note: I arrived at a solution, but it seemed a bit cryptic so I made my best effort to explain how I arrived to it. All of what is said in this section very likely already known and it probably has a name, but I had fun discovering it on my own, there is a TL;DR at the end of the section and working code if you want to skip all the text. If you have an alphabet of length $A$, and you need to generate $N$ prefix-free words (from here on the hint and word would be used interchangeably), since we are talking about prefixes, a reasonable approach is to think in tries, in particular it is useful to think the order in which words are generated by expanding a trie breadth-first, for example, for the alphabet "abc", the first few words generated by its trie expansion would be: ``` "a", "b", "c", "aa", "ab", "ac", "ba", "bb", "bc", "ca", "cb", "cc", "aaa", ... ``` and for practicality, let's enumerate this list starting with 1 (you could argue that the empty string is the 0-numbered one, but we don't care about the empty string in the context of hints), so, together with their numbers this would look like: ``` "a", "b", "c", "aa", "ab", "ac", "ba", "bb", "bc", "ca", "cb", "cc", "aaa", ... 1 2 3 4 5 6 7 8 9 10 11 12 13 ... ``` (from here on, whenever we mention in-order or just order we refer to this particular order) If looked in the trie expansion, it would be something like this ``` . ├── a │ ├── aa │ │ └── aaa │ ├── ab │ └── ac ├── b │ ├── ba │ ├── bb │ └── bc └── c ├── ca ├── cb └── cc ``` * **observation 1)** A useful observation is that when looked like this, only nodes that are leafs in the trie expansion are prefix-free since any node that has children nodes is a prefix to the words its children represents. * **observation 2)** In the order described, as you keep adding words, earlier words will inevitably become prefixes of later words, and it will happen in order and without gaps. That is, in the example, the first word to become a prefix of another will be "a" (when "aa" appears), the second will be "b", (when "ba" appears). * **observation 3)** As a consequence of observation 2), all prefix-free words are always at the tail of the expanded list (and also without gaps). * **observation 4)** The first time you need to drop a word because it prefixes another is when the word $A+1$ is added ($A$ is the length of the alphabet). In the example above, that is when "aa" (word number 4=3+1) is added. * **observation 5)** When thinking on expanding tries, when a node becomes a parent of another (and therefore it becomes a prefix) , it is always when the first character is added again. In the example above: "a" becomes a prefix when "aa" is added, "b" becomes a prefix when "ba" is added, "c" becomes a prefix when "ca" is added, ... All this means that a words become prefixes at "regular intervals", and that interval is $A$, which implies that every time you add $A$ new words to the list, exactly one word in the list has become now a prefix and your resulting list has now a total of $A-1$ new prefix-free words. And with this we can derive that if you want to find $N$ words that are prefix-free, all you have to do is skip the first $$ \left\lfloor \frac{N-2}{A-1} \right\rfloor \text{for N>2}, \text{0 otherwise} $$ from the ordered list. The $A-1$ comes from the fact that the number of prefix-free words grows in intervals of $A-1$, the $-2$ is encoding that the first time you have a prefix is at word $A+1$ (if you replace $N$ with $A-1$, you end up with $\lfloor{A-1}/{A-1}\rfloor=1$). ### TL; DR If your alphabet is of size $A$ and you need to generate $N$ prefix-free words/hints, and you generate the list of words/hints by expanding a trie breadth-first, you need to skip the first $$ \left\lfloor \frac{N-2}{A-1} \right\rfloor \text{for N>2}, \text{0 otherwise} $$ words and the next $N$ are guaranteed to be prefix-free. ### Working code The following three functions provide the functionality to: * determine how many words need to be skipped to guarantee $N$ consecutive prefix-free words. * given an index and an alphabet recover the word the index represents. * given a word and an alphabet recover the index it corresponds to the word. All three consider that the word with index 1 is the first non-empty word. ```go // wordsToSkip calculates how many words to skip based on the given n and // alphabet size so that the next n words generated by expanding the prefix tree // of an alphabet of size alphabetSize will be prefix-free. // // The result is 1-based, meaning that the first word to be skipped is the first // non-empty word. // // For example, if alphabet was "abc" and n was 5, the first non-empty words // from that alphabet would be: "a", "b", "c", "aa", "ab", "ac", ... // the result of wordsToSkip would be 1, and this would mean that if you skip // "a" from the list above, the next 5 words are prefix-free: // "b", "c", "aa", "ab", "ac". func wordsToSkip(n int, alphabetSize int) int { if n < 2 { n = 2 } return (n - 2) / (alphabetSize - 1) } // generateWord generates the word corresponding to the given index in the // breadth-first traversal of the prefix tree generated by the given alphabet. // // For example, given the alphabet "abc", the words would be generated in // the following order: // 1. "a" // 2. "b" // 3. "c" // 4. "aa" // 5. "ab" // ``` // "a", "b", "c", "aa", "ab", "ac", "ba", "bb", "bc", "ca", "cb", "cc", "aaa", ... // 1 2 3 4 5 6 7 8 9 10 11 12 13 ... // ``` func generateWord(alphabet string, i int) string { l := len(alphabet) hint := "" // this i-=1 is out of the loop only so that the case of i=0 results // in empty string, although indexing from 0 is not necessary // in this case. And also, we don't really care about the empty // string hint. i -= 1 for i >= 0 { mod := i % l char := string(alphabet[mod]) i /= l hint = char + hint i -= 1 } return hint } // wordToIndex converts a word to its corresponding index as it would appear in // the breadth-first traversal of the prefix tree generated by the given // alphabet. // // For example, given the alphabet "abc", the words would be generated in // the following order: // 1. "a" // 2. "b" // 3. "c" // 4. "aa" // 5. "ab" func wordToIndex(hint string, alphabet string) int { l := len(alphabet) mapCharToIndex := make(map[rune]int) for index, char := range alphabet { mapCharToIndex[char] = index } index := 0 for _, c := range hint { index = index*l + (mapCharToIndex[c] + 1) } return index } ``` #### **Other things to consider** 1. `hints/main.go` uses an index that is different from the one proposed here, the one proposed here is shifted by the number of skipped words. To retrieve the original index of a hint, you need to keep in memory how many were skipped or how many hints you had to generate ($N$). I believe this **won't** be an issue in [hints/main.go](https://github.com/kovidgoyal/kitty/blob/39ba5e271f4e3442bae349e71fdfc6c996358649/kittens/hints/main.go), that information seems to be available in the relevant scopes. 2. The behavior of the flag `--hints-offset`/`o.HintsOffset` would have to be redefined under the `prefix free` context. Would it mean to skip `min(o.HintsOffset, <number of words skipped to get a prefix-free set>)` or to skip `min(o.HintsOffset, <number of words skipped to get a prefix-free set>)` 3. If the size of the alphabet is 1, your set of prefix-free words can only have 1 word (or 0). 4. It would be simpler to force all hints to be of length $\lceil \log_A(N) \rceil$, but from the usability perspective it seems nice to use hints as short as possible whenever possible. If hints where forced to be of fix length, asking for 11 hints with alphabet "0123456789" would result in: ``` 00, 01, 02, 03, 04, 05, 06, 07, 08, 09, 10 ``` instead of ``` 1, 2, 3, 4, 5, 6, 7, 8, 9, 01 ```