10
\$\begingroup\$

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.

Task

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

\$\endgroup\$
  • \$\begingroup\$ Also, how would this configuration be scored? Is it \$3\$ (the longest reflected ray) or \$5\$ (the sum of all reflected rays)? \$\endgroup\$ – Arnauld Apr 18 at 15:27
  • \$\begingroup\$ @Arnauld 5. As stated in the post, we're only counting reflected elements. \$\endgroup\$ – subdermatoglyphic Apr 18 at 15:40
  • \$\begingroup\$ 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)? \$\endgroup\$ – Jonathan Allan Apr 18 at 19:08
  • \$\begingroup\$ It has to fit; there's a reason why I talked about 45 degrees and \$\sqrt{2}\cdot\min(m,n)\$. \$\endgroup\$ – subdermatoglyphic Apr 19 at 3:00
  • \$\begingroup\$ Can you add another larger test case, maybe something whose min side is 10-15? \$\endgroup\$ – Jonah Apr 22 at 4:27
3
\$\begingroup\$

Charcoal, 91 bytes

≔⟦⟧θWS⊞θI⪪ι ≔L§θ⁰η≔⊖⌊⟦Lθη⟧ζF⁻LθζF⁻ηζF²⊞υ⟦Σ⭆⊕ζ⭆⊕ζ⁼§§θ⁺ι⎇λμ⁻ζμ⁺κθ⁺ι⎇λξ⁻ζξ⁺κμ⎇λι⁺ιζκλ⟧I✂⌈υ¹

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

≔⟦⟧θWS⊞θI⪪ι 

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.)

≔L§θ⁰η

Get the width of the mosaic.

≔⊖⌊⟦Lθη⟧ζ

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.

F⁻Lθζ

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

F⁻ηζ

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

F²

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.

I✂⌈υ¹

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

| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.