This is code golf. The winner is the valid code with the smallest number of bytes.
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 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.
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:
# # # # ###
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: