Save last N keystrokes

Question

I lost a little what to do here. I want certain keystroke sequences to perform certain actions.

I basically need to save the last N keystrokes, and when the key is pressed, find the sequence that matches the last keystrokes.

So, I have 2 sequences:

yes no 

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

 a ab abc abcn abcno 

at this moment, he should recognize the sequence no and perform the corresponding action.

It should also work with sequences such as:

 year yell 

and input, for example:

 yeayell 

Key sequences are finite in 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 by the Keys enumeration.

What data structures or algorithm should I use, will it allow me to save the last N keystrokes and find the sequences at the end?

Answer 1

There is a proof of concept that will allow you to work with any set of character sequences. I assume that you are only matching 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); } } 

Change Adapted for working with keys.

I can't easily test against Keys , so Ive worked with ConsoleKey ; however, you do not need to translate the code too much.

 // 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 does not match 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

Quick and easy way to use rolling hash

Answer 5

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

Create a generic CircularBuffer<T> container.

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

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

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

The Add method increments i , wraps it to 0 if i = N and stores the value at the appropriate position in the array. This should allow you to add values ​​to the buffer, storing only N in memory.

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

For N = 4, let's say you have this array:

  abcd the indices are 0 1 2 3 the last added value is ^ `ToString` should return 'dabc' 

Wrapper logic is an exercise for the user.

Each time you press a key, add it to the ring buffer, call its ToString method, and see if it contains the sequences you are looking for.