Is it a canonical elementary CA rule number?

Question

Background

Given an elementary cellular automaton rule number like, for example, 28 = 00011100...

description of rule 28

• We can swap \$\color{red}{\text{the 2nd bit with the 5th bit}}\$ and \$\color{orange}{\text{the 4th bit with the 7th bit}}\$ to get a rule that acts the same way but mirrored horizontally. This gets us 01000110 = 70.
• We can reverse and flip all the bits to get a rule that does the same thing but with black and white reversed: 11000111 = 199.
• And we can combine these two processes — it doesn't matter which order we apply them in — to get a mirrored, reversed rule: 10011101 = 157.

Or, as MathWorld puts it:

The mirror image, complement, and mirror complement are rules 70, 199, and 157, respectively.

The automata identified by rules {28, 70, 199, 157} all behave the same way, up to arbitrary distinctions of colors and axis orientation. But because 28 is the lowest of these four numbers, it is the "canonical" rule number.

Task

Write a program or function that takes an input \0ドル \leq n \leq 255\$ and decides whether it is a canonical rule number.

These 88 inputs should be give a "true" result:

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 18 19 22 23 24 25 26 27 28 29 30 32 33 34 35 36 37 38 40 41 42 43 44 45 46 50 51 54 56 57 58 60 62 72 73 74 76 77 78 90 94 104 105 106 108 110 122 126 128 130 132 134 136 138 140 142 146 150 152 154 156 160 162 164 168 170 172 178 184 200 204 232

and all other inputs should give a "false" result.

This is code-golf. The I/O defaults apply.

• doug: Not that it affects the statement of the challenge but don’t rule 28 and 199 produce the same result for both 1 1 0 and 0 1 0 and not inverse results? I.e. the 2nd and 5th bits are the same.
• lynn: @doug I don't understand what you mean, sorry. Counting the leftmost / most significant bit as the first bit, the 2nd bit of 28 is 0 and the 2nd bit of 199 is 1.
• doug: However you mean to count if you line up the binary representation some bits in the same position agree.
• lynn: By "reverse and flip" I mean that abcdefgh becomes HGFEDCBA, if uppercase means NOT. You have to invert all the output colors (0 ↔ 1) but also the input colors (which happens to correspond to reversing the bit order).
• lynn: Maybe to see why this works, you can literally invert the image i.sstatic.net/02nbY.png — now the "black black black" rule is all the way on the right, "black black white" is to its left, etc and to restore the original order we would have to exactly reverse the 8 boxes.

Answer 1

Jelly, 18 bytes

^{I imagine there may be a shorter hashing based Link that any approach like this, but finding it might take a while ;p}

+9BḊ(¦hœ?,ƊU¬;ƊḄṂ=

A monadic Link that accepts an integer from \$[0,255]\$ and yields \1ドル\$ if connonical, else \0ドル\$.

Try it online!

How?

+9BḊ(¦hœ?,ƊU¬;ƊḄṂ= - Link: integer, Rule
+9 - {Rule} add 256
 B - convert to binary
 Ḋ - dequeue (remove the leading 256-bit)
 Ɗ - last three links as a monad f(Rule-Byte=that):
 (¦h - 2355
 œ? - {2355}th permutation of {Rule-Byte}
 (swap bit 2 with bit 5 and bit 4 with bit 7)
 , - pair with {Rule-Byte}
 Ɗ - last three links as a monad f(Mirrors=that):
 U - reverse each
 ¬ - logical Not
 ; - concatenate {Mirrors}
 Ḅ - convert from binary
 Ṃ - minimum
 = - equals {Rule}?

Answer 2

Nekomata, 19 bytes

\+Ƃi:↔¬?:Jĭ,Ťđ,?ƃa≤

Attempt This Online!

\+Ƃi:↔¬?:Jĭ,Ťđ,?ƃa≤
\+ Add 256 to ensure that binary length is 9
 Ƃ Binary digits; least significant bit comes first
 i Remove the last digit (the 1 from the 256)
 Now the list contains exactly 8 digits
 : ? Optional apply:
 ↔¬ Reverse and logical NOT
 : ? Optional apply:
 Jĭ,Ťđ, Swap the 2nd and 5th digits, and the 4th and 7th digits
 ƃ Convert from binary to decimal
 a≤ Check that all possible values are greater than or equal to the input

Answer 3

Python, 95 bytes

lambda x:x==min(z for y in(x,256+~int(f'{x:08b}'[::-1],2))for z in(y,y&165|(y&80)>>3|(y&10)*8))

Attempt This Online!

• gsitcia: you can use 255^... instead of 256+~... to flip the bits

Answer 4

Python 3, 61 bytes

lambda i:61!=i<=255^int(f'{i:08b}'[::-1],2)!=194>i*8&80>=i&80

Try it online!

Answer 5

JavaScript (ES11), 54 bytes

Expects a BigInt. Returns 1 for canonical or 0 for non-cannonical.

n=>0x10005012777AFFA0F0A0F0FAFFFAFFn>>n%2n*64n+n/2n&1n

Try it online!

We take advantage of the following properties to reduce the size of the lookup bit-mask:

$$f(2k+128)=f(2k+1),\:0\le k<64$$ $$f(2k+1)=0,\:k>52$$

---

JavaScript (ES6), 75 bytes

Returns 0 for canonical or 1 for non-cannonical.

n=>(g=n=>n&165|n/8&10|n*8&80)(n)<n|(h=i=>q=i--&&~n>>i&1|2*h(i))(8)<n|g(q)<n

Try it online!

Answer 6

J, 36 bytes

=[:<./(,&(,:2354&A.)1-|.)@{.~&_8&.#:

Try it online!

Constructs all possible representations according to the spec, and checks if the input is the min of those.

• Conor O'Brien: That's beautiful, especially using a negative number to ensure padding, as well as that trick with ,& to apply the anagram transformation. Kudos!
• Conor O'Brien: An alternative that avoids the cap starts with */@:<:, also 36b; I had that fragment in my original (albeit much much longer) solution which generated only the 3 transformations, eschewing the original input. Not sure if that path leads to any saved bytes in your solution, though.
• Jonah: @ConorO'Brien Thanks. */@:<: is a nice insight. In theory it means you only have to return the 3 transforms and not the original, but I didn't see an obvious to take advantage of it -- I still needed to use the original in the calcs to get the other 3. Might be a way though.

Answer 7

sclin, 65 bytes

"256+2X>b1dp."Q"2b>X"map"&"fold~ =
["""_` ! ""perm2354:""++"Q ] Q

Try it here!

For testing purposes:

28 ;
"256+2X>b1dp."Q"2b>X"map"&"fold~ =
["""_` ! ""perm2354:""++"Q ] Q

Explanation

Prettified code:

\; Q 2.b>X map \& fold~ =
256+ 2X>b 1dp.
["" "_` ! " "perm2354:" \++ Q ] Q

Assuming input n:

• 256+ 2X>b 1dp convert n + 256 to binary and drop 0th bit
  • i.e. convert n to binary digits, padded to length 8
• [ "" "_` ! " "perm 2354:" \++ Q ] Q vectorized-evaluate the binary digits over the following...
  • "" just return the digits
  • "_` ! " reverse array + vectorized-NOT
  • "perm 2354:" 2354th permutation
  • \++ Q get concatenation of previous 2 strings
• 2.b>X map convert back to decimal
• \& fold~ minimum
• = check if equal to n

Answer 8

Charcoal, 39 bytes

⊞υΦ↨+256N2κ⊞υE04261537§⌊υIι¬⌕υ⌊+υEυ−1⮌ι

Try it online! Link is to verbose version of code. Explanation:

⊞υΦ↨+256N2κ

Convert the input to base 2 padded to 8 digits and push the result to the predefined empty list.

⊞υE04261537§⌊υIι

Apply the permutation to the result given by reflecting the binary for each index and push that.

¬⌕υ⌊+υEυ−1⮌ι

Logically invert and reverse each of the two results and check that the minimum of the four values is the original input.

Answer 9

K (ngn/k), 42 bytes

{x~&//2/''(~|:')1円@[;|815637664円]\(8#2)\x}

Try it online!

Answer 10

Retina, 118 bytes

.+
*
8+`^(_*)1円(_?)
1ドル$.2
(.)(.)(.)(.)(.)(.)(.)(.)
$&¶$&¶1ドル5ドル3ドル7ドル2ドル6ドル4ドル8ドル
¶(.+)
¶$^1ドル$&
T`d`10`¶(.+)¶
O`¶(.+)
^(.+)¶1円

Try it online! Link includes test suite. Explanation:

.+
*

Convert to unary.

8+`^(_*)1円(_?)
1ドル$.2

Convert to 8 bits of binary.

(.)(.)(.)(.)(.)(.)(.)(.)
$&¶$&¶1ドル5ドル3ドル7ドル2ドル6ドル4ドル8ドル

Duplicate the input, then append the shuffled input.

¶(.+)
¶$^1ドル$&

Duplicate both new rows but with the bits reversed.

T`d`10`¶(.+)¶

Complement the bits in the reversed rows.

O`¶(.+)

Sort all the rows except the very original.

^(.+)¶1円

Check that the first of the sorted rows is the same as the original.

Answer 11

05AB1E, 23 bytes

^{Should have been 20 bytes, but there is a bug in the \$n^{th}\$ permutation builtin .I for bit-lists..}

1+2в¦Dā<Ž9x.Iè‚Dí_«JCßQ

Try it online or verify all truthy test cases.

Explanation:

1+ # Add 256 to the (implicit) input-integer
 2в # Convert it to a binary-list (this cannot be a binary-string,
 # because builtin `.I` only works with lists)
 ¦ # Remove the first 1 to 'subtract' the 256 again
 D # Duplicate this bit-list
 ā< # Workaround part 1 of 2: Push a list in the range [0,length)
 # without popping the list itself
 Ž9x # Push compressed integer 2354
 .I # Get the 2354th permutation of the [0,length) list
 è # Workaround part 2 of 2: Index those into the duplicated bit-list
 ‚ # Pair the two bit-lists together
 D # Duplicate this pair
 í # Reverse each inner list
 _ # And negate each with an ==0 check
 « # Merge the two pairs together
 JC # Convert the inner bit-lists to integers
 ß # Pop and push the minimum
 Q # Check whether it's equal to the (implicit) input-integer
 # (after which the result is output implicitly)

Answer 12

JavaScript (V8), 135 bytes

x=>/^(.|2[^01]|[37][^0159]|[369]0|4[0-6]|5[^2359]|35|62|94|1([^67]|0[458]|10|22|[3-7][02]|[2367]8|[3568]4|[02-5]6)|20[04])$|32/.test(x)

Try it online!

Can't wait for Deadcode to outgolf this :-)