Page 1 of 1
Problem 741
Posted: Sat Jan 02, 2021 9:46 pm
by roosephu
Hello, can anyone explain a little bit about "unique up to rotations and reflections"? I don't really understand it.
My current understanding is that two colorings are the same iff there exists a sequence of rotations/reflections (can be applied to both rows and columns) which turns one to another. However, my brute-force solutions only finds 8 unique colorings for g(4), which are
Code: Select all
===
1100
1100
0011
0011
===
1100
1010
0101
0011
===
1010
1100
0101
0011
===
1100
0110
1001
0011
===
0110
1100
1001
0011
===
1100
0011
1100
0011
===
1010
1010
0101
0101
===
1010
0101
1010
0101
I'd appreciate it if anyone can show an example of a missing coloring from above.
Thanks!
Re: Problem 741
Posted: Sun Jan 03, 2021 1:47 am
by roosephu
I realized that *rotation* here doesn't mean rotating rows/columns (like numpy.roll), but probably rotating the grid for 90 degrees (like numpy.rot90).
Re: Problem 741
Posted: Sun Jan 03, 2021 2:27 am
by amagri
Yes indeed, rotations are centered on the center of the grid with angles Pi/2, Pi or 3Pi/2.
Good luck!
Re: Problem 741
Posted: Sat Feb 06, 2021 5:20 am
by Bashar_AL-Rfooh
Hi I am really confused about reflections and rotations if some one can verify for me how many unique and repeated pattern are there in 3 * 3 matrix I will be thankful
Re: Problem 741
Posted: Sat Feb 06, 2021 8:06 am
by philiplu
Bashar_AL-Rfooh wrote: Sat Feb 06, 2021 5:20 am
Hi I am really confused about reflections and rotations if some one can verify for me how many unique and repeated pattern are there in 3 * 3 matrix I will be thankful
Let me see if it helps to explain a bit more before giving out hint numbers. Consider the following 3x3 matrices:
$
\begin{pmatrix} 1&2&3 \\ 4&5&6 \\ 7&8&9 \end{pmatrix}
\begin{pmatrix} 7&4&1 \\ 8&5&2 \\ 9&6&3 \end{pmatrix}
\begin{pmatrix} 9&8&7 \\ 6&5&4 \\ 3&2&1 \end{pmatrix}
\begin{pmatrix} 3&6&9 \\ 2&5&8 \\ 1&4&7 \end{pmatrix}
\\
\begin{pmatrix} 3&2&1 \\ 6&5&4 \\ 9&8&7 \end{pmatrix}
\begin{pmatrix} 9&6&3 \\ 8&5&2 \\ 7&4&1 \end{pmatrix}
\begin{pmatrix} 7&8&9 \\ 4&5&6 \\ 1&2&3 \end{pmatrix}
\begin{pmatrix} 1&4&7 \\ 2&5&8 \\ 3&6&9 \end{pmatrix}
$
"Up to rotations and reflections", those are all the same matrix. Start with the upper left matrix, then pick it up and rotate it 90 degrees clockwise at a time, and you'll get the other 3 on that row. The lower left matrix is just the upper left one, flipped across the vertical axis of the middle column. That's a reflection. You can then take that reflected matrix, and rotate it 90 degrees clockwise at a time to get the other 3 on the second row. So there are 8 ways to move this matrix around, and still have fundamentally the same matrix.
Re: Problem 741
Posted: Mon Feb 08, 2021 12:23 am
by Bashar_AL-Rfooh
philiplu wrote: Sat Feb 06, 2021 8:06 am
Bashar_AL-Rfooh wrote: Sat Feb 06, 2021 5:20 am
Hi I am really confused about reflections and rotations if some one can verify for me how many unique and repeated pattern are there in 3 * 3 matrix I will be thankful
Let me see if it helps to explain a bit more before giving out hint numbers. Consider the following 3x3 matrices:
$
\begin{pmatrix} 1&2&3 \\ 4&5&6 \\ 7&8&9 \end{pmatrix}
\begin{pmatrix} 7&4&1 \\ 8&5&2 \\ 9&6&3 \end{pmatrix}
\begin{pmatrix} 9&8&7 \\ 6&5&4 \\ 3&2&1 \end{pmatrix}
\begin{pmatrix} 3&6&9 \\ 2&5&8 \\ 1&4&7 \end{pmatrix}
\\
\begin{pmatrix} 3&2&1 \\ 6&5&4 \\ 9&8&7 \end{pmatrix}
\begin{pmatrix} 9&6&3 \\ 8&5&2 \\ 7&4&1 \end{pmatrix}
\begin{pmatrix} 7&8&9 \\ 4&5&6 \\ 1&2&3 \end{pmatrix}
\begin{pmatrix} 1&4&7 \\ 2&5&8 \\ 3&6&9 \end{pmatrix}
$
"Up to rotations and reflections", those are all the same matrix. Start with the upper left matrix, then pick it up and rotate it 90 degrees clockwise at a time, and you'll get the other 3 on that row. The lower left matrix is just the upper left one, flipped across the vertical axis of the middle column. That's a reflection. You can then take that reflected matrix, and rotate it 90 degrees clockwise at a time to get the other 3 on the second row. So there are 8 ways to move this matrix around, and still have fundamentally the same matrix.
Thanks, I understood rotations and reflections right now my problem is to understand the difference between the unique solutions and the repeated ones when we consider the solution unique
Re: Problem 741
Posted: Wed Feb 10, 2021 10:14 am
by DJohn
The problem is asking how many equivalence classes there are, under the equivalence relation "the same after some rotation or reflection". So: take all of the grids that satisfy the conditions, and sort them into groups. Two grids will be assigned to the same group if one is a rotation or reflection of the other. Then count the groups.
Since this is Project Euler, actually carrying out that process is likely to be impractical. The challenge is to find an efficient method that produces the same number.