Language Word Checker

Question

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 code-golf 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.

Answer 1

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.

Answer 2

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.

Answer 3

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.

Answer 4

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.

Answer 5

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.

Answer 6

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.

Answer 7

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.