21–30 of 36 posts
Spoiler warning, this comment contains a solution, this is your chance to stop reading, especially if you didn’t have a chance to play yet. With 8 moves and rows only: 2->1, 1->2, 2->1, 3->2, 2->3, 4->3, 4->1, 1->4. A more efficient solution should be possible; did anyone find any?
10 moves, still not optimal
Note that two matrices (of the same dimensions) can be transformed into each other if and only if they have the same rank. A (non-optimal, but straightforward) procedure for doing so is like so: First, use Gaussian elimination row-wise to put any matrix into reduced row echelon form. One can now use Gaussian elimination column-wise to transform the matrix into a 2x2 block matrix whose upper-left block is an identity…
Spoiler warning, this comment contains a solution, this is your chance to stop reading, especially if you didn’t have a chance to play yet. With 8 moves and rows only: 2->1, 1->2, 2->1, 3->2, 2->3, 4->3, 4->1, 1->4. A more efficient solution should be possible; did anyone find any?
I found one using a program: [('row', 0, 1), ('row', 1, 2), ('row', 2, 0), ('row', 0, 3), ('col', 2, 3), ('col', 1, 2), ('col', 0, 1)]. It says it's the optimal.
Note that two matrices (of the same dimensions) can be transformed into each other if and only if they have the same rank. A (non-optimal, but straightforward) procedure for doing so is like so: First, use Gaussian elimination row-wise to put any matrix into reduced row echelon form. One can now use Gaussian elimination column-wise to transform the matrix into a 2x2 block matrix whose upper-left block is an identity…
This implicitly relies on row and column rank being the same.
> The game is inspired by the synthesis of linear reversible circuits; a problem in reversible and quantum computation. Here, the goal is to construct a target operation, the target pattern in Swapple, using a sequence of simpler operations, specifically controlled NOT (CNOT) gates, which flip the state of a target bit if and only if a control bit is set. In Swapple, each row and column operation corresponds to applying a CNOT gate. Your task is to find a sequence of these gates, i.e. a circuit, that transform the initial configuration, corresponding to an empty circuit, into the target configuration. Moreover, finding one of the shortest sequences of moves to achieve this goal corresponds to finding one of the most efficient circuits that implements the desired operation.
Spoiler warning, this comment contains a solution, this is your chance to stop reading, especially if you didn’t have a chance to play yet. With 8 moves and rows only: 2->1, 1->2, 2->1, 3->2, 2->3, 4->3, 4->1, 1->4. A more efficient solution should be possible; did anyone find any?
I found one using a program: [('row', 0, 1), ('row', 1, 2), ('row', 2, 0), ('row', 0, 3), ('col', 2, 3), ('col', 1, 2), ('col', 0, 1)]. It says it's the optimal.
Alternatively, you could use 7 col. Your 4 row ops are equivalent to ('col', 3, 0), ('col', 0, 2), ('col', 2, 1), ('col', 1, 0).
Earlier quoted context omitted.
I tried implementing A* using pointwise Hamming distance, found that it was inadmissible (since it yielded a suboptimal result on par with my manual attempt), then tried again with row-wise Hamming distance but was pretty sure that's inadmissible too (although it did yield an optimal result). I then tried min(row-Hamming, column-Hamming) but I'm not convinced that's admissible either. I then switched to pure Dijkstra…
You may need to add some factor for the Hamming distance to make it admissible. On a 4x4 board each move change at most 4 bits. So 4 x the hamming distance should be OK. Edit: I 'm maybe getting this wrong confusing lower bound and upper bound. Sorry I'm a little rusty. Edit2: For 4x4 one lower bound is hamming distance/4 , because you need at least these many moves to reach the goal. For 5x5 hamming distance / 5 and…
- there are 1536 solutions
- almost all moves are useful, non are required
- for every row-xoring move there is exactly one column-xoring move that appears in the same number of solutions (and no move appears twice in a solution)
Here is the number of solutions a move appears in (0-based indices):
C3→2 R2→3 0
C3→1 R2→1 82
C2→0 R3→0 93
C0→3 R0→2 163
C2→1 R3→1 342
C1→3 R1→2 426
C1→2 R1→3 558
C3→0 R2→0 614
C2→3 R3→2 640
C1→0 R1→0 726
C0→1 R0→1 810
C0→2 R0→3 922