11
\$\begingroup\$

Background

An atomic bomb has exploded near the fencepost factory! Since fenceposts are essential for the survival of our civilization, we must rescue as many as possible. We are sending radiation-resistant robots to search the area, and it is your task to program their artificial vision.

Input

Your input is a rectangular grid of the characters |-#, representing two kinds of fencepost parts and rubble, given as a newline-delimited string. The fenceposts have been horribly maimed by the explosion, and some have even been fused together by the heat. We define a candidate fencepost to be either a horizontal pattern that starts and ends in | and has one or more -s between them (like |-| or |---| but not ||), or a vertical pattern that starts and ends in - and has one or more |s between them (essentially a horizontal candidate fencepost rotated 90 degrees). An actual fencepost is a candidate fencepost which does not share any of its parts with another candidate fencepost.

Output

Your output is the number of actual fenceposts in the input grid.

Example

Consider the input grid

|#|-|#|##
#||--|||#
###|#|--#
###-||--|
-#-|#-|#-
#---#-#-|
#-#-|#--|

There are 5 candidate fenceposts in this grid, but only 2 of them are actual fenceposts (shown in bold). Thus the correct output is 2.

Rules

You can write either a full program or a function. The lowest byte count wins, and standard loopholes are disallowed.

Additional Test cases

Input:

##--
||##
-#|-
|#|#

Output: 0 (0 candidate fenceposts)

Input:

-##|-##--
#|#-|#||-
--|-#|#||
##||||-##
||#|--|-|
-#|-#--|#
|####|#-#

Output: 0 (5 candidate fenceposts)

Input:

#|--|---|-|#
####|##--||-
-|-##||#|---
-#|#-|-#-|||
#|-##--###|-
---#-||-#-##
#|---|###|-#
-|---#-#|#|#
|#--|####-|-

Output: 4 (8 candidate fenceposts)

Input:

-|-||---##|#
---|######-#
####-##|#--|
|||##|#-||||
####-#-||-#|
---#--|#-#--
-|#-####-##-
#||-|-|-###|
|-##||-||-#-

Output: 5 (7 candidate fenceposts)

Input:

|#-|#|#-###|#-#
----#####|#----
|#--#-##-#|##-|
|#-|#-|--##||--
||#-#---##|||##
#|#-|||-#-#--||
--#|-||#|--|#|#
-#-|###||-#--#|
-#||-|#-##||##|
|--|-|||-##|-#|

Output: 4 (9 candidate fenceposts)

Input:

||-|-|-##-#-#-|#--#-
-##|-#|-#-##-|#|--|-
||#---###||-|#|##|-#
#||-#-#-|---|#||#|##
-#-###-##-|-#-|-#||#
##-#--#||-----||-|##
-|--#-#-#|---#-#|#-#
###|-|#-#|-|###|#-|#
#||#-#|--|-||#------
||##|-||#-|--#|#-#-#
|#-|-#-|-|--##-#|||#
-|#--#||##---##|-##-
#|-|-|-||-||#-#-|##-
|-#|##|-|#|#|--||#--

Output: 9 (30 candidate fenceposts)

\$\endgroup\$
  • \$\begingroup\$ So are the periods in the |--...--| pattern wildcards? Does that mean horizontal fences have to have a t least 5 hyphens? I'm a bit confused by the notation. \$\endgroup\$ – BMac May 21 '15 at 17:00
  • \$\begingroup\$ @BMac They are supposed to be an ellipsis, meaning that some hyphens are omitted. I agree that it's not the clearest notation. Let me think of something less ambiguous. \$\endgroup\$ – Zgarb May 21 '15 at 17:02
  • \$\begingroup\$ If we write a function, may it take one 2D-array argument as input, eg. [[-,|,-],[#,#,-],[-,-,|]]? \$\endgroup\$ – blutorange May 21 '15 at 18:59
  • \$\begingroup\$ @blutorange No, in this challenge it needs to be a single string. \$\endgroup\$ – Zgarb May 21 '15 at 19:07
3
\$\begingroup\$

Ruby, 266 268 bytes

To get this started. Makes use of the fact that variables point to objects (a 1-char string for each element of the 2D array) to eliminate overlapping candidates.

Eg. if you execute a="s";b=a, both a and b point to the same string. "test"=="test" returns true, but "test".equal?("test") returns false, because we have created two different String objects.

->d{c=->d,f,v,u{i=0
r=[]
d.map{|y|j=0
e=[]
y.map{|x|f[j]||=[]
f[j][i]=x
x==v ?e[1]?r<<e+[x]&&e=[x]:e[0]?e=[x]:e<<x :x==u&&e[0]?e<<x :e=[]
j+=1}
i+=1}
r}
y=c[d.split.map(&:chars),f=[],?|,?-]+c[f,[],?-,?|]
y.count{|x|y.all?{|q|x.equal?(q)||!(q+x).uniq!(&:object_id)}}}

Test cases on ideone.

\$\endgroup\$
  • 1
    \$\begingroup\$ you can use map instead of each \$\endgroup\$ – Cristian Lupascu May 22 '15 at 10:02
  • \$\begingroup\$ @w0lf thanks, applied. funny thing is, I should have known that... \$\endgroup\$ – blutorange May 22 '15 at 13:22

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.