Skip to main content
Ilmari Karonen's user avatar
Ilmari Karonen's user avatar
Ilmari Karonen's user avatar
Ilmari Karonen
  • Member for 14 years, 5 months
  • Last seen this week
revised
Is there a name for this theorem?
use \frac and \cdots instead of a fraction slash and three periods
Loading…
suggested
Approve
comment
Mathematical conjectures on which applications depend
In fact, essentially the only known encryption scheme that is unconditionally secure is the one-time pad. There are a few other cryptographic (but not encryption) primitives that don't rely on any unproven assumptions, such as Shamir's secret sharing and Carter-Wegman MACs (when used with OTP). But those are still few and far between.
Loading…
comment
The 1-step vanishing polyplets on Conway's game of life
Nice. I added another extensible family of vanishing polyominoes to my own answer. In fact, there seem to be plenty of such families.
revised
Loading…
awarded
revised
Loading…
revised
Loading…
revised
Loading…
revised
The 1-step vanishing polyplets on Conway's game of life
exhaustive search completed up to N=16, working on N=20
Loading…
comment
Vanishing line on Conway's game of life
@DavidEppstein: FYI, I replied to your comment here (to avoid fragmenting the discussion too much).
comment
The 1-step vanishing polyplets on Conway's game of life
@SebastienPalcoux: True, connectedness is a global property. But if you're generating the pattern e.g. row by row, it should be possible to keep track of the connected components of each partial pattern and to prune any extension that either a) closes off a component so that it cannot be connected to the rest of the pattern, or b) has two separate components so far apart that connecting them would require exceeding the $n$ cell limit. I'd expect the time savings from restricting the search space to be worthwhile, even with the extra cost of tracking the connected components.
comment
The 1-step vanishing polyplets on Conway's game of life
It should be pretty efficient, if you make sure to prune the search space as early as possible. For an even more efficient search, you could use something like David Eppstein's de Bruijn graph based spaceship search algorithm (which is actually directly applicable: just search for "spaceships" with speed 0 and period 1 in rule B3/S0145678) with extra pruning rules to reject patterns that are disconnected or too large.
comment
The 1-step vanishing polyplets on Conway's game of life
I guess you're doing something like generating all the $n-1$ cell polyplets, then extending each of them by one cell in every direction and removing duplicates to get the $n$ cell polyplets? That's pretty inefficient, both because you end up generating lots of duplicates, and also because you can't really do any pruning. I'd suggest a different approach; for example, you could simply start recursively filling an $n \times n$ grid from one corner with cells that are either live or dead, pruning any subpatterns that a) won't vanish, b) can't be connected or c) have more than $n$ live cells.
awarded
revised
Loading…
comment
The 1-step vanishing polyplets on Conway's game of life
Also note that 1-step vanishing patterns in standard GoL (rule B3/S23) are exactly the same as still life patterns in the "semi-complementary" rule B3/S0145678, so any existing software for exhaustively enumerating still lifes (or oscillators or spaceships) in Life-like cellular automata could be directly repurposed as long as they don't have the GoL rules hardcoded.
comment
The 1-step vanishing polyplets on Conway's game of life
I'm not familiar enough with Haskell to fully follow your code, but it looks like it's first generating the polyplets and testing them to see if they vanish. I suspect a considerably more efficient method would be to check the GoL rules during the polyplet generation (e.g. check all the neighbors of a cell whenever it is set on or off) and to prune the search space early as soon as you find a subpattern that cannot vanish.
1 2 3
4
5
9