18
\$\begingroup\$

In a twist on finding a needle in a haystack, you need to find the largest contiguous haystack containing exactly one needle. Note that you cannot connect cells on diagonals, only left/right/up/down.

Input

An array (or a number of user input lines, your pick) of 'N' (needles) and '#' (hay) characters. Input only contains those two characters, and must contain at least one of each. For example:

N#N#N
#NN##
###N#
N##N#

Output

The size of the largest possible valid haystack. For our example, we would output 11 (there are 11 pieces of hay, and one needle).

   # 
#  ##
###N#
 ## #

This is , so shortest code wins. Standard loophole restrictions apply.

Test Cases

Input on left, possible maximal haystack on right

Case 1: 4

N##    ##
NN#     #
#NN     N
#N#     #

Case 2: 7

###   ###
N#N    # 
NNN    N 
###   ###

Case 3: 10

N###N    ### 
#N#N#   #N#  
#N#N#   # #  
N###N    ###

Case 4: 10

N#N#N        
#N#N#   # # #
##N##   ##N##
#N#N#   # # #
N#N#N        

Case 5: 1

NN#NN        
NNNNN         
#NNN#   #N    
NN#NN        
\$\endgroup\$
0
4
\$\begingroup\$

JavaScript (ES6), 152 bytes

s=>[...s].map((n,i)=>n>'M'&&(a=[...s],a[i]=r=1,a.map(_=>a.map((c,j)=>c=='#'&&a[j+1]|a[j-1]|a[j+l]|a[j-l]?a[j]=++r:0)),o=r>o?r:o),o=0,l=~s.search`
`)|o-1

Explanation

For each needle in the input, sets the needle to a part of the haystack (represented by setting it to a non-zero number) and continuously checks hay cells. If hay contains an adjacent part of the hay stack, also sets it part of the haystack and increments the size of the hay stack. Outputs the highest result.

var solution =

s=>
  [...s].map((n,i)=>n>'M'&&(          // for each needle in s at index i
      a=[...s],                       // a = array of each character in s
      a[i]=1,                         // set the starting needle to 1 (haystack)
      r=0,                            // r = haystack size starting from this needle
      a.map(_=>                       // loop to ensure the complete haystack is found
        a.map((c,j)=>                 // for each cell c at index j
          c=='#'&&                    // if the current cell is hay
          a[j+1]|a[j-1]|a[j+l]|a[j-l] // and any adjacent cells are part of the haystack
          ?a[j]=++r:0                 // add the current cell to the haystack, increment r
        )
      ),
      o=r>o?r:o                       // o = max of o and r
    ),
    o=0,                              // o = final output, initialise to 0
    l=~s.search`
`                                     // l = line length of s
  )
  |o                                  // return o
<textarea id="input" rows="6" cols="40">N#N#N
#N#N#
##N##
#N#N#
N#N#N</textarea><br />
<button onclick="result.textContent=solution(input.value)">Go</button>
<pre id="result"></pre>

\$\endgroup\$
4
\$\begingroup\$

Ruby, 207

->a{d=->b{0...b.size}
f=c=s=->y,x{(d[a]===y&&d[a[0]]===x&&!f[y][x]&&a[y][x]==c)?(c,f[y][x]=?#,1
1+s[y,x-1]+s[y,x+1]+s[y-1,x]+s[y+1,x]):0}
d[a].map{|y|d[y].map{|x|f,c=a.map{|b|b.map{p}},?N
s[y,x]}.max}.max-1}

This is an anonymous function that takes in the input as an array of arrays. Usage:

f=->a{......}

f["
N##
NN#
#NN
#N#
".strip.split.map(&:chars)] # => 4

The proc named s recursively finds the size of the haystack with needle at specific coordinates and is called on each needle in the haystack.

\$\endgroup\$
0

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.