Show HN: Swapple, a little daily puzzle on linear reversible circuit synthesis
1–10 of 36 posts
Re: Show HN: Swapple, a little daily puzzle on linear reversible circuit synthesis
#2Reminds me of the row-echelon form algorithm we learned in algebra!
Re: Show HN: Swapple, a little daily puzzle on linear reversible circuit synthesis
#3I found the instructions pretty confusing because you're not actually moving anything. You're combining the first selected row/column with the second selected row/column and replacing the second with the result of the combination.
Re: Show HN: Swapple, a little daily puzzle on linear reversible circuit synthesis
#4I found the instructions pretty confusing because you're not actually moving anything. You're combining the first selected row/column with the second selected row/column and replacing the second with the result of the combination.
Yep, I see what you're saying; let me try to clarify that part!
Re: Show HN: Swapple, a little daily puzzle on linear reversible circuit synthesis
#5Oof, it's brutally hard!
Re: Show HN: Swapple, a little daily puzzle on linear reversible circuit synthesis
#6Oof, it's brutally hard!
On the other hand, if you find a way to make it easier (I believe the general case is O(n²) in gates), then you've improved a very hard computer science problem!
Re: Show HN: Swapple, a little daily puzzle on linear reversible circuit synthesis
#7Reminds me of the row-echelon form algorithm we learned in algebra!
Heh, nice catch, I think you'll find that with a bit of work, you can make row reduction/Gaussian elimination work here as well. But that the resulting sequences of operations can get very long! One thing I personally like about the puzzle is that once you've played it for a few days, you start gaining some intuition about sequences of moves that are useful, but coming up with a good general algorithm (that also works for larger than 4x4 boards) is still a challenge.
Re: Show HN: Swapple, a little daily puzzle on linear reversible circuit synthesis
#8Hmm, Gaussian elimination over GF(2). Let's go!
...Some time later... This is quite hard!
I think thinking about this puzzle as Gaussian elimination is not helpful!
I think the controls would work better if you dragged the row/column onto the one want to change.
Re: Show HN: Swapple, a little daily puzzle on linear reversible circuit synthesis
#9Neither the instructions nor the interface helped me to understand what I was doing or how to achieve it, for example I don't understand why if I click a row I can't click a column next, and vice versa. From which I can only conclude that it's just not for my sort of brain.
However I'm sure there is a diverting puzzle game in here somewhere. I wonder if you used narrative language and symbolism unrelated to linear reversible circuit synthesis (but kept whatever mechanic is important) an average player might be able to grasp it more easily?
Re: Show HN: Swapple, a little daily puzzle on linear reversible circuit synthesis
#10Note 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 matrix (of size corresponding to the rank) and whose other blocks are zero. Since all moves are invertible, any two matrices of the same rank are thus connected via the same such block matrix.
In general, it is necessary to use both row and column moves. However, if both matrices are square with full rank (as in today's puzzle), one can just use row moves (or just as well, just use column moves), using just Gaussian elimination. More generally, one can just use row moves iff both matrices have the same row space, and similarly for columns.