I'd like to get output from input.
It should be pushed element like chasing tails and it couldn't be duplicated.
The rule is very simple.
Firstly, if there is the same element with input[0][1] in input[i][0],
you can put the first value of the element in a result.
The element is [1,5] so result becomes [[0,1]].
Now you can just repeat. The first element of [5,29] is the same element with [1,5][1] and result becomes [[0,1,5]]
I've been really frustrating for few weeks to solve this issue. Please help. Any comments would be appreciated.
input =
[
[ 0, 1 ], [ 0, 2 ], [ 0, 3 ],
[ 0, 4 ], [ 1, 5 ], [ 2, 6 ],
[ 3, 7 ], [ 4, 10 ], [ 4, 11 ],
[ 4, 12 ], [ 4, 13 ], [ 5, 29 ],
[ 6, 29 ], [ 7, 8 ], [ 8, 29 ],
[ 9, 29 ], [ 12, 18 ], [ 13, 19 ],
[ 17, 29 ], [ 18, 29 ], [ 19, 29 ],
[ 21, 29 ], [ 24, 29 ], [ 26, 29 ],
[ 28, 29 ]
]
output = [
[0,1,5,29],[0,2,6,29],[0,3,7,8,29],[0,4,10],[0,4,11],
[0,4,12,18,29],[0,4,13,19,29]
]
You can write solver as a generator with an input of t and a starting query of q. Other answers suggest reshaping your input or other functional techniques that iterate over the input multiple times. This simple imperative-style technique uses only one pass (per recursive call). The use of a generator allows you to find all solutions, but can be paused/stopped at any time, for any other reason -
function* solver (t, q) {
let atLeastOnce = false
for (const [parent, child] of t) {
if (parent == q) {
atLeastOnce = true
for (const sln of solver(t, child))
yield [parent, ...sln]
}
}
if (!atLeastOnce) {
yield [q]
}
}
const input =
[[0,1],[0,2],[0,3],[0,4],[1,5],[2,6],[3,7],[4,10],[4,11],[4,12],[4,13],[5,29],[6,29],[7,8],[8,29],[9,29],[12,18],[13,19],[17,29],[18,29],[19,29],[21,29],[24,29],[26,29],[28,29]]
for (const sln of solver(input, 0))
console.log(JSON.stringify(sln))
[0,1,5,29]
[0,2,6,29]
[0,3,7,8,29]
[0,4,10]
[0,4,11]
[0,4,12,18,29]
[0,4,13,19,29]
Generators are iterable and so you can collect all results in an array using Array.from -
const all = Array.from(solver(input, 0))
console.log(all)
[
[0,1,5,29],
[0,2,6,29],
[0,3,7,8,29],
[0,4,10],
[0,4,11],
[0,4,12,18,29],
[0,4,13,19,29],
]
Combine generators with an optimized input type for even better results.
Based on how I understood your output, what you want is kind of like a domino-chain. You seed the output with arrays start contain 0 in the first element, e.g. [0,1] and [0,2]..., and then you simply find the next array to join to the chain based on the last item in the array vs the first item in the next entry.
This process is recursive in nature, since you start with the seeds and have no idea how far/deep you will need to join. To break this down, we can do this:
input into seeds and non-seeds (nodes).The function should invoke itself recursively, and here's a quick logic:
/**
* @method
* @params arr The seed array (which will grow in length)
* @params nodes The collection of non-seeds
*/
function chain(arr, nodes) {
// We first find whatever nodes left that we can domino-chain to the current seed
const nextNodes = nodes.filter(node => node[0] === arr[arr.length - 1]);
// If nothing is to be found, return the array
if (!nextNodes.length) return [arr];
// Otherwise we go through all the next nodes and create a copy of the current seed
// And then append the next node to it
return nextNodes.map(nextNode => {
return chain([...arr, nextNode[1]], nodes);
}).flat();
}
See proof-of-concept below:
const input = [
[0, 1],
[0, 2],
[0, 3],
[0, 4],
[1, 5],
[2, 6],
[3, 7],
[4, 10],
[4, 11],
[4, 12],
[4, 13],
[5, 29],
[6, 29],
[7, 8],
[8, 29],
[9, 29],
[12, 18],
[13, 19],
[17, 29],
[18, 29],
[19, 29],
[21, 29],
[24, 29],
[26, 29],
[28, 29]
];
const seeds = input.filter(entry => entry[0] === 0);
const nodes = input.filter(entry => entry[0] !== 0);
function chain(arr, nodes) {
const nextNodes = nodes.filter(node => node[0] === arr[arr.length - 1]);
if (!nextNodes.length) return [arr];
return nextNodes.map(nextNode => {
return chain([...arr, nextNode[1]], nodes);
}).flat();
}
const output = seeds.map(seed => {
return chain(seed, nodes);
}).flat();
console.log(output);
I would split the problem in 2:
Here's an implementation of that approach:
const input =
[
[ 0, 1 ], [ 0, 2 ], [ 0, 3 ],
[ 0, 4 ], [ 1, 5 ], [ 2, 6 ],
[ 3, 7 ], [ 4, 10 ], [ 4, 11 ],
[ 4, 12 ], [ 4, 13 ], [ 5, 29 ],
[ 6, 29 ], [ 7, 8 ], [ 8, 29 ],
[ 9, 29 ], [ 12, 18 ], [ 13, 19 ],
[ 17, 29 ], [ 18, 29 ], [ 19, 29 ],
[ 21, 29 ], [ 24, 29 ], [ 26, 29 ],
[ 28, 29 ]
];
const nodes = {};
// Store all paths between nodes
for (const [ start, end ] of input) {
nodes[end] = nodes[end] || { id: end, children: [] };
nodes[start] = nodes[start] || { id: start, children: [] };
nodes[start].children.push(nodes[end]);
}
// Find all paths from 0
const getPaths = ({ children, id }) => children.length === 0
? [[ id ]]
: children.flatMap(
n => getPaths(n).map(p => [ id, ...p ])
)
console.log(getPaths(nodes[0]));