17
\$\begingroup\$

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 . The I/O defaults apply.

Improve this question
\$\endgroup\$
8
  • \$\begingroup\$ 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. \$\endgroup\$ Commented Aug 26, 2023 at 5:52
  • \$\begingroup\$ @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. \$\endgroup\$ Commented Aug 26, 2023 at 12:16
  • \$\begingroup\$ However you mean to count if you line up the binary representation some bits in the same position agree. \$\endgroup\$ Commented Aug 26, 2023 at 12:37
  • \$\begingroup\$ 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). \$\endgroup\$ Commented Aug 26, 2023 at 12:50
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ Commented Aug 26, 2023 at 12:54

12 Answers 12

Reset to default
7
\$\begingroup\$

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

+⁹BḊ⁽¦hœ?,ƊU¬;ƊḄṂ⁼

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

Try it online!

How?

+⁹BḊ⁽¦hœ?,ƊU¬;ƊḄṂ⁼ - Link: integer, Rule +⁹ - {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}?
Improve this answer
\$\endgroup\$
6
\$\begingroup\$

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
Improve this answer
\$\endgroup\$
5
\$\begingroup\$

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!

Improve this answer
\$\endgroup\$
1
  • 2
    \$\begingroup\$ you can use 255^... instead of 256+~... to flip the bits \$\endgroup\$ Commented Aug 26, 2023 at 1:53
4
\$\begingroup\$

Python 3, 61 bytes

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

Try it online!

Improve this answer
\$\endgroup\$
4
\$\begingroup\$

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!

Improve this answer
\$\endgroup\$
3
\$\begingroup\$

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.

Improve this answer
\$\endgroup\$
3
  • 1
    \$\begingroup\$ That's beautiful, especially using a negative number to ensure padding, as well as that trick with ,& to apply the anagram transformation. Kudos! \$\endgroup\$ Commented Aug 26, 2023 at 23:17
  • \$\begingroup\$ 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. \$\endgroup\$ Commented Aug 26, 2023 at 23:21
  • 1
    \$\begingroup\$ @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. \$\endgroup\$ Commented Aug 27, 2023 at 0:28
2
\$\begingroup\$

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
Improve this answer
\$\endgroup\$
2
\$\begingroup\$

Charcoal, 39 bytes

⊞υΦ↨⁺²⁵⁶Ｎ²κ⊞υＥ04261537§⌊υＩι¬⌕υ⌊⁺υＥυ⁻¹⮌ι

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

⊞υΦ↨⁺²⁵⁶Ｎ²κ

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

⊞υＥ04261537§⌊υＩι

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

¬⌕υ⌊⁺υＥυ⁻¹⮌ι

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

Improve this answer
\$\endgroup\$
2
\$\begingroup\$

K (ngn/k), 42 bytes

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

Try it online!

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

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.

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

05AB1E, 23 bytes

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

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

Try it online or verify all truthy test cases.

Explanation:

₁+ # 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)
Improve this answer
\$\endgroup\$
0
\$\begingroup\$

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 :-)

Improve this answer
\$\endgroup\$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.