Traversing an entire object with a nested property recursively-CodePudding

I have a bunch of techniques (as in fighting moves) from which I'm looking to find all sequences. Each object has a property called 'results' which contains what can be done after this technique. It is possible, that a result contains another technique, which contains multiple results itself which may or may not contain another technique, and so on.

I'm currently using recursion to find these sequences, the function calls itself if the result contains a technique and returns a partial sequence if no techniques were found in the results.

findSequencesRecursively(technique: Technique, partialSequence: Technique[]): Technique[] | null {
    // In order to prevent a stack-overflow, sequences are capped at an arbitrary number,
    // as these are likely infinite cycles as opposed to actual sequences.
    if (partialSequence.length <= 25) {
      for (let result of technique.results) {
        if (result.technique) {
          const completeSequence = this.findSequencesRecursively(
            result.technique,
            [...partialSequence, result.technique]
          );
          if (completeSequence) return completeSequence;
        }
      }
      return partialSequence;
    } else return null;
  }

However, this always returns the first sequence it finds but not all sequences. Consider the following:

In the object t4 (Elbow-Strike) there are two results that contain a technique:

{ id: 't4r1', technique: t3, otherInfo: null };
{ id: 't4r4', technique: t2, otherInfo: 'bar' };

(technique t3 is named Backflip, t1 is named Knee-Action)

The algorithm (in its current state will always return t4 -> t3 and lookup its results and so on, but the sequence of t4 -> t2 -> t1 is never found, because the sequence of t4 -> t2 is never found.

How can I find all sequences from these objects?

Here's a StackBlitz recreating my problem, if you manage to solve it, you should also see Elbow-Strike -> Butterfly-Kick -> Knee-Action as output

CodePudding user response：

You're on the right paths, only few details are wrong. Specifically, you return early, without looking into 2nd and deeper branches.

Here is a sample that works as you expect:

public createSequences(): void {
  function findAllPaths(initialTechniques: Technique[]): SequenceData[] {
    const result: SequenceData[] = [];
    function walk(technique: Technique, currentPath: Technique[] = []): void {
      currentPath = [ ...currentPath, technique ];
      const continuations = technique.results.map(v => v.technique).filter(v => !!v);
      if (continuations.length) {
        continuations.forEach(t => walk(t, currentPath))
      } else {
        result.push({ sequentialTechniques: currentPath });
      }
    }
    initialTechniques.forEach(t => walk(t));
    return result;
  }
  
  this.sequences.push(...findAllPaths(this.data));
}

And the output it produces:

Knee-Action
Butterfly-Kick -> Knee-Action
Backflip
Elbow-Strike -> Backflip
Elbow-Strike -> Butterfly-Kick -> Knee-Action

And the StackBlitz project to see it in action.

CodePudding user response：

I'm going to make a few suggestions. I think you should use constructors to avoid building so much data by hand -

ngOnInit() {
  const t1 = new Technique('t111', 'Knee-Action', [
    new Snapshot('t1r1', null, null),
    new Snapshot('t1r2', null, 'foo'),
    new Snapshot('t1r3', null, null),
    new Snapshot('t1r4', null, 'bar'),
    new Snapshot('t1r5', null, 'bas'),
  ])
  const t2 = ...
  ...
}

This is a matter of updating your classes -

class Snapshot {
  id: string;
  technique?: Technique;
  otherInfo?: any;
  constructor(id: string, technique?: Technique, otherInfo?: any) {
    Object.assign(this, {id, technique, otherInfo})
  }
}

class Technique {
  id: string;
  name: string;
  results: Snapshot[];
  constructor(id: string, name: string, results: Snapshot[] = []) {
    Object.assign(this, {id, name, results})
  }
}

class SequenceData {
  sequentialTechniques: Technique[];
  constructor(sequentialTechniques: Technique[]) {
    Object.assign(this, {sequentialTechniques})
  }
}

Next, the findSequencesRecursively and createSequences functions do not need to be tangled up in your class context. Your App component can get right to the point -

export class AppComponent implements OnInit {
  public sequences: SequenceData[];
  ngOnInit() {
    const t1 = new Technique('t111', 'Knee-Action', [
      new Snapshot('t1r1', null, null),
      new Snapshot('t1r2', null, 'foo'),
      new Snapshot('t1r3', null, null),
      new Snapshot('t1r4', null, 'bar'),
      new Snapshot('t1r5', null, 'bas'),
    ])
    const t2 = new Technique('t211', 'Butterfly-Kick', [
      new Snapshot('t2r1', null, null),
      new Snapshot('t2r2', null, 'foo'),
      new Snapshot('t2r3', null, null),
      new Snapshot('t2r4', t1, 'bar'),
      new Snapshot('t2r5', null, 'bas'),
    ])
    const t3 = new Technique('t311', 'Backflip', [
      new Snapshot('t3r1', null, null),
      new Snapshot('t3r2', null, 'foo'),
      new Snapshot('t3r3', null, null),
      new Snapshot('t3r4', null, 'bar'),
      new Snapshot('t3r5', null, 'bas'),
    ])
    const t4 = new Technique('t411', 'Elbow-Strike', [
      new Snapshot('t4r1', t3, null),
      new Snapshot('t4r2', null, 'foo'),
      new Snapshot('t4r3', null, null),
      new Snapshot('t4r4', t2, 'bar'),
      new Snapshot('t4r5', null, 'bas'),
    ])
    const data = [t1, t2, t3, t4]
    this.sequences = Array.from(graph(data), path => new SequenceData(path))
  }
}

graph is an ordinary generator function that can be implemented outside of the component class -

function *graph(t): Generator<Technique[]> {
  switch (t?.constructor) {
    case Array:
      for (const x of t)
        yield *graph(x)
      break
    case Snapshot:
      if (t.technique)
        yield *graph(t.technique)
      break
    case Technique:
      for (const snapshot of t.results)
        for (const path of graph(snapshot))
          yield [ t, ...path ]
      yield [t]
      break
    default:
      throw Error(`unsupported type: ${t?.constructor}`)
  }
}

The final output is

Hello!

Knee-Action

Butterfly-Kick -> Knee-Action

Butterfly-Kick

Backflip

Elbow-Strike -> Backflip

Elbow-Strike -> Butterfly-Kick -> Knee-Action

Elbow-Strike -> Butterfly-Kick

Elbow-Strike

Verify the result on your stackblitz