| Bytes | Lang | Time | Link |
|---|---|---|---|
| 021 | Haskell + hgl | 240722T164318Z | Wheat Wi |
| 029 | K ngn/k | 230730T055022Z | doug |
| 016 | Jelly | 230310T074138Z | Unrelate |
| 074 | Scala | 230525T104351Z | 138 Aspe |
| 063 | Python | 230310T083101Z | JvdV |
| 134 | Go | 230310T150805Z | bigyihsu |
| 033 | Charcoal | 230311T010149Z | Neil |
| 017 | 05AB1E | 230310T100654Z | Kevin Cr |
| 028 | Retina 0.8.2 | 230310T094925Z | Neil |
| 055 | JavaScript Node.js | 230310T065841Z | tsh |
Haskell + hgl, 21 bytes
cP$rX"[AB]/r[AC]/r?|"
No regex, 32 bytes
x=py$xay"AB"<*x<*xay"AC"<*x
cP x
No parsers, 41 bytes
g=no<jn<(lL<db)<<ce
g 'C'<pxn*^*g 'B'<sxn
Reflection
- There should be a shortcut for
cP<rX. (<*?)and(?*>)have the wrong type they aret m -> t m -> t m, but the two input types do not need to be the same.- There could be a parser combinator for the recursive pattern used in the no regex answer. It appears in a lot of balanced string type questions. This could then be
cP$on blj xys"AB""AC"which would tie the regex answer at least.
K (ngn/k), 43 41 36 29 bytes
~&/0{(0>)_,/x+/:1-2*&2 2\-y}/
-2 bytes : Better lookup
-5 bytes : Even better thanks to @ngn
-7 bytes : Fairly sizeable overhaul by @ngn (go team ngn/k!!)
Jelly, 18 15 16 bytes
,UċƤ"⁾CBḤ«ƑJ>LḂ$
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.
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)
}
}
}
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.
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)}
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.
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.
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.
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.
JavaScript (Node.js), 55 bytes
f=([x,...y],z)=>x?x<'C'&f(y,-~z)|x!='B'&z>0&f(y,~-z):!z
This question can be solved in linear time, however we do prefer golf instead of time complexity.
