10
\$\begingroup\$

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.

\$\endgroup\$
6
  • \$\begingroup\$ Can we assume the input will only consist of these three letters, or do we have to test for and reject other letters? \$\endgroup\$
    – Bbrk24
    Mar 10, 2023 at 5:21
  • \$\begingroup\$ Of course! Isn't this the norm for our site? Anyway, I'll edit the question. \$\endgroup\$ Mar 10, 2023 at 5:22
  • \$\begingroup\$ 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. \$\endgroup\$
    – Bbrk24
    Mar 10, 2023 at 5:24
  • 4
    \$\begingroup\$ Suggested title: "Accept this funky context-free language". "Language Word Checker" suggests some kind of natlang battery thing. \$\endgroup\$ Mar 10, 2023 at 7:03
  • 3
    \$\begingroup\$ Suggested tag: balanced-string \$\endgroup\$
    – tsh
    Mar 10, 2023 at 7:08

9 Answers 9

7
\$\begingroup\$

Jelly, 18 15 16 bytes

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

Try it online!

Validated against tsh's Python demonstration and against JvdV's regex. (But, I neglected to check extremely unbalanced odd cases...) 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.
\$\endgroup\$
5
  • \$\begingroup\$ I don’t know Jelly but from your description I don’t get how it accommodates concatenation. For instance AACCBA. \$\endgroup\$
    – doug
    Jul 31, 2023 at 4:17
  • \$\begingroup\$ @doug In AACCBA, the prefix C counts are 0, 0, 1, 2, 2, 2, and the suffix B counts backwards are 1, 1, 1, 1, 1, 0. None of those are strictly greater than 1, 2, 3, 4, 5, 6, so it knows that there aren't so many of one or the other that the string can't possibly be balanced (if you treat A as something that can be arbitrarily made into a B or C). \$\endgroup\$ Jul 31, 2023 at 6:59
  • \$\begingroup\$ But this a valid string as it’s the concatenation of AACC and BA. \$\endgroup\$
    – doug
    Jul 31, 2023 at 7:02
  • \$\begingroup\$ @doug And it's properly accepted, since neither the Bs nor Cs are too "heavy". \$\endgroup\$ Jul 31, 2023 at 7:43
  • 1
    \$\begingroup\$ Oh, fair enough. I hadn't grokked your description. I thought you were pairing stuff from the front with the back. I'm not sure I get it still, but I'll ruminate on it. Thanks for the clarification. \$\endgroup\$
    – doug
    Jul 31, 2023 at 7:55
4
\$\begingroup\$

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

enter image description here

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.

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

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.

\$\endgroup\$
3
\$\begingroup\$

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.

\$\endgroup\$
3
\$\begingroup\$

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.
\$\endgroup\$
6
  • 1
    \$\begingroup\$ 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. \$\endgroup\$
    – Bbrk24
    Mar 11, 2023 at 0:41
  • 2
    \$\begingroup\$ Fails for AACC. \$\endgroup\$
    – Neil
    Mar 11, 2023 at 0:50
  • 1
    \$\begingroup\$ This submission is still invalid after the fix. Please stress test your code. \$\endgroup\$ Mar 11, 2023 at 5:30
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ Mar 11, 2023 at 17:31
  • 1
    \$\begingroup\$ I noticed that you did a fix. You can do more stress testing on longer inputs, for example inputs of length 10. \$\endgroup\$ Mar 11, 2023 at 17:35
2
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

Charcoal, 33 bytes

⊞υSFυFABFACF⌕Aι⁺κλ⊞υΦι∧⁻ξμ⁻ξ⊕μ¬⌊υ

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

⊞υS

Start a breadth-first search with the input string.

Fυ

Loop over all of the found strings.

FABFAC

Loop over AB, AC, BA and BC.

F⌕Aι⁺κλ

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.

\$\endgroup\$
2
\$\begingroup\$

Scala, 74 bytes

Golfed version. Try it online!

f={case(x::y,z)=>(x<'C'&f(y,z+1))|(x!='B'&z>0&f(y,z-1));case(Nil,z)=>z==0}

Ungolfed version. Try it online!

object Main {

  def f(chars: List[Char], z: Int): Boolean = chars match {
    case x :: y =>
      (x < 'C' && f(y, z + 1)) || (x != 'B' && z > 0 && f(y, z - 1))
    case Nil => z == 0
  }

  def main(args: Array[String]): Unit = {
    val testcases = List(
      ("AA", true),
      ("CBAA", false),
      ("CBBB", false),
      ("BCCA", false),
      ("CCAC", false),
      ("ABAC", true),
      ("ACAB", false),
      ("AAAC", true),
      ("BBAC", true),
      ("CABC", false),
      ("CCAB", false)
    )

    for ((i, e) <- testcases) {
      val result = f(i.toList, 0)
      println(if (result == e) "v" else "x", result)
    }
  }

}

\$\endgroup\$
2
\$\begingroup\$

K (ngn/k), 43 41 36 29 bytes

~&/0{(0>)_,/x+/:1-2*&2 2\-y}/

Try it online!

-2 bytes : Better lookup
-5 bytes : Even better thanks to @ngn
-7 bytes : Fairly sizeable overhaul by @ngn (go team ngn/k!!)

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.