Storing the last N keystrokes

Question

I'm at a bit of a loss with what to do here. I want to have certain sequences of keystrokes perform certain actions.

I basically need to store the last N keystrokes, and when a key is pressed, look for a sequence that matches the most recent keystrokes.

So say I have 2 sequences:

yes
no

and as I type, my keystroke history looks like this:

a
ab
abc
abcn
abcno

at which point it should recognize the sequence no and perform the appropriate action.

It will also need to work with sequences such as:

year
yell

and input such as:

yeayell

Key sequences are of a finite length, so old keystrokes can be discarded, using something like a circular buffer, in this case with an optimal size of 3.

My keystrokes are represented with the Keys enum.

What data structure(s) or algorithm(s) should I use that will let me store the last N keystrokes and find sequences at the end?

Answer 1

Here’s a proof-of-concept that will allow you to work with any collection of character sequences. I’m assuming that you’re only matching against characters (and not other keys such as Keys.Left).

// Initialize the collection of strings to be matched against here.
string[] stringSequences = new string[] { "yes", "no", "hello" };
int maxLength = stringSequences.Max(s => s.Length);

// The buffer to hold the sequence of the last N characters.
string buffer = "";

while (true)
{
    // Read the next character, and append it to the end of the buffer.
    ConsoleKeyInfo next = Console.ReadKey();
    buffer += next.KeyChar;

    // If the buffer has exceeded our maximum length, 
    // trim characters from its start.
    if (buffer.Length > maxLength)
        buffer = buffer.Substring(1);

    // Check whether the last n characters of the buffer
    // correspond to any of the sequences.
    string match = stringSequences.FirstOrDefault(s => buffer.EndsWith(s));
    if (match != null)
    {
        // Match! Perform any custom processing here.
        Console.WriteLine(Environment.NewLine + "Match: " + match);
    }
}

Edit: Adapted to work with keys.

I can’t easily test against Keys, so I’ve worked with ConsoleKey instead; however, it shouldn’t be too hard for you to translate the code.

// Initialize the collection of key sequences to be matched against here.
ConsoleKey[][] keysSequences = new ConsoleKey[][]
{ 
    new ConsoleKey[] { ConsoleKey.Y, ConsoleKey.E, ConsoleKey.S },
    new ConsoleKey[] { ConsoleKey.N, ConsoleKey.O },
    new ConsoleKey[] { ConsoleKey.H, ConsoleKey.E, ConsoleKey.L, ConsoleKey.L, ConsoleKey.O },
};
int maxLength = keysSequences.Max(ks => ks.Length);

// The buffer to hold the sequence of the last N keys.
List<ConsoleKey> buffer = new List<ConsoleKey>();

while (true)
{
    // Read the next key, and append it to the end of the buffer.
    ConsoleKeyInfo next = Console.ReadKey();
    buffer.Add(next.Key);

    // If the buffer has exceeded our maximum length, 
    // trim keys from its start.
    if (buffer.Count > maxLength)
        buffer.RemoveAt(0);

    // Check whether the last n keys of the buffer
    // correspond to any of the sequences.
    ConsoleKey[] match = keysSequences.FirstOrDefault(ks => 
        buffer.Skip(buffer.Count - ks.Length).SequenceEqual(ks));
    if (match != null)
    {
        // Match! Perform any custom processing here.
        Console.WriteLine(Environment.NewLine + "Match: " + 
            string.Concat(match.Select(k => k.ToString()).ToArray()));
    }
}

Answer 2

A simple state machine should work well.

It can reset on any input that is not following your rules.

enum States
{
 initial,
 y,
 e,
 s,
 n,
 o
}

if(char == 'n' && state == states.Initial)
{
  state = States.n;
}

if(char == 'o' && state == states.n)
{
  state = States.o;
}

... // etc for y, e, s - resetting to `Initial` where needed

... // Check for states o or s 

Answer 3

You can use a circular buffer:

char[] buf = new char[3];
int pos = 0;

// on key press
buf[pos] = key;

if (buf[pos] == 'o' && buf[(pos + 2) % 3] == 'n')
    No();

if (buf[pos] == 's' && buf[(pos + 2) % 3] == 'e' && buf[(pos + 1) % 3] == 'y')
    Yes();

pos = (pos + 1) % 3;

Answer 4

Fast and simple way for this is using Rolling hash

Answer 5

Not necessarily the optimal, but perhaps the easiest and reusable:

Create a CircularBuffer<T> generic container.

This takes one parameter in the constructor, N, the maximum number of elements in the buffer.

The class has an array of T with N elements and an index variable, i, holding the index of the last added value, initialize it to -1.

CircularBuffer has two methods, Add(T) and ToString().

The Add method increments i, wraps it around to 0 if i = N and stores the value at the appropriate position in the array. This should let you add values to the buffer while keeping only N of them in memory.

The ToString will output a string equivalent to the one stored in the buffer.

For N = 4, say you have this array:

                         a b c d

the indices are          0 1 2 3

the last added value is      ^

`ToString` should return 'dabc'

The wrapping logic here is an exercise for the user.

Every time a key is pressed add it to the circular buffer, call its ToString method and see if it contains the sequences you seek.