9

Cette question est similaire à Biggest Square dans une grille .

Défi

Étant donné une matrice de 1et 0dans un format de chaîne "xxxx,xxxxx,xxxx,xx.."ou un format de tableau ["xxxx","xxxx","xxxx",...], vous allez créer une fonction qui détermine la zone de la plus grande sous-matrice carrée qui contient tout 1.

Une sous-matrice carrée est une largeur et une hauteur égales, et votre fonction doit renvoyer la zone de la plus grande sous-matrice qui contient uniquement 1.

Par exemple:

Étant donné "10100,10111,11111,10010", cela ressemble à la matrice suivante:

1 0 1 0 0

1 0 1 1 1

1 1 1 1 1

1 0 0 1 0

Vous pouvez voir les caractères gras 1créer la plus grande sous-matrice carrée de taille 2x2, donc votre programme doit retourner la zone qui est 4.

Règles

La sous-matrice doit avoir une largeur et une hauteur égales
La sous-matrice doit contenir uniquement des valeurs 1
Votre fonction doit renvoyer la zone de la plus grande sous-matrice
Si aucune sous-matrice n'est trouvée, retournez 1
Vous pouvez calculer l'aire de la sous-matrice en comptant le nombre de 1dans la sous-matrice

Cas de test

Entrée: "10100,10111,11111,10010" Sortie: 4

Entrée: "0111,1111,1111,1111" Sortie: 9

Sortie d' entrée "0111,1101,0111" : 1

C'est le code-golf , donc la réponse la plus courte en octets gagne.

code-golf matrix Luis felipe De jesus Munoz
la source

3

Pourquoi le format de chaîne?

Stewie Griffin

3

Pouvons-nous prendre l'entrée comme une matrice binaire (numérique)?

Stewie Griffin

5

Pour [0] toujours nécessaire pour sortir 1?

l4m2

6

Attendez, pourquoi renvoyer 1 lorsqu'aucune sous-matrice tout-1 n'est trouvée, 0 n'aurait-il pas beaucoup plus de sens? (Sinon, c'est simplement un cas spécial à gérer)

Jonathan Allan

2

Dans l'état actuel des choses, je pense que les deux répondeurs ne verraient pas d'inconvénient à ce que vous changiez les spécifications et je recommande fortement de le faire car il n'y a pas de raison de renvoyer 1 et cela ne rend pas les soumissions plus intéressantes.

2018

2

Gelée , 18 octets

_{+2 pour gérer la sortie actuelle de la sous-liste no-all-1}

ẆZṡ¥"L€$ẎȦÐfL€Ṁ²»1

Essayez-le en ligne! Ou consultez la suite de tests

Comment?

ẆZṡ¥"L€$ẎȦÐfL€Ṁ²»1 - Link: list of lists of 1s and 0s
Ẇ                  - all slices (lists of "rows") call these S = [s1,s2,...]
       $           - last two links as a monad:
     L€            -   length of each (number of rows in each slice) call these X = [x1, x2, ...]
    "              -   zip with (i.e. [f(s1,x1),f(s2,x2),...]):
   ¥               -     last two links as a dyad:
 Z                 -       transpose (get the columns of the current slice)
  ṡ                -       all slices of length xi (i.e. squares of he slice)
        Ẏ          - tighten (to get a list of the square sub-matrices)
          Ðf       - filter keep if:
         Ȧ         -   any & all (all non-zero when flattened?)
            L€     - length of €ach (the side length)
              Ṁ    - maximum
               ²   - square (the maximal area)
                »1 - maximum of that and 1 (to coerce a 0 found area to 1)

Jonathan Allan
la source

Impressionnant. Pouvez-vous ajouter quelques explications?

Luis felipe De jesus Munoz

Je le ferai, j'essaie de penser à un plus court en premier ...

Jonathan Allan

@ Mr.Xcoder J'ai mis à jour pour gérer l'exigence pour l'instant

Jonathan Allan

5

Haskell , 113 121 118 117 117 octets

x!s=[0..length x-s]
t#d=take t.drop d
f x=last$1:[s*s|s<-min(x!0)$x!!0!0,i<-x!!0!s,j<-x!s,all(>'0')$s#i=<<(s#j)x,s>0]

Essayez-le en ligne!

_{-3 octets grâce à Laikoni !}

_{-1 octet merci à Lynn !}

_{+8 octets pour l'exigence ridicule de renvoyer 1 pour aucune sous-matrice tout-1.}

Explication / Non golfé

La fonction d'assistance suivante crée simplement des décalages pour xpermettre de les décrémenter de s:

x!s=[0..length x-s]

x#ysupprimera des yéléments d'une liste, puis prendra x:

t#d=take t.drop d

La fonction fparcourt toutes les tailles possibles pour les sous-matrices dans l'ordre, génère chaque sous-matrice de la taille correspondante, teste si elle ne contient que '1's et stocke la taille. Ainsi, la solution sera la dernière entrée de la liste:

--          v prepend a 1 for no all-1s submatrices
f x= last $ 1 : [ s*s
                -- all possible sizes are given by the minimum side-length
                | s <- min(x!0)$x!!0!0
                -- the horizontal offsets are [0..length(x!!0) - s]
                , i <- x!!0!s
                -- the vertical offsets are [0..length x - s]
                , j <- x!s
                -- test whether all are '1's
                , all(>'0') $
                -- from each row: drop first i elements and take s (concatenates them to a single string)
                              s#i =<<
                -- drop the first j rows and take s from the remaining
                                      (s#j) x
                -- exclude size 0...........................................
                , s>0
                ]

ბიმო
la source

4

Haskell , 99 97 octets

b s@((_:_):_)=maximum$sum[length s^2|s==('1'<$s<$s)]:map b[init s,tail s,init<$>s,tail<$>s]
b _=1

Vérifie si l'entrée est une matrice carrée de seulement avec s==('1'<$s<$s), si elle l'est, la réponse est la longueur ^ 2, sinon 0. Ensuite, coupe récursivement la première / dernière colonne / ligne et prend la valeur maximale qu'elle trouve n'importe où.

Essayez-le en ligne!

Angs
la source

3

K (ngn / k) , 33 28 octets

{*/2#+/|/',/'{0&':'0&':x}\x}

Essayez-le en ligne!

ngn
la source

Je n'ai jamais su que tu avais une version K!

Zacharý

3

J , 33 27 octets

-6 octets grâce à FrownyFrog!

[:>./@,,~@#\(#**/)@,;._3"$]

Essayez-le en ligne!

Explication:

Je vais utiliser le premier cas de test dans mon explication:

    ] a =. 3 5$1 0 1 0 0 1 0 1 1 1 1 1 1 1 1 1 0 0 1 0
1 0 1 0 0
1 0 1 1 1
1 1 1 1 1

Je génère toutes les sous-matrices carrées possibles avec une taille de 1 au nombre de lignes de l'entrée.

,~@#\crée une liste de paires pour les tailles des sous-matrices en cousant ,.ensemble la longueur des préfixes successifs #\de l'entrée:

   ,~@#\ a
1 1
2 2
3 3

Ensuite, je les utilise pour couper x u ;. _3 yl'entrée en sous-matrices. J'ai déjà x(la liste des tailles); yest le bon argument ](l'entrée).

 ((,~@#\)<;._3"$]) a
┌─────┬─────┬─────┬───┬─┐
│1    │0    │1    │0  │0│
│     │     │     │   │ │
│     │     │     │   │ │
├─────┼─────┼─────┼───┼─┤
│1    │0    │1    │1  │1│
│     │     │     │   │ │
├─────┼─────┼─────┼───┼─┤
│1    │1    │1    │1  │1│
└─────┴─────┴─────┴───┴─┘

┌─────┬─────┬─────┬───┬─┐
│1 0  │0 1  │1 0  │0 0│ │
│1 0  │0 1  │1 1  │1 1│ │
│     │     │     │   │ │
├─────┼─────┼─────┼───┼─┤
│1 0  │0 1  │1 1  │1 1│ │
│1 1  │1 1  │1 1  │1 1│ │
├─────┼─────┼─────┼───┼─┤
│     │     │     │   │ │
└─────┴─────┴─────┴───┴─┘

┌─────┬─────┬─────┬───┬─┐
│1 0 1│0 1 0│1 0 0│   │ │
│1 0 1│0 1 1│1 1 1│   │ │
│1 1 1│1 1 1│1 1 1│   │ │
├─────┼─────┼─────┼───┼─┤
│     │     │     │   │ │
│     │     │     │   │ │
├─────┼─────┼─────┼───┼─┤
│     │     │     │   │ │
└─────┴─────┴─────┴───┴─┘

Pour chaque sous-matrice, je vérifie si elle est entièrement composée de 1: (#**/)@,- aplatissez la matrice et multipliez le nombre d'articles par leur produit. Si tous les éléments sont 1s, le résultat sera leur somme, sinon - 0:

   (#**/)@, 3 3$1 0 0 1 1 1 1 1 1
0
   (#**/)@, 2 2$1 1 1 1
4 

   ((,~@#\)(+/**/)@,;._3"$]) a
1 0 1 0 0
1 0 1 1 1
1 1 1 1 1

0 0 0 0 0
0 0 4 4 0
0 0 0 0 0

0 0 0 0 0
0 0 0 0 0
0 0 0 0 0

Enfin j'aplatis la liste des résultats pour chaque sous-matrice et trouve le maximum:

>./@,

   ([:>./@,,~@#\(+/**/)@,;._3"$]) a
4

Galen Ivanov
la source

1

,~@#\et "1 2->"$

FrownyFrog

@FrownyFrog Merci! Je ne savais pas"$

Galen Ivanov

1

#est plus court que l'addition des 1.

FrownyFrog

@ FrownyFrog Hmm, ça l'est vraiment. Cool merci!

Galen Ivanov

3

APL (Dyalog Unicode) , 35 34 32 octets

{⌈/{×⍨⍵×1∊{∧/∊⍵}⌺⍵ ⍵⊢X}¨⍳⌊/⍴X←⍵}

Essayez-le en ligne!

Le SBCS d'Adám possède tous les caractères du code

Explication à venir éventuellement!

Zacharý
la source

2

Rétine , 143 octets

%`$
,;#
+%(`(\d\d.+;#)#*
$1¶$&¶$&#
\G\d(\d+,)|\G((;#+¶|,)\d)\d+
$1$2
)r`((11)|\d\d)(\d*,;?#*)\G
$#2$3
1,
#
Lv$`(#+).*;\1
$.($.1*$1
N`
-1G`
^$
1

Essayez-le en ligne! Le lien inclut des cas de test. Prend l'entrée sous forme de chaînes séparées par des virgules. Explication:

%`$
,;#

Ajoutez un ,pour terminer la dernière chaîne, un ;pour séparer les chaînes du #s et un #comme compteur.

+%(`
)

Répétez le bloc jusqu'à ce qu'il n'y ait plus de substitution (car chaque chaîne ne comporte plus qu'un seul chiffre).

(\d\d.+;#)#*
$1¶$&¶$&#

Tripliquez la ligne en mettant le compteur à 1 sur la première ligne et en l'incrémentant sur la dernière ligne.

\G\d(\d+,)|\G((;#+¶|,)\d)\d+
$1$2

Sur la première ligne, supprimez le premier chiffre de chaque chaîne, tandis que sur la deuxième ligne, supprimez tous les chiffres sauf le premier.

r`((11)|\d\d)(\d*,;?#*)\G
$#2$3

Sur la troisième ligne, au niveau du bit et des deux premiers chiffres ensemble.

1,
#

À ce stade, chaque ligne se compose de deux valeurs, a) un compteur de largeur horizontale et b) au niveau du bit et du nombre de bits pris dans chaque chaîne. Convertissez tous les 1s restants en #s afin qu'ils puissent être comparés au compteur.

Lv$`(#+).*;\1
$.($.1*$1

Trouvez toutes les séries de bits (verticalement) qui correspondent au compteur (horizontalement), correspondant aux carrés de 1s dans l'entrée d'origine, et mettez la longueur au carré.

N`

Trier numériquement.

-1G`

Prenez le plus gros.

^$
1

Cas particulier de la matrice zéro.

Neil
la source

2

JavaScript, 92 octets

a=>(g=w=>a.match(Array(w).fill(`1{${w}}`).join(`..{${W-w}}`))?w*w:g(w-1))(W=a.indexOf`,`)||1

Afficher l'extrait de code

f=
a=>(g=w=>a.match(Array(w).fill(`1{${w}}`).join(`..{${W-w}}`))?w*w:g(w-1))(W=a.indexOf`,`)||1
console.log(f('0111,1111,1111,1111'));
console.log(f('10100,10111,11111,10010'));
console.log(f('0111,1101,0111'));

Développer l'extrait

tsh
la source

2

APL (Dyalog Classic) , 21 20 octets

×⍨{1∊⍵:1+∇2×/2×⌿⍵⋄0}

Essayez-le en ligne!

ngn
la source

Récursivité! Agréable!

Zacharý

@ Zacharý Merci. En fait, au lieu de récursivité, je préférerais quelque chose comme k \ f \ x pour un monadique f, qui est (x; fx; ffx; ...) jusqu'à la convergence, mais il n'y a pas d'équivalent en APL (pour l'instant). Le faire avec ⍣≡ prend trop d'octets.

ngn le

2

Python 2 , 117 109 octets

Nous remercions @etene d'avoir signalé une inefficacité qui m'a coûté un octet supplémentaire.

lambda s:max(i*i for i in range(len(s))if re.search(("."*(s.find(',')-i+1)).join(["1"*i]*i),s))or 1
import re

Essayez-le en ligne!

Prend l'entrée comme une chaîne séparée par des virgules. Il s'agit d'une approche basée sur l'expression rationnelle qui essaie de faire correspondre la chaîne d'entrée avec les modèles du formulaire 111.....111.....111pour toutes les tailles possibles du carré.

Dans mes calculs, le faire avec un lambda anonyme est juste un peu plus court que la fonction définie ou un programme complet. La or 1partie à la fin n'est nécessaire que pour gérer le cas de bord étrange, où nous devons sortir 1s'il n'y a personne dans l'entrée.

Kirill L.
la source

2

Python 2 , 116 115 117 117 109 octets

Crédits à @Kirill pour m'avoir aidé à jouer au golf encore plus et pour sa solution intelligente et précoce

Edit : Golfé 1 octet en utilisant un lambda, je ne savais pas que l'affecter à une variable ne comptait pas dans le nombre d'octets.

Edit 2 : Kirill a souligné que ma solution ne fonctionnait pas dans les cas où l'entrée ne contient que des 1s, j'ai dû le réparer et perdu deux précieux octets ...

Edit 3 : plus de golf grâce à Kirill

Prend une chaîne séparée par des virgules, retourne un entier.

lambda g:max(i*i for i in range(len(g))if re.search(("."*(g.find(",")+1-i)).join(["1"*i]*i),g))or 1
import re

Essayez-le en ligne!

J'ai trouvé indépendamment une réponse qui est proche de celle de Kiril, c'est-à-dire basée sur l'expression rationnelle, sauf que j'utilise re.search ~~et adef~~ .

Il utilise une expression régulière construite pendant chaque boucle pour correspondre à un carré incrémentiel plus grand et renvoie le plus grand, ou 1.

étène
la source

1

Bien, j'ai en quelque sorte rejeté automatiquement l' ifapproche comme "trop longue pour sûr", mais j'ai ensuite dû trouver un autre moyen de faire une valeur booléenne du match. Malheureusement, votre solution manque un point - vous ne pouvez pas l'avoir juste range(l)- elle manquera le cas quand il n'y aura aucun zéro. Par exemple, prenez le 2ème cas de test et faites-en tous les 1 - il devrait devenir 16, pas 9.

Kirill L.

Merde, j'ai pensé à tester avec tous les zéros mais pas avec tous (jamais mentionné dans le défi ...). Je vais essayer de faire quelque chose.

etene

@KirillL. au fait, vous êtes rapide! Je travaillais toujours sur ma réponse lorsque vous avez posté la vôtre et j'étais un peu déçu (et fier!) Lorsque j'ai vu que nos approches étaient similaires ... le niveau ici est impressionnant.

etene

1

Golfé quelques octets de plus en se débarrassant des doublons find. Maintenant que nos codes ne sont plus identiques, je suggère que nous corrigions au moins les erreurs évidentes les uns des autres - dans votre cas, l'octet supplémentaire provient de l'utilisation de tuple ("1"*i,)au lieu de list.

Kirill L.

Merci, ouais le tuple inutile est assez stupide de ma part. Et le plus findaussi, c'était intelligent de votre part.

etene

2

Rubis `-n` , 63 octets

p (1..l=$_=~/,|$/).map{|i|/#{[?1*i]*i*(?.*(l-i+1))}/?i*i:1}.max

Essayez-le en ligne!

Version Ruby de ma réponse Python . Golfier comme programme complet. Alternativement, un lambda anonyme:

Rubis , 70 68 octets

->s{(1..l=s=~/,|$/).map{|i|s=~/#{[?1*i]*i*(?.*(l-i+1))}/?i*i:1}.max}

Essayez-le en ligne!

Kirill L.
la source

1

Perl 6 , 61 60 58 octets

{(^$_ X.. ^$_).max({[~&](.[|$^r||*])~~/$(1 x$r)/&&+$r})²}

Essayez-le en ligne!

nwellnhof
la source

1

Python 2 , 138 128 octets

def f(m):j=''.join;L=j(m);k=map(j,zip(*m));return len(L)and max(len(L)*(len(m)**2*'1'==L),f(k[1:]),f(k[:-1]),f(m[1:]),f(m[:-1]))

Essayez-le en ligne!

Enregistré

-10 octets grâce aux ovs

TFeld
la source

1

Clojure, 193 octets

#(apply max(for [f[(fn[a b](take-while seq(iterate a b)))]R(f next %)R(f butlast R)n[(count R)]c(for[i(range(-(count(first R))n -1)):when(apply = 1(for[r R c(subvec r i(+ i n))]c))](* n n))]c))

Wow, les choses ont dégénéré: o

Moins golfé:

(def f #(for [rows (->> %    (iterate next)    (take-while seq)) ; row-postfixes
              rows (->> rows (iterate butlast) (take-while seq)) ; row-suffixes
              n    [(count rows)]
              c    (for[i(range(-(count(first rows))n -1)):when(every? pos?(for [row rows col(subvec row i(+ i n))]col))](* n n))] ; rectangular subsections
          c))

NikoNyrh
la source

La plus grande place

Réponses:

Gelée , 18 octets

Comment?

Haskell , 113 121 118 117 117 octets

Explication / Non golfé

Haskell , 99 97 octets

K (ngn / k) , 33 28 octets

J , 33 27 octets

Explication:

APL (Dyalog Unicode) , 35 34 32 octets

Rétine , 143 octets

JavaScript, 92 octets

APL (Dyalog Classic) , 21 20 octets

Python 2 , 117 109 octets

Python 2 , 116 115 117 117 109 octets

Rubis `-n` , 63 octets

Rubis , 70 68 octets

Perl 6 , 61 60 58 octets

Python 2 , 138 128 octets

Clojure, 193 octets

La plus grande place

Réponses:

Gelée , 18 octets

Comment?

Haskell , 113 121 118 117 117 octets

Explication / Non golfé

Haskell , 99 97 octets

K (ngn / k) , 33 28 octets

J , 33 27 octets

Explication:

APL (Dyalog Unicode) , 35 34 32 octets

Rétine , 143 octets

JavaScript, 92 octets

APL (Dyalog Classic) , 21 20 octets

Python 2 , 117 109 octets

Python 2 , 116 115 117 117 109 octets

Rubis -n , 63 octets

Rubis , 70 68 octets

Perl 6 , 61 60 58 octets

Python 2 , 138 128 octets

Clojure, 193 octets

Rubis `-n` , 63 octets