Find the paths!

Question

You must write a program or function.

The input is a 'map' of numbers. You can choose to take the map as either a string with new line characters (\n) or a 2D array of strings.

All maps are 5 characters by 5 characters, and the characters are always either digits greater than 0 or spaces.

Here is an example of a map:

12 45
11233
  233
    1
2 899

Your task is to find the connected components in the map. A valid component is a series of at least three horizontally and/or vertically (not diagonally) connected identical digits (not spaces). You will then need to replace the characters of the valid connected components with xs and print or return that result.

So, the output for the above example would be:

x2 45
xx2xx
  2xx
    1
2 899

Here's another test case (thanks to Martin Ender):

Input:
2   3
    4
 1  5
111 6
11  7

Output:
2   3
    4
 x  5
xxx 6
xx  7

This is code golf so shortest code in bytes wins!

Answer 1

Python 3, 238 237 200 199 192 181 bytes

def f(a,i=0):F=lambda i,n,c:29>i>=0!=" "!=a[i]==c!=n and(a.__setitem__(i,n)or-~sum(F(i+j,n,c)for j in[-1,1,-6,6]));j=i+i//5;F(j,[a[j],"x"][2<F(j,1,a[j])],1);i>23or f(a,i+1);return a

Defines a function f(a) that takes the input as an array of characters and returns the same array modified. (Arrays of characters are acceptable as strings by default.)

Ungolfed with explanation

The modified code is recursive, but works the same.

# The main function; fills all continuous nonempty areas of size >= 3 in array
# with x's. Both modifies and returns array.
def findpaths(array):
    # Fills a continuous area of curr_char in array with new_char, starting
    # from index. Returns the number of cells affected.
    def floodfill(index, new_char, curr_char):
        if (0 <= index < 29                   # Check that the position is in bounds
                and (index + 1) % 6 != 0      # Don't fill newlines
                and array[index] != " "       # Don't fill empty cells
                and array[index] == curr_char # Don't fill over other characters
                and curr_char != new_char):   # Don't fill already filled-in cells
            array[index] = new_char # Fill current position
            return (1 # Add neighboring cells' results, plus 1 for this cell
                    + floodfill(index + 1, new_char, curr_char)  # Next char
                    + floodfill(index - 1, new_char, curr_char)  # Previous char
                    + floodfill(index + 6, new_char, curr_char)  # Next line
                    + floodfill(index - 6, new_char, curr_char)) # Previous line
        return 0 # Nothing was filled. The golfed solution returns False here,
                 # but that's coerced to 0 when adding.

    for i in range(25): # Loop through the 25 cells
        i += i // 5 # Accommodate for newlines in input
        curr_char = array[i] # Get the cell's contents
        # Fill the area from the cell with dummies
        area_size = floodfill(i, 1, curr_char)
        # Convert dummies to "x" if area was large enough, back to original otherwise
        fill_char = "x" if 2 < area_size else curr_char
        floodfill(i, fill_char, 1)
    return array

Answer 2

Ruby, 304 bytes

def b(s,i)
  @v=[]
  b2(s,i,s[i])
end
def b2(s,i,c)
  if(0...s.size)===i&&s[i]==c&&!@v[i]
    @v[i]=s[i]='x'
    [1,-1,6,-6].each{|j|b2(s,i+j,c)}
  end
  s
end
def f(s)
  z = s.dup
  ps = ->(i){b(z.dup,i).scan('x').size}
  (0...s.size).each{|i|b(s, i)if ![' ',"\n"].include?(s[i])&&ps.call(i)>2}
  s
end

example usage:

puts f(File.read("map.txt"))

the code reuses the 'blot' method to calculate the path length.

variables/methods:

• f(s): function to convert map string, returns new map with 'x's
• ps(i): path size from map index i (where x = i % 6, y = i / 6)
• s: input string, map lines separated by "\n"
• z: copy of input string
• b(s,i): 'blot' function: writes 'x' from map index i over paths
• @v: 'visited' array

Attempt at more detailed explanation:

make a copy of the input string, which we use for finding the length of the path from any given point in the map.

z = s.dup

define a 'ps' (path length) anonymous function (lambda) which takes the map index i as an argument. it returns the length of the path from that point. it does this by calling the 'b' (blot) method to insert x's on a copy of the original map and then counting the number of x's in the returned string.

  ps = ->(i){b(z.dup,i).scan('x').size}

the following part iterates over each character in the map (index i, character s[i]). it calls the 'b' (blot) function on map position i if the path length from position i is greater than 2, and if it's not a space or newline character.

  (0...s.size).each { |i|
     b(s, i) if ![' ',"\n"].include?(s[i]) && ps.call(i) > 2
  }

the b (blot) function takes the map string and an index as argument. it initialises @v (visited array) and calls the b2 helper function.

def b(s,i)
  @v=[]
  b2(s,i,s[i])
end

the b2 function takes the map string, a map position (i), and a character in the current path (c). it calls itself recursively to replace connected sections of digits with the 'x' character. it returns the input string (this is so the ps function can call scan() on the return value).

this if statement is checking that the map position (i) given is within the bounds of the string (0...s.size) and that the character at s[i] is the same as the starting character. also @v[i] is checked to avoid infinite recursion.

if(0...s.size) === i && s[i] == c && !@v[i]

this is the bit that replaces the character at index (i) with the 'x' character. it also marks that index as visited.

@v[i] = s[i] = 'x'

this is where b2 calls itself recursively searching for the path. i+1 is one character to the right, i-1 is one character to the left, i+6 is one row down (5 digits + 1 newline = 6 characters), i-6 is one row up.

[1,-1,6,-6].each { |j| b2(s, i+j, c) }

Answer 3

JavaScript (ES6), 171 161 139 137 136 133 132 bytes

f=(a,i=0)=>(F=i=>" "<c&&a[i]===c&&(a[i]=n,1+F(i-1)+F(i+1)+F(i-6)+F(i+6)),n=1,c=a[i],n=F(i)>2?"x":c,c=1,F(i),i>28?a:f(a,++i+(i%6>4)))

<!-- this HTML included just for testing --><textarea rows=5 cols=6 oninput="document.querySelector`pre`.innerHTML=this.value.length==29?f([...this.value]).join``:'invalid input'">12 45&#10;11233&#10;  233&#10;    1&#10;2 899</textarea><br/><pre></pre>

This is a translation of my Python answer. I/O as character arrays.

Too bad there's no efficient way of doing sum...

Answer 4

C(Ansi), 243 233 179 188 Bytes

Golfed:

#define O o[1][l]
x,n,l,L;r(o,l)char**o;{if(!(l>L|l<0|O<47|O!=x))n++,O++,r(o,l-1),r(o,l+6),r(o,l-6),r(o,l+1),n>2?O='x':O--;}main(g,o)char**o;{for(;(L=30)>l;l++)n=0,x=O,r(o,l);puts(o[1]);}

With Annotations:

#define O o[1][l]
x,n,l,L;      /*-------------------------- Globals*/
r(o,l)char**o;{ /*------------------------ Recursive Function*/
    if(!(l>L|l<0|O<47|O!=x)) /*----------- if this cell is valid(in
                                              range, is a number, is the 
                                              same as the parent number*/
    n++,     /*--------------------------- Increment count*/
    O++,     /*--------------------------- Increment character to mark*/
    r(o,l-1),  /*------------------------- Recurse left*/
    r(o,l+6),  /*------------------------- Recurse down*/
    r(o,l-6),  /*------------------------- Recurse down*/
    r(o,l+1),  /*------------------------- Recurse right*/
    n>2?O='x':O--;  /*---------------------If greater than 3, replace with x, else decrement character*/ 
}          /*----------------------------- Return*/

main(g,o)char**o;{ /*--------------------- Main*/
    for(;l<(L=30);l++){ /*---------------- For entire string and set L*/
        n=0;
        x=O;        /*-------------------- set counter to 0*/
        r(o,l); /*------------------------ Recurse*/
    } /*---------------------------------- End While*/
    puts(o[1]); /*------------------------ Print*/

}

Input:

Expects a newline at the beginning and end of the string.

Example Input:

./findPaths "
12 45
11233
  233
    1
2 899
"

Example Output:

x2 45
xx2xx
  2xx
    1
2 899

Update

Making the grid fixed allowed me to shave off nearly 60 bytes.

Answer 5

Mathematica, 180 bytes

(f=Flatten@#;p=Partition)[If[Tr[1^VertexComponent[r~Graph~Cases[##&@@p[#,2,1]&/@Join[g=p[r,5],g],{a_,b_}/;(A=f[[a]])==f[[b]]&&A!=" ":>a<->b],#]]<3,f[[#]],"x"]&/@(r=Range@25),5]&

Explanation:

(f=Flatten@#;p=Partition)[
  If[
    Tr[1^VertexComponent[
        r~Graph~Cases[
          ##&@@p[#,2,1]&/@Join[g=p[r,5],g],
          {a_,b_}/;(A=f[[a]])==f[[b]]&&A!=" ":>a<->b
        ],
        #
      ]]<3,
    f[[#]],
    "x"
  ]&/@(r=Range@25),
  5
]&

Pure function which accepts a 5x5 array.  is the 3-byte private-use character U+F3C7 representing the postfix transpose operator \[Transpose].

(f=Flatten@#;p=Partition): Flattens the input list and stores it in f. Sets p = Partition and returns it.

g=p[r,5]: The array {{1,2,3,4,5}, ..., {21,22,23,24,25}} (this is because r gets set to Range@25).

Join[g=p[r,5],g]: the list of rows and columns of g.

p[#,2,1]&: Pure function which partitions the list # into sublists of length 2 with overlap 1; i.e., the list of adjacent pairs in #.

##&@@p[#,2,1]&: Same as above except it returns a Sequence.

##&@@p[#,2,1]&/@Join[g=p[r,5],g]: Maps the previous function of the rows and columns of g to obtain a list of all of the adjacent entries in g. My gut says there is a shorter way to do this.

r~Graph~Cases[...]: Graph whose vertices are the integers 1, ..., 25 and whose edges are the edges between adjacent entries in g which have the same corresponding entries in the input array (other than " ")

{a_,b_}/;(A=f[[a]])==f[[b]]&&A!=" ": Pattern which matches {a,b} such that f[[a]] == f[[b]] (same value in the input array) and which are not equal to " ". Set A = f[[a]] to save 1 byte.

...:>a<->b: Replace every match with an undirected edge from a to b.

VertexComponent: Returns the connected component of the second argument (a vertex) in the first argument (a graph).

Tr[1^VertexComponent[...]]: The size of the connected component. Saves 1 byte from Length@VertexComponent[...].

If[Tr[...]<3,f[[#]],"x"]&: Pure function which takes an entry # in g. If the size of its connected component is less than 3, replace it with the corresponding entry in the input. Otherwise, replace it with "x".

(f=Flatten@#;p=Partition)[...,5]: And finally reshape the result to be a 5x5 array.

Answer 6

Clojure, 188 bytes

This is quite overwhelming :D

#(apply str(map-indexed(fn[i v](if((set(flatten(for[m(range 30)](let[n(for[p[-1 -6 1 6]:when(=(get %(+ m p)0)((set"123456789")(% m)))](+ m p))](if(< 1(count n))(conj n m)[])))))i)\x v))%))

Called like this (it takes a 1D vector of characters):

(def f #(apply str(...))

(print (str "\n" (f (vec (str "12 45\n"
                              "11233\n"
                              "  233\n"
                              "    1\n"
                              "2 899\n")))))

(print (str "\n" (f (vec (str "2   3\n"
                              "    4\n"
                              " 1  5\n"
                              "111 6\n"
                              "11  7\n")))))

Too lazy to ungolf it but basically for[m(range 30)] visits each index and for each index the inner let[n(for[p[-1 -6 1 6]...(+ m p))] makes a list of 0 to 4 elements which lists locations which had the same value (1 - 9) as the middle location. If more than 1 neighbour matches the mid piece it means that all these form a cluster, so those locations are added to the set used at (if((set(flatten(...)))i). If index i is found from the set then \x is emitted and the original value otherwise. That :when( ... ) is quite interesting...

Answer 7

Julia

256 bytes

too long...

readable version:

~A=(
  B=hcat(collect.(split(A,"\n"))...);C=copy(B);
  s\T=(
    L=[s];
    C[s...]='_';
    [(-1,0),(1,0),(0,-1),(0,1)].|>y->get(C,y.+s,'_')==T&&(L=vcat(L,(y.+s)\T));
    L
  );
  keys(C).|>x->isdigit(C[x])&&length((L=Tuple(x)\C[x];L))>2&&L.|>y->B[y...]='x';
  join(eachcol(B).|>join,"\n")
)

Attempt This Online!

• classical floodfill
• converts the input to char matrix (B), copy it (C, it is used for admin the visitedness), then performs floodfill from each (current) digits of C. \ returns the vector of connected component L and if it fulfills the reqs then modify B. At the end it builds a string from B.
• works for arbitrary, "rectangular" strings

194 bytes

input as char matrix (split+join are outsourced):

~B=(
  C=copy(B);
  s\T=(
    L=[s];
    C[s...]='_';
    [(-1,0),(1,0),(0,-1),(0,1)].|>y->get(C,y.+s,'_')==T&&(L=vcat(L,(y.+s)\T));
    L
  );
  keys(C).|>x->isdigit(C[x])&&length((L=Tuple(x)\C[x];L))>2&&L.|>y->B[y...]='x';
  B
)

Attempt This Online!