I have a map with these arrays. What I want from here it choose the fewest item to get from 0-10. For example.

 {
      '11100171' => [ 0, 1, 2, 3 ],
      '11100060' => [ 1, 2, 3 ],
      '12100062' => [ 4 ],
      '12100012' => [ 5, 6, 7 ],
      '12100011' => [ 6, 7 ],
      '12100020' => [ 7 ],
      '12100121' => [ 7 ],
      '11100130' => [ 8, 9 ],
      '11100140' => [ 8, 9 ],
      '11100470' => [ 8, 9 ],
      '11400080' => [ 8, 9, 10 ]
    }

I would choose

• '11100171' => [ 0, 1, 2, 3 ],
• '12100062' => [ 4 ],
• '12100012' => [ 5, 6, 7 ],
• '11400080' => [ 8, 9, 10 ]

From here.

CodePudding user response：

This is a graph path finding problem. If we assume all arrays consist of consecutive numbers, we can interpret one such array as an edge in a graph that links the node identified by the first number with the node identified by that last number plus 1.

The goal is then to find the shortest path from start to end 1.

For that we can use a breadth-first search in that graph.

Here is an implementation of that idea in JavaScript:

function createAdjacencyList(data) {
    let adj = {};
    for (let key in data) {
        let arr = data[key];
        let start = arr[0];
        if (!adj[start]) adj[start] = [];
        adj[start].push(arr);
    }
    return adj;
}

function shortestPath(adj, start, end) { // BFS algo
    let frontier = [start];
    let comeFrom = {};
    while (frontier.length) {
        let nextFrontier = [];
        for (let node of frontier) {
            if (node === end   1) { // Unwind path
                let path = [];
                do {
                    arr = comeFrom[node];
                    path.push(arr);
                    node = arr[0];
                } while (node != start);
                return path.reverse();
            }
            if (adj[node]) {
                for (let arr of adj[node]) {
                    let neighbor = arr.at(-1)   1;
                    if (!comeFrom[neighbor]) {
                        comeFrom[neighbor] = arr;
                        nextFrontier.push(neighbor);
                    }
                }
            }
        }
        frontier = nextFrontier;
    }
}

// Example run
let data = {
  '11100171': [0, 1, 2, 3],
  '11100060': [1, 2, 3],
  '12100062': [4],
  'aaaaaaaa': [4, 5],
  '12100012': [5, 6, 7],
  '12100011': [6, 7],
  '12100020': [7],
  '12100121': [7],
  '11100130': [8, 9],
  '11100140': [8, 9],
  '11100470': [8, 9],
  '11400080': [8, 9, 10],
  'xxxxxxxx': [9, 10]
};

let adj = createAdjacencyList(data);
let path = shortestPath(adj, 0, 10);
for (let arr of path) {
    console.log(...arr);
}