Das ist Code Golf. Der Gewinner ist der gültige Code mit der geringsten Anzahl von Bytes.

Herausforderung

Bei den Eingaben M und N , der Breite und Höhe eines rechteckigen Quadratrasters, wird ein Polygon ausgegeben, das die folgenden Anforderungen erfüllt:

• Die Polygonkanten bestehen nur aus quadratischen Kanten: Es gibt keine diagonalen Kanten - alle sind vertikal oder horizontal.
• Das Polygon hat keine Löcher: Jedes Quadrat außerhalb des Polygons kann durch orthogonale Schritte auf Quadraten außerhalb des Polygons erreicht werden, beginnend mit einem Quadrat außerhalb des Polygons an der äußeren Begrenzung des Rechtecks.
• Das Polygon hat keine Selbstüberschneidung: Von den quadratischen Kanten, die sich an einem Scheitelpunkt treffen, dürfen nicht mehr als 2 Teile des Polygonumfangs sein.
• Das Polygon ist verbunden: Jedes Quadrat im Polygon muss über orthogonale Schritte, die innerhalb des Polygons bleiben, von jedem anderen Quadrat im Polygon aus erreichbar sein.
• Das Polygon hat den maximal möglichen Umfang: gemäß der unten gezeigten Formel.

Ihr Code muss für M und N von 1 bis 255 funktionieren .

Formel für maximalen Umfang

Die Herausforderung besteht darin, das am besten geeignete Polygon mit dem maximalen Umfang zu finden. Der maximale Umfang selbst wird immer durch die Formel definiert:

Dies ist richtig, da für einen maximalen Umfang jeder quadratische Eckpunkt auf dem Umfang liegen muss. Für eine ungerade Anzahl von Scheitelpunkten ist dies nicht möglich und das Beste, was erreicht werden kann, ist ein Scheitelpunkt weniger (da der Umfang immer gerade ist).

Ausgabe

Geben Sie die Form als Zeichenfolge mit Zeilenumbrüchen aus ( N Zeilen mit genau M Zeichen). Hier verwende ich Platz für Quadrate außerhalb des Polygons und '#' für Quadrate innerhalb des Polygons. Sie können jedoch zwei beliebige visuell unterschiedliche Zeichen verwenden, sofern deren Bedeutung für alle Eingaben konsistent ist.

Sie können bis zu eine führende und bis zu eine nachfolgende Zeile einfügen.

Wenn Sie möchten, können Sie stattdessen Ausgang M Reihen von genau N Zeichen, und Sie können wählen M von N für einige Ein- und Ausgang N von M für die anderen Ausgang.

Beispiele

Ungültig wegen einer Lücke:

###
# #
###

Ungültig wegen Schnittpunkt (diagonal berühren - ein Scheitelpunkt mit 4 quadratischen Kanten am Umfang) und im Übrigen ein Loch:

##
# #
###

Ungültig , da die Verbindung getrennt wurde:

#
# #
  #

Gültiges Polygon mit maximalem Umfang:

# #
# #
###

Credits

Ich habe anfangs unterschätzt, wie schnell der Wert des maximalen Umfangs berechnet werden kann, und wollte nur diesen Wert als Ausgabe anfordern. Vielen Dank an die wunderbar hilfreichen Personen im Chat, die erklärt haben, wie man den maximalen Umfang für beliebiges N und M errechnet und dabei hilft, dies zu einer Herausforderung zu machen, die für mehr als eine Antwort Bestand hat ...

Speziell danke an:

Sparr , Zgarb , Feersum , Jimmy23013 .

CJam, 47 Bytes

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

Probieren Sie es online aus

Erläuterung:

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.

Es gibt zwei Hauptfälle für das Ergebnis. Wenn mindestens eine der Größen ungerade ist, ist das Muster ein einfacher "Rechen". Zum Beispiel für die Eingabe 7 6:

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

Wenn beide Größen gerade sind, gibt es eine zusätzliche Spalte, in der jedes zweite Quadrat "an" ist. Zum Beispiel für die Eingabe 8 6:

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

Um zu zeigen, dass diese Muster das theoretische Maximum des Umfangs erreichen, wie in der Problembeschreibung angegeben, müssen wir bestätigen, dass das erste Muster den Umfang (M + 1) * (N + 1)und das zweite den gleichen Wert minus 1 hat.

Für das erste Muster haben wir für den Umfang mit Meiner ungeraden Dimension:

1. M für die Oberkante.
2. 2 an der Seite der obersten Reihe.
3. (M - 1) / 2 für die Lücken zwischen den Zähnen.
4. (M + 1) / 2Zähne mit Umfang 2 * (N - 1) + 1.

Dies summiert sich zu:

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)

Für den zweiten Fall, in dem beide Mund gerade Nsind, addiert sich der Umfang aus:

1. M für die Oberkante.
2. 2 an der Seite der obersten Reihe.
3. M / 2 für das offene # in der oberen Reihe.
4. M / 2Zähne mit Umfang 2 * (N - 1) + 1jeweils für die einfachen Zähne.
5. Der Zahn ganz rechts hat einen zusätzlichen 2 * (N / 2 - 1)Umfang für die Zacken.

Alles zusammen addieren:

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, Rev. 1, 66

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

Wird verwendet, mum 0 oder 1 zu erhöhen , um zu entscheiden, ob 1 oder 1 m #gedruckt wird.

Dient >zum Testen der letzten Zeile anstelle von ==.

Ich kann weder den Platz nach dem Put noch irgendwelche Klammern loswerden!

Ruby, Rev 0, 69

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

Dies ist eine anonyme Lambda-Funktion. Benutze es so:

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)

Am Ende brauchte ich es nicht, nachdem ich gefragt hatte, ob M und N vertauscht werden könnten.

Typische Ausgänge für N ungerade. Wenn wir die #auf der rechten Seite einzeln löschen , haben wir eindeutig (N + 1) (M + 1). Wenn Sie sie zum Verbinden der Form hinzufügen, werden 2 Quadrate des horizontalen Umfangs entfernt und 2 Quadrate des vertikalen Umfangs hinzugefügt, sodass keine Änderung erfolgt.

Hier verlassen wir uns auf den Ausdruck "#"*(i%2==0?m:1), um abwechselnde Reihen von M- #Symbolen und ein #Symbol zu geben und M-Zeichen rechtsbündig auszurichten.

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

Typische Ausgänge für N gerade. 5 6hat eindeutig den gleichen Umfang wie 6 5oder ein Inkrement von M + 1 = 6, verglichen mit 5 5der Addition des vertikalen Umfangs aufgrund der Zinnenbildung der unteren Reihe. 6 6hat das gleiche wie 6 5plus ein Inkrement von (M + 1) -1 = 6 im vertikalen Umfang. Sie stimmen also mit der Formel überein.

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

Es ist sehr praktisch, dass Sie mit Ruby den rjustAbstand festlegen können, der für die leeren Zellen verwendet werden soll. Normalerweise ist das Auffüllen auf eingestellt, " "aber für die letzte Zeile, zu der wir wechseln "# "(beachten Sie, dass das Auffüllen nur in der letzten Zeile erforderlich ist, wenn N gerade ist. Wenn N ungerade ist, ist die letzte Zeile vollständig und es gibt keine Rechtfertigung, also Sie werde die Zinnen nicht sehen.)

Schau es dir hier an.

C, 109 97 Bytes und Korrektheitsnachweis

Ich habe meine Lösung geschrieben, aber @steveverrill hat mich geschlagen. Ich dachte, ich würde es trotzdem teilen, da ich einen Korrektheitsnachweis für die verwendete Strategie beigefügt habe.

Reduzierter Code:

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));}

Vor der Reduktion:

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));
}

Strategie und Beweis:

Unter der Annahme, dass die maximale Perimiter-Gleichung (M + 1) (N + 1) - ((M + 1) (N + 1)) mod 2 korrekt ist , wird im Folgenden die optimale Strategie erläutert und ihre Richtigkeit durch Induktion bewiesen:

Für ungerades M zeichnen wir eine handähnliche Form mit M / 2 + 1 Fingern, zum Beispiel:

3x2
# # 
###

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

Wir beweisen nun, dass diese Strategie für alle ungeraden M durch Induktion optimal ist:

Basisfall: M = N = 1
Die einzelne Zelle ist gefüllt. Die Lösung ist korrekt, da (1 + 1) * (1 + 1) = 2 * 2 = 4 und ein Quadrat 4 Seiten hat.

Induktion über die Breite:
Nehmen Sie an, dass die Handformstrategie für (N, M-2) funktioniert , wobei M ungerade ist, das heißt, sein Perimiter optimal ist und (N + 1) (M - 2 + 1) + ((M -1) (N + 1)) mod 2 . Wir zeigen nun, dass es für (N, M) funktionieren wird .

Beim Hinzufügen eines Fingers wird eine Kante aus dem Polygon entfernt und 3 + 2N hinzugefügt . Beispielsweise:

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

In Kombination mit unserer Hypothese, dass der vorherige Umfang optimal war, lautet der neue Umfang:

(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

Da es sich um Modulo 2-Arithmetik handelt,

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

Der Beweis, dass eine Vergrößerung der Breite durch Hinzufügen von Fingern zu einem optimalen Umfang führt.

Induktion auf Höhe:
Angenommen, die Handformstrategie funktioniert für (N-1, M) , wobei M ungerade ist, das heißt, sein Umfang optimal ist und N (M + 1) + ((M + 1) N) mod ist 2 . Wir zeigen nun, dass es für (N, M) funktionieren wird .

Das Erhöhen der Hand verlängert lediglich die Finger, die sich am ersten und an jedem zweiten x-Index befinden. Für jede Höhenzunahme addiert jeder Finger zwei zum Umfang, und es gibt (M + 1) / 2 Finger, daher führt eine Zunahme von N zu einer Zunahme von 2 (M + 1) / 2 = M + 1 in der Umfang.

Wenn wir dies mit der Hypothese kombinieren, ist der neue Umfang:

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

Modulare Arithmetik erlaubt es uns, den letzten Term zu vereinfachen, so dass wir erhalten:

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

Beweis, dass die Lösung für alle N> 0 und ungeraden M> 0 optimal ist.

Für gerade M füllen wir die Tafel genauso aus wie für ungerade M, aber wir fügen dem letzten Segment Zinnen hinzu, zum Beispiel:

4x3
# ##
# # 
####

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

Wir beweisen nun, dass diese Strategie optimal ist.

Induktion für gerade M:
Angenommen, die Lösung ist korrekt für (N, M-1) mit ungerader M-1 (wie im letzten Fall bewiesen), die einen optimalen Umfang von (N + 1) M - (hat. M (N + 1)) mod 2 . Wir zeigen nun, dass es für (N, M) funktionieren wird.

Wie bei der Vergrößerung der Finger erhöht jede Zinnenordnung den Umfang des Polygons um zwei. Die Gesamtzahl der Zinnen ist (N + N mod 2) / 2 , wobei insgesamt N + N mod 2 Perimeter hinzugefügt werden.

Wenn wir dies mit der Hypothese kombinieren, ist der neue Umfang:

(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

Wir haben das

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

Denn wenn N ungerade ist, verringert sich dies auf 0 = 0, und wenn N gerade ist, verringert sich dies auf

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

Somit ist die Strategie für alle M, N> 0 optimal .