# Language Word Checker

Develop a program to check if a given word is part of a language defined by the following rules:

• The language has a set of rules.
• The empty string is considered a valid word in the language.
• Two words from the language can be concatenated to create a new word in the language.
• If X is a word in the language, then "A" + X + "A" is also a word in the language.
• If X is a word in the language, then "A" + X + "C" is also a word in the language.
• If X is a word in the language, then "B" + X + "A" is also a word in the language.
• If X is a word in the language, then "B" + X + "C" is also a word in the language.

You can assume all inputs only consist of the characters A, B and C.

Examples:

• The word "CB" doesn't belong to the language. There is no way to arrive at this word from the above rules.

• The word "BAAC" belongs to the language.

Reasoning: The empty string is a valid word. Applying the "A" + X + "A" rule, we get "AA". Now we apply the "B" + X + "C" rule to get "BAAC".

• The word "BCBC" belongs to the language.

Reasoning: The empty string is a valid word. Applying the "B" + X + "C" rule, we get "BC". Now we apply the concatenation rule to get "BCBC". The concatenation rule can be used to concatenate a word with itself.

## Test cases

CBAA ---> false
CBBB ---> false
BCCA ---> false
CCAC ---> false
ABAC ---> true
ACAB ---> false
AAAC ---> true
BBAC ---> true
CABC ---> false
CCAB ---> false


This is a problem. While the language looks random, I hope you can find a pattern in the language to write the shortest code possible. Hint: It is possible to check in linear time.

• Can we assume the input will only consist of these three letters, or do we have to test for and reject other letters? Mar 10 at 5:21
• Of course! Isn't this the norm for our site? Anyway, I'll edit the question. Mar 10 at 5:22
• I just wanted to be sure, since this problem is about input validation. It feels different than saying a number will only consist of digits, for example. Mar 10 at 5:24
• Suggested title: "Accept this funky context-free language". "Language Word Checker" suggests some kind of natlang battery thing. Mar 10 at 7:03
• Suggested tag: balanced-string
– tsh
Mar 10 at 7:08

# Jelly, 18 15 bytes

,UċƤ"⁾CBḤ«ƑJ^LḂ


Try it online!

Validated against tsh's Python demonstration and against JvdV's regex. Checks that no more than half of the symbols in every prefix are C and that no more than half of the symbols in every suffix are B.

,U                 Pair the input with its reverse.
"⁾CB           For the original and C, and the reverse and B:
ċƤ               Count how many times the symbol occurs in each prefix.
Ḥ          Double the counts.
«Ƒ        Are all elements less than or equal to
J       their 1-indices?
^LḂ    Also, reject any odd-length inputs.


# JavaScript (Node.js), 55 bytes

f=([x,...y],z)=>x?x<'C'&f(y,-~z)|x!='B'&z>0&f(y,~-z):!z


Try it online!

This question can be solved in linear time, however we do prefer golf instead of time complexity.

# Retina 0.8.2, 28 bytes

^((A|B)|(?<-2>A|C))*$(?(2)^)  Try it online! Link includes test cases. Explanation: ^(  Starting at the beginning of the string, ... (A|B)|  match either of A or B, or... (?<-2>A|C)  ... match a previously matched A or B with an A or C, removing the knowledge of the match, so that a subsequent A or C has to match a previous Aor B, ... )*$


... repeating until the end of the string, ...

(?(2)^)


without leaving any unmatched leading As or Bs.

# Python, 63 bytes

lambda x:bool(match('^([AB](?1)*[AC])*$',x)) from regex import*  See an online demo This is based on the PCRE regex pattern: ^([AB](?1)*[AC])*$


See an online demo. I was unsure if we were allowed to simply post the pattern for 18 bytes.

# Excel (ms365), 120 bytes

Formula in B1:

=REDUCE(A1,ROW(A:A),LAMBDA(a,b,IFERROR(REPLACE(a,MIN(IFERROR(FIND({"AC","BA","BC"},a),"")),2,),SUBSTITUTE(a,"AA",))))=""


The idea here is to 1st replace any of the compound words that are not a copy of itself. If not found, try to replace 'AA'. Check if the final result after the last iteration is empty.

• If you're any good with .NET regex, you could always do a Retina answer Mar 10 at 8:31
• ...Also erroneously rejects AABA, AACACA. ^([AB](?1)*[AC])*\$ seems to work though. Mar 10 at 8:43
• You can't hardcode the input into your program. However, you can submit a function like this: ato.pxeger.com/… Mar 10 at 13:34
• You can also use a star import to save one byte: ato.pxeger.com/… Mar 10 at 13:37
• Building on @xigoi's suggestion: another byte saved Mar 10 at 16:12

# 05AB1E, 17 bytes

„AB„ACâIgиæõδ.;õå


Try it online or verify all test cases. The test suite contains a ; (halve) after the g to speed it up substantially.

Explanation:

„AB„ACâ     # Push ["AA","AC","BA","BC"] by taking the cartesian product of "AB" & "AC"
Ig         # Push the length of the input-string
и        # Repeat the earlier list of strings that many times as single list,
# so each individual pair is repeated the input-length amount of times
æ       # Get the powerset of this list
δ     # Map over each inner list:
õ .;   #  Replace every first occurrence of the pairs one by one with an empty
#  string in the (implicit) input-string
õå # Check if the resulting list contains an empty string
# (after which the result is output implicitly)


Minor note: for an explicit empty string input, it'll do the following steps: „AB„ACâIgи=[]æ=[[]]õδ.;=[""]õå=1 (truthy). This is different than if no input is provided, since õδ.; would then keep [[]] and the result is falsey: try it online with explicit empty string input vs try it online without any input.

# Charcoal, 33 bytes

⊞υＳＦυＦABＦACＦ⌕Ａι⁺κλ⊞υΦι∧⁻ξμ⁻ξ⊕μ¬⌊υ


Try it online! Link is to verbose version of code. Explanation:

⊞υＳ


Start a breadth-first search with the input string.

Ｆυ


Loop over all of the found strings.

ＦABＦAC


Loop over AB, AC, BA and BC.

Ｆ⌕Ａι⁺κλ


Loop over all of the indices of those substrings in the string being considered.

⊞υΦι∧⁻ξμ⁻ξ⊕μ


Push the string with the substring at that index removed to the list of strings to consider.

¬⌊υ


See whether we were able to end up with the empty string.

# Go, 125 134 bytes

import."strings"
func f(s string)bool{l:=s
for _,e:=range[]string{"BA","AC","BC","AA"}{l=ReplaceAll(l,e,"")}
return l==""||l!=s&&f(l)}


Attempt This Online!

Recursive function that repeatedly replaces the A[empty string]B pairs with an empty string.

### Explanation, slightly ungolfed

import."strings"      // boilerplate
func f(s string)bool{ // function that maps string -> bool
l:=s                  // init
for _,e:=range[]string{"BA","AC","BC","AA"}{
// replace these pairs in this exact order
l=ReplaceAll(l,e,"")} // with an empty string
return l==""||l!=s&&f(l)} // ok if empty, not ok if non-empty


### Changelog

• +9 bytes for matching AACC, using a different approach.
• This rejects empty string as an input, but I think that can be fixed by rearranging the return statement: l==E||l!=s&&f(l). As a bonus, it's shorter, too. Mar 11 at 0:41
• Fails for AACC.
– Neil
Mar 11 at 0:50
• This submission is still invalid after the fix. Please stress test your code. Mar 11 at 5:30
• To stress test, you can do what Unrelated String did. One test case you fail on among many is AAAACCCC. I recommend you don't attempt ad hoc fixes to patch individual test cases. Use stress testing instead to validate your program. Mar 11 at 17:31
• I noticed that you did a fix. You can do more stress testing on longer inputs, for example inputs of length 10. Mar 11 at 17:35