11
\$\begingroup\$

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

\$\endgroup\$
7
  • 1
    \$\begingroup\$ I think snake would have fit better here... :P \$\endgroup\$
    – math
    Jun 13 at 12:52
  • \$\begingroup\$ Was a bit sleepy when I wrote the question. \$\endgroup\$
    – Razetime
    Jun 13 at 13:36
  • 1
    \$\begingroup\$ " (2D array, string, boolean matrix, so on)" -- Is a list of the coordinates of the # characters an acceptable input method? \$\endgroup\$
    – Jonah
    Jun 13 at 16:50
  • \$\begingroup\$ 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. \$\endgroup\$
    – Jonah
    Jun 13 at 20:49
  • \$\begingroup\$ In fact, you could ask the same question about sheep with diagonal thickness? \$\endgroup\$
    – Jonah
    Jun 13 at 21:05
6
\$\begingroup\$

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)

Helper link

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

Main link

Ḷ                                           | [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
\$\endgroup\$

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.