Couverture rectangulaire minimale

23

Couvertures rectangulaires

Supposons que vous ayez une matrice de bits, par exemple la suivante.

1 1 0 0 0 1 1 0
1 1 1 1 0 1 1 1
0 1 1 1 0 1 1 1
1 1 0 1 1 1 1 0
1 1 0 1 1 1 0 1

Nous aimerions trouver une couverture rectangulaire pour cette matrice. Il s'agit d'un ensemble de sous-ensembles rectangulaires de la matrice qui ne contiennent aucun 0, mais qui contiennent ensemble tous les 1. Il n'est pas nécessaire que les sous-ensembles soient disjoints. Voici un exemple de couverture rectangulaire pour la matrice ci-dessus.

+----+         +----+
|1  1| 0  0  0 |1  1| 0
|    |         |    |
|  +-|-----+   |    |+-+
|1 |1| 1  1| 0 |1  1||1|
+----+     |   |    || |
   |       |   |    || |
 0 |1  1  1| 0 |1  1||1|
   +-------+   |    |+-+
+----+   +-----|-+  |
|1  1| 0 |1  1 |1| 1| 0
|    |   |     +----+
|    |   |       |   +-+
|1  1| 0 |1  1  1| 0 |1|
+----+   +-------+   +-+

Le nombre de rectangles dans cette couverture est de 7.

La tâche

Votre entrée est une matrice rectangulaire de bits, prise dans n'importe quel format raisonnable. Vous pouvez supposer qu'il contient au moins un 1. Votre sortie est le nombre minimum de rectangles dans un rectangle de couverture de la matrice.

Le nombre d'octets le plus bas gagne. Les règles de standard s'appliquent.

Cas de test

[[1]] -> 1
[[1,1]] -> 1
[[1],[1]] -> 1
[[1,0,1]] -> 2
[[1,0],[0,0]] -> 1
[[1,0],[0,1]] -> 2
[[1,0],[1,1]] -> 2
[[1,1,1],[1,0,1]] -> 3
[[0,1,0],[1,1,1],[0,1,0]] -> 2
[[1,1,1],[1,0,1],[1,1,1]] -> 4
[[1,1,0],[1,1,1],[0,1,1]] -> 2
[[1,0,1,0],[1,1,1,1],[1,0,1,0]] -> 3
[[1,1,1,0],[1,0,1,0],[1,1,1,1],[0,0,1,0]] -> 4
[[1,1,1,0],[1,0,1,0],[1,1,1,1],[0,0,1,1]] -> 5
[[1,1,1,0],[1,0,1,0],[1,1,1,1],[0,1,1,1]] -> 4
[[1,1,0,0],[1,1,1,0],[0,1,1,1],[0,0,1,1]] -> 3
[[0,1,0,0],[0,1,1,1],[1,1,1,0],[0,0,1,0]] -> 4
[[0,0,1,0,0],[0,1,1,1,0],[1,1,1,1,1],[0,1,1,1,0],[0,0,1,0,0]] -> 3
Zgarb
la source
Est-ce inspiré par la carte de Karnaugh ?
1
@ThePirateBay Plus par la complexité de la communication non déterministe .
Zgarb
@ThePirateBay pour une k-map tous les rectangles doivent avoir une puissance de deux dimensions.
Sparr
@Sparr. Oui je le sais. Je viens de demander si c'était peut-être l'inspiration pour ce défi.
1
Cas de test utile pour les approches gourmandes [[0,1,0,0],[0,1,1,1],[1,1,1,0],[0,0,1,0]]
:,

Réponses:

6

Python 2 , 318 315 271 octets

Mr.Xcoder, ovs et Jonathan Frech ont économisé beaucoup d'octets

p=range
def f(x,i=0,j=-1):z=len(x[0]);j+=1;i+=j/z;j%=z;return i<len(x)and(x[i][j]and-~min([f([[v,v[:j]+[2]*(r-j)+v[r:]][i<=y<=e]for y,v in enumerate(x)],i,j)for e in p(i,len(x))for r in p(j+1,z+1)if all(all(k[j:r])for k in x[i:e+1])]+[f(x,i,j)-1]*(x[i][j]>1))or f(x,i,j))

Essayez-le en ligne!

Halvard Hummel
la source
4

Gelée ,  25  24 octets

FJ‘ṁ×⁸ẆZ€Ẇ€ẎŒPFQP$$ÐṀL€Ṃ

Essayez-le en ligne! Une solution de complexité de golf typique, ne vous embêtez même pas avec des cas de test plus grands, ils expireront (l'ensemble de puissance de tous les rectangles possibles est inspecté *)

Comment?

Forme tous les rectangles possibles qui peuvent être créés. Prend le jeu de puissance de ces rectangles et les inspecte en ne gardant que les jeux qui ne contiennent pas de zéros et contiennent chacun de ceux au moins une fois.

Pour obtenir la partie "conserver les ensembles qui ne contiennent pas de zéros et contiennent chacun de ceux au moins une fois", le code contraint d'abord ceux-ci à un ensemble d'entiers distincts supérieurs à un, en laissant les zéros tels quels afin qu'ils deviennent " trouver les maxima du produit des valeurs uniques ".

FJ‘ṁ×⁸ẆZ€Ẇ€ẎŒPFQP$$ÐṀL€Ṃ - Link: list of lists of ones and zeros, M
F                        - flatten M into a single list
 J                       - range of length = [1,2,3,...,len(flattened(M))]
  ‘                      - increment       = [2,3,4,...,len(flattened(M))+1]
   ṁ                     - mould like M - reshapes it just like M again
     ⁸                   - chain's left argument, M
    ×                    - multiply (vectorises) - unique integers > 1 at M's 1s and 0s at M's 0s
      Ẇ                  - non-empty sublists - i.e. row selections
       Z€                - transpose €ach
         Ẇ€              - non-empty sublists of €ach - column selections of those
           Ẏ             - tighten - a flat list of all of the rectangles
            ŒP           - power-set - all possible selections of rectangles
                   ÐṀ    - filter keep those for which the following is maximal:
                  $      -   last two links as a monad:
              F          -     flatten
                 $       -     last two links as a monad:
               Q         -       de-duplicate
                P        -       product
                     L€  - length of €ach - # of rectangles used by each full-cover
                       Ṃ - minimum

* Pour une matrice n par m , c'est-à-dire voies (n, m) = 2 ^ (T (n) × T (m)) , donc ...
voies (3,2) = 2 ^ ((3 + 2 + 1) × (2 + 1)) = 2 ^ 18 = 262.144 (le lien TIO)
(3,3) = 2 ^ ((3 + 2 + 1) × (3 + 2 + 1)) = 2 ^ 36 = 68,719,476,736
voies (3,4) = 2 ^ ((3 + 2 + 1) × (4 + 3 + 2 + 1)) = 2 ^ 60 = 1,152,921,504,606,846,976
voies (5,5) = 2 ^ 225 ~ = 5.4e + 67 (le plus grand cas de test)
voies (8,5) = 2 ^ 540 ~ = 3,6e + 162 (l'exemple)

Jonathan Allan
la source
Fonctionnerait FJṁ×⁸ẆZ€Ẇ€ẎŒPFQS$$ÐṀL€Ṃpour -1? Pas le temps de tester rn.
Erik the Outgolfer
Non, car une couverture qui a négligé (uniquement) celle qui a été forcée 1aurait le même produit qu'une couverture valide (par exemple, tournez l'exemple de huit par cinq d'un demi-tour et elle reviendrait (en théorie) 6car elle négligerait de couvrir le haut cellule gauche et la considérer comme valide.)
Jonathan Allan
... encore plus facile - le cas de test [[1,0],[0,1]]reviendrait 1plutôt que 2.
Jonathan Allan
1

JavaScript, 434 octets

Code:

for(_='),d=...-1||(,Ad<=a,u[o][n]=d,    =0,(e,r,C,m))&&()=>.map((h((A,n,on<e|o<r|n>C|o>mf=u=>(q(s=(e>C[e,C]=[C,e]r>m[r,m]=[m,r]lk=1,k&=!!A)kl|=&1,=2k&lh=f=>uA,$ABf(B,$))))(($,Bae=r=C=m=,d=to-Bt=n$&n>$e   C=nn+1~ee   C=ttn-$t=oB&o>Br    m=oo+1~rr   m=tq+=sg=[],h((ca||g.push(c)gigb,j(p=1,q+=i<j&&s(b)q)';G=/[-]/.exec(_);)with(_.split(G))_=join(shift());eval(_)

Hexdump (en raison de caractères non imprimables):

66 6F 72 28 5F 3D 27 29 2C 13 13 64 3D 12 2E 2E 2E 11 2D 31 10 7C 7C 28 0F 2C 41 0F 64 3C 3D 0E 61 2C 0C 75 5B 6F 5D 5B 6E 5D 0B 3D 64 2C 09 3D 30 2C 08 28 65 2C 72 2C 43 2C 6D 07 29 29 13 06 26 26 28 05 29 3D 3E 04 2E 6D 61 70 28 28 03 68 28 28 41 2C 6E 2C 6F 04 02 02 6E 3C 65 7C 6F 3C 72 7C 6E 3E 43 7C 6F 3E 6D 0F 01 66 3D 75 3D 3E 28 71 08 28 73 3D 07 04 28 65 3E 43 05 5B 65 2C 43 5D 3D 5B 43 2C 65 5D 13 72 3E 6D 05 5B 72 2C 6D 5D 3D 5B 6D 2C 72 5D 13 6C 08 6B 3D 31 2C 01 6B 26 3D 21 21 41 29 13 6B 05 01 6C 7C 3D 0B 26 31 2C 0B 3D 32 06 6B 26 6C 13 68 3D 66 3D 3E 75 03 41 2C 24 04 41 03 0C 42 04 66 28 0C 42 2C 24 29 29 29 29 28 28 0C 24 2C 42 04 61 10 0F 65 3D 72 3D 43 3D 6D 3D 10 2C 64 3D 74 08 02 6F 2D 42 0F 74 3D 6E 0E 24 26 6E 3E 24 05 65 09 43 3D 6E 10 12 6E 2B 31 06 7E 65 0F 65 09 43 3D 74 12 74 08 02 6E 2D 24 0F 74 3D 6F 0E 42 26 6F 3E 42 05 72 09 6D 3D 6F 10 12 6F 2B 31 06 7E 72 0F 72 09 6D 3D 74 13 71 2B 3D 73 07 06 67 3D 5B 5D 2C 68 28 28 0C 11 63 04 61 10 7C 7C 67 2E 70 75 73 68 28 63 29 13 67 03 0C 69 04 67 03 62 2C 6A 04 28 70 3D 31 2C 71 2B 3D 69 3C 6A 26 26 73 28 11 0C 11 62 29 06 71 29 27 3B 47 3D 2F 5B 01 2D 13 5D 2F 2E 65 78 65 63 28 5F 29 3B 29 77 69 74 68 28 5F 2E 73 70 6C 69 74 28 47 29 29 5F 3D 6A 6F 69 6E 28 73 68 69 66 74 28 29 29 3B 65 76 61 6C 28 5F 29

Essayez-le en ligne!

Ce n'est pas très golfique, mais au moins ça marche très vite. Tous les cas de test peuvent être calculés en quelques millisecondes.

Non golfé

f=mat=>(
  iterate=f=>mat.map((A,x)=>A.map((a,y)=>f(a,y,x))),
  fill=(x1,y1,x2,y2)=>(
    x1>x2&&([x1,x2]=[x2,x1]),
    y1>y2&&([y1,y2]=[y2,y1]),
    isFilled=0,

    canBeFilled=1,
    iterate((A,X,Y)=>X<x1|Y<y1|X>x2|Y>y2||(
      canBeFilled&=!!A
    )),

    canBeFilled&&(
      iterate((A,X,Y)=>X<x1|Y<y1|X>x2|Y>y2||(
        isFilled|=mat[Y][X]&1,
        mat[Y][X]=2
      ))
    ),

    canBeFilled&isFilled
  ),

  rectangles=0,

  iterate((a,x,y)=>a-1||(
    x1=y1=x2=y2=-1,

    start=end=0,
    iterate((A,X,Y)=>Y-y||(
      end=X,
      A||(
        start<=x&X>x&&(x1=start,x2=X-1),
        start=X+1
      )
    )),
    ~x1||(x1=start,x2=end),

    start=end=0,
    iterate((A,X,Y)=>X-x||(
      end=Y,
      A||(
        start<=y&Y>y&&(y1=start,y2=Y-1),
        start=Y+1
      )
    )),
    ~y1||(y1=start,y2=end),

    rectangles+=fill(x1,y1,x2,y2)
  )),


  ones=[],
  iterate((a,...c)=>a-1||ones.push(c)),
  ones.map((a,i)=>ones.map((b,j)=>(
    M=1,
    rectangles+=i<j&&fill(...a,...b)
  ))),

  rectangles
)

Explication

Il utilise un algorithme similaire comme pour la résolution des cartes de Karnaugh. Premièrement, il essaie d'en trouver au moins un 1qui peut faire partie d'exactement un rectangle non extensible. Par non extensible, je veux dire que si nous l'étendons dans n'importe quelle direction (haut, gauche, droite, bas), elle en inclura au moins une 0(ou dépassera les limites de la matrice). Une fois 1trouvé, trouvez le plus grand rectangle qui l'inclut et marquez tous les 1s dans ce rectangle. Répétez jusqu'à ce qu'il n'y ait plus de s non marqués 1qui remplissent ces conditions.

Dans certains cas (comme dans le 16e cas de test), il reste des 1s après l'application de la première étape. Énumérer ensuite tous ces 1s et appliquer une sorte de recherche améliorée par force brute. Cette étape est rarement appliquée, et même dans ces cas, nous devons vérifier la force brute uniquement une ou deux combinaisons, donc cela devrait fonctionner très rapidement même pour les cas de test plus volumineux.


la source