Search within an array and look for elements in a particular order

[Cinebeast (Torniron)]

I’m trying to implement a system where the player inputs a series of commands, and then these commands are examined and a particular sequence of commands are recognized.

I’ll just use colors as an example – say the player has 6 slots, and they put in green, green, blue, red, green, red. There’s a code the player can find, and it can be found anywhere in the commands, the only thing that matters is the order. Let’s say red, green, red. So, in the example I gave, the last three commands fit the bill, so the input is a success.

(Ideally multiple codes can be found, but I’m just using one in the example.)

I figured the best way to go about this was to create an array of enums, except the problem I’m running into is I don’t know how to check within an array and match it with another array. I want the player to be able to create an array through their inputs, and then it gets compared to a bunch of smaller arrays. (You can compare the whole thing, sure, but I mean specifically looking for a particular sequence in the array and matching that.)

If the color example doesn’t make sense, another way of thinking of it is like executing a combo in a fighting game, but from a limited string of inputs.

I’ve been searching all day for a solution to this and have yet to come up with anything. I’m not even sure how I would go about brute-forcing it.

Hopefully I expressed my problem well! Thanks for any help.

[jwatte]

If arrays are very long, you will want to use an algorithm like Knuth-Morris-Pratt or maybe Boyer-Moore. (Look them up – they’re in any undergrad algorithms textbook)

If at least one of the arrays is short (say, 30 elements or less) it’s good enough to just loop through, brute force style.

(Note: I wired this up for illustration but haven’t actually tested it. The general idea is to iterate through each index in the longer array and then iterate from there through the shorter array to verify that each element matches; non-matches immediately stops iterating at that spot; matches all the way to the end stops all iterations and returns success with the index at which the subsequence was found.)

(And now someone will find that there’s actually a built-in subsequence finding function of some sort, which would be much more efficient – here’s hoping )