Find the paths!

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!

• – Martin Ender Jul 13 '16 at 14:37
• Are built-ins allowed? – Ioannes Jul 13 '16 at 14:47
• @Joannes, yeah. – Daniel Jul 13 '16 at 14:51

JavaScript (ES6), 171161139137136133 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.querySelectorpre.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...

Python 3, 238237200199192 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

• 2 bytes off to beat the mathematica solution... – FlipTack Jan 4 '17 at 21:40
• @FlipTack Yeah. I don't think it's happening today, but I'm translating this to JS and it looks promising. – PurkkaKoodari Jan 4 '17 at 21:41

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) }


C(Ansi), 243233179 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.

• I guess I can save like 22 characters if I change this to a fixes map size - I'll change that if I find anything else I want to change – dj0wns Jul 15 '16 at 20:56

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.

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