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.
Show HN: Swapple, a little daily puzzle on linear reversible circuit synthesis
11–20 of 36 posts
Re: Show HN: Swapple, a little daily puzzle on linear reversible circuit synthesis
#12Reminds 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 work…
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.
Re: Show HN: Swapple, a little daily puzzle on linear reversible circuit synthesis
#13I 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.
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.
Re: Show HN: Swapple, a little daily puzzle on linear reversible circuit synthesis
#1413 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.
Re: Show HN: Swapple, a little daily puzzle on linear reversible circuit synthesis
#1510 moves, still not optimal
Re: Show HN: Swapple, a little daily puzzle on linear reversible circuit synthesis
#16Earlier quoted context omitted.
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 work…
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 tha…
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.
Re: Show HN: Swapple, a little daily puzzle on linear reversible circuit synthesis
#1713 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.
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!
Re: Show HN: Swapple, a little daily puzzle on linear reversible circuit synthesis
#18Spoiler 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?
Re: Show HN: Swapple, a little daily puzzle on linear reversible circuit synthesis
#19Earlier quoted context omitted.
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 tha…
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 so on... But not sure how much this will reduce the need to graph.
Re: Show HN: Swapple, a little daily puzzle on linear reversible circuit synthesis
#20Earlier 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…
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.