A well linked challenge

Question

An activity I sometimes do when I'm bored is to write a couple of characters in matching pairs. I then draw lines (over the tops never below) to connect these characters. For example I might write \$abcbac\$ and then I would draw the lines as:

Or I might write \$abbcac\$

Once I've drawn these lines I try to draw closed loops around chunks so that my loop doesn't intersect any of the lines I just drew. For example, in the first one the only loop we can draw is around the entire thing, but in the second one we can draw a loop around just the \$b\$s (or everything else)

If we play around with this for a little while we will find that some strings can only be drawn so that closed loops contain all or none of the letters (like our first example). We will call such strings well linked strings.

Note that some strings can be drawn in multiple ways. For example \$bbbb\$ can be drawn in both of the following ways (and a third not included):

or

If one of these ways can be drawn such that a closed loop can be made to contain some of the characters without intersecting any of the lines, then the string is not well linked. (so \$bbbb\$ is not well linked)

Task

Your task is to write a program to identify strings that are well linked. Your input will consist of a string where every character appears an even number of times, and your output should be one of two distinct consistent values, one if the strings are well linked and the other otherwise.

In addition your program must be a well linked string meaning

• Every character appears an even number of times in your program.

• It should output the truthy value when passed itself.

Your program should be able to produce the correct output for any string consisting of characters from printable ASCII or your own program. With each character appearing an even number of times.

Answers will be scored as their lengths in bytes with fewer bytes being a better score.

Hint

A string is not well linked iff a contiguous non-empty strict substring exists such that each character appears an even number of times in that substring.

Test Cases

abcbac -> True
abbcac -> False
bbbb -> False
abacbc -> True
abcbabcb -> True
abcbca -> False

Answer 1

Regex (ECMAScript 2018 or .NET), 140 126 118 100 98 82 bytes

^(?!(^.*)(.+)(.*$)(?<!^\2|^\1(?=(|(<?(|(?!\8).)*(\8|\3$){1}){2})*$).*(.)+\3$)!?=*)

This is much slower than the 98 byte version, because the ^\1 is left of the lookahead and is thus evaluated after it. See below for a simple switcheroo that regains the speed. But due to this, the two TIOs below are limited to completing a smaller test case set than before, and the .NET one is too slow to check its own regex.

Try it online! (ECMAScript 2018)
Try it online! (.NET)

To drop 18 bytes (118 → 100), I shamelessly stole a really nice optimization from Neil's regex that avoids the need to put a lookahead inside the negative lookbehind (yielding an 80 byte unrestricted regex). Thank you, Neil!

That became obsolete when it dropped an incredible 16 more bytes (98 → 82) thanks to jaytea's ideas which led to a 69 byte unrestricted regex! It's much slower, but that's golf!

Note that the (|( no-ops for making the regex well-linked have the result of making the it evaluate very slowly under .NET. They do not have this effect in ECMAScript because zero-width optional matches are treated as non-matches.

ECMAScript prohibits quantifiers on assertions, so this makes golfing the restricted-source requirements harder. However, at this point it's so well-golfed that I don't think lifting that particular restriction would open up any further golfing possibilities.

Without the extra characters needed to make it pass the restrictions (101 69 bytes):

^(?!(.*)(.+)(.*$)(?<!^\2|^\1(?=((((?!\8).)*(\8|\3$)){2})*$).*(.)+\3))

It's slow, but this simple edit (for just 2 extra bytes) regains all the lost speed and more:

^(?!(.*)(.+)(.*$)(?<!^\2|(?=\1((((?!\8).)*(\8|\3$)){2})*$)^\1.*(.)+\3))

^
(?!
    (.*)               # cycle through all starting points of substrings;
                       # \1 = part to exclude from the start
    (.+)               # cycle through all ending points of non-empty substrings;
                       # \2 = the substring
    (.*$)              # \3 = part to exclude from the end
    (?<!               # Assert that every character in the substring appears a total
                       # even number of times.
        ^\2            # Assert that our substring is not the whole string. We don't
                       # need a $ anchor because we were already at the end before
                       # entering this lookbehind.
    |                  # Note that the following steps are evaluated right to left,
                       # so please read them from bottom to top.
        ^\1            # Do not look further left than the start of our substring.
        (?=
            # Assert that the number of times the character \8 appears in our
            # substring is odd.
            (
                (
                    ((?!\8).)*
                    (\8|\3$) # This is the best part. Until the very last iteration
                             # of the loop outside the {2} loop, this alternation
                             # can only match \8, and once it reaches the end of the
                             # substring, it can match \3$ only once. This guarantees
                             # that it will match \8 an odd number of times, in matched
                             # pairs until finding one more at the end of the substring,
                             # which is paired with the \3$ instead of another \8.
                ){2}
            )*$
        )
        .*(.)+         # \8 = cycle through all characters in this substring
        # Assert (within this context) that at least one character appears an odd
        # number of times within our substring. (Outside this negative lookbehind,
        # that is equivalent to asserting that no character appears an odd number
        # of times in our substring.)
        \3             # Skip to our substring (do not look further right than its end)
    )
)

I wrote it using molecular lookahead (103 69 bytes) before converting it to variable-length lookbehind:

^(?!.*(?*(.+)(.*$))(?!^\1$|(?*(.)+.*\2$)((((?!\3).)*(\3|\2$)){2})*$))

^
(?!
    .*(?*(.+)(.*$))       # cycle through all non-empty substrings;
                          # \1 = the current substring;
                          # \2 = the part to exclude from the end
    (?!                   # Assert that no character in the substring appears a
                          # total even number of times.
        ^\1$              # Assert that our substring is not the whole string
                          # (i.e. it's a strict substring)
    |
        (?*(.)+.*\2$)    # \3 = Cycle through all characters that appear in this
                          # substring.
        # Assert (within this context) that this character appears an odd number
        # of times within our substring.
        (
            (
                ((?!\3).)*
                (\3|\2$)
            ){2}
        )*$
    )
)

And to aid in making my regex itself well-linked, I've been using a variation of the above regex:

(?*(.+)(.*$))(?!^\1$|(?*(.)+.*\2$)((((?!\3).)*(\3|\2$)){2})*$)\1

When used with regex -xml,rs -o, this identifies a strict substring of the input that contains an even number of every character (if one exists). Sure, I could have written a non-regex program to do this for me, but where would be the fun in that?

Answer 2

Jelly, 20 bytes

ĠẈḂẸẆṖÇ€Ạ
ĠẈḂẸ
ẆṖÇ€Ạ

Try it online!

The first line is ignored. It's only there to satisfy the condition that every character appear an even number of times.

The next line first Ġroups indices by their value. If we then take the length of each sublist in the resulting list (Ẉ), we get the number of times each character appears. To check whether any of these are non-even, we get the last Ḃit of each count and ask whether there Ẹxists a truthy (nonzero) value.

Therefore, this helper link returns whether a substring cannot be circled.

In the main link, we take all substrings of the input (Ẇ), Ṗop off the last one (so that we don't check whether the entire string can be circled), and run the helper link (Ç) on €ach substring. The result is then whether Ạll substrings cannot be circled.

Answer 3

J, 34 bytes

2:@':.,|~*'>1(#.,)*/@(1>2|#/.~)\.\

Try it online!

-8 bytes thanks to FrownyFrog

original

J, 42 bytes

(*#'.,012&|@~#')=1#.[:,([:*/0=2&|@#/.~)\.\

Try it online!

explanation

(*#'.,012&|@~#') = 1 #. [: , ([: */ 0 = 2&|@#/.~)\.\

(*#'.,012&|@~#')                                       NB. this evaluates to 1
                                                       NB. while supplying extra
                                                       NB. chars we need.  hence...
                 =                                     NB. does 1 equal...
                   1 #.                                NB. the sum of...
                        [: ,                           NB. the flatten of...
                             (                  )\.\   NB. the verb in parens applied
                                                       NB. to every suffix of every
                                                       NB. prefix, ie, all contiguous 
                                                       NB. substrings
                             ([: */ 0 = 2&|@#/.~)      NB. def of verb in paren:
                                             /.~       NB. when we group by each
                                                       NB. distinct char...
                              [: */                    NB. is it the case that
                                                       NB. every group...
                                           @#          NB. has a length...
                                    0 = 2&|            NB. divisible by 2...

Answer 4

Python 3.8 (pre-release), 66 bytes

lambda l,b={id}:len({str(b:=b^{c})for(c)in l})<len(l)#,<^fmnost{}#

Try it online!

The Era of Assignment Expressions is upon us. With PEP 572 included in Python 3.8, golfing will never be the same. You can install the early developer preview 3.8.0a1 here.

Assignment expressions let you use := to assign to a variable inline while evaluating to that value. For example, (a:=2, a+1) gives (2, 3). This can of course be used to store variables for reuse, but here we go a step further and use it as an accumulator in a comprehension.

For example, this code computes the cumulative sums [1, 3, 6]

t=0
l=[1,2,3]
print([t:=t+x for x in l])

Note how with each pass through the list comprehension, the cumulative sum t is increased by x and the new value is stored in the list produced by the comprehension.

Similarly, b:=b^{c} updates the set of characters b to toggle whether it includes character c, and evaluates to the new value of b. So, the code [b:=b^{c}for c in l] iterates over characters c in l and accumulates the set of characters seen an odd number of times in each non-empty prefix.

This list is checked for duplicates by making it a set comprehension instead and seeing if its length is smaller than that of s, which means that some repeats were collapsed. If so, the repeat means that in the portion of s seen in between those times every character encountered an even number of numbers, making the string non-well-linked. Python doesn't allow sets of sets for being unhashable, so the inner sets are converted to strings instead.

The set b is initialized as an optional arguments, and successfully gets modified in the function scope. I was worried this would make the function non-reusable, but it seems to reset between runs.

For the source restriction, unpaired characters are stuffed in a comment at the end. Writing for(c)in l rather than for c in l cancels the extra parens for free. We put id into the initial set b, which is harmless since it can start as any set, but the empty set can't be written as {} because Python will make an empty dictionary. Since the letters i and d are among those needing pairing, we can put the function id there.

Note that the code outputs negated booleans, so it will correctly give False on itself.

Answer 5

Python 2, 74 bytes

bmn0=f=lambda s,P={0},d=[]:s<" "if(P in d)else+f(s[f<s:],P^{s[0^0]},[P]+d)

Try it online!

Iterates through the string, keeping track in P of the set of characters seen an odd number of times so far. The list d stores all past values of P, and if see the current P already in d, this means that in the characters seen since that time, each character has appeared an even number of times. If so, check if we've gone through the entire input: if we have, accept because the whole string is paired as expected, and otherwise reject.

Now about the source restriction. Characters needing pairing are stuffed into various harmless places, underlined below:

bmn0=f=lambda s,P={0},d=[]:s<" "if(P in d)else+f(s[f<s:],P^{s[0^0]},[P]+d)
_____              _              _      _    _    ___        ___    

The f<s evaluates to 0 while pairing off an f, taking advantage of the function name also being f so that it's defined (by the time the function is called.) The 0^0 absorbs an ^ symbol.

The 0 in P={0} is unfortunate: in Python {} evaluates to an empty dict rather than an empty set as we want, and here we can put in any non-character element and it will be harmless. I don't see anything spare to put in though, and have put in a 0 and duplicated it in bmn0, costing 2 bytes. Note that initial arguments are evaluated when the function is defined, so variables we define ourselves can't be put in here.

Answer 6

Perl 6, 76 bytes

*.comb[^*X+(^*).map(^*)].grep({$_&[&]($_)}).none.Bag{*}.none%2#*^+XBob2rec%#

Try it online!

A Whatever lambda that returns a None Junction of None Junctions that can be boolified to a truthy/falsey value. I would recommend not removing the ? that boolifies the return result though, otherwise the output gets rather large.

This solution is a little more complex than needed, due to several involved functions being unlinked, e.g. .., all, >>, %% etc. Without the source restriction, this could be 43 bytes:

*.comb[^*X.. ^*].grep(?*).one.Bag{*}.all%%2

Try it online!

Explanation:

*.comb                     # Split the string to a list of characters
      [^*X+(^*).map(^*)]   # Get all substrings, alongside some garbage
                        .grep({$_&[&]($_)})        # Filter out the garbage (empty lists, lists with Nil values)
                                           .none                 # Are none of
                                                .Bag{*}          # The count of characters in each substring
                                                       .none%2   # All not divisible by 2

                                               #*^+XBob2rec%#    And garbage to even out character counts

Answer 7

Retina, 150 96 bytes

^(?!(.*)(.+)(.*)$(?<!^\2|^\1(?:(^?(?:(?!\6).)*\6){2})*(|(?!\6).)*(?!.+\6.*\3$)(.){1,}\3)(?!,<)?)

Try it online! Link includes test cases, including itself. Edit: Golfed down the original regex a fair bit with help from @Deadcode, then padded back up slightly less extravagently to maintain the source layout. Explanation:

^(?!(.*)(.+)(.*)$

Assert that no substring \3 exists that matches the following constraints.

(?<!^\2|

Assert that the substring is not the whole original string.

^\1(?:(^?(?:(?!\6).)*\6){2})*(|(?!\6).)*(?!.+\6.*\3$)(.){1,}\3)(?!,<)?)

Assert that there is no character \6 such that:

• it does not appear between the character itself (exclusive) and the end of the substring
• it appears an even number of times between the start of the substring and itself (exclusive)

In order to pass the source layout constraint, I replaced (((( with (?:(^?(?:( and (( with (|(. I still had one source constraint )) left and the characters !()1<{} left over, so I changed a + into {1,} and inserted the useless (?!,<)? to consume the rest.

Answer 8

Perl 5 -p, 94, 86, 78 bytes

m-.+(?{$Q|=@q&grp,$\|=$&eq$_^!grep+/^/&(@m=$g=~/\Q$_/g),($g=$&)=~/./g})(?!)-}{

ouput 0 if well-linked 1 otherwise.

78 bytes

86 bytes

94 bytes

How it works

• -p with }{ ending trick to output $\ at the end
• m-.+(?{ .. })(?!)-, to execute code over all non-empty substring (.+ matches the whole string first, and after executing code between (?{ ..}) backtracks because of failed forced (?!)
• $Q|=@q&grp, garbage because of source restriction
• $\|= integer bitwise or assignment, if there's almost one 1, $\ will be 1 (true), by default it is empty (false)
• $&eq$_ the case where the sbustring is the whole string is bitwise xored ^ with "no odd character occurence"
• ($g=$&)=~/./g to copy the matched substring into $g (because will be overwirtten after next regex match) and return the array of character of substring.
• /^/ garbage which evaluates to 1
• grep 1 &(@m=$g=~/\Q$_/g), for each character in substring get the array of character in $g matching itself, array in scalar evaluates to its size and grep to filter the chracters with odd occurence 1&x is equivalent to x%2==1

Answer 9

C# (Visual C# Interactive Compiler), 208 206 200 198 bytes

x=>!x.GroupBy(c=>c).Any(g=>g.Count()%2>0)&!Enumerable.Repeat(x.Count,x.Count*x.Count).Where(
(l,i)=>i%l>0&!x.Skip(i/l).Take(i%l).GroupBy(c=>c).Any(g=>g.Count()%2>0)
).Any()/*>!oyAnC0EmeablR*WhiS/T*/

Try it online!

-2 bytes thanks to @KevinCruijssen!

Finally got it below 200, so I might be done golfing for now :) I ended up creating a second TIO to test things out based on a previous answer.

Try it online!

Things that made this task tricky:

• Equality operator == was not allowed
• Increment/assign operator ++ was not allowed
• Linq All() function was not allowed

Commented code below:

// anonymous function that takes an IList as input
x=>
  // the first condition makes sure the string even
  // counts of each character
  !x.GroupBy(c=>c).Any(g=>g.Count()%2>0)&
  // the second condition generates all proper substrings of x
  // and tests for any that contain even character counts
  // the string length `l` is repeated `l*l` times
  !Enumerable.Repeat(x.Count,x.Count*x.Count)
    .Where((l,i)=>
      // check that the substring length is greater than 0
      i%l>0&
      // use skip/take to generate a substring
      // and check for a character count thats odd
      // negate the result meaning we have found
      // a substring that invalidates the input
      !x.Skip(i/l).Take(i%l)
        .GroupBy(c=>c).Any(g=>g.Count()%2>0)
    )
    // if any invalid substrings are found
    // then the result in invalid
    // the comment string at the end is needed
    // to make the program well-linked
    .Any()/*>!oyAnC0EmeablR*WhiS/T*/

Answer 10

Python 2, 108 bytes

lambda d,e=enumerate:min(max(d[l:l+b].count(k)%2for(k)in d)for b,c in e(d[2:],2)for l,f in e(d) )#b =:x+.%2#

Try it online!

-2 thanks to Ørjan Johansen.

Answer 11

Brachylog, 16 bytes

sᶠb∋p~j&sᶠb∋p~j&

Try it online!

Prints false. for truthy instances and true. for falsy instances. The TIO version is too slow to handle itself, but it's clearly well-linked since it's a string with unique characters repeated twice.

Explanation

    Input is a string: "abcacbaa"
sᶠ  Find all substrings: ["abcacbaa","abcacba","abcacb",..,"a"]
b   Behead (now the proper substrings remain): ["abcacba","abcacb",..,"a"]
∋   Take one of them: "abcacb"
p   Permute it: "abcabc"
~j  It is some string repeated twice: "abc"
&   Get the input again: "abcacbaa"
    Then repeat the above.
    If the constraints can be satisfied, the result is true, otherwise false.

Answer 12

05AB1E, 22 20 bytes

Œε¢Pà}KŒIKεSIS¢ÈP}àÈ

Outputs 1 if the string is well-linked, and 0 if the string is not well-linked.

Try it online or verify all test cases.

Explanation:

The base program is ŒsKεsS¢ÈP}à (11 bytes), which outputs 0 if well-linked and 1 if not well-linked. The trailing È (is_even) is a semi no-op that inverts the output, so 1 for well-linked strings and 0 for not well-linked strings. The other parts are no-ops to comply to the challenge rules.

Œε¢Pà}K         # No-ops: substrings, map, count, product, maximum, close map, remove
                # Due to the last remove, we're back at the (implicit) input again
Π              # Take the substrings of the input
 IK             # Remove the input itself from that list of substrings
   ε            # Map each substring to:
    S           #  No-op: transform the substring into a list of characters
     IS         #  Get the input-string as a list of characters
       ¢        #  Count the occurrence of each character in the current substring
        È       #  Check which counts are even (1 if truthy; 0 if falsey)
         P      #  Take the product of that
          }à    # After the map: check if any are truthy by taking the maximum
            È   # Semi no-op: check if this maximum is even (0 becomes 1; 1 becomes 0)
                # (and output the result implicitly)