Given a plot with broken paths, return the plot with all paths connected in the minimum number of changes.
This problem deals with graphs on the Cartesian plane. Every node has 8 possible edges, extending vertically, horizontally, or diagonally. Each direction is represented by a number 0-7 as follows:
0 7 1 6 X 2 5 3 4
In other terms:
0 = North 1 = Northeast 2 = East 3 = Southeast 4 = South 5 = Southwest 6 = West 7 = Northwest
A "broken path" occurs when one node has an edge that would reach another node, but the node it reaches toward does not have the corresponding path to reach it. For example, assume we have nodes A, B, C, and D laid out as:
If node A has the path 2 and all the other nodes have no paths, then there is a broken path between nodes A and B. This can be resolved in one of two ways:
- Removing path 2 from A
- Adding path 6 to B
In this case, it does not matter which way you choose to resolve the conflict, because either way results in 1 node being changed.
This first example can be illustrated as follows (
* represents nodes):
Original: *- * * * First method: * * * * Second method: *--* * *
If node A has path 3, B has path 4, C has path 2, and D has no paths, the paths from A to D, B to D, and C to D are all broken. This can be resolved in one of two ways:
- Removing path 3 from A, 4 from B, and 2 from C
- Adding paths 6, 7, and 0 to D
In this case, adding to node D is the optimal choice, because it results in 1 node being changed rather than 3. It does not matter how many paths get changed when you change a node; the optimal method is determined by how many nodes get changed.
This example can be illustrated as:
Original: * * \ | *- * Suboptimal method: * * * * Optimal method: * * \ | \| *--*
A 2D matrix of bytes, where each bit represents whether that path is present in the node. 7 represents the most significant bit, and 0 the least significant; in other words, the bits are given in the order
For example, the first scenario given above would be:
0b00000010 0b00000000 0b00000000 0b00000000
The second scenario given above would be:
0b00000100 0b00001000 0b00000010 0b00000000
You may take in these values as strings in the base of your choice, or integral types with the width of your choice (e.g. if your language supports a
char type, you may still use
int if you so choose), but include your choice in your answer.
You should either write a function that returns the corrected map or a program that prints it. Your output format should be the same as your input format.
These are just one example of correct output; valid output with the same number of values changed is also accepted.
[[0x04, 0x00], [0x00, 0x00]] -> [[0x04, 0x40], [0x00, 0x00]] [[0x08, 0x10], [0x04, 0x00]] -> [[0x08, 0x10], [0x04, 0xC1]] [[0x04, 0x10, 0x00], [[0x10, 0x10, 0x00], [0x01, 0x80, 0x10], -> [0x01, 0x09, 0x10], [0x00, 0x00, 0x81]] [0x00, 0x00, 0x81]] Or -> [[0x18, 0x10, 0x00], [0x01, 0x89, 0x10], [0x00, 0x00, 0x81]]
The first two test cases are illustrated above. The third test case can be illustrated as:
Original: *- * * | | \ * * * | \| * * * Solution: * * * | | | | * * * \ | \| * * * Another solution: * * * |\ | | \| * * * \ | \| * * *
This is code-golf, so the fewest bytes in each language wins.