loop threw an array of arrays in recursion (algorithm problem)

Question

I kinda want to create a feature which is most often known in factories. Kind of rotation system, where people swap their station, while others are on break.

via DragnDrop I create/add/update a Map and convert this map to an array of arrays like this:

let example1 = [
    ['John',    ['99', '1']],
    ['Jo',      ["1", "3"]],
    ["Alpha",   ["99", "4"]],
    ["Beta",    ["3", "2"]],
    ["Gamma",   ["2", "99"]],
    ["Delta",   ["4", "5"]],
    ["Maria",   ["5", "6"]],
    ["Epsilon", ["6", "99"]],
];

the first number is for the old Position, the second number is for the new position. The number 99 stands for beeing on break. the output for above example should be something like:

outputExample1 = [
    ["John", "1", "3", "2"], 
    ["Alpha", "4, "5", "6"] 
]

so every sequenze and recursion should start with a breaker (=number 99) and end with a breaker. in above example: after placing "john" at station one, it should "search" where the guy/ladie from station 1 is "now". in this example, he is on 3. now search again where the one from statin 3 is now. (=2) ... until the number is 99, which is the case at this example. thats why I started to filter the original array in 'activ'(<99) and 'breakers'(==99). I tried so many ways and fail continously ( while loops ends in an endless loop, outputs which are totally wrong), because i dont find a nice recursion.

Any hints are very preciated

PS: please consider that above array is "finished" to provide a good example and may not be completed on the fly (via drag and drop). Meaning: if I start to drag the sequenze is for sure not completed.

Edit: there will be for sure at least ONE '99'. if not no sequenze and no output. Also there are no duplicates on the 'new position' except 99er. (which are the starters anyway

"I tried so many ways and fail continously" - please edit your question to include them so that we can tell what went wrong — Bergi
– Bergi, Commented Oct 30, 2021 at 20:39
@Bergi: what you mean by edit your question. I didn´t provide any snippets because all my loops (either forEach, while, ....) end up miserable. ;-) — Block West
– Block West, Commented Oct 30, 2021 at 20:44
You say the sequences might not be complete, if you call the function while the user still drags'n'drops. What exactly are the restrictions on input that you can guarantee? Does every circle contain at least one 99? Are the sequences allowed to diverge, i.e. can there be duplicates in the positions? What is the expected output in these cases? — Bergi
– Bergi, Commented Oct 30, 2021 at 20:46
@Bergi my thought was/is using a Map with the name as key (which is unique) i can drag and drop easily and update the map "easily" . Therfore the "old" and "new" position gets stroed as values in an array . — Block West
– Block West, Commented Oct 30, 2021 at 20:48

Nina Scholz · Accepted Answer · 2021-10-31 07:48:55Z

2

You could take a sequential approach and visit all nodes in the order, you have. Then take a nested property for the most top items and keep the relation with the nodes. At the end return just top nodes.

If necessary take the entries of the result for an array of key/value pairs.

const
    data = [['John',    ['99', '1']], ['Jo',      ["1", "3"]], ["Alpha",   ["99", "4"]], ["Beta",    ["3", "2"]], ["Gamma",   ["2", "99"]], ["Delta",   ["4", "5"]], ["Maria",   ["5", "6"]], ["Epsilon", ["6", "99"]]],
    relations = data
        .reduce((r, [top, [from, to]]) => {
            if (to === '99') return r;
            if (from === '99') {
                r[to] = r.top[top] = [to];
            } else {
                r[from].push(to);
                r[to] = r[from];
            }
            return r;
        }, { top: {} })
        .top;

console.log(relations);

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

Version without reduce.

const
    data = [['John',    ['99', '1']], ['Jo',      ["1", "3"]], ["Alpha",   ["99", "4"]], ["Beta",    ["3", "2"]], ["Gamma",   ["2", "99"]], ["Delta",   ["4", "5"]], ["Maria",   ["5", "6"]], ["Epsilon", ["6", "99"]]],
    temp = {},
    relations = {};

for (const [top, [from, to]] of data) {
    if (to === '99') continue;
    if (from === '99') {
        temp[to] = relations[top] = [to];
    } else {
        temp[from].push(to);
        temp[to] = temp[from];
    }
}

console.log(relations);

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

edited Oct 31, 2021 at 7:48

answered Oct 30, 2021 at 21:01

Nina Scholz

388k26 gold badges367 silver badges417 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

Block West Over a year ago

Jesus Christ. This is extra ordinary. In the beginning (and still a bit) I had no idea why on earth the reduce-method should work. Tank you miss Nina-Scholz. it works absolutely fine. (except the fact that i have to start dragging with the 'breakers', otherwise the code breaks, but this is my 'fault' due to less information provided.) thank you again. sending 'coffee' to Düsseldorf ;)

Bergi Over a year ago

@BlockWest Tbh imo this would be much cleaner without .reduce.

Scott Sauyet Over a year ago

Note that this is sensitive to the order of the elements in the initial array. If they were shuffled, this would usually fail.

Scott Sauyet · Accepted Answer · 2021-11-01 20:07:47Z

The answer from Nina is fine, so long as your data is always sorted as in the example. If not, then this might help:

const cycleUntil = (schedule, x, [_, [f, t]] = schedule .find (([_, [f]]) => x == f)) => 
  f == 99 ? [] : [f, ... cycleUntil (schedule, t)]

const transform = (schedule) => 
  schedule .filter (([n, [f]]) => f == '99') 
           .map (([n, [f, t]]) => [n, ... cycleUntil (schedule, t)])

const example1 = [['John', ['99', '1']], ['Jo', ["1", "3"]], ["Alpha", ["99", "4"]], ["Beta", ["3", "2"]], ["Gamma", ["2", "99"]], ["Delta", ["4", "5"]], ["Maria", ["5", "6"]], ["Epsilon", ["6", "99"]] ]
console .log (transform (example1))

const example2 = [...example1, ["Zeta", ["99", "7"]], ["Eta", ["7", "10"]], ["Theta", ["8", "99"]], ["Iota", ["9", "8"]], ["Kappa", ["10", "9"]]]
console .log (transform (example2))

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

Here our transform function finds all elements that start with '99' and returns the name associated with them alongside the result of calling the cycleUntil function, which takes a station and the entire schedule and returns an array including that station, and, recursively, the element with that to station in its from position.

This will fail if the data is not constructed properly. It would almost certainly need some error-checking to ensure that the data is complete. But I'll leave that as an exercise.

Collectives™ on Stack Overflow

loop threw an array of arrays in recursion (algorithm problem)

2 Answers 2

3 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

3 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related