Highest perimeter polyomino
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.
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.
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:
Mfor the top edge.2on the side of the top row.(M - 1) / 2for the gaps between the teeth.(M + 1) / 2teeth with perimeter2 * (N - 1) + 1each.
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:
Mfor the top edge.2on the side of the top row.M / 2for the open # in the top row.M / 2teeth with perimeter2 * (N - 1) + 1each for the plain teeth.- 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