Open kklimonda-cl opened 1 month ago
longestCommonSubsequence
is not the right name, as this is really a variation on LongestCommonSubstring algorithm, but instead of strings we want to handle slices of Movable types.
It's also pretty inefficient when generating the longest common sequence as we constantly reallocate results, and we should be reusing that array (after preallocation).
Added an optimization pass:
To simplify the move actions generation, algorithm doesn't check if any previous move made current one reduntant. So for some sequences it can generate extra movements.
For example, with the existing list '(A B C D E)
and given entries list '(C B)
with position PositionBefore{Directly: false, Pivot: D}
the following expected list is generated '(A C B D E)
and we generate two movements '((C before D)(B after C))
but the optimization can be applied to transform it into just '((B after C))
.
This is done in a separate step, where we take existing list and simulate all moves one by one, verifying which moves can be skipped.
Description
This new algorithm implements generation of move actions by calculating steps between existing and expected sequences: