Tutorials/Coding Life simulators/eightfold reducer - Revision history

HotdogPi: Undo revision 173216 by WhiteHawk (talk) LifeWiki:Style_guide

2026-06-07T20:14:02Z

Undo revision 173216 by WhiteHawk (talk) LifeWiki:Style_guide

← Older revision		Revision as of 20:14, 7 June 2026
Line 9:		Line 9:
	You would imagine that this article would be very short, and would explain only that if you would like to exhaustively search states in an isotropic rule, you should iterate over all 2n2 states and check for each whether it's the minimum<ref group="n">We can use integer comparisons to find the minimum if you are making a bitwise program, but if each cell is instead stored as an array element, most programming languages implement lexicographical comparisons (ie. check the first element of each against each other, then if they're equal defer to the second and third, and so on), we will be referring to this when describing values as larger or smaller than others.</ref> of its eight orientations. However, we have a more efficient convention that has more interesting properties, that may seem at first to be unnecessarily complicated but by the end you will realise to be a more natural way.		You would imagine that this article would be very short, and would explain only that if you would like to exhaustively search states in an isotropic rule, you should iterate over all 2n2 states and check for each whether it's the minimum<ref group="n">We can use integer comparisons to find the minimum if you are making a bitwise program, but if each cell is instead stored as an array element, most programming languages implement lexicographical comparisons (ie. check the first element of each against each other, then if they're equal defer to the second and third, and so on), we will be referring to this when describing values as larger or smaller than others.</ref> of its eight orientations. However, we have a more efficient convention that has more interesting properties, that may seem at first to be unnecessarily complicated but by the end you will realise to be a more natural way.

	We divide the square state into "layers," which will hereafter refer to collections of cells of the same displacement (under symmetry) from the origin, and count over each of the cells in these in binary (each layer carrying the 1 onto the beginning of the next upon overflowing, and returning to the outermost layer upon the one-carrying finishing), with the layers of lowest precedence being on the outside (from the corners to the cells at the ~~centers~~ of the edges, then again for the edges of the (n-2)*(n-2) square inside, repeating until terminating in the ~~center~~).		We divide the square state into "layers," which will hereafter refer to collections of cells of the same displacement (under symmetry) from the origin, and count over each of the cells in these in binary (each layer carrying the 1 onto the beginning of the next upon overflowing, and returning to the outermost layer upon the one-carrying finishing), with the layers of lowest precedence being on the outside (from the corners to the cells at the centres of the edges, then again for the edges of the (n-2)*(n-2) square inside, repeating until terminating in the centre).

	This all seems very arbitrary, however for each layer we store the cumulative intersection of the "symmetries" of those preceding it (further inwards).		This all seems very arbitrary, however for each layer we store the cumulative intersection of the "symmetries" of those preceding it (further inwards).

WhiteHawk at 20:12, 7 June 2026

2026-06-07T20:12:19Z

← Older revision		Revision as of 20:12, 7 June 2026
Line 9:		Line 9:
	You would imagine that this article would be very short, and would explain only that if you would like to exhaustively search states in an isotropic rule, you should iterate over all 2n2 states and check for each whether it's the minimum<ref group="n">We can use integer comparisons to find the minimum if you are making a bitwise program, but if each cell is instead stored as an array element, most programming languages implement lexicographical comparisons (ie. check the first element of each against each other, then if they're equal defer to the second and third, and so on), we will be referring to this when describing values as larger or smaller than others.</ref> of its eight orientations. However, we have a more efficient convention that has more interesting properties, that may seem at first to be unnecessarily complicated but by the end you will realise to be a more natural way.		You would imagine that this article would be very short, and would explain only that if you would like to exhaustively search states in an isotropic rule, you should iterate over all 2n2 states and check for each whether it's the minimum<ref group="n">We can use integer comparisons to find the minimum if you are making a bitwise program, but if each cell is instead stored as an array element, most programming languages implement lexicographical comparisons (ie. check the first element of each against each other, then if they're equal defer to the second and third, and so on), we will be referring to this when describing values as larger or smaller than others.</ref> of its eight orientations. However, we have a more efficient convention that has more interesting properties, that may seem at first to be unnecessarily complicated but by the end you will realise to be a more natural way.

	We divide the square state into "layers," which will hereafter refer to collections of cells of the same displacement (under symmetry) from the origin, and count over each of the cells in these in binary (each layer carrying the 1 onto the beginning of the next upon overflowing, and returning to the outermost layer upon the one-carrying finishing), with the layers of lowest precedence being on the outside (from the corners to the cells at the ~~centres~~ of the edges, then again for the edges of the (n-2)*(n-2) square inside, repeating until terminating in the ~~centre~~).		We divide the square state into "layers," which will hereafter refer to collections of cells of the same displacement (under symmetry) from the origin, and count over each of the cells in these in binary (each layer carrying the 1 onto the beginning of the next upon overflowing, and returning to the outermost layer upon the one-carrying finishing), with the layers of lowest precedence being on the outside (from the corners to the cells at the centers of the edges, then again for the edges of the (n-2)*(n-2) square inside, repeating until terminating in the center).

	This all seems very arbitrary, however for each layer we store the cumulative intersection of the "symmetries" of those preceding it (further inwards).		This all seems very arbitrary, however for each layer we store the cumulative intersection of the "symmetries" of those preceding it (further inwards).

Confocal: /* External Links */ cat

2023-03-10T08:10:22Z

External Links: cat

← Older revision		Revision as of 08:10, 10 March 2023
Line 436:		Line 436:

	[[Category:Tutorials]]		[[Category:Tutorials]]
			[[Category:Algorithms]]

HotdogPi: Category:Tutorials

2023-02-10T17:59:28Z

Category:Tutorials

← Older revision		Revision as of 17:59, 10 February 2023
Line 434:		Line 434:
	==External Links==		==External Links==
	* [https://github.com/DroneBetter/ChessPieceVision/blob/main/eightfold%20reducer.py the program]		* [https://github.com/DroneBetter/ChessPieceVision/blob/main/eightfold%20reducer.py the program]

			[[Category:Tutorials]]

Confocal: an attempted (continued) fix (hopefully) for the

 indentation splitting (by adding linebreaks around)

2023-01-03T06:42:32Z

an attempted (continued) fix (hopefully) for the <pre> indentation splitting (by adding linebreaks around)

Show changes

Confocal: attempt to add linebreaks outside

layerPriorities

to see if that improves anything

2023-01-02T18:29:57Z

attempt to add linebreaks outside <pre>layerPriorities</pre> to see if that improves anything

← Older revision		Revision as of 18:29, 2 January 2023
Line 87:		Line 87:
	self.instanceReflectionAllowednesses=tuple(tuple((i>>(8l))&((1<<8)-1) for l in range(2*t)) for t,i in zip(self.typeLengths,(0xff104050203060108090c040a02080f001114010010101108101401020202010020242102202021080028010202020200301011102030201020103012202020304104440241004400404044080808040051040500111401004104440a0208050061040402002664080960440202020600101011002010211020101102002220108180840202008408808084080808080091040102001691080990810808080900a0208502022201080808840a02080a0020101100202020102010211202220020c040444080c040408080c048808080c04040440080404400808044480880804080404400808044408080804808088080f0104500203061008090c40a02080ff,0xffff,0xff50a0f0031122030c44880c0f50a0ff,0xff1144502203661188990c44a02288ff)))		self.instanceReflectionAllowednesses=tuple(tuple((i>>(8l))&((1<<8)-1) for l in range(2*t)) for t,i in zip(self.typeLengths,(0xff104050203060108090c040a02080f001114010010101108101401020202010020242102202021080028010202020200301011102030201020103012202020304104440241004400404044080808040051040500111401004104440a0208050061040402002664080960440202020600101011002010211020101102002220108180840202008408808084080808080091040102001691080990810808080900a0208502022201080808840a02080a0020101100202020102010211202220020c040444080c040408080c048808080c04040440080404400808044480880804080404400808044408080804808088080f0104500203061008090c40a02080ff,0xffff,0xff50a0f0031122030c44880c0f50a0ff,0xff1144502203661188990c44a02288ff)))
	self.instanceReflectionPriorities=tuple(tuple(tuple(j>>(self.typeBits[m]*l)&(self.typeLengths[m]-1) for l in range(8)) for j in i) for m,i in enumerate(((0,1635557,3959123,799370,12818092,4829193,5087304,10154067,15141658,6894081,7152192,12477633,6390865,13881882,16205448,2396160,5361783,569427,1889510,1635557,9122351,5169255,5943399,5927005,6361619,11362855,12402782,10055773,12822117,13353501,13869597,10154067,9089598,5365885,827482,1667820,4297242,7033404,7807100,5927019,14849716,13226556,16130611,10055787,12818092,13353515,13869611,13881882,2433051,5361783,3522743,569427,9089598,2433051,5419134,5361783,10892350,9032247,4755483,7430255,4297242,9089598,9380413,2433051,7687617,3438995,2892993,3959123,4555976,5437313,5945800,6186817,13511624,11364801,12138945,10315585,15403353,15419208,15935304,12477633,267475,1111390,3950485,799370,6493543,340107,1979285,1700629,12945877,9205070,4985538,8152396,6390410,13091029,15930691,5058625,296154,1111411,1886122,1893731,8881523,2838843,294984,1958698,15075242,2101320,12130272,8152417,13076266,12825386,13600097,5087304,571767,841015,1357111,1635557,6460734,2773239,3547390,569427,10589502,8966391,7611191,5796581,10720500,8827070,4554842,5361783,11415432,2635393,7950145,6056715,10980634,9166024,7810824,6187713,6620808,13229825,14003976,10316481,15141658,15420104,15936200,16205448,2102931,3177118,3951829,3700949,8624798,4646943,295425,1701973,14818517,2101761,13938372,7895692,14883484,14891093,15665804,6894081,2131610,846524,3686186,799825,8624819,2204697,7572145,3831338,15076586,14797930,6850128,10283672,6390865,12826730,15665825,6922760,4299582,841911,1358007,1373862,6461630,4638270,5412414,3265591,10590398,10831415,11339902,2634259,12818092,4297242,13338220,9089598,4757184,7396802,7687617,2892993,9346960,2434752,7744968,5884865,11415432,11358081,4757184,7687617,6620808,13254472,11415432,4757184,2895333,2907604,3423700,3959123,6721428,646604,3550659,1927499,10850196,8970115,9743811,2892993,15109395,6362753,11411330,7687617,6623148,2907618,3423714,3955098,6721442,4374433,5414360,828616,10850210,10833816,11607960,7654864,15141658,14887705,6620808,11415432,585,571767,2895333,799370,4299582,38043,296154,1635557,6623148,2102931,2361042,3959123,6390865,12818092,15141658,0),(0,0),(0,13158,52377,21760,23055,10011,36174,23055,42480,29361,55524,42480,85,13158,52377,0),(0,10011,29361,13158,36174,23055,5140,10011,55524,16705,42480,29361,52377,36174,55524,0))))		self.instanceReflectionPriorities=tuple(tuple(tuple(j>>(self.typeBits[m]*l)&(self.typeLengths[m]-1) for l in range(8)) for j in i) for m,i in enumerate(((0,1635557,3959123,799370,12818092,4829193,5087304,10154067,15141658,6894081,7152192,12477633,6390865,13881882,16205448,2396160,5361783,569427,1889510,1635557,9122351,5169255,5943399,5927005,6361619,11362855,12402782,10055773,12822117,13353501,13869597,10154067,9089598,5365885,827482,1667820,4297242,7033404,7807100,5927019,14849716,13226556,16130611,10055787,12818092,13353515,13869611,13881882,2433051,5361783,3522743,569427,9089598,2433051,5419134,5361783,10892350,9032247,4755483,7430255,4297242,9089598,9380413,2433051,7687617,3438995,2892993,3959123,4555976,5437313,5945800,6186817,13511624,11364801,12138945,10315585,15403353,15419208,15935304,12477633,267475,1111390,3950485,799370,6493543,340107,1979285,1700629,12945877,9205070,4985538,8152396,6390410,13091029,15930691,5058625,296154,1111411,1886122,1893731,8881523,2838843,294984,1958698,15075242,2101320,12130272,8152417,13076266,12825386,13600097,5087304,571767,841015,1357111,1635557,6460734,2773239,3547390,569427,10589502,8966391,7611191,5796581,10720500,8827070,4554842,5361783,11415432,2635393,7950145,6056715,10980634,9166024,7810824,6187713,6620808,13229825,14003976,10316481,15141658,15420104,15936200,16205448,2102931,3177118,3951829,3700949,8624798,4646943,295425,1701973,14818517,2101761,13938372,7895692,14883484,14891093,15665804,6894081,2131610,846524,3686186,799825,8624819,2204697,7572145,3831338,15076586,14797930,6850128,10283672,6390865,12826730,15665825,6922760,4299582,841911,1358007,1373862,6461630,4638270,5412414,3265591,10590398,10831415,11339902,2634259,12818092,4297242,13338220,9089598,4757184,7396802,7687617,2892993,9346960,2434752,7744968,5884865,11415432,11358081,4757184,7687617,6620808,13254472,11415432,4757184,2895333,2907604,3423700,3959123,6721428,646604,3550659,1927499,10850196,8970115,9743811,2892993,15109395,6362753,11411330,7687617,6623148,2907618,3423714,3955098,6721442,4374433,5414360,828616,10850210,10833816,11607960,7654864,15141658,14887705,6620808,11415432,585,571767,2895333,799370,4299582,38043,296154,1635557,6623148,2102931,2361042,3959123,6390865,12818092,15141658,0),(0,0),(0,13158,52377,21760,23055,10011,36174,23055,42480,29361,55524,42480,85,13158,52377,0),(0,10011,29361,13158,36174,23055,5140,10011,55524,16705,42480,29361,52377,36174,55524,0))))
	</pre>The typeLengths tells you the number of cells in a layer of each type, and typeBits the log base 2 of this. For a layer with the type t, there are 2**typeLengths[t] possible states. We store in instanceReflectionAllowednesses, for each layer type, a list of states, and within each of these a symmetry byte describing whether each reflection makes them minimal or not (which can be determined in one of many ways but we use an empty state containing only the layer and compare lexicographically). In instanceReflectionPriorities, we similarly have a list of states for layers, except each state containing the rank of the result of each reflection in the sorted list of reflections. The idea is that we will be able to begin by going through the layers, beginning with an all-1s symmetry byte, and recursively bitwise AND it with each layer's corresponding instanceReflectionAllowednesses element, until we reach the end of the layers or a point at which doing so would make the symmetry byte zero, because all actions that would make the current layer minimal are ones we've already disqualified in prior layers, so we switch to instead disqualifying those that don't lead to the resultant state's rank being minimal of those left allowed. The lists are decoded from integers that will be explained later.<pre>		</pre>The typeLengths tells you the number of cells in a layer of each type, and typeBits the log base 2 of this. For a layer with the type t, there are 2**typeLengths[t] possible states. We store in instanceReflectionAllowednesses, for each layer type, a list of states, and within each of these a symmetry byte describing whether each reflection makes them minimal or not (which can be determined in one of many ways but we use an empty state containing only the layer and compare lexicographically). In instanceReflectionPriorities, we similarly have a list of states for layers, except each state containing the rank of the result of each reflection in the sorted list of reflections. The idea is that we will be able to begin by going through the layers, beginning with an all-1s symmetry byte, and recursively bitwise AND it with each layer's corresponding instanceReflectionAllowednesses element, until we reach the end of the layers or a point at which doing so would make the symmetry byte zero, because all actions that would make the current layer minimal are ones we've already disqualified in prior layers, so we switch to instead disqualifying those that don't lead to the resultant state's rank being minimal of those left allowed. The lists are decoded from integers that will be explained later.

			<pre>
	layerPriorities=(lambda layer,type: self.instanceReflectionPriorities[type][self.ORsum(l<<i for i,l in enumerate(layer))])		layerPriorities=(lambda layer,type: self.instanceReflectionPriorities[type][self.ORsum(l<<i for i,l in enumerate(layer))])
	def constructCellular(self,layers):		def constructCellular(self,layers):
Line 99:		Line 101:
	return(tuple(output))		return(tuple(output))
	setLayers=(lambda self,state: (lambda layers: (layers,[self.ORsum(m<<i for i,m in enumerate(l)) for l in layers]))([list(map((lambda l: state>>self.BIAS+l%boardWidthself.cellWidth+l//boardWidthself.COLSHIFT&1) if self.bitwise else state.__getitem__,l)) for l in unreflectedLayerIndices]))		setLayers=(lambda self,state: (lambda layers: (layers,[self.ORsum(m<<i for i,m in enumerate(l)) for l in layers]))([list(map((lambda l: state>>self.BIAS+l%boardWidthself.cellWidth+l//boardWidthself.COLSHIFT&1) if self.bitwise else state.__getitem__,l)) for l in unreflectedLayerIndices]))
	</pre>layerPriorities converts an input layer to a symmetry byte (with our little-endian indexing convention), and constructCellular converts a list of layers back into a state. setLayers converts a state to two lists, layers and layerNumbers (the latter being only generating an integer for indexing in the instance lists, the first step of layerPriorities, for our convenience). Now, onto the reflection functions.		</pre>

			layerPriorities converts an input layer to a symmetry byte (with our little-endian indexing convention), and constructCellular converts a list of layers back into a state. setLayers converts a state to two lists, layers and layerNumbers (the latter being only generating an integer for indexing in the instance lists, the first step of layerPriorities, for our convenience). Now, onto the reflection functions.

	Firstly, functions to change indexes to correspond with reflections through a single axis (where x is 0, y is 1 and the x=y line of symmetry is 2). These will go in the __init__ function, as you will see the reason for shortly.<pre>		Firstly, functions to change indexes to correspond with reflections through a single axis (where x is 0, y is 1 and the x=y line of symmetry is 2). These will go in the __init__ function, as you will see the reason for shortly.<pre>

DroneBetter: Create (I don't know how to fix the indentation splitting

's into multiple segments, the problem seems somewhat worse in this article (being that it's comprised of more indented parts and trees and such)), more explaining may be necessary later

2023-01-02T17:43:50Z

Create (I don't know how to fix the indentation splitting <pre>'s into multiple segments, the problem seems somewhat worse in this article (being that it's comprised of more indented parts and trees and such)), more explaining may be necessary later

Show changes

Tutorials/Coding Life simulators/eightfold reducer - Revision history

HotdogPi: Undo revision 173216 by WhiteHawk (talk) LifeWiki:Style_guide

WhiteHawk at 20:12, 7 June 2026

Confocal: /* External Links */ cat

HotdogPi: Category:Tutorials

Confocal: an attempted (continued) fix (hopefully) for the
indentation splitting (by adding linebreaks around)

Confocal: attempt to add linebreaks outside
layerPriorities
to see if that improves anything

DroneBetter: Create (I don't know how to fix the indentation splitting
's into multiple segments, the problem seems somewhat worse in this article (being that it's comprised of more indented parts and trees and such)), more explaining may be necessary later