| Bytes | Lang | Time | Link |
|---|---|---|---|
| 012 | Jelly | 241228T042426Z | Unrelate |
| 082 | Regex ECMAScript 2018 or .NET | 190204T043601Z | Deadcode |
| 016 | Brachylog | 190512T084616Z | Zgarb |
| 034 | J | 190204T005741Z | Jonah |
| 066 | Python 3.8 prerelease | 190205T055823Z | xnor |
| 198 | C# Visual C# Interactive Compiler | 190204T013201Z | dana |
| 096 | Retina | 190203T014515Z | Neil |
| 078 | Perl 5 p | 190203T174522Z | Nahuel F |
| 076 | Perl 6 | 190204T101401Z | Jo King |
| 020 | 05AB1E | 190204T084735Z | Kevin Cr |
| 074 | Python 2 | 190204T070416Z | xnor |
| 108 | Python 2 | 190203T111626Z | Erik the |
| 020 | Jelly | 190203T011050Z | Doorknob |
Jelly, 12 bytes
Q⁼þµ^\µ⁼Q^þ\
I felt oh so clever for coming up with this until I scrolled past xnor's solution on the way to post, caught a ^ out of the corner of my eye, and realized it's the exact same thing 🙃 Regardless, it still feels good to satisfy the source restriction without extra characters for comments.
Q Uniquify the input
⁼þ and table that by equality with the full input.
µ Then,
^\ scan the columns by XOR.
⁼ Is that equal to
µ Q itself uniquified?
\ Scan the scalar Boolean result (treated as length 1, hence a no-op)
^þ by tabling XOR.
Before accounting for the source restriction, I had =þ`^\QƑ, and also toyed with ċⱮƤQḂQƑ.
A contiguous substring is a suffix of a prefix, or equivalently a prefix with a smaller prefix removed. Hence, a substring has all-even counts if and only if the difference in each count between a pair of distinct prefixes is even, which is to say that the parity of the counts in each prefix is equal. Jelly's scan doesn't generate a cumulative result corresponding to the empty prefix, so the improper prefix consisting of the entire input is uniquely all-even so long as no other prefix is, and everything wraps itself up nicely with a bow.
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?
Brachylog, 16 bytes
sᶠb∋p~j&sᶠb∋p~j&
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.
J, 34 bytes
2:@':.,|~*'>1(#.,)*/@(1>2|#/.~)\.\
-8 bytes thanks to FrownyFrog
original
J, 42 bytes
(*#'.,012&|@~#')=1#.[:,([:*/0=2&|@#/.~)\.\
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...
Python 3.8 (pre-release), 66 bytes
lambda l,b={id}:len({str(b:=b^{c})for(c)in l})<len(l)#,<^fmnost{}#
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.
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*/
-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.
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*/
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.
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.
How it works
-pwith}{ending trick to output$\at the endm-.+(?{..})(?!)-, 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=$&)=~/./gto 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 1grep1&(@m=$g=~/\Q$_/g),for each character in substring get the array of character in$gmatching itself, array in scalar evaluates to its size andgrepto filter the chracters with odd occurence1&xis equivalent tox%2==1
Perl 6, 76 bytes
*.comb[^*X+(^*).map(^*)].grep({$_&[&]($_)}).none.Bag{*}.none%2#*^+XBob2rec%#
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
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
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)
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)
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.
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#
-2 thanks to Ørjan Johansen.
Jelly, 20 bytes
ĠẈḂẸẆṖÇ€Ạ
ĠẈḂẸ
ẆṖÇ€Ạ
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.