0

I have checked Check if an array is subset of another array and related questions but they aren't quite the same. They wanted to see if all elements of a sub array are within some other array (independent of order), which you can tell by the answers is fairly straightforward. I am not sure if now the following question is as straightforward.

I am trying to write JavaScript compiler testing for a compiler written in JS (it doesn't compile JS, in my situation now it just has to do with testing the final memory layout is what is expected). So I am trying to write a Jest matcher. The matcher part is easy but the algorithm for matching the grid of elements doesn't seem easy and is making my head spin.

Basically, this is sort of like an image matching problem. How do you find if a square/rectangle of pixels is exactly within another image? And do so somewhat efficiently?

In the same way, I would like to find is a sequence of bytes in a "test" array is within a larger array, in the exact order as defined.

So for example:

var given = [
  1, 3, 5, 7, 9, 11, 13, 15, 17, 19,
  21, 23, 25, 27, 29, 31, 33, 35, 37,
  39, 41, 43, 45, 47, ...
]

var expectedSubset = [
  13, 15, 17, 19, 21, 23, 25, 27
]

expect(given).toContainSequence(expectedSubset)

Any ideas how to do this? Maybe it's simple, but it seems complex.

Where it seems to get tricky is here:

var given = [
  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 5, 8, 0, 0, 0, 0, 0, 0,
  0, 5, 8, 11, 14, 0, 0, 0, 0, 0, 0,
  ...
]

var expected = [ 0, 0, 0, 0, 5, 8, 11 ]
Lance
  • 75,200
  • 93
  • 289
  • 503
  • While all the flavor text may be interesting, the "in the exact order as defined" is the important part. – ASDFGerte Dec 01 '19 at 14:47
  • You’ve mentioned squares/rectangles in images, but your example looks more like a string search (one-dimensional). Which is it? – Ry- Dec 01 '19 at 14:47
  • My example is matching an array/sequence of bytes. – Lance Dec 01 '19 at 14:47
  • 2
    If you care about order, it's called [*subsequence*](https://en.wikipedia.org/wiki/Subsequence) (in contrast to test for subset). If you care abut order and need the matched elements to be consecutive, it's called a [*substring*](https://en.wikipedia.org/wiki/Substring). Given your examples you seem to be looking for the latter, which has [well-known algorithms](https://en.wikipedia.org/wiki/String_searching_algorithm). – Bergi Dec 01 '19 at 14:47
  • 2
    Use some appropriate [string search](https://en.wikipedia.org/wiki/String-searching_algorithm), then. There are a few implementations on npm, and you can convert to a string to use `String.prototype.indexOf`/`includes` in a pinch. – Ry- Dec 01 '19 at 14:49
  • I don't want to convert the array of bytes to a string, I would like to keep it an array of bytes. For example, [this](https://github.com/ospatil/string-search/blob/master/lib/index.js) is of no use in trying to learn the algorithm. – Lance Dec 01 '19 at 14:50
  • String search algorithms work on arbitrary elements, not literally just whatever the implementation language calls a string. – Ry- Dec 01 '19 at 14:52
  • @Ry- I am searching npm and not finding anything but stuff using regexes and built-in methods... Maybe [this](https://github.com/trekhleb/javascript-algorithms/blob/master/src/algorithms/string/knuth-morris-pratt/knuthMorrisPratt.js)? Or perhaps [this](https://gist.github.com/jhermsmeier/2138865)??? – Lance Dec 01 '19 at 14:53
  • Example keywords: “kmp”, “knuth morris”. See the Wikipedia pages for the tradeoffs. (I don’t make any guarantees about the safety of npm packages that you find this way, of course.) – Ry- Dec 01 '19 at 14:58

0 Answers0