List recursion and string building-CodePudding

Intuitively I feel like I have a problem that can be solved with recursion, however, after staring at this for several days I cannot find the first thread to pull and start the process of tackling it.

I'd love any help you can offer both with how to approach this problem and break it down for solving it and for solving itself. I'm currently attempting to solve this in javascript.

Given a list of objects like this:

[
    {position: 1, jump: 1, letter: "b"},
    {position: 1, jump: 2, letter: "b"},
    {position: 1, jump: 1, letter: "c"},
    {position: 2, jump: 2, letter: "e"},
    {position: 2, jump: 1, letter: "e"},
    {position: 3, jump: 1, letter: "a"},
    {position: 4, jump: 1, letter: "t"},
    {position: 4, jump: 1, letter: "d"},
]

I want to generate a list of possible strings like this:

bet
bed
beat
bead
bat
bad
cet
ced
ceat
cead

I want to recursively? work through the list and at each object I want to take the letter, then jump from that position the number of spaces indicated by the jump value, take that letter and add it to the string for every possible path through the list of objects.

So for the first string, we would start at the first object {position: 1, jump: 1, letter "b"} and I would grab the letter "b" and jump from position 1 to position 2 as the jump indicated is only 1. Then I would grab the letter of the first object that was indicated at that new position and make its jump till I finished the list. But after I finish the first word I go back through unfinished positions so in this case after I had successfully created "bet" I would then return to position 4 to grab the other possibility, and then I would go back to position 2 and start working on the additional possibilities the next object allows. Eventually, I would create the list shown.

I can work through the list and find words with no problem, but I can't seem to work out a method that manages the necessity to look at multiple options at any one position. So for the case of the first two strings "bet" and "bed", when I've reached the end of the list would it be useful to capture a list of all objects at a position? Perhaps it would be better to start the whole process by separating each of the objects into lists based on their positions and then loop through each list and evaluate it against the criteria of the correct jumps?

Any help would be appreciated.

EDIT:

I don't know how to simplify this further, but perhaps a different second explanation would help?

I have a list of objects with three properties. The first property describes a position numerically (position), the second property describes a step to take to the next position numerically (jump) and the third property is a single character string (letter). I want to run through this list as many times as it takes to generate all possible multi-character strings based on their position and jumps.

So to generate the first string I would iterate through the list hit the first object {position: 1, jump: 1, letter: "b"} and pull out the letter "b". It lets me know I am at position 1 and that the next step is one jump away so position 1 plus jump 1 equals position 2. I go to the first object described as position 2 in this case it is the fourth object {position: 2, jump: 2, letter: "e"} I add the "e" to the "b" making "be" and note that the next jump is two, so currently at position 2 I jump 2 to position 4. At the first object described as position 4 the 7th object listed in my example {position: 4, jump: 1, letter: "t"} I grab the "t" and add it to "be" to get "bet" and then the next jump goes off the end of the list so this entire iteration is complete.

I then want to repeat this process for every described combination in the list of objects.

CodePudding user response：

A simple recursive version might look like this:

const words = (input, position = 1, matches = input .filter (x => x .position == position)) =>
  matches .length
    ? matches .flatMap (
        ({jump, letter}) => words (input, position   jump) .map (p => letter   p)
      )
    : ['']

const data = [{position: 1, jump: 1, letter: "b"}, {position: 1, jump: 2, letter: "b"}, {position: 1, jump: 1, letter: "c"}, {position: 2, jump: 2, letter: "e"}, {position: 2, jump: 1, letter: "e"}, {position: 3, jump: 1, letter: "a"}, {position: 4, jump: 1, letter: "t"}, {position: 4, jump: 1, letter: "d"}]

console .log (words (data))

.as-console-wrapper {max-height: 100% !important; top: 0}

This works by first finding all the values that match our position. If there are none, we return an array containing only the empty string. If not, then for each one, we add position and jump and recur, combining its results with the current letter.

If there are inefficiencies in this because of having to search for matches, then we could restructure the input data to look like this:

{
  1: [{jump: 1, letter: "b"}, {jump: 2, letter: "b"}, {jump: 1, letter: "c"}], 
  2: [{jump: 2, letter: "e"}, {jump: 1, letter: "e"}],
  3: [{jump: 1, letter: "a"}], 
  4: [{jump: 1, letter: "t"}, {jump: 1, letter: "d"}]
}

at which point finding the next positions is just a lookup. This variant would do that:

const restructure = (data) => data .reduce (
  (a, {position, jump, letter}) => 
    ((a [position] = a [position] || []), (a [position] .push({jump, letter})), a), 
  {}
)

const words = (input, position = 1) => 
  position in input
    ? input [position] .flatMap (
        ({jump, letter}) => words (input, position   jump) .map (p => letter   p)
      )
    : ['']

const data = [{position: 1, jump: 1, letter: "b"}, {position: 1, jump: 2, letter: "b"}, {position: 1, jump: 1, letter: "c"}, {position: 2, jump: 2, letter: "e"}, {position: 2, jump: 1, letter: "e"}, {position: 3, jump: 1, letter: "a"}, {position: 4, jump: 1, letter: "t"}, {position: 4, jump: 1, letter: "d"}]

console .log (words (restructure (data)))

.as-console-wrapper {max-height: 100% !important; top: 0}

CodePudding user response：

You can use a recursive generator function:

var positions = [
    {position: 1, jump: 1, letter: "b"},
    {position: 1, jump: 2, letter: "b"},
    {position: 1, jump: 1, letter: "c"},
    {position: 2, jump: 2, letter: "e"},
    {position: 2, jump: 1, letter: "e"},
    {position: 3, jump: 1, letter: "a"},
    {position: 4, jump: 1, letter: "t"},
    {position: 4, jump: 1, letter: "d"},
]
function* build(p, s){
    var c = positions.filter(x => x.position === p);
    if (c.length === 0){
        yield s
    } 
    else{
        for (var i of c){
            yield* build(i.position i.jump, s i.letter)
        }
    }
}
console.log(Array.from(build(1, '')))