Problem 741

A place to air possible concerns or difficulties in understanding ProjectEuler problems. This forum is not meant to publish solutions. This forum is NOT meant to discuss solution methods or giving hints how a problem can be solved.
Forum rules
As your posts will be visible to the general public you
are requested to be thoughtful in not posting anything
that might explicitly give away how to solve a particular problem.

This forum is NOT meant to discuss solution methods for a problem.

In particular don't post any code fragments or results.

Don't start begging others to give partial answers to problems

Don't ask for hints how to solve a problem

Don't start a new topic for a problem if there already exists one


See also the topics:
Don't post any spoilers
Comments, questions and clarifications about PE problems.
Post Reply
roosephu
Posts: 7
Joined: Sat Aug 16, 2014 8:47 am

Problem 741

Post 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!
roosephu
Posts: 7
Joined: Sat Aug 16, 2014 8:47 am

Re: Problem 741

Post 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).
amagri
Posts: 7
Joined: Tue May 21, 2019 1:20 pm

Re: Problem 741

Post by amagri »

Yes indeed, rotations are centered on the center of the grid with angles Pi/2, Pi or 3Pi/2.
Good luck!
Bashar_AL-Rfooh
Posts: 2
Joined: Sat Feb 06, 2021 5:17 am

Re: Problem 741

Post 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
philiplu
Posts: 45
Joined: Wed Aug 02, 2017 8:51 pm
Location: Redmond, WA, USA

Re: Problem 741

Post 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.
Image
Bashar_AL-Rfooh
Posts: 2
Joined: Sat Feb 06, 2021 5:17 am

Re: Problem 741

Post 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
DJohn
Posts: 67
Joined: Sat Oct 11, 2008 12:24 pm

Re: Problem 741

Post 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.
Post Reply