Implement any 10-ary truth function with cyclic symmetry

Question

Implement a function \$f\$ that takes 10 boolean inputs and returns a boolean.

The only requirement on \$f\$ is that it satisfies the identity

$$ f(x_1,x_2,x_3,x_4,x_5,x_6,x_7,x_8,x_9,x_{10})=f(x_2,x_3,x_4,x_5,x_6,x_7,x_8,x_9,x_{10},x_1) $$

and the 9 other "input rotation" identities (including the trivial one) that follow from this, and does not satisfy any other identities corresponding to permutations of the input tuple. (Please justify this in your answer.)

The spirit of the challenge is to find and golf a function with the required symmetry group, not to golf a brute-force search through all \$2^{1024}\$ 10-ary truth functions. Therefore, your program should run for at most 1 minute on each input.

Answer 1

Python, 21 bytes

lambda s:"1011"in s*2

Try it online!

Checks whether the input contains 1011, reading left to right wrapping around. The reason for not testing with a shorter substring like "11" or "100" is that reversing the input would always preserve whether these are present.

To justify why no other permutation preserves this, consider the input 0000001011 and its cyclic permutations, which give True. The permutation would have to keep the three 1's of each in the formation 1011, which does not appear possible other than by cycling the input.

The input is taken as a string of 1's and 0's. Doubling the string connects the front and back, letting us check for substrings in a way that includes wrapping around.

---

Python, 15 bytes

lambda n:n%11<1

Try it online!

If input may be taken as a 10-bit number, like 419 for 0110100011, we can simply check if it's a multiple of 11. This is preserved by cycling because 2**10-1 = 1023 is a multiple of 11. And to satisfy an identity, a permutation would have to once again preserve cycles of 0000001011 (11 in binary) up to cycling.

Answer 2

J, 56 bytes

b=:monad define
{:#:(+/(0|.y)*.(-.1|.y)*.(2|.y)*.3|.y)
)

Try it online!

Usage:

> echo b 1 0 1 0 1 0 1 0 1 0
0
> echo b 1 0 1 0 1 0 1 1 0 0
1

This is a terrible solution in terms of score, I'm aware. This is both my first time code golfing and my first time using J, and my interest in this problem was the finding the function part, not the golfing. Consider the golfing as just an excuse for me to post my solution to what is in spirit a math puzzle.

How does it work?

The function I wrote takes a list of 10 Boolean values, and counts the number of (cyclic) occurrences of the pattern 1011, mod 2. ("Cyclic" means that e.g. if bits 9, 0, 1, 2 are 1 0 1 1 respectively, then the pattern is considered to have occurred at position 9. In other words, indices modulo 10.)

The program accomplishes this by basically doing a bitwise AND of copies of the string rotated by 0, 1, 2, and 3 positions, of which the one rotated by 1 position was also bitwise negated, then counting the 1s in the resulting string and extracting the final bit of that number.

Clearly, this function is invariant under rotations. To show that it's not invariant under any permutation that isn't a rotation, I'll show that there's a 1011 pattern that doesn't get preserved under the permutation; then an input consisting of just that one 1011 pattern and all 0s otherwise would return 1 without the permutation, but 0 with it.

Consider a permutation P of {0, 1, 2, ..., 9}. Suppose there's a 1011 pattern at the 0th position, and everything else is all zeros. Then, in order to preserve it, there must exist an n such that 0, 2, 3 are mapped under P to some permutation Q of {n, n + 2, n + 3}. Then we can show that, in each of the six cases,

• (i), 1 must be mapped to n + 1, otherwise some 1011 pattern would be destroyed;
• (ii), all permutations Q that aren't the identity permutation would also cause some 1011 pattern to be destroyed, if we assume (i).

For both points, our "culprit" will be two positions at a distance of 3 or less which are mapped to positions at a distance of 4 or more. Since our test patterns are ones that have only a single 1011 pattern and all zeros otherwise, and so all 1s in such patterns have a distance of 3 or less to each other, it will be impossible for P to preserve 1011 patterns if we can show it maps even one pair with distance 3 or less to a pair with distance 4 or more. That's because if two 1s end up at distance 4 or more, and we only have three 1s to work with, we can't assemble a 1011 pattern anymore. This distance argument works even though the ten positions are cyclic because 4 < 10/2: if something is closer from the left side and still 4 or more spots away, it can't actually secretly be within 3 spots away from the right side, because then it'd be closer from the right side.

This basically breaks the proof down into six cases. Illustratively I'll work through the proof for the case Q = {n, n + 3, n + 2}:

• (i) Suppose 1 isn't mapped to n + 1, but instead somewhere outside the 1011 pattern. If it's closer to the pattern from the right, i.e. it's mapped to n + 4 or more, then since 0 is mapped to n, 0 and 1 would be mapped to a distance of 4 or more. If it's closer from the left, i.e. n - 1 or less, then 2 is mapped to n + 3, and so 1 and 2 would be mapped to a distance of 4 or more.
• (ii) Now that it's established that 1 is mapped to n + 1, let's continue to enforce what is mapped where by using the 1011-preserving property. A pattern at position 1 would map its starting 101 to 110, which, to preserve 1011, must mean that position 4 (which now contains the only remaining 1) must map to n - 1. Then a pattern at position 2 would map its starting 101 to 1..01, where two of the 1s are at distance 4, contradiction. In general, for each of the cases where Q isn't the identity, (ii) always takes at most two deduction steps to run into a contradiction -- and they always consider patterns at positions 1 and 2, except the case {n + 3, n, n + 2}, which for some reason instead required considering patterns at positions -1 and -3 (i.e. 9 and 7).

If you found that extremely verbose and at the same time way too abbreviated and convoluted, I'm with you. I'm finding it nearly impossible to carry out this proof in a way that reads well without going on for far too long. Instead, I carried out the full proof in a much neater way as a proof without words -- by encoding it into six pretty dot diagrams:

In the center of each is the permutation Q being considered, but with the rotation effect removed, and with 1 already being assumed to map to n + 1. The tiny dots at the very bottom and the arrows at the very top represent step (i), finding pairs of positions close enough that map to positions too far away. All the other dots above and below represent step (ii), where, using 1011 patterns at positions other than 0, we deduce more about what gets mapped where, and finish by finding a pair of 1s mapped too far away, marked with a brace. The conclusions in (ii) happen outward from the center in a "spiral" order: the first additional use of the 1011-preserving property happens one level below the central permutation; its conclusions, one level above it; the next use is two levels below the permutation; the conclusions from that are two levels above it, and so on.

In each case, we're able to do step (i), and in each case except when Q is the identity, also step (ii). Thus all of 0, 1, 2, 3 must map by the same offset, and then by considering a pattern starting at position 1, it follows that 4 too must map by the same offset, and so on, until we conclude that the whole mapping P is a rotation.

A little addendum

My first solution idea that got somewhat far was to count the occurrences of the simpler pattern 01, and I started working on a proof that rotations are the only permutations that preserve adjacency, so that if a permutation wasn't a rotation, then it would map some pair 11 onto two disjoint 1s, thus increasing the count of 01 patterns from 1 to 2 if the rest of the input is all zeros. However, I found that the permutations that preserve adjacency are not just rotations: they're precisely the rotations and reflections. In fact it's quite easy to see that we can't exclude reflections, because the number of cyclic occurrences of 01 will always be equal to the number of cyclic occurrences of 10. So if anyone ever submits an identical problem except now the function must be invariant under reflections too, there's a solution to that.

The smallest bit pattern that doesn't play along with reflections in this way (i.e. it's not mirror-symmetric itself, and it doesn't occur exactly as often as its mirror image) must be 4 bits long. I picked 1011 and rolled with it, but obviously 1101, 0100, and 0010 (at least) would work equally well.

Answer 3

Retina 0.8.2, 11 bytes

$
$`
1`1011

Try it online! Takes input as a binary string. Explanation: Now a port of @xnor's answer, since my previous answer failed for reversals. (Plus it was longer.)

Answer 4

Japt, 3 bytes

Based on xnor's observations. Takes input as a binary string, outputs 1 or 0.

ÍvB

Try it

ÍvB     :Implicit input of string
Í       :Convert to decimal
 v      :Is that divisible by
  B     :  11

Answer 5

05AB1E, 4 bytes

C11Ö

Port of @xnor's second Python answer.

Input as a binary-string.

Try it online or verify all test cases.

Explanation:

C     # Convert the (implicit) input-string from binary to a base-10 integer
 11Ö  # Check if this integer is divisible by 11
      # (which is output implicitly as result)

Since I was curious, a port of his other Python answer would be 5 bytes instead:

«11bå

Input also as a binary-string.

Try it online or verify all test cases.

Explanation:

«      # Merge the (implicit) input to the (implicit) input
 11b   # Push 11, and convert it to a binary string "1011"
    å  # Check whether the double input contains "1011" as substring
       # (which is output implicitly as result)

The 11b has a few equal-bytes alternatives: Ž3÷ (compressed 1011); т>Ć (100, +1, append own head); Tb> (10, to binary 1010, +1); Ƶ0Ć (compressed 101, append own head); T>b (10, +1, to binary); TĆĆ (10, append own head, append own head); etc.

Answer 6

C (gcc), 15 bytes

f(n){n=1>n%11;}

Try it online!

Same as @xnor's Python answer.

Answer 7

Haskell + hgl, 10 bytes

Takes input as a list of booleans and implements the divisiblity by 11 trick.

fby 11<ubi

ubi (convert from binary to natural number) is not on ato yet.

12 bytes

Takes input as a string of 1s and 0s and implements the other trick.

iw"1101"<rt2

Attempt This Online!

Reflection

• The divisbility by operation by/fby should have pre-made functions for divisors up to 12. (1 and 2 already exist)
• This challenge has to do with necklaces. I should add support for a necklace type as well as some necklace operations on both the necklace type and on lists.