# Challenge

## Premise

Consider a mosaic of $$\m\times n\$$ tiles, in $$\k\$$ unique colours designated by integers. Example ($$\3\times6\$$, four colours):

4 1 3 2 4 2
1 2 4 2 1 3
4 3 2 1 4 4


My poor man's mirror is a pane of glass of width $$\\sqrt{2}\cdot\min(m,n)\$$. I stand it diagonally on the mosaic, like so:

4 1 3 M 4 2
1 2 M 2 1 3
4 M 2 1 4 4


For this example I can pretend it reflects exactly two full tiles:

x 1 x M x x
x 2 M x x x
x M 2 1 x x


No matter what diagonal I choose, this is the greatest number of full tiles I can fake-reflect. Yay.

Input: an integer matrix of $$\m\$$ rows and $$\n\$$ columns where $$\2\leq m\leq1000,2\leq n\leq1000\$$. The number of unique values is $$\k\$$ where $$\3\leq k\ll mn\$$.

Output: three integers, in any format. The first and second respectively represent the row coordinate and column coordinate of the matrix element ('mosaic tile') at the left end of the 45-degree diagonal where the fake mirror should be placed for 'best effect', effectiveness being defined as shown above. The third integer is 0 or 1, respectively meaning a rising (bottom left to top right) or falling (top left to bottom right) diagonal.

For clarity's sake, here are some simple test cases.

### Example 1

Input:

4 1 3 2 4 2
1 2 4 2 1 3
4 3 2 1 4 4


Output: 3 2 0

### Example 2

Input:

3 6
4 7
5 8
1 2
2 1


Output: 4 1 1 or 5 1 0 (not both)

As you can see, a unique solution isn't guaranteed.

### Example 3

Input:

2  7  4  10 7  8  9  5  6  4  2  4  10 2  1  7  10 7  2  4  10 10 8  7
6  5  6  2  2  3  6  1  6  9  7  2  10 3  4  7  8  8  3  7  1  8  4  2
3  3  7  6  10 1  7  9  10 10 2  6  4  7  5  6  9  1  1  5  7  6  2  7
7  10 3  9  8  10 9  3  6  1  6  10 3  8  9  6  3  6  2  10 1  2  8  1
7  7  8  1  1  6  4  8  10 3  10 4  9  3  1  9  5  9  10 4  6  7  10 4
1  10 9  7  7  10 3  3  7  8  2  2  4  2  4  7  1  7  7  1  9  9  8  7
5  9  5  3  8  6  5  7  6  7  2  7  9  9  7  10 8  8  7  3  5  9  9  10
9  3  8  2  9  2  1  3  6  3  8  5  7  10 10 9  1  1  10 2  5  1  6  9
8  7  6  2  3  2  9  9  9  7  9  5  8  3  8  2  2  5  2  2  10 10 3  5
7  1  1  2  3  2  10 1  2  10 3  3  2  1  4  2  5  6  10 9  6  5  3  8
8  9  5  2  1  4  10 6  8  6  9  10 10 8  1  6  10 6  4  8  7  9  3  5
8  1  5  7  1  8  7  5  8  6  4  5  10 1  6  1  4  4  10 7  6  3  3  6


Output: 1 10 1

## Edit - indexing

The example outputs are 1-indexed, but 0-indexing is allowed.

# Remarks

• Also, how would this configuration be scored? Is it $3$ (the longest reflected ray) or $5$ (the sum of all reflected rays)? Apr 18, 2020 at 15:27
• @Arnauld 5. As stated in the post, we're only counting reflected elements. Apr 18, 2020 at 15:40
• Can the mirror leave the mosaic or must it be placed such that it fits (e.g. in the 3x6 example are 2 1 0 and 2 4 1 placements to be considered or not)? Apr 18, 2020 at 19:08
• It has to fit; there's a reason why I talked about 45 degrees and $\sqrt{2}\cdot\min(m,n)$. Apr 19, 2020 at 3:00
• Can you add another larger test case, maybe something whose min side is 10-15? Apr 22, 2020 at 4:27

# Charcoal, 91 bytes

≔⟦⟧θＷＳ⊞θＩ⪪ι ≔Ｌ§θ⁰η≔⊖⌊⟦Ｌθη⟧ζＦ⁻ＬθζＦ⁻ηζＦ²⊞υ⟦Σ⭆⊕ζ⭆⊕ζ⁼§§θ⁺ι⎇λμ⁻ζμ⁺κξ§§θ⁺ι⎇λξ⁻ζξ⁺κμ⎇λι⁺ιζκλ⟧Ｉ✂⌈υ¹


Try it online! Link is to verbose version of code. 0-indexed. Explanation:

≔⟦⟧θＷＳ⊞θＩ⪪ι


Input the mosaic. (These 12 bytes could be avoided by requiring the input to be in JSON format, but I was too lazy to punctuate the example.)

≔Ｌ§θ⁰η


Get the width of the mosaic.

≔⊖⌊⟦Ｌθη⟧ζ


Get the inner size of the mirror, i.e. the distance from the first to the last character of the mirror in terms of diagonal steps.

Ｆ⁻Ｌθζ


Loop over the possible row(s) of the top left corner of the mirror's enclosing square.

Ｆ⁻ηζ


Loop over the possible column(s) of the top left corner of the mirror's square.

Ｆ²


Loop over the possible rotations of the mirror.

⊞υ⟦Σ⭆⊕ζ⭆⊕ζ⁼§§θ⁺ι⎇λμ⁻ζμ⁺κξ§§θ⁺ι⎇λξ⁻ζξ⁺κμ⎇λι⁺ιζκλ⟧


Calculate the number of tiles it reflects exactly. Exact matches are counted twice and the diagonal is also counted but this doesn't affect the relative score. Push this number along with the potential solution to the predefined empty list.

Ｉ✂⌈υ¹


Output the solution with the highest number of exactly reflected tiles.

# Python3, 557 bytes:

E=enumerate
V=lambda x,y,n,m:0<=x<n and 0<=y<m
U=lambda j,k,J,K,b,n,m:b[j][k]==b[J][K]if V(j,k,n,m)and V(J,K,n,m)else 0
def f(b):
n,m=len(b),len(b[0])
q,r=[i for x,u in E(b)for y,_ in E(u)for i in[(x,y,0,0,x,y)]*(x+1>=min(n,m)and y+min(n,m)<=m)+[(x,y,1,0,x,y)]*(x+1>=min(n,m)and y+1>=min(n,m))],[]
while q:
x,y,d,c,X,Y=q.pop(0)
if abs(X-x)+1==min(n,m):r+=[(*[[x,y],[X,Y]][d],d,c)];continue
q+=[(x,y,d,c+U(*[[X+1,Y+1,X-1,Y-1],[X+1,Y-1,X-1,Y+1]][d],b,n,m)+U(*[[X,Y+1,X-1,Y],[X,Y-1,X+1,Y]][d],b,n,m),X-1,Y+[1,-1][d])]
return max(r,key=lambda x:x[-1])


Try it online!