15
\$\begingroup\$

Given a cycle of non-zero numbers we say a "block" is a substring appearing immediately after \$n\$ and immediately before \$-n\$, which contains neither \$n\$ nor \$-n\$.

Here is an example block and cycle (\$n=-1\$):

... -1, 4, -3, 4, 2, 1, 1, -2, -3, ... ============

... indicates where the cycle loops to the other end.

Your task is to take a cycle and determine whether every element of the cycle is in some block. In other words: "Is the union of all blocks the complete cycle?"

You may take input as a list with the assumption that it wraps around again.

You should output one of two distinct consistent values if every element is in a block, and the other one if not.

This is the goal is to minimize the size of your source code as measured in bytes.

Examples

False

... 1, 3, 8, 3, 3, 9, ...

There are no blocks so this is false.

... -1, 4, 1, -3, 2, 4, 2, -1, 1, ...

The only \$n\$ with both signs is 1 so no 1 can appear in a block

... 2, 3, 2, 1, -2, -3, -1, 1, ...

The 3 is not contained in a block.

True

The following cases are all true:

... 1, 2, -1, -2, ... ... 1, 1, 2, -1, -2, ... ... 8, 1, 1, -8, -8, -1, -1, 8, ... ... 1, 2, 3, 2, -1, -1, -2, 3, -2, 1, ... ... 1, 2, 3, 2, -1, 2, -3, 1, -2, 3, -2, -1, -3, ...
Improve this question
\$\endgroup\$
4
  • \$\begingroup\$ ... 1, 1, 2, -1, -2, ... isn't this false? The first 1 isn't in a block. Your 3rd example says that the 3 isn't in a block, despite a 2 coming before it and a -2 after it. \$\endgroup\$ Commented Apr 30 at 22:13
  • 3
    \$\begingroup\$ @mbomb007 (1) it's true - -2, ... 1, 1, 2 covers the first 1. The third example has no block covering the 3 because blocks cannot contain their n or -n. \$\endgroup\$ Commented Apr 30 at 22:23
  • 3
    \$\begingroup\$ This problem is very interesting! I wonder whether it's inspired by some real-world mathematical or computational problem \$\endgroup\$ Commented May 2 at 7:55
  • 2
    \$\begingroup\$ @NicolaSap Sort of. Cycles like this can represent conjugacy classes in free groups (if you cancel the adjacent inverses there's a 1-to-1 correspondence). This question was related to a rough conjecture a colleague and I had formulated, which we rather quickly determined was false. The problem stuck with me though as potentially interesting for code-golf. \$\endgroup\$ Commented May 2 at 12:38

6 Answers 6

Reset to default
3
\$\begingroup\$

Jelly, 28 bytes

Ė;`ẆZṪṪ;ḢSȯfɗƲƊÐḟṖ€Ḋ€ẎZḢḟ@JẸ

A monadic Link that accepts a list of non-zero integers and yields 0 if the set of its blocks covers its elements, or 1 if not.

Try it online! Or see the test-suite.

How?

Ė;`ẆZṪṪ;ḢSȯfɗƲƊÐḟṖ€Ḋ€ẎZḢḟ@JẸ - Link: list of integers, C Ė - enumerate {C} -> [[1, c1], [2, c2], ... [|C|, c|C|]] ;` - concatenate that with itself Ẇ - all non-empty sublists of that ƊÐḟ - discard those for which: Z - transpose Ṫ - tail -> S = the raw sublist of C S = [ca, cb, ... cy, cz] Ʋ - last four links as a monad - f(S): Ṫ - tail of {S} (alters S -> [ca, cb, ... cy]) Ḣ - head of {S} (alters S -> [cb, ... cy]) ; - concatenate these -> [cz, ca] ɗ - last three links as a dyad - f([cz, ca], [cb, ... cy]): S - sum {[cz, ca]} -> 0 if cz == -1 × ca f - {[cz, ca]} filter keep {[cb, ... cy]} ȯ - logical OR of these Ṗ€Ḋ€ - pop each and dequeue each ZḢ - traspose and head -> indices covered ḟ@J - indices of {C} filter keep {indices covered} Ẹ - any?
Improve this answer
\$\endgroup\$
3
\$\begingroup\$

Python3, 162 bytes

def f(s): k=[] for i,a in enumerate(s): I,t=i,[] while(I:=(I+1)%len(s))!=i and s[I]!=a: t+=[I] if -1*s[I]==a:k+=t[:-1];break return len({*k})==len(s)

Try it online!

Improve this answer
\$\endgroup\$
3
  • \$\begingroup\$ If I loops all the way back around to i then s[I] will be a again, so while(I:=(I+1)%len(s))!=i and s[I]!=a: can just be while s[(I:=~-I%len(s))]!=a:. (I've included a golf of (I+1) -> ~-I in there.) - 152 \$\endgroup\$ Commented May 1 at 20:20
  • \$\begingroup\$ ...get rid of enumerate and use tuples to allow shoving initialisation of variables into f's parameters - 145. \$\endgroup\$ Commented May 1 at 20:24
  • \$\begingroup\$ return s>s[:len({*k})] (inverts results) saves two more. \$\endgroup\$ Commented May 1 at 20:55
2
\$\begingroup\$

05AB1E, 31 30 bytes

.āD«ŒʒøнDÁ2£DO_Š¢P*}妨€θ}˜Ù∍Q

Try it online or verify all test cases.

Explanation:

.ā # Enumerate the (implicit) input-list, # pairing each value with its index D # Duplicate this list « # Merge the two together Œ # Get all sublists of this 2x-cycled list ʒ # Filter this list of sublists by: ø # Zip/transpose; swapping rows/columns н # Leave just the first list of values, # since we don't need to indices yet D # Duplicate this list Á2£ # Pop and leave a pair of the first and last values # (or just one if it's a singleton-list) Á # Rotate the copy once clockwise 2£ # Pop and leave the first two items D # Duplicate that pair O_ # Check that it's an [n,-n]-pair O # Sum the pair together _ # Check whether that sum equals 0 Š # Triple-swap so the duplicated list and pair are at the top ¢ # Count how many times the values in the pair occur in the list P # Product these counts # (we're expecting counts [1,1], for the first/last items themselves) * # Multiply the two checks together # (only 1 is truthy in 05AB1E) }ε # After the filter: map over all remaining sublists: ¦¨ # Remove the first and last items € # Map over each remaining pair θ # Leave just the last item with indices }˜ # After the nested maps: flatten the list of indices Ù # Uniquify this list of indices ∍Q # Check that its length equals the length of the input-list: ∍ # Pop and extend/shorten the (implicit) input-list to a size equal to # this list Q # Check if that extended/shortened list equals the (implicit) input, # aka it hasn't been extended nor shortened # (after which the result is output implicitly)
Improve this answer
\$\endgroup\$
0
2
\$\begingroup\$

Charcoal, 45 32 27 bytes

⬤θ⊙θ¬ΣＥ²§ΦＥθ§θ⁺κ×ρ⊖⊗ν⁼↔π↔λ⁰

Try it online! Link is to verbose version of code. Outputs a Charcoal boolean, i.e. - if the cycle is covered, nothing if not. Explanation:

⬤θ

All members of the input must be in a block, computed as...

⊙θ

... some value exists...

Ｅ²§ΦＥθ§θ⁺κ×ρ⊖⊗ν⁼↔π↔λ⁰

... whose first occurrences in the cyclic and reverse cyclic permutations of the input starting at that member...

¬Σ

... differ only in sign. (So the member itself doesn't qualify, because its first occurrences don't differ as they are both itself.)

 θ Input array ⬤ All elements satisfy θ Input array ⊙ Any element satisfies ² Literal integer `2` Ｅ Map over implicit range θ Input array Ｅ Map over elements θ Input array § Indexed by κ Outermost index ⁺ Plus ρ Innermost index × Times ν Inner value ⊗ Doubled ⊖ Decremented Φ Filtered where π Innermost value ↔ Absolute value ⁼ Equals λ Outer value ↔ Absolute value § Indexed by ⁰ Literal integer `0` Σ Take the sum ¬ Is zero Implicitly print
Improve this answer
\$\endgroup\$
1
\$\begingroup\$

Google Sheets, 231 bytes

=let(e,tocol({A:A;A:A},1),s,sequence(rows(e)),count(unique(e))=count(unique(reduce(tocol(,1),s,lambda(a,i,let(c,index(e,i),j,+filter(s,s>i,-e=c),v,filter(e,i<s,s<j),if(isna(j)+ifna(sort(match(abs(c),abs(v),0))),a,vstack(a,v))))))))

screenshot

Ungolfed:

=let( elements, tocol(vstack(A1:A, A1:A), 1), indices, sequence(rows(elements)), withinCycles, reduce(tocol(, 1), indices, lambda(acc, i, let( curr, index(elements, i), j, single(filter(indices, indices > i, -elements = curr)), within, filter(elements, i < indices, indices < j), if(isna(j) + ifna(sort(match(abs(curr), abs(within), 0))), acc, ifna(vstack(acc, within)) ) ))), count(unique(withinCycles)) = count(unique(elements)) )
Improve this answer
\$\endgroup\$
1
\$\begingroup\$

Python, 126 bytes

def f(L,i=0,j=0):n=len(L);a,*S,b=(3*L)[i+n-1-j%n:i+n+2+j//n];c=({a,b}&{*S}or a+b)and-1;return i==n or j<n*n and f(L,c-~i,c*~j)

Attempt This Online!

Returns True if input is block covered, otherwise False. Input cannot be empty.

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.