tag:blogger.com,1999:blog-37404288.post2947909129018849708..comments2023-11-02T14:40:18.756+01:00Comments on JP Moresmau's Programming Blog: Rust helped me escape Cthulhu!JP Moresmauhttp://www.blogger.com/profile/09964251063221757176noreply@blogger.comBlogger1125tag:blogger.com,1999:blog-37404288.post-86173191078275791562019-02-10T18:47:55.570+01:002019-02-10T18:47:55.570+01:00I believe I found a direct way: you can flip preci...I believe I found a direct way: you can flip precisely the bit in the (i,j) position as follows: perform the swap operation on all the squares in the i-th row and in the j-th column (i.e. flip in terms of swaps is defined exactly as swap in terms of flips).<br />Then you can simply collect all swaps as above for all the bits in the starting position and you're done.<br />But we can do better because the swap operations commute (this is not obvious and I only checked by drawing a picture) and are involutive, so you can actually reduce multiplicities of every swap mod 2, giving a shortest path (which is likely what your path search found).<br />This also shows that 16 swaps always suffice. And I believe 16 are also required for the position where the whole board needs to be flipped.twoldhttps://www.blogger.com/profile/07368869740412839184noreply@blogger.com