Highest perimeter polyomino

Question

This is code golf. The winner is the valid code with the smallest number of bytes.

---

Challenge

Given inputs M and N, the width and height of a rectangular grid of squares, output a polygon that satisfies the following:

• The polygon edges are made up only of square edges: there are no diagonal edges - all are vertical or horizontal.
• The polygon has no holes: every square outside the polygon may be reached by orthogonal steps on squares outside the polygon, starting from a square outside the polygon on the outer boundary of the rectangle.
• The polygon has no self-intersection: of the square edges meeting at a vertex, no more than 2 may be part of the polygon perimeter.
• The polygon is connected: any square in the polygon must be reachable from any other square in the polygon via orthogonal steps that stay within the polygon.
• The polygon has the maximum possible perimeter: according to the formula shown below.

Your code must work for M and N from 1 to 255.

---

Formula for maximum perimeter

The challenge here is finding the most golfable of those polygons with the maximum perimeter. The maximum perimeter itself is always defined by the formula:

This is true because for a maximum perimeter every square vertex must be on the perimeter. For an odd number of vertices this is not possible and the best that can be attained is one vertex less (since the perimeter is always even).

---

Output

Output the shape as a string of newline separated characters (N rows of exactly M characters). Here I am using space for squares outside the polygon, and '#' for squares inside the polygon, but you may use any two visually distinct characters, provided their meaning is consistent for all inputs.

You may include up to one leading newline and up to one trailing newline.

If you wish, you may instead output M rows of exactly N characters, and you may choose M by N output for some inputs and N by M output for others.

---

Examples

Invalid due to a hole:

###
# #
###

Invalid due to intersection (touching diagonally - a vertex with 4 square edges on the perimeter) and, incidentally, a hole:

##
# #
###

Invalid due to being disconnected:

#
# #
  #

Valid polygon of maximum perimeter:

# #
# #
###

---

Credits

I initially underestimated how quickly the value of the maximum perimeter could be calculated, and was going to just ask for that value as the output. Thanks to the wonderfully helpful people in chat for explaining how to work out the maximum perimeter for arbitrary N and M and helping turn this into a challenge that will last for more than one answer...

Specifically thanks to:

Sparr, Zgarb, feersum, jimmy23013.

Answer 1

CJam, 47 bytes

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

Try it online

Explanation:

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.

There are two main cases for the result. If at least one of the sizes is odd, the pattern is a plain "rake". For example, for input 7 6:

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

If both sizes are even, there is an extra column where every second square is "on". For example, for input 8 6:

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

Now, to show that these patterns reach the theoretical maximum of the perimeter as given in the problem description, we need to confirm that the first pattern has perimeter (M + 1) * (N + 1), and the second one the same value minus 1.

For the first pattern, we have for the perimeter, with M an odd dimension:

1. M for the top edge.
2. 2 on the side of the top row.
3. (M - 1) / 2 for the gaps between the teeth.
4. (M + 1) / 2 teeth with perimeter 2 * (N - 1) + 1 each.

This adds up to:

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)

For the second case where both M and N are even, the perimeter adds up from:

1. M for the top edge.
2. 2 on the side of the top row.
3. M / 2 for the open # in the top row.
4. M / 2 teeth with perimeter 2 * (N - 1) + 1 each for the plain teeth.
5. The rightmost tooth has an extra 2 * (N / 2 - 1) perimeter pieces for the jaggies.

Adding this all together:

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

Answer 2

Ruby, Rev 1, 66

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

Used raising m to power 0 o 1 to decide whether 1 or m #'s will be printed.

Used > to test for last row instead of ==.

Can't get rid of the space after puts, nor any brackets!

Ruby, Rev 0, 69

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

This is an anonymous lambda function. Use it like this:

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)

In the end, after asking if M and N could be interchanged I didnt need it.

---

Typical outputs for N odd. If we delete the # on their own on the right hand side, clearly we will have (N+1)(M+1). Including them to join the shape removes 2 squares of horizontal perimeter and adds 2 squares of vertical perimeter, so there is no change.

Here we rely on the expression "#"*(i%2==0?m:1) to give alternating rows of M# symbols and one # symbol, and right justify to M characters.

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

---

Typical outputs for N even. 5 6 clearly has the same perimeter as 6 5, or an increment of M+1=6 compared with 5 5 by addition of vertical perimeter due to the crenelation of the bottom row. 6 6 has the same as 6 5 plus an increment of (M+1)-1=6 in the vertical perimeter. Thus they are in accordance with the formula.

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

It's very handy that Ruby's rjust allows you to specify the padding to use for the empty cells. Normally the padding is set to " " but for the last row we switch to "# " (note that padding will only be needed on the last row if N is even. Where N is odd the last row will be complete and there will be no justifying, so you won't see the crenelations.)

Check it out here.

Answer 3

C, 109 97 bytes and correctness proof

I was writting up my solution but @steveverrill beat me to it. I thought i'd share it all the same, since I included a correctness proof for the strategy used.

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

Before Reduction:

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

Strategy and Proof:

Assuming the correctness of the maximum perimiter equation (M+1)(N+1) - ((M+1)(N+1)) mod 2, the following explains the optimal strategy used and proves its correctness by induction:

For odd M, we draw a hand-like shape with M/2 + 1 fingers, for example:

3x2
# # 
###

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

We now prove this strategy is optimal for all odd M by induction:

Base Case: M=N=1
The single cell is filled. The solution is correct since (1 + 1)*(1 + 1) = 2*2 = 4, and a square has 4 sides.

Induction on width:
Assume that the hand-shape strategy works for (N, M-2) where M is odd, that is, its perimiter is optimal and is (N + 1)(M - 2 + 1) + ((M-1)(N+1)) mod 2. We now show that it will work for (N,M).

The process of adding a finger removes one edge from the polygon, and adds 3 + 2N. For example:

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

Combining this with our hypothesis that the previous perimeter was optimal, the new perimeter is:

(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

Since we are dealing with modulo 2 arithmetic,

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

Thus, proving that increasing the width by adding fingers leads to an optimal perimeter.

Induction on height:
Assume the hand-shape strategy works for (N-1, M), where M is odd, that is, its perimeter is optimal and is N(M + 1) + ((M+1)N) mod 2. We now show that it will work for (N,M).

Increasing the height of the hand merely elongates the fingers, located at the first and every other x-index. For each height increase, each finger adds two to the perimeter, and there are (M+1)/2 fingers, thus, an increase in N leads to an increase of 2(M+1)/2=M+1 in the perimeter.

Combining this with the hypothesis, we have that the new perimeter is:

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

Modular arithmetic permits us to simplify the last term, so that we obtain:

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

Proving that the solution is optimal for all N>0 and odd M>0.

For even M, we fill in the board the same as we would for odd M, but we add crenelations to the last segment, for example:

4x3
# ##
# # 
####

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

We now prove that this strategy is optimal.

Induction for even M:
Assume that the the solution is correct for (N,M-1), with odd M-1 (as was proven in the last case), which has an optimal perimeter of (N + 1)M - (M(N+1)) mod 2. We now show that it will work for (N,M).

Like increasing the fingers, each crenelation adds two to the perimeter of the polygon. The total number of crenelations is (N + N mod 2)/2, for a total of N + N mod 2 perimeter added.

Combining this with the hypothesis, we have that the new perimeter is:

(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

We have that

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

Because if N is odd, then this reduces to 0=0, and if N is even, it reduces to

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

Thus the strategy is optimal for all M,N>0.