C'est le golf de code. Le gagnant est le code valide avec le plus petit nombre d'octets.

Défi

Étant donné les entrées M et N , la largeur et la hauteur d'une grille rectangulaire de carrés, sortez un polygone qui satisfait les éléments suivants:

• Les arêtes du polygone sont constituées uniquement d'arêtes carrées: il n'y a pas d'arêtes diagonales - toutes sont verticales ou horizontales.
• Le polygone n'a pas de trous: chaque carré à l'extérieur du polygone peut être atteint par des pas orthogonaux sur des carrés à l'extérieur du polygone, à partir d'un carré à l'extérieur du polygone sur la limite extérieure du rectangle.
• Le polygone n'a pas d'auto-intersection: des arêtes carrées se rencontrant au sommet, pas plus de 2 peuvent faire partie du périmètre du polygone.
• Le polygone est connecté: tout carré du polygone doit être accessible à partir de tout autre carré du polygone via des étapes orthogonales qui restent à l'intérieur du polygone.
• Le polygone a le périmètre maximum possible: selon la formule ci-dessous.

Votre code doit fonctionner pour M et N de 1 à 255.

Formule pour le périmètre maximum

Le défi ici est de trouver le plus golfable de ces polygones avec le périmètre maximum. Le périmètre maximal lui-même est toujours défini par la formule:

Cela est vrai car pour un périmètre maximum, chaque sommet carré doit être sur le périmètre. Pour un nombre impair de sommets, cela n'est pas possible et le meilleur qui peut être atteint est un sommet de moins (puisque le périmètre est toujours pair).

Production

Sortez la forme sous la forme d'une chaîne de caractères séparés par un saut de ligne ( N lignes d'exactement M caractères). Ici, j'utilise l'espace pour les carrés à l'extérieur du polygone et '#' pour les carrés à l'intérieur du polygone, mais vous pouvez utiliser deux caractères visuellement distincts, à condition que leur signification soit cohérente pour toutes les entrées.

Vous pouvez inclure jusqu'à une nouvelle ligne de début et jusqu'à une nouvelle ligne de fin.

Si vous le souhaitez, vous pouvez produire à la place M lignes d'exactement N caractères, et vous pouvez choisir la sortie M par N pour certaines entrées et N par la sortie M pour d'autres.

Exemples

Invalide en raison d'un trou:

###
# #
###

Invalide en raison de l'intersection (toucher en diagonale - un sommet avec 4 bords carrés sur le périmètre) et, accessoirement, d'un trou:

##
# #
###

Non valide en raison de la déconnexion:

#
# #
  #

Polygone valide de périmètre maximal:

# #
# #
###

Crédits

Au début, j'ai sous-estimé la vitesse à laquelle la valeur du périmètre maximum pouvait être calculée, et j'allais simplement demander cette valeur comme sortie. Merci aux personnes merveilleusement utiles dans le chat pour avoir expliqué comment déterminer le périmètre maximal pour N et M arbitraires et contribué à en faire un défi qui durera plus d'une réponse ...

Plus précisément grâce à:

Sparr , Zgarb , feersum , jimmy23013 .

CJam, 47 octets

l~_2%{\}|_'#:H*@({N+1$(2md\HS+*H+\SH+R=*++}fR\;

Essayez-le en ligne

Explication:

l~      Get and convert input.
_2%     Calculate second value modulo 2.
{\}|    If value is even, swap the two inputs. This puts odd on top if one is odd.
_'#:H*  Create top row of all # signs. Also save away # character as shortcut for later.
@(      Pull number of rows to top, and decrement because first is done.
{       Start loop over rows.
N+      Add newline.
1$      Copy row length to top of stack.
(2md    Decrement, and calculate mod/div with 2.
\       Swap mod and div, will use div first.
HS+     "# "
*       Repeat it based on div 2 of row length.
H+      Add one more #.
\       Swap mod of earlier division to top.
SH+     " #"
R=      Pick space or # depending on even/odd row number.
*       Repeat 0 or 1 times depending on mod 2 of row length.
+       Add the possible extra character to line.
+       Add line to result.
}fR     End of for loop over lines.
\;      Remove row length from stack, leaving only result string.

Il y a deux cas principaux pour le résultat. Si au moins une des tailles est impaire, le motif est un simple "râteau". Par exemple, pour la saisie 7 6:

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

Si les deux tailles sont égales, il y a une colonne supplémentaire où chaque deuxième carré est "activé". Par exemple, pour la saisie 8 6:

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

Maintenant, pour montrer que ces modèles atteignent le maximum théorique du périmètre comme indiqué dans la description du problème, nous devons confirmer que le premier modèle a un périmètre (M + 1) * (N + 1)et le second la même valeur moins 1.

Pour le premier motif, nous avons pour le périmètre, avec Mune dimension impaire:

1. M pour le bord supérieur.
2. 2 sur le côté de la rangée supérieure.
3. (M - 1) / 2 pour les espaces entre les dents.
4. (M + 1) / 2dents avec périmètre 2 * (N - 1) + 1chacune.

Cela revient à:

M + 2 + (M - 1) / 2 + (M + 1) / 2 * (2 * (N - 1) + 1) =
M + 2 + (M - 1) / 2 + (M + 1) * (N - 1) + (M + 1) / 2 =
2 * M + 2 + (M + 1) * (N - 1) =
(M + 1) * 2 + (M + 1) * (N - 1) =
(M + 1) * (N + 1)

Pour le deuxième cas où les deux Met Nsont pairs, le périmètre s'additionne à partir de:

1. M pour le bord supérieur.
2. 2 sur le côté de la rangée supérieure.
3. M / 2 pour le # ouvert dans la rangée du haut.
4. M / 2dents avec périmètre 2 * (N - 1) + 1chacune pour les dents plates.
5. La dent la plus à droite a un 2 * (N / 2 - 1)périmètre supplémentaire pour les dents.

En ajoutant tout cela ensemble:

M + 2 + M / 2 + (M / 2) * (2 * (N - 1) + 1) + 2 * (N / 2 - 1) =
M + 2 + (M / 2) * (2 * (N - 1) + 2) + N - 2 =
M + M * N + N =
(M + 1) * (N + 1) - 1

Ruby, Rév.1, 66

->(m,n){n.times{|i|puts ("#"*m**(1-i%2)).rjust(m,i>n-2?"# ":" ")}}

Utilisé mpour augmenter la puissance 0 o 1 pour décider si 1 ou m #les caractères seront imprimés.

Utilisé >pour tester la dernière ligne au lieu de ==.

Impossible de se débarrasser de l'espace après les puts, ni des supports!

Ruby, Rév 0, 69

->(m,n){n.times{|i|puts ("#"*(i%2==0?m:1)).rjust(m,i==n-1?"# ":" ")}}

Il s'agit d'une fonction lambda anonyme. Utilisez-le comme ceci:

f=->(m,n){n.times{|i|puts ("#"*(i%2==0?m:1)).rjust(m,i==n-1?"# ":" ")}}

M=gets.to_i
N=gets.to_i
f.call(M,N)

Finalement, après avoir demandé si M et N pouvaient être échangés, je n'en avais pas besoin.

Sorties typiques pour N impair. Si nous supprimons le #sur le côté droit, nous aurons clairement (N + 1) (M + 1). Les inclure pour joindre la forme supprime 2 carrés de périmètre horizontal et ajoute 2 carrés de périmètre vertical, il n'y a donc pas de changement.

Ici, nous nous appuyons sur l'expression "#"*(i%2==0?m:1)pour donner des rangées alternées de M #symboles et un #symbole, et justifier à droite à M caractères.

5                        6
5                        5
#####                    ######
    #                         #
#####                    ######
    #                         #
#####                    ######

Sorties typiques pour N pair. 5 6a clairement le même périmètre que 6 5, ou un incrément de M + 1 = 6 par rapport à l' 5 5ajout de périmètre vertical en raison de la crénulation de la rangée inférieure. 6 6a la même chose que6 5 plus un incrément de (M + 1) -1 = 6 dans le périmètre vertical. Ils sont donc conformes à la formule.

5                        6
6                        6
#####                    ######
    #                         #
#####                    ######
    #                         #
#####                    ######
# # #                    # # ##

Il est très pratique que Ruby rjustvous permette de spécifier le remplissage à utiliser pour les cellules vides. Normalement, le rembourrage est réglé sur" " mais pour la dernière ligne, nous passons à "# "(notez que le remplissage ne sera nécessaire que sur la dernière ligne si N est pair. Où N est impair, la dernière ligne sera complète et il n'y aura pas de justification, donc vous ne verra pas les créneaux.)

Vérifiez le ici.

C, 109 97 octets et preuve d'exactitude

J'écrivais ma solution mais @steveverrill m'a battu. J'ai pensé que je partagerais tout de même, car j'ai inclus une preuve d'exactitude pour la stratégie utilisée.

Code réduit:

m,n,x;main(){for(scanf("%i%i",&m,&n); n;)putchar(x<m?"# "[x%2*(++x^m||~n&1)&&n^1]:(x=0,n--,10));}

Avant réduction:

m,n,x;

main(){
    for(scanf("%i%i",&m,&n); n;) 

        /* If x == m, prints out a newline, and iterates outer 
         * loop (x=0,n--) using comma operator.
         * Otherwise, paints a '#' on :
         *     Every even column (when x%2 is 0)
         *     On odd columns of the last row (++x^m||~n&1 is 0)
         *     On the first row (when n^1 is 0)
         * And a ' ' on anything else (when predicate is 1) */
        putchar(x<m?"# "[x%2*(++x^m||~n&1)&&n^1]:(x=0,n--,10));
}

Stratégie et preuve:

En supposant l'exactitude de l'équation du périmètre maximal (M + 1) (N + 1) - ((M + 1) (N + 1)) mod 2 , ce qui suit explique la stratégie optimale utilisée et prouve son exactitude par induction:

Pour un M impair, nous dessinons une forme semblable à une main avec M / 2 + 1 doigts, par exemple:

3x2
# # 
###

5x3
# # #
# # #
#####

Nous prouvons maintenant que cette stratégie est optimale pour tout M impair par induction:

Cas de base: M = N = 1
La cellule unique est remplie. La solution est correcte puisque (1 + 1) * (1 + 1) = 2 * 2 = 4, et un carré a 4 côtés.

Induction sur la largeur:
Supposons que la stratégie de la forme de la main fonctionne pour (N, M-2) où M est impair, c'est-à-dire que son périmètre est optimal et est (N + 1) (M - 2 + 1) + ((M -1) (N + 1)) mod 2 . Nous montrons maintenant que cela fonctionnera pour (N, M) .

Le processus d'ajout d'un doigt supprime un bord du polygone et ajoute 3 + 2N . Par exemple:

 5x3 -> 7x3
 # # # $
 # # # $
 #####$$

En combinant cela avec notre hypothèse que le périmètre précédent était optimal, le nouveau périmètre est:

(N + 1)*(M - 2 + 1) - ((M+1)*(N+1)) mod 2 - 1 + 3 + 2*N
(N + 1)*(M + 1) - ((M-1)*(N+1)) mod 2 - 2(N + 1) - 1 + 3 + 2*N
(N + 1)*(M + 1) - ((M-1)*(N+1)) mod 2

Puisque nous avons affaire à l'arithmétique modulo 2,

((M-1)*(N+1)) mod 2 = ((M+1)*(N+1)) mod 2

Ainsi, prouver que l'augmentation de la largeur en ajoutant des doigts conduit à un périmètre optimal.

Induction sur la hauteur:
Supposons que la stratégie de la forme de la main fonctionne pour (N-1, M) , où M est impair, c'est-à-dire que son périmètre est optimal et est N (M + 1) + ((M + 1) N) mod 2 . Nous montrons maintenant que cela fonctionnera pour (N, M) .

L'augmentation de la hauteur de la main ne fait qu'allonger les doigts, situés au premier et à tous les autres index x. Pour chaque augmentation de hauteur, chaque doigt ajoute deux au périmètre, et il y a (M + 1) / 2 doigts, donc, une augmentation de N entraîne une augmentation de 2 (M + 1) / 2 = M + 1 dans le périmètre.

En combinant cela avec l'hypothèse, nous avons que le nouveau périmètre est:

N*(M + 1) + ((M+1)*N) mod 2 + M + 1
(N + 1)*(M + 1) + ((M+1)*N) mod 2

L'arithmétique modulaire nous permet de simplifier le dernier terme, pour obtenir:

(N + 1)*(M + 1) + ((M+1)*(N+1)) mod 2

Prouver que la solution est optimale pour tout N> 0 et impair M> 0.

Pour M même, nous remplissons le tableau de la même manière que pour M impair, mais nous ajoutons des créneaux au dernier segment, par exemple:

4x3
# ##
# # 
####

6x4
# # #
# # ##
# # #
######

Nous prouvons maintenant que cette stratégie est optimale.

Induction pour même M:
Supposons que la solution est correcte pour (N, M-1), avec M-1 impair (comme cela a été prouvé dans le dernier cas), qui a un périmètre optimal de (N + 1) M - ( M (N + 1)) mod 2 . Nous montrons maintenant que cela fonctionnera pour (N, M).

Comme pour augmenter les doigts, chaque créneau ajoute deux au périmètre du polygone. Le nombre total de créneaux est (N + N mod 2) / 2 , pour un total de N + N mod 2 périmètre ajouté.

En combinant cela avec l'hypothèse, nous avons que le nouveau périmètre est:

(N + 1)*M - (M*(N+1)) mod 2 + N + N mod 2
(N + 1)*(M + 1) - (M*(N+1)) mod 2 + N mod 2 - 1
(N + 1)*(M + 1) - (M*(N+1)) mod 2 - (N + 1) mod 2

Nous avons ça

(M*(N+1)) mod 2 - (N + 1) mod 2 = ((M+1)*(N+1)) mod 2

Parce que si N est impair, cela se réduit à 0 = 0, et si N est pair, il se réduit à

- A mod 2 - 1 = -(A + 1) mod 2

Ainsi, la stratégie est optimale pour tout M, N> 0 .