Two Parallel Linked Chains

Question

Background

We define the two types of chain to be a string that contains only dashes, "-", or only underscores, "_". We link two chains using one equals sign, "=".

Criteria:

1. The type of chain must change following an equals sign.
2. You must link the chains, you can do so multiple times, and it does not matter what length the chains are so long as they are equal to or above one.
3. The chain must not start or end with an equals sign.
4. No two equals signs may be adjacent.
5. There must be at least three characters, and both types of chain must show up.
6. The chain must only contain underscores, dashes, and equals signs.

Your Task

Given a string, return True if it is a valid two-parallel-linked-chains (tplc) and return False otherwise.

• Input: The string will be maximum 256 characters long. It may contain characters which are not underscores, dashes, or equals signs.

• Output: Return either True or False, depending of if it is valid tplc or not.

Explained Examples

Input => Output
______=-------=___=-----=_=- => True

The string is a valid tplc because it follows all criteria.

Input => Output
 => False

Empty string does not satisfy criteria 5.

Input => Output
=_=- => False

The string starts with an equals sign, and does not satisfy criteria 3.

Input => Output
___ => False

There is only one type of chain, so the string does not satisfy criteria 5.

Input => Output
__==--- => False

There are two consecutive adjacent equals signs, so the string does not satisfy criteria 4.

Input => Output
_=- => True

The string satisfies all criteria.

Input => Output
_=----=___=--@- => False

The string contains a forbidden character, @, so the string does not satisfy criteria 6.

Input => Output
__=__ => False

The type of chain does not change after an equals sign, so does not satisfy criteria 1.

Input => Output
___--- => False

The chains are not linked (no equals sign), and does not satisfy criteria 2.

Test Cases

Input ~> Output
 
 ~> False
_ ~> False
_- ~> False
== ~> False
==_ ~> False
-_- ~> False
_== ~> False
=_=- ~> False 
____ ~> False
-=__£ ~> False
*=___ ~> False
->-=_ ~> False
__=]- ~> False
0x=+y ~> False
--X__ ~> False
_==-- ~> False
-=_=_ ~> False
_-==_- ~> False
_-_-_= ~> False
_==__= ~> False
_=--__ ~> False
___=__ ~> False
--=__ _ ~> False
__=___=___ ~> False
______=----&---- ~> False
___=---------=________-_____ ~> False
--------=_________=-=_=-=_=----=__==----- ~> False
-=_ ~> True
_=- ~> True
-=__=--- ~> True
_=--=___ ~> True
_=-=_=-=_ ~> True
__=------ ~> True
__=------------=____________=--------------=_____________=-------- ~> True
---------=____________=----------=_=-=_=---------------=_______________________ ~> True

This is code-golf, so shortest answer wins.

• Arnauld: Please note that input validation is one of the most upvoted thing to avoid.
• Arnauld: Just to clarify, I'm referring here to the rule [the input] may contain characters which are not underscores, dashes, or equals signs. (The challenge itself is obviously about validating a string and that's perfectly fine.)
• Neil: Suggested test case: -=_=_ (contains both types of chain but they do not alternate correctly).
• xnor: The non-allowed characters seem like a gotcha and at least need more test cases, since it seems easy to accidentally write a solution that would fail on -=_? or -A__ or xx=yy or others.
• Jacob Creutzfeldt: @xnor Thanks! Been added, will remove input validation in future golfs.

Answer 1

Regex, (削除) 36 (削除ここまで) (削除) 32 (削除ここまで) (削除) 30 (削除ここまで) 29 bytes

^(?=.*=)(_|(^|\b=)-+(=_|$))*$

Try it online!

-1 thanks to @InSync which allowed for another -1

This is my first regex answer, so it's quite possible I missed some optimizations.

Explanation

We start with a (?=.*=) to make sure the string contains a =.

Once we know it does, we can use the following DFA. Let's convert it to a regular expression.

DFA

We'll start by removing the bottom two states, and making sure there's only a single accepting state:

DFA2

Now we remove the left state.

DFA3

We can remove the -+ since it's inconsistent with there being a = in the string, so we get:

DFA4

which is equivalent to (-+=)?_(_|=-+=_)*(=-+)?.

Then, we can notice the duplication of =-+, and since we end with $ regardless we can optimize it to (-+=)?_(_|=-+(=_|$))*. Now, we can do the same for -+=, and optimize it to (_|(^|=)-+(=_|$))*. However, this introduces the problem that a match can start with =. To fix this, we can notice that _ is a word character, while - and = aren't. This means that \b= matches iff the previous character was _, which works in our scenario.

• The Thonnu: You could have also made this a 36 byte Regex solution: regex101.com/r/3VkvPM/1
• Command Master: @TheThonnu Just did that, the Javascript part was indeed superficial
• InSync: 31 bytes, unless I'm missing something: ^(?=.*=)(-+=)?(_+(=-+(=|$))?)+$.
• Command Master: @InSync Thanks! I managed to golf another byte using |$

Answer 2

Jelly, 12 bytes

f)-_Œgj"==>E

Try it online!

f)-_ Filter out all characters but -_.
 Œg Group runs of consecutive equal elements.
 j"= Join on =.
 = Does this result equal the input?
 >E And, are the elements of the input not all equal?

Answer 3

JavaScript (ES6), 70 bytes

This code is using an explicit finite-state machine rather than regular expression functions.

Expects a list of characters and returns 0 or 1.

a=>a.map(c=>a|=(s=+"0X00XX11X143"[s+5*"-_=".indexOf(c)])>2,s=2)&&a&s<2

Try it online!

This could be 56 bytes if the input was guaranteed to contain only underscores, dashes and equal signs. (This version expects a list of ASCII codes.)

States

• State 0: We are within a "-" chain and expect either another "-" or a "=".
• State 1: We are within a "_" chain and expect either another "_" or a "=".
• State 2: This is the initial state where we expect either "-" or "_".
• State 3: We are just after a "=" preceded by a "_" chain. We now expect a "-".
• State 4: We are just after a "=" preceded by a "-" chain. We now expect a "_".
• State X: An error has occurred.

State-transition table

This table gives the new state based on the current state and the next character.

 | 0 1 2 3 4 X
----+------------
"-" | 0 X 0 0 X X
"_" | X 1 1 X 1 X
"=" | 4 3 X X X X

The rightmost column is not stored in the lookup string because the X state is actually encoded as NaN, which forces any further lookup index to be evaluated to NaN as well and leaves the state unchanged till the end.

We don't have to store the trailing X's either.

Hence the final lookup string: "0X00X" + "X11X1" + "43".

Output

The input is correct if and only if:

• We end up in state 0 or 1.
• We've reached state 3 or 4 at least once.

• Jonah: Nice answer! "solution based on a state machine without any regular expression" -- I thought FSM and regexes were theoretically equivalent... what am I missing that makes this an exception?
• Arnauld: @Jonah I just meant that the code is not using any regex literal nor any regex function. But yes, it's doing the same job.

Answer 4

Python, 74 bytes

lambda s:0<2*(c:=(s+s[::-1]).count)("_=-")==2*len(s)-c("_")-c("-")+c("_-")

Attempt This Online!

How?

Looking at the counts of certain substrings we can enforce Rules 1,3,4 by requiring that #"-=_" + #"_=-" = #"=" and rule 5 by requiring this number be positive.

Rule 2 by requiring neither "-_" nor "_-" occurring, i.e. their counts being zero.

Rule 6 by requiring #"=" + #"-" + #"_" = |s| (the length of the input).

Answer 5

05AB1E, (削除) 25 (削除ここまで) (削除) 20 (削除ここまで) (削除) 15 (削除ここまで) (削除) 13 (削除ここまで) 12 bytes

„-_Ãγ'=ýQIË›

-2 bytes porting @UnrelatedString's Jelly answer, so make sure to upvote that answer as well!
-1 byte thanks to @CommandMaster

Outputs 1 for truthy and 0 for falsey.

Try it online or verify all test cases.

Previous 15 bytes approach:

'=¡€Ôι€Ù ̃{„-_SQ

Outputs 1 for truthy and 0 for falsey.

Try it online or verify all test cases.
Or verify all test cases with add debug-lines, to better understand what's going on.

Original (削除) 25 (削除ここまで) 20 bytes approach:

ê...-=_ÊI„-_‚åI'=¡õåM

Outputs a reversed boolean (0 for truthy; 1 for falsey). If this is not allowed, a single trailing byte can be added to reverse it.

Try it online or verify all test cases.

Explanation:

„-_Ã # Only keep the "-_" characters of the (implicit) input-string,
 # removing any other characters
 γ # Split this string into equal adjacent groups
 '=ý '# Join it with "="-delimiter
 Q # Check if this string is equal to the (implicit) input,
 # resulting in 1 or 0 for truthy/falsey respectively
I # Push the input-string again
 Ë # Check if all of its characters are the same (or it's an empty string)
› # Check that the first check is larger than the second
 # (aka, verify whether the first is truthy and second is falsey)
 # (after which the result is output implicitly)

'=¡ '# Split the (implicit) input-string by "="
 € # Map over each substrings:
 Ô # Connected uniquify the characters in the substring
 ι # Uninterleave it into two parts
 € # Map over both inner lists:
 Ù # Uniquify the list of substrings
 ̃ # Flatten the pair of lists of strings
 { # Sort it
 „-_SQ # Check if what remains is equal to pair ["-","_"]
 # (after which the result is output implicitly)

ê...-=_Ê # Rules 5 and 6:
ê # Sorted-uniquify the characters in the (implicit) input-string
 ...-=_ # Push string "-=_"
 Ê # Pop both, and check whether they're NOT equal
I„-_‚å # Rule 1:
I # Push the input-string again
 „-_ # Push string "-_"
 Â # Bifurcate it; short for Duplicate & Reverse copy
 ‚ # Pair the two together: ["-_","_-"]
I å # Check for both whether they occur in the input-string
I'=¡õ '# Rules 3 and 4:
I # Push the input-string yet again
 '=¡ '# Split it on "="
 õå # Check if this list of parts contains an empty string ""
M # Push the largest integer on the stack (also looks within lists)
 # (after which it is output implicitly as result)

• Command Master: „-_Ãγ'=ýQIË› (verify all test cases) 12 bytes
• Kevin Cruijssen: @CommandMaster Ah, I'm an idiot.. :/ I should have checked what E does in Jelly.. Now it's a direct port of the Jelly answer (where Jelly's Œg is 05AB1E's 1 byte shorter γ, but Jelly has an implicit argument for E and 05AB1E needs an explicit I, making their byte-counts the same). Thanks!
• Neil: Ah yes, that use of the greater than operator as a non-implication operator!

Answer 6

Charcoal, 28 bytes

∧Noθ=∧⌊⪪θ=⬤θNo"{"→↘λΠz*"✂θκ+3κ

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

∧Noθ=

The input must contain at least one =, and...

∧⌊⪪θ=

... it must not contain leading, consecutive or trailing =s, and...

⬤θNo"{"→↘λΠz*"✂θκ+3κ

each sliding window of length 3 must be contained within the compressed string ---=_=-=___=--.

Answer 7

Regex with conditionals, 29 bytes

^((?(2)=(?!2円))(-|_)2円*){2,}$

Try it online! Link includes test cases. Explanation:

^(...){2,}$

Match at least two chains.

(?(2)=(?!2円))

If there is a previous chain, then it must be a different chain separated by =.

(-|_)2円*

Match a chain, but capturing only its first character.

Regex with lookbehind, (削除) 31 (削除ここまで) 30 bytes

^(-+|_+)(=(-|_)(?<!3円=.)3円*)+$

Try it online! Link includes test cases. Explanation:

^(-+|_+)

Match a leading chain.

(...)+$

Match at least one more chain.

=(-|_)(?<!3円=.)

Ensure that each chain differs from the previous chain. (We don't have to match 3円 twice because the . much match the 3円 we just captured.)

3円*

Match the rest of this chain.

Regex with capture groups, 32 bytes:

^(-|_)1円*(=(?!1円)(?<1>-|_)1円*)+$

Try it online! Link includes test cases. Explanation:

^(-|_)1円*

Match an initial chain, but capturing only its first character.

(...)+$

Match at least one more chain.

=(?!1円)

Ensure that each chain differs from the previous chain.

(?<1>-|_)1円*

Match the next chain, but capturing only its first character, pushing it to the original group.

Answer 8

Brainfuck, 379 bytes (wrap + soft non-wrap)

>+>>+++[>+++++<-]>[>+++>++++<<-]<,[>+<<+>-]>>[<-<+>>-]<[<[>->+<<-]>-----[<<<->>>
>[<+<+>>-]<<[>+>+<<-]>+++++[-]]]<[>>+<<-],[<[>>+<-<-]>[>[<+<+>>-]>>[<<<->+>>-]<<
<-[<<[-]>>+>[<+>>>+<<-]<[-]]>[>>+<<-],<<[>+>-<<-]>>[<[>+<-]]<[<<[-]>>[-]<]<<[-]+
>>>>>[<-<+>>-]<[<[>->+<<-]>-----[<<<[-]>>>>[<+<+>>-]<<[>+>+<<-]>++++[-]]>[<<+<+>
>>-]<<<+++++>>]<[>+>+<<-]]>[<<+>>-]<,]<<<[->+<]>--[<]>>>>>.

Try it online! Outputs - for False and < for True. With EOF = 0.

It's been a while since I did anything in brainfuck. I'm sure I missed something that can obviously be golfed further.

This program works for the usual implementation that wraps cells at 255, but also for programs without wrap (soft non-wrap: they accept negative numbers). Accepting negative numbers bloats the size quite a lot, because you always need to go back to a point where you're certain the number isn't negative for [-] to terminate. I might come back to simplify the wrapping version, there's at least 65 free bytes to save and maybe more.

It's nice how the ASCII value for _ (95) is almost double - (45) and that - and = (61) almost have a common divisor of 15. Creating the constants is either unnecessary or can be easily combined.

I did not yet try using a state-machine that sets up the - and _ values and compares each chain to the appropriate one, but I think that could actually make the opposite + valid check simpler.

Summary of steps

LINES 4 TO 6: setup
LINES 8 TO 17: check if valid first character
LINES 19 TO 55: core: consume alleged chain and mark if invalid
 LINES 23 TO 52: not identical: is the next value an equals sign and the value after that the opposite chain
 LINES 26 TO 31: Check if interruption an equals sign
 LINES 33 TO 39: Check if next chain not identical to current
 LINES 42 TO 52: Check if new chain is valid
LINES 57 TO 63: Output

Summary of cells

When	0	1	5	6
Always (except when being used)	Is there at least one = in the chain	Is there NOT [an invalid transition or an invalid character (including EOF after =)]	45: -	60: <, = - 1

When	2	3	4
Interrupted by =?	Previous chain value	Interrupt - 61	60, then next chain
Identical chain	0	Previous chain value, then 0	0
Not identical chain	0	0	Next chain value
Non-destructively - or _?	0 or 50	45	0 or (50, then 0) or (other, then 0)

Full code with comments

OUTPUTS MINUS FOR FALSE AND LESS THAN FOR TRUE works both with wrap and without wrap (soft)
LINES 4 TO 6: setup
 >+>>+++[>+++++<-]> # Create marker for invalid and value 15
 [>+++>++++<<-] # Create 45 and 60
 <,[>+<<+>-]> # Store first input twice to validate as hyphen or underscore and compare to next values
LINES 8 TO 17: check if valid first character
 >[<-<+>>-] # Compare to hyphen
 <[ not a hyphen
 <[>->+<<-]>----- # Test against 95 underscore and resets 45
 [ not an underscore
 <<<->>>> # Mark as invalid
 [<+<+>>-]<<[>+>+<<-] # Add 90 again
 >+++++[-] # Add 5 and reset
 ]
 ]
 <[>>+<<-] # Reset 45 if started with hyphen
LINES 19 TO 55: core: consume alleged chain and mark if invalid
 Left (third) cell contains the previous value
 ,[ while there is a new value
 <[>>+<-<-] # Compare to previous
 LINES 23 TO 52: not identical: is the next value an equals sign and the value after that the opposite chain
 >[ not same chain check if equals sign
 >[<+<+>>-] # Reset value and store for later
 LINES 26 TO 31: Check if interruption an equals sign
 >>[<<<->+>>-] # Compare to equals sign
 <<<-[ chain interrupt not an equals sign
 <<[-]>> # Mark as invalid
 +>[<+>>>+<<-]<[-] # Reset value and 60 then remove value
 ]
 >[>>+<<-], # Move 60 back if not already and store next chain value
 LINES 33 TO 39: Check if next chain not identical to current
 <<[>+>-<<-] # Compare to previous chain value
 >>[ not equal to previous chain
 <[>+<-] # Reset new chain value pointer now moves one left
 ]
 <[ non empty only if pointer didn't move left and values were equal
 <<[-]>>[-]< # Mark as invalid and remove stored value of previous chain
 ]
 <<[-]+>> # Mark as having an equals sign in the string
 LINES 42 TO 52: Check if new chain is valid
 >>>[<-<+>>-] # Compare to hyphen
 <[ not a hyphen
 <[>->+<<-]>----- # Test against 95 underscore and resets 45
 [ not an underscore
 <<<[-]>>>> # Mark as invalid
 [<+<+>>-]<<[>+>+<<-] # Add 90 again
 >++++[-] # Add 5 and reset; we can add 4 because null would have been filtered already
 ]
 >[<<+<+>>>-]<<<+++++>> # Add 50 to spot of next chain value
 ]
 <[>+>+<<-] # Re add 45 if started with hyphen and copy back for comparison to next value
 ]
 >[<<+>>-]<, # Set next value and move to start previous
 ]
LINES 57 TO 63: Output
 string ended pointer at 3
 <<<[->+<]>--[<] # Move one to the right if valid string
 Three options:
 * either no equals sign so never go right
 * equals sign but also invalid go right then back to left
 * equals sign and valid go right then back to left
 >>>>>. # Output minus/less than sign

Answer 9

JavaScript (Node.js), 66 bytes

a=>!!a.map(c=>a|=s=+"XX22200XX03X1"[s+5*"-_=".indexOf(c)],s=4)&a+s

Try it online!

Modified from Arnauld's

!!a.map(...) is true or 1 when used in bitwise operation.

a is the bitor of all historical value of s, so if a and s have different lowest bit then a has 1 and s has 0

Answer 10

Nibbles, 11.5 bytes (23 nibbles)

^==*"=";`=|$?"_-"$$_<<

Inspired by Unrelated String's Jelly answer.

Outputs a non-empty list (truthy) if the input is a valid, an empty list (falsy) if the input is not valid.

^==*"=";`=|$?"_-"$$_<< # full program
^==*"=";`=|$?"_-"$$_<<$ # with implicit arg added;
 | # filter
 $ # the input
 ? $ # for letters that occur in
 "_-" # "_-"
 `= # and split into chunks
 $ # of identical items
 ; # (save this for later);
 * # now join these chunks
 "=" # using "=" between them
 == # and check if this is equal to
 _ # the input (1 if it is, 0 otherwise);
^ # finally, use this value to replicate
 $ # the saved chunks from earlier
 << # but without the last one 

enter image description here

Answer 11

Vyxal G, (削除) 90 (削除ここまで) (削除) 86 (削除ここまで) 79 bits^v2 , (削除) 11.25 (削除ここまで) (削除) 10.75 (削除ここまで) 9.875 bytes

\_‹↔Ġ\=j(≈≠

Try it Online!

Ports jelly but uses inverted booleans. Truly goofy hours here.

Explained

\_‹↔Ġṅ\=j(≈≠­⁡​‎‎⁡⁠⁤‏‏​⁡⁠⁡‌⁢​‎‎⁡⁠⁡‏⁠‎⁡⁠⁢‏⁠‎⁡⁠⁣‏‏​⁡⁠⁡‌⁣​‎‎⁡⁠⁢⁡‏⁠‎⁡⁠⁢⁢‏‏​⁡⁠⁡‌⁤​‎‎⁡⁠⁢⁣‏⁠‎⁡⁠⁢⁤‏⁠‎⁡⁠⁣⁡‏‏​⁡⁠⁡‌⁢⁡​‎‎⁡⁠⁣⁢‏⁠‎⁡⁠⁣⁣‏⁠‏​⁡⁠⁡‌⁢⁢​‎‎⁡⁠⁣⁢‏⁠‎⁡⁠⁣⁤‏‏​⁡⁠⁡‌­
 ↔ # ‎⁡The input filtered to only keep characters from
\_‹ # ‎⁢the string "_-" 
 Ġṅ # ‎⁣Grouped on consecutive characters
 \=j # ‎⁤Joined on "="s
 (≈ # ‎⁢⁡Check whether every item is the same (inverted boolean here makes it so that 0 means there's more than one pipe type)
 ( ≠ # ‎⁢⁢Check that the string does not equal the input (inverted boolean here means 0 means its the same) 
💎 Created with the help of Luminespire at https://vyxal.github.io/Luminespire

Answer 12

Pyth, 19 bytes

q{SM.:{McQ\=2,M]"-_

Try it online!

Feels like there's one or two more bytes to be shaved here, but I couldn't get them for now.

Explanation

 # implicitly assign Q = eval(input())
 cQ\= # split q on "="
 {M # deduplicate each element, turning runs into single chars
 .: 2 # get all sublists of length 2
 SM # sort each sublist
 { # deduplicate the whole list
q ,M]"-_ # compare to [["-", "_"]]

Answer 13

Python 3, (削除) 60 (削除ここまで) 97 bytes

• Edit: missed some of the rules, will revisit!

fun challenge!

lambda s:{str({*q})for q in s.split('=')}=={"{'-'}","{'_'}"}and(s.count("-=-")+s.count("_=_")==0)

Try it online!

Python 3.9, 53 bytes

3.9 allows str unpacking/decoding which doesnt work in 3.8 (at least not on TIO). The dreaded "works on my computer" lol.

lambda s:{str(*{*q})for q in s.split('=')}=={'-','_'}

As always any help is appreciated!

• Neil: Unfortunately you seem to have optimised for the test cases, as your code returns True for the invalid tplc -=_=_.
• spooky_simon: agh, youre right

Answer 14

J, 44 bytes

1-:&~.2+/\'_-=';@(2<@(,3#~1~:#)@~.;._1@,i.)]

Try it online!

Surprisingly difficult problem to golf well in J. I tried a few approaches.

Here we:

• Convert _-= to 0 1 2
• Split on 2, and to each split group...
• Take the unique and...
• Append nothing to it if it has length 1, otherwise append a 3
• The result at this point will have the alternating form 0 1 0 1... or 1 0 1 0... iff it is a valid chain
• To check this, we take all sums of consecutive elements, take the unique of the result, and check if it is 1

Answer 15

JavaScript (Node.js), 84 bytes

Interesting challenge!
This is a more classic JS solution, quite longer than the two "finite-state machine" answers.

p=>!p.split`=`.some(a=(s,i)=>(s<1|[...s].some(c=>c!="_-"[((p[0]!='_')+(a=i))%2])))&a>0

Try it online!

---

• The two some are basically two every negated, with their inner condition also negated
• The first some parses each string between and around the =, and the second some parses each character inside each string and controls that they all have the correct value (using the index of the string inside the splitted array, and the starting character of the whole input)
• The a>0 controls that the input contains at least one =
• The s<1 controls that no string are empty between and around the =