Page 1 of 1
Frequencies of various NxN patterns
Posted: September 25th, 2015, 7:08 pm
by praosylen
I am interested in knowing what the most/least common patterns (not necessarily stable) that can occur inside a NxN square. I know that there was some census of 3x3 patterns done with relation to the backtracking searcher a while back, but I'm not sure that exact issue was addressed. I believe that for all grid sizes, the most common pattern is empty space, but the question of the least common pattern is more difficult to answer. I think that for 2x2, the solution is
.
For 3x3, there are a number of options that I would consider:
Code: Select all
x = 63, y = 3, rule = B3/S23
3o2b3o2b3o2bobo2bobo2b2o3bobo2bobo2bo4b2o3bo4bo5bo$3o2b3o2b3o2b2o3b2o
4bo4bo3b3o2b3o12bobo3b2o$3o3b2o2bobo2b3o3b2o2bobo2bobo2bobo2bobo2bobo
2bobo2bobo2b3o!
I think 4x4 is a much more difficult question to answer. There are a multitude of options to choose from (not just these):
Code: Select all
x = 53, y = 4, rule = B3/S23
2obo3b4o2b2obo2bob2o4bo3b2o4bo2bo2bobo3b2obo$obo4b2obo3bobo2b2obo2b2o
6b2o2b4o3b3o3bo$bobo3bob2o2bobo3bob2o4b2o2b2o4b4o2b4o2bob2o$ob2o3b4o2b
ob2o2b2obo3bo6b2o2bo2bo3b3o3bobo!
This problem cannot continue indefinitely to larger grid sizes; GoE patterns would have a frequency of exactly zero.
Re: Frequencies of various NxN patterns
Posted: September 25th, 2015, 8:21 pm
by simsim314
A for awesome wrote:I am interested in knowing what the most/least common patterns
First of all when you're talking about common pattern - you need to make few choices:
1. What is the initial pattern.
2. For how long do you evolve it.
3. From what generation you start calculating popularity.
I've a small utility that worked hardcoded for 5x5, and it gave some results. Obviously the most common is empty square, after that one cell on the border, then two cells etc. After a while it start to get a bit more interesting.
Anyway you can check out the
Predecty project on GitHub specifically
StatsCollector.cpp
Re: Frequencies of various NxN patterns
Posted: September 25th, 2015, 8:44 pm
by gameoflifeboy
A for awesome wrote:I am interested in knowing what the most/least common patterns (not necessarily stable) that can occur inside a NxN square.
EDIT: I didn't see the words "not necessarily stable". Sorry if this wasn't what you wanted.
I once made an apgsearch hack for just this purpose. Not sure how well I made it, other than that it works on at least two computers. I can provide my code if anyone wants.
After 2 1/2 minutes of searching I got this census for 65536 4x4 soups:
Code: Select all
xs4_33 71043
xp2_7 65040
xs6_696 40784
xq4_153 21280
xs7_2596 7956
xs5_253 7648
xs6_356 6020
xs8_6996 5062
xs4_252 920
xs12_g8o653z11 676
xs7_25ac 476
xs14_g88m952z121 384
xp2_7e 232
xs6_25a4 80
xs8_69ic 80
xp3_co9nas0san9oczgoldlo0oldlogz1047210127401 64
xs6_39c 64
xp2_318c 48
xs6_bd 24
xs10_g8o652z01 24
xs8_35ac 22
xs8_25ak8 12
xs16_g88m996z1221 8
xs7_178c 8
xq4_6frc 8
xp2_2a54 4
You can see my results for 5x5 (formatted, and with object names) here:
viewtopic.php?f=2&t=1141&p=21106&hilit=5x5#p21106
Re: Frequencies of various NxN patterns
Posted: September 25th, 2015, 9:22 pm
by simsim314
Here is a report of the 78 most common 5x5 patterns (up to symmetry) with their relative frequency:
Code: Select all
1 : 9223372036854M
.....
.....
.....
.....
.....
2 : 40185M
.....
.....
.....
.....
O....
3 : 16087M
...OO
.....
.....
.....
.....
4 : 12943M
.....
.....
.....
.....
.O...
5 : 11137M
.OO..
.....
.....
.....
.....
6 : 10490M
.....
.....
.....
.....
..O..
7 : 7842M
.O...
O....
.....
.....
.....
8 : 5380M
.....
.....
.....
...OO
...OO
9 : 4954M
.....
.....
..OO.
..OO.
.....
10 : 4928M
.....
.....
...OO
...OO
.....
11 : 4579M
.OOO.
.....
.....
.....
.....
12 : 4172M
OOO..
.....
.....
.....
.....
13 : 3202M
...OO
....O
.....
.....
.....
14 : 2936M
.....
.....
.....
...O.
...O.
15 : 2523M
.....
....O
...O.
....O
.....
16 : 2492M
.....
.....
.....
...OO
..O..
17 : 2457M
O.O..
.O...
.....
.....
.....
18 : 2442M
.....
.O...
.O...
.O...
.....
19 : 2438M
.....
.....
.OOO.
.....
.....
20 : 2348M
.....
.....
.....
.O...
O....
21 : 2084M
.....
.....
.....
..OO.
.O..O
22 : 2067M
...O.
...OO
.....
.....
.....
23 : 1912M
.....
OOO..
.....
.....
.....
24 : 1812M
.....
.....
OO...
.....
.....
25 : 1554M
.....
.....
.....
.....
..O.O
26 : 1508M
.....
.....
..O..
..O..
..O..
27 : 1422M
.....
.....
.....
.....
.O.O.
28 : 1382M
.....
.....
.....
...O.
...OO
29 : 1325M
.....
.....
...OO
..O..
...OO
30 : 1312M
.....
.OO..
O..O.
.OO..
.....
31 : 1306M
.....
.....
..OO.
.O..O
..OO.
32 : 1304M
.....
...OO
..O..
...OO
.....
33 : 1112M
O.O..
OO...
.....
.....
.....
34 : 1023M
.....
.....
.....
....O
..OO.
35 : 992M
..O.O
..OO.
.....
.....
.....
36 : 973M
.....
.....
.....
...O.
..O..
37 : 968M
.O.O.
.OO..
.....
.....
.....
38 : 803M
.....
.....
.....
.....
O...O
39 : 800M
..OO.
...O.
.....
.....
.....
40 : 762M
..OO.
...OO
.....
.....
.....
41 : 723M
.OO..
..O..
.....
.....
.....
42 : 717M
.....
.....
.....
..O..
.O...
43 : 698M
..O..
..OOO
.....
.....
.....
44 : 624M
.....
.....
.....
O....
O.O..
45 : 617M
.....
.....
.....
...O.
.OO..
46 : 612M
.....
.....
O....
.O...
..O..
47 : 600M
.....
.....
.....
..O..
OO...
48 : 599M
OO...
.OO..
.....
.....
.....
49 : 582M
.OO..
..OO.
.....
.....
.....
50 : 580M
....O
.....
.....
.....
O....
51 : 572M
...O.
...O.
...O.
.....
OO...
52 : 572M
.....
.....
...O.
...O.
...OO
53 : 569M
.....
...O.
...O.
...OO
.....
54 : 568M
.....
.....
.....
..O..
..O.O
55 : 561M
...O.
...O.
.....
OO...
.....
56 : 557M
..OOO
.....
O....
O....
O....
57 : 548M
.....
.....
.....
.O...
.O.O.
58 : 543M
.....
.....
.....
O.O..
OO...
59 : 533M
.....
.....
.....
.O...
OOO..
60 : 532M
.....
.....
.....
..O.O
..OO.
61 : 528M
.....
.....
....O
..OO.
...OO
62 : 524M
.....
.....
.....
.O.O.
.OO..
63 : 518M
.....
.....
O....
O.O..
OO...
64 : 518M
.....
.....
...O.
..O..
..OOO
65 : 518M
.....
.....
O.O..
OO...
.O...
66 : 518M
.....
O.O..
OO...
.O...
.....
67 : 516M
.....
.....
..O..
..O.O
..OO.
68 : 516M
.....
.O...
O....
OOO..
.....
69 : 515M
.....
.....
..O..
.O...
.OOO.
70 : 514M
...O.
..O..
..OOO
.....
.....
71 : 513M
.....
..O..
.O...
.OOO.
.....
72 : 511M
.....
.....
.O.O.
.OO..
..O..
73 : 511M
.....
...O.
.OO..
..OO.
.....
74 : 511M
..O..
.O...
.OOO.
.....
.....
75 : 510M
.....
.....
..O.O
..OO.
...O.
76 : 510M
.....
...O.
..O..
..OOO
.....
77 : 510M
.....
....O
..OO.
...OO
.....
78 : 508M
.....
..O.O
..OO.
...O.
.....