Press n or j to go to the next uncovered block, b, p or k for the previous block.
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 | 1x 1x 1x 1x 1x 1x 1x 1x 1x 1x 1x 36x 36x 36x 36x 36x 36x 36x 54x 54x 12x 12x 12x 36x 36x 1x 1x 6x 6x 6x 6x 6x 6x 6x 6x 6x 6x 6x 6x 6x 6x 36x 36x 36x 36x 36x 54x 54x 54x 54x 36x 36x 36x 36x 54x 36x 36x 36x 6x 6x 6x 6x 6x 2x 1x 1x 4x 4x 1x 1x | import findPathChildToParent from "../utils/findPathChildToParent";
type Graph = {
[key: string]: {
[key: string]: number;
};
};
type CostTable = { [key: string]: number };
const findTheNextCheapestNode = (
cost: CostTable,
nodeProcessed: string[]
): string | undefined => {
const keys = Object.keys(cost);
const keysNotProcessed = keys.filter((key) => !nodeProcessed.includes(key));
return keysNotProcessed.reduce<string | undefined>((previous, current) => {
if (!previous) return current;
if (cost[previous] > cost[current]) {
return current;
}
return previous;
}, undefined);
};
export const solutionFull = (
graph: Graph,
start: string,
end: string
): { path: string[]; cost: number } => {
const childParent: { [key: string]: string } = {};
const costTable: { [key: string]: number } = {
[start]: 0,
};
const processedNode: string[] = [];
let currentNode: string | undefined = start;
// loop in currentNode
// find root cost
while (currentNode) {
processedNode.push(currentNode);
const children = graph[currentNode];
const rootCost = costTable[currentNode];
for (let child in children) {
const currentCost = costTable[child];
const newCost = children[child] + rootCost;
if (!currentCost || currentCost > newCost) {
// update costTable, childParent
costTable[child] = newCost;
childParent[child] = currentNode;
}
}
// update currentNode with cheapest node
currentNode = findTheNextCheapestNode(costTable, processedNode);
}
return {
path: findPathChildToParent(childParent, end),
cost: costTable[end],
};
};
const solution = (graph: Graph, start: string, end: string): number => {
return solutionFull(graph, start, end).cost;
};
export default solution;
|