Descriptive Keywords (for searching): Make Two Matrices Equivalent, Overlap, Array, Find
Santa has had a history of elves stealing presents from his vault in the past, so this year he designed a lock that is very hard to crack, and it seems to have kept the elves out this year. Unfortunately, he has lost the combination and he can't figure out how to open it either! Fortunately, he has hired you to write a program to find the combination. It doesn't need to be the shortest one, but he needs to find it as fast as possible!
He has a very strict schedule and he can't afford to wait for very long. Your score will be the total run-time of your program multiplied by the number of steps your program outputs for the scoring input. Lowest score wins.
The lock is a square matrix of 1s and 0s. It is set to a random arrangement of 1s and 0s and needs to be set to a specified code. Fortunately, Santa remembers the required code.
There are a few steps he can perform. Each step can be performed on any contiguous sub-matrix (that is, you must select a sub-matrix that is entirely bounded by a top-left and bottom-right corner) (it can be a non-square sub-matrix):
- Rotate right 90 degrees*
- Rotate left 90 degrees*
- Rotate 180 degrees
- Cycle each row
nelements right or left (wraps)
- Cycle each column
melements up or down (wraps)
- Flip Horizontally
- Flip Vertically
- Flip on the Main Diagonal*
- Flip on the Main Anti-diagonal*
*only if the sub-matrix is square
Of course, he can also perform these steps on the entire matrix. Since 1s and 0s can only be swapped on the matrix but the value of a square cannot be directly changed, the number of 1s and 0s is the same for the start and end configuration.
Formatting Specifications + Rules
You will be given the input as two square matrices (starting position and ending position) in any reasonable format you want. The output should be a sequence of these steps in any readable format. Since this isn't code-golf, please make it an easily verifiable format, but that's not a strict requirement. You can choose to take the side-length of the matrices in the input if you want.
Your program will be run on my computer (Linux Mint, exact version details available upon request if anyone cares :P) and I will time it based on the amount of time between the time I press "enter" on the command line and when the command exits.
1 0 0 1 0 0 0 0 0 1 1 0 -> 0 0 0 0 0 1 1 0 -> 1 1 1 1 1 0 0 1 1 1 1 1
- Take the entire matrix. Cycle each column up 1.
- Take the middle two columns as a sub-matrix. Cycle each column down 2.
1 0 1 0 1 0 1 0 1 0 0 1 0 1 0 1 0 1 0 1 1 0 1 0 1 -> 0 1 1 1 0 0 1 0 1 0 1 0 1 0 1 1 0 1 0 1 0 1 0 1 0
- Take the entire matrix. Cycle each column down 1.
- Take the middle column. Cycle it down 2.
- Take the top 2 rows. Flip it vertically.
- Take the top row's rightmost 2 elements. Swap them (rotate right/left 1, flip horizontally).
- Take the top row's leftmost 2 elements. Swap them.
There might be more efficient methods, but that doesn't matter. Feel free to point them out in the comments if you find one though :)
Judging Test Case
This test case will be used to judge your submission. If I believe that an answer is specializing for the test case too much, I have the right to repick a random input and rejudge all answers with the new case. The test case can be found here where the top is the start and the bottom is the desired configuration.
If I believe answers are specializing too much, the MD5 of the next test case is
3c1007ebd4ea7f0a2a1f0254af204eed. (This is written here right now to liberate myself from accusations of cheating :P)
Standard Loopholes Apply. No answer will be accepted. Happy coding!
Note: I drew inspiration for this challenge series from Advent Of Code. I have no affiliation with this site
You can see a list of all challenges in the series by looking at the 'Linked' section of the first challenge here.