# Count all my sheep

Sandbox

Given a boolean matrix representing my grass field, sheep length $$\n\$$ and wool thickness $$\k\$$, you will have to count my sheep.

A sheep is a single independent unbroken line of sheep length $$\n\$$ and thickness $$\k\$$.

#|##|# | #
#|  | #|#


are all valid sheep for $$\n=2,k=1.\$$

##|###|##  |  ##
##|###| ## | ##
##|   |  ##|##


are all valid sheep for $$\n=3,k=2.\$$

The diagonal sheep must be composed of horizontal lines of length k.

you are to count occurrences of valid sheep across a given grid.

Sheep will not intersect. You will be guaranteed that $$\n,k≥1\$$ and $$\n ≠ k.\$$

so for $$\n=2,k=1\$$:

##
#
##  #


should give 3. Sheep may be right next to each other, and smaller animals may be present in the grid. You should get the max number of sheep that can be recognized from the grid.

Since the grass becomes really short after the sheep graze, your code must be short as well ().

## I/O

You may take the field in any way you like (2D array, string, boolean matrix, so on)

Output must be a single integer ≥ 0.

## Test Cases

n=3, k=1

#      #
# ### #
#
#
#
#


Output: 3

n=1,k=4

####
####

#
#
####


Output: 3

n=3, k=1

#  #
##
###
#
#


Output: 2

n=2, k=5

###
###
###
###
###
###


Output: 1

• I think snake would have fit better here... :P Jun 13, 2021 at 12:52
• Was a bit sleepy when I wrote the question. Jun 13, 2021 at 13:36
• " (2D array, string, boolean matrix, so on)" -- Is a list of the coordinates of the # characters an acceptable input method? Jun 13, 2021 at 16:50
• Also is this a single unbroken line of n=3, thickness k=2? Here the "width" is in the vertical direction, which seems valid, but I wasn't sure as there weren't any test cases like this. Jun 13, 2021 at 20:49
• In fact, you could ask the same question about sheep with diagonal thickness? Jun 13, 2021 at 21:05

# Jelly, 66 55 bytes

ZQ€Ƒȧ)Ẏ+€4ḶB¤fƑƇƊṆ)Ạ
ḶŒp,U;Ä,_@\€ƊƲ+þẎfƑƇŒPŒcÇaẎQƑ\$ƲƇẈṀ


Try it online!

A pair of links that takes a left argument of [n,k] and a right argument of the 1-indexed coordinates of the cells containing the hashes. Returns an integer with the maximal number of sheep that can be found.

The intersecting diagonals as seen in the third example make this quite a bit harder. Removing this requirement saves 26 bytes.

## Explanation (outdated)

Takes a pair of sheep and checks whether they intersect

.ịⱮ                   | Last and first list member of each sheep
Ẏ                  | Tighten (merge outer lists)
œc3               | Combinations of length 3
Ʋ€     | For each combination:
_Ṫ             | - Subtract the last one from each of the first two
¥/         | - Reduce using the following:
U×           |   - Reverse x and y for left hand item and then multiply by right
>/       | - Reduce using greater than
s2   | Split into lists of length 2
I  | Increments (vectorises)
Ȧ | Any and all


Ḷ                                           | [0..n-1], [0..k-1]
Œp                                         | Cartesian product of these
Ʋ                              | Following as a monad f(z)
,U                                       | - Pair z with reversed pairs of z
;      Ɗ                               | - Concatenate to the following applied to z:
Ä                                     |   - Cumulative sum of each member of z
,_@\€                                |   - Paired with cumulative subtraction of each member of z with reversed arguments
+þ                            | Outer sum with right hand argument (grid of sheep coordinates)
Ẏ                           | Tighten -> list of all potential sheep
fƑƇ                        | Keep those where all coordinates are in the original list
ŒP                     | Power set
ƒ€“”   | Reduce each list starting with an empty list on the left:
ʋ?       | - If:
¥€             |   - For each current sheep in list:
,                |     - Pair with potential new sheep
Ç               |     - Call helper link to check if they intersect
o            |   - Or:
fƇ          |     - Filter any current sheep that contain an overlapping coordinate
Ẹ         |   - Any of the above
¹                    | - Then: identity function (i.e. don’t append new sheep)
ṭ@                  | - Else: tag new sheep to end of list
Ẉ  | Lengths of lists of sheep
Ṁ | Max


# Python3, 629 bytes:

lambda b,n,k:max(map(len,F({r for x,R in E(b)for y,_ in E(R)for r in S(b,x,y,n,k)})))
E=enumerate
def S(b,x,y,n,k):
q=[(x,y,[],r,w,h)for r,w,h in[(0,n,k),(0,k,n),(1,k,n),(-1,k,n)]]
while q:
x,y,C,r,w,h=q.pop(0)
if h==0:yield tuple(C);continue
if x<len(b)and 0<=y and y+w<=len(b)and all(b[x][y:y+w]):q+=[(x+1,y+r,C+[(x,y+i)for i in range(w)],r,w,h-1)]
O=lambda x,y:any(t==Tand t>Tfor t in x for T in y)and any(t==Tand t>Tfor t in x for T in y)
def F(s,c=[]):
if[]==(o:=[i for i in s if all({*j}&{*i}==set()for j in c)and 0==any(O(j,i)for j in c)]):yield c
for i in o:yield from F(s-{i},c+[i])


Try it online!

• 526 byte (footer stripped) Sep 5, 2022 at 19:14