Show HN: Swapple, a little daily puzzle on linear reversible circuit synthesis • Hacker News Board

Re: Show HN: Swapple, a little daily puzzle on linear reversible circuit synthesis

#31

Post by vitus » Mon, Sep 29, 2025, 9:42 PM UTC

dooglius wrote: post #29

GistNoesis wrote: post #19

Earlier quoted context omitted.

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…

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…

Yeah, that was what I tried with row-Hamming / col-Hamming (namely: treat entire rows / cols as matches or not). I then used the min of the two to address those issues.

Either way, I guess my implementation had a bug -- A* does yield a significant speedup, but adding the 0.25x scaling factor to ensure that the heuristic is admissible loses almost all of those gains.

For some concrete numbers: with the bug that basically reduced to BFS, it ran in about 7s; with the bug fixed but a wildly inadmissible heuristic, it ran in about 0.01s; with the heuristic scaled down by 4x to guarantee its admissibility, it ran in about 5s.

I think scaling it down by 2x would be sufficient: that lower bound would be tight if the problem is one row move and one column move away from the goal state, but potentially all four rows and columns would not match. In that case, it ran in about 1.6s.

Re: Show HN: Swapple, a little daily puzzle on linear reversible circuit synthesis

#32

Post by [deleted] » Tue, Sep 30, 2025, 6:55 AM UTC

MisterMusion wrote: post #30

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…

[deleted]

Re: Show HN: Swapple, a little daily puzzle on linear reversible circuit synthesis

#33

Post by fuglede_ » Tue, Sep 30, 2025, 6:59 AM UTC

MisterMusion wrote: post #30

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…

That's nifty! There's a lot of symmetry that can help to boil it down. For example, you actually only need row moves, and any solution with column moves can canonically be turned into one with row moves; post-composing with Ci→j is pre-composing with Rj→i.

One can think of the set of all possible board configurations as the vertices as a graph, with edges indicating how to move between configurations. Then your 1536 solutions are the 1536 distinct shortest paths between the starting and target configuration.

Then, you can also choose to consider not just board configurations, but board configurations up to simultaneous permutation of rows and columns; that will also reduce the number of unique solutions.

Re: Show HN: Swapple, a little daily puzzle on linear reversible circuit synthesis

#34

Post by fuglede_ » Tue, Sep 30, 2025, 11:52 AM UTC

jxf wrote: post #6

d--b wrote: post #5

Oof, 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!

Yeah, the problem is in a sense solved asymptotically by the optimal construction in https://arxiv.org/abs/quant-ph/0302002, but that one tends to lead to long solutions in practice, so there's plenty of room to try to come up with solutions that give shorter solutions for concrete instances.

Re: Show HN: Swapple, a little daily puzzle on linear reversible circuit synthesis

#35

Post by cpcallen » Wed, Oct 01, 2025, 8:16 AM UTC

Seems interesting but for some reason on Chrome on my iPhone 13 mini the page is too big for the screen: I have to pinch zoom out to see the X that dismisses the instructions, and can't scroll the about page.

Did you make some assumptions about the minimum window / screen size based on oversized modern smartphones, forgetting that lots of us still cling to more reasonably sized older devices?

Re: Show HN: Swapple, a little daily puzzle on linear reversible circuit synthesis

#36

Post by fuglede_ » Sat, Oct 04, 2025, 8:55 AM UTC

cpcallen wrote: post #35

Seems interesting but for some reason on Chrome on my iPhone 13 mini the page is too big for the screen: I have to pinch zoom out to see the X that dismisses the instructions, and can't scroll the about page. Did you make some assumptions about the minimum window / screen size based on oversized modern smartphones, forgetting that lots of us still cling to more reasonably sized older devices?

Hm, yeah, tested it down to about 500 px width, and the low-resolution devices in Chromium but that was too optimistic then. The modals should of course be closeable, and both game boards simultaneously visible. Played around with the modals a bit, so maybe it works better now?