4
\$\begingroup\$

Challenge

Given a plot with broken paths, return the plot with all paths connected in the minimum number of changes.

Explanation

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:

AB
CD

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:
 *  *
  \ |
   \|
 *--*

Input

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 76543210.

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 byte or char type, you may still use int if you so choose), but include your choice in your answer.

Output

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.

Test Cases

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 , so the fewest bytes in each language wins.

\$\endgroup\$
  • 2
    \$\begingroup\$ This challenge will be clearer if you display actual graphs. \$\endgroup\$ – DavidC May 15 '17 at 18:38
  • \$\begingroup\$ @DavidC Done! Let me know if there's anything else I can clarify, or if you need more test cases. \$\endgroup\$ – musicman523 May 16 '17 at 1:18
  • \$\begingroup\$ Here is a visualization program I made in Jelly for some odd reason. \$\endgroup\$ – fireflame241 May 16 '17 at 23:19
  • \$\begingroup\$ @fireflame241 this is cool! I drew these out by hand actually ahaha \$\endgroup\$ – musicman523 May 17 '17 at 3:59
1
\$\begingroup\$

Haskell, 655 bytes

u%w=u!!w
r=zip[-1,0,1,1,1,0,-1,-1][-1,-1,-1,0,1,1,1,0]
g _[]_= -1
g i(e:l)x|x==e=i|1>0=g(i+1)l x
l?x=g 0 l x
d _[]_ _=[]
d i(e:l)t v|i==t=v:l|1>0=e:d(i+1)l t v
c=d 0
f n|all(==0).concat.q$n=n|1>0=f$foldr(\p b->s b[k,m]p)n$k!m where
 h=length n-1
 e=mapM(\w->[0..w])[h,h]
 i!j=[[x,y]|[x,y]<-e,x>i-2&&x<i+2&&y>j-2&&y<j+2]
 q o=[[sum[1|[x,y]<-w!l,let
  u=(x-w,y-l)
  p=(w-x,l-y)in u/=p&&('1'==(o%w%l)%(r?u))/=('1'==(o%x%y)%(r?p))]|l<-[0..h]]|w<-[0..h]]
 v[x,y][a,b]|q n%x%y>q n%a%b=[x,y]|1>0=[a,b]
 [k,m]=foldr1 v e
 s w[x,y][a,b]|x==a&&y==b=w|'1'==w%x%y%(r?(a-x,b-y))=z '0'|'1'==w%a%b%(r?(x-a,y-b))=z '1'|1>0=w where z u=c w x$c(w%x)y$c(w%x%y)(r?(a-x,b-y))u

Man... 655 is a lot. I'm sure this isn't the best approach but since no one's answered this challenge yet I figured I would throw something at it.

Input is a list of lists of strings, viz. [[String]] or, equivalently, [[[Char]]]. The string format is "76543210", where the string is a '0' or a '1' in any given position based on whether or not the node points in that corresponding direction. This should conform with the spec:

7 represents the most significant bit, and 0 the least significant; in other words, the bits are given in the order 76543210.

But the examples below that seem to contradict it, instead doing something more like ?7654321, so I'm not sure.

Test suite:

main :: IO ()
main = print $ f
    [ ["00000100", "00010000", "00000000"]
    , ["00000001", "10000000", "00010000"]
    , ["00000000", "00000000", "10000001"]
    ]

(That's the last test case in the spec^)

\$\endgroup\$
  • \$\begingroup\$ "7 represents the most significant bit, and 0 the least significant; in other words, the bits are given in the order 76543210." What I meant by this is the following: Say you have a node with only path 0 present. Then its binary representation is 0b00000001. A node with paths 3 and 5 present would have the binary representation 0b00101000. The test cases are written in hex, but they follow this convention. Well done! (I would help you golf it more but I don't know Haskell.) \$\endgroup\$ – musicman523 May 18 '17 at 18:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.