fuglede_•1d
Show HN: Swapple, a little daily puzzle on linear reversible circuit synthesisfuglede.dk
29 comments
  • dooglius•5h

    The 'i' has more background:

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

  • ollysb•14h

    I 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.

    • hmokiguess•10h

      I agree, to this point, my expectation was that it would animate for me the combination and updated result after my choice. I had to fill that gap and it confused me at first.

    • fuglede_•13h

      Yep, I see what you're saying; let me try to clarify that part!

  • MisterMusion•2h

    Enumerating all 7-Move solutions of today's puzzle, I expected some kind simple pattern, like some key moves with a few permutations. I found that it is far more complex:

    - 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
  • Chinjut•11h

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

    • selimthegrim•5h

      This implicitly relies on row and column rank being the same.

      • Chinjut•5h

        That's not a problem, as they are the same.

        • selimthegrim•4h

          Yes, I know. It was just what my thoughts went to.

  • pekim•11h

    So if I'm understanding it correctly, it applies an xor operation on the pairs of cells. For example, click column A then column B. For each of the pairs of cells in the two columns, it performs B = A xor B.

  • jmkd•11h

    Neither 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?

  • merelysounds•9h

    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?

    • PinkRidingHood•7h

      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.

      • merelysounds•5h

        Thanks for sharing and congrats!

      • dandanua•4h

        You could use 7 row operations. row and col ops commute, and your last 3 col ops are equivalent to ('row', 1, 0), ('row', 2, 1), ('row', 3, 2) if acted on identity matrix. So, use them at first, and then your four row ops.

        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).

  • gus_massa•10h

    13 moves (I guess it's too inefficient :( )

    Feature request: I was expecting an animation (three stars and confeti!) or at least a congratulation message when I won.

    • fuglede_•9h

      The confetti is currently there for when you find a shortest solution. I'd say 13 moves deserves at least a star or two, so I'll have to add that!

  • arjvik•14h

    Reminds me of the row-echelon form algorithm we learned in algebra!

    • fuglede_•12h

      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.

      • GistNoesis•10h

        Have you tried some generic pathfinding algorithm like D star lite on the graph with heuristic being the hamming distance from current node to the start ?

        For the 4x4 board there is only 2^16 nodes, and 8*2^16 edges, so you can materialize the graph and get away with brute-forcing the whole graph.

        But for bigger boards you won't be able to materialize the whole graph.

        Maybe there are better heuristics to be found than the simple hamming distance. You should try have an AI look for them, by comparing the performance of a RL path planning vs the basic heuristic.

        • vitus•9h

          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 which ended up being faster because evaluation was much cheaper at each step, and despite these heuristics being inadmissible, they didn't result in substantially fewer nodes expanded.

          That's almost certainly a function of the problem size -- if it were 5x5, this approach would not have been as successful.

          • GistNoesis•8h

            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 so on... But not sure how much this will reduce the need to graph.

            • dooglius•3h

              Hamming distance doesn't strike me as a useful metric here because how "close" two rows are is entirely dependent on what the other rows are. E.g. if you have a row of all 1's then two rows with maximal hamming distance are only one move away and if on average you have a bunch of n/2-weight rows then two rows different by 1 bit are not close. The best you can do is count the number of total rows matching the target I think?

            • fuglede_•8h

              Thanks for sharing your thoughts!

              I know of some work on trying out various heuristics for A*; Section 5 of https://arxiv.org/pdf/2201.06508 gives some examples of what works and what doesn't. I don't think D* Lite specifically has ever featured. There's plenty of room for trying to come up with other heuristics, and just for other takes in general.

              > But for bigger boards you won't be able to materialize the whole graph.

              If we restrict to boards corresponding to solvable puzzles, the number of vertices is https://oeis.org/A002884 (1, 1, 6, 168, 20160, 9999360, 20158709760, …) and indeed grows quickly. It's possible to manipulate the 7×7 case (https://arxiv.org/abs/2503.01467, shameless plug) but anything bigger than that seems hard.

              One can ask, for example, how many moves are needed for the hardest n×n Swapple. For n = 1, …, 7 the answers are 0, 3, 6, 9, 12, 15, 18 respectively, but we don't know what the answer is for n = 8.

  • nickcw•12h

    Hmm, 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.

  • dandanua•9h

    10 moves, still not optimal

    • gaanbal•5h

      me too and I absolutely cannot remember the steps I took

  • d--b•13h

    Oof, it's brutally hard!

    • jxf•12h

      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!