Constrain sequence optimizer DFS to buffer size

[cxcorp]

No description provided.

[ThatsNinja]

I have a branch ready to PR for this change. It's based off of the branch in PR #6 though, so I'd like to settle that PR before opening this one.

[ThatsNinja]

(See PR #9)

[cxcorp]

Cool! I took a peek at your PR and it looks like it moves the result filtering to the sequence optimizer. Sorry for the lack of context in this issue - the possible optimization here was to backtrack the depth-first search in minimatch after a discovered sequence combination result's length is over the buffer size. That is, instead of filtering after discovering all the solutions, don't continue the recursion down the sequence combination subtrees at all.

I suspect that this could be done by filtering childSplits to remove any sequence combination whose result.length > bufferSize.

cyberpunk2077-hacking-solver/lib/sequence-optimizer.ts

Lines 54 to 57 in 1e72476

	const childSplits = match2(remainder, split.result, [
	remainder,
	...split.includes,
	]);

[cxcorp]

If it helps, here's a description I wrote to somebody about the general outlines of the solver's algorithm:

I start from the initial sequences and generate possible matching combinations one level down, meaning one sequence matched with another sequence in all matching positions (including just straight up concatenating them - important if RNG handed sequences with no overlap!). This produces a list of objects which contain the sequence being shifted, the sequence it's being matched to, the level of shift (how many indices to the left or right), the root sequences included in the result so far, and the actual output of the overlapped sequences.

Then, I iterate this list and recursively generate a tree from it using the same "possible matching combinations" function to match the other unused root sequences, with the remaining unused root sequences so far being passed down when recursing, and backtracking when either all root sequences have been exhausted for the subtree or the output sequence length has passed the length of the player's buffer.

Building a tree helps me with debugging since I can just generate a graph out of it with GraphViz (extra wide image warning): https://i.imgur.com/fKHC7bm.png
After I've gathered all of the possible overlapping sequences (including the root sequences alone here since it's possible that the player's buffer is so small there are no solutions for any overlapped sequences), I go through them ordering by amount of sequences matched, starting from the ones that match the most, and find solutions for them from the code matrix. If there are solutions for the overlapped sequences of this "amount of (root) sequences matched", I find the one that has the shortest route length (just sum of the euclidean distances) and return that. If not, I go through the overlapped sequences that match one fewer sequences. Etc.

I return the one with the shortest route length since I figured the pattern would be easier to recall after just quickly taking a look at it after alt+tab/steam overlay. This however seems to return pretty bunched up sequences sometimes, so I'm probably going to tune it later.

If you take a look at the linked graph, you can see how the leaf nodes of the tree have some very large lengths, and their amount increases...I don't know, polynomially? Compared to sequence count. So for a smaller buffer size with the sequences from the graph, we could easily cut out a majority of the combinations. Then again, even if there's a few thousand results, it's still fast enough to not notice.

[ThatsNinja]

I'm still puzzling over this one a bit, working through the code to see how everything hangs together. I have some tests written around this, but I'm not certain yet the best way to optimize.

I feel like I'm learning a lot, though. Thanks for all the info, and for letting me be a part of the project!