9
\$\begingroup\$

Background

Imagine that I'm creating a really long necklace, consisting of only two characters, A and B. You must count the number of occurrences of the substring AB in the string.

However, since it's a necklace, you must also consider if the last character and the first character join to make AB. For example, in BBBA, there would be 1 occurrence of AB, as the final A would join to the first B.

Finally, since I'm not finished making the chain, you must continually accept an input. Every successive input after the first is intended to be appended to the current necklace. You must also provide the output for the entire appended necklace after each input. Due to I/O limitations however, these inputs will be given as an array.

Your Task

  • Sample input: An array consisting of strings consisting of any two different characters of your choosing, only. You must clarify in your answer what the substring you're checking for is (which is of length two, and contains both of the distinct characters you're using). You may not use a boolean array.

  • Output: The number of occurrences of the substring, as an array of outputs.

Explained Examples

Input => Output
ABABA => 2
ABABA => 4

The chain at the second output would be ABABAABABA, which contains 4 ABs.
Input => Output
BA => 1
BABA => 3
BB => 3
BAAAAB => 4

The chain at the second output would be BABABA, which contains 3 ABs including the A at the end and the B at the start.
The chain at the third output would be BABABABB, which contains 3 ABs
The chain at the fourth output would be BABABABBBAAAAB, which contains 4 ABs 

Test Cases

Input => Output
ABABA => 2
ABABA => 4
//
BA => 1
BABA => 3
BB => 3
BAAAAB => 4
//
AB => 1
AAA => 1
B => 2
AB => 3
//
BAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAB => 1 
A => 2
B => 2
A => 3
A => 3
B => 3
//
BABABABABABAB => 6
A => 7

This is , so shortest answer wins. (# of bytes)

\$\endgroup\$
3
  • 5
    \$\begingroup\$ Not allowing a boolean array seems like needless restriction \$\endgroup\$
    – mousetail
    Jul 24, 2023 at 9:23
  • 4
    \$\begingroup\$ How can ABABA have 2 possible outputs? How do you know how often a chain repeats \$\endgroup\$
    – mousetail
    Jul 24, 2023 at 9:26
  • 4
    \$\begingroup\$ @mousetail - The input is an array of strings. In the first test-case, the input array is [ABABA,ABABA], with 2 outputs (one for each element of the array). In this case, the two elements of the array happen to be the same, which indeed makes it a little confusing at first... \$\endgroup\$ Jul 24, 2023 at 13:04

17 Answers 17

6
\$\begingroup\$

Vyxal, 5 bytes

¦ƛǏ₀O

Try it Online!

Uses the characters 1 and 0, checks for substring 10.

Explained

¦ƛǏ₀O­⁡​‎‎⁡⁠⁡‏⁠‎⁡⁠⁢‏‏​⁡⁠⁡‌⁢​‎‎⁡⁠⁣‏‏​⁡⁠⁡‌⁣​‎‎⁡⁠⁤‏⁠‎⁡⁠⁢⁡‏‏​⁡⁠⁡‌­
¦ƛ     # ‎⁡To each prefix of the input:
  Ǐ    # ‎⁢  Append the first character to the end
   ₀O  # ‎⁣  And count the number of instances of "10" in that
💎

Created with the help of Luminespire.

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

JavaScript (ES6), 117 bytes

k=>{for(let i=1;i<=k.length;i++)console.log(((s=k.slice(0,i).join('')).match(/01/g)||[]).length+!(+s.at(-1)-~-s[0]))}

Uses 0 instead of A and 1 instead of B.

I could probably get rid of the first/last character special case by appending the first character at the end like Vyxal did using (k.slice(0,i).join('')+k[0][0]).match(/01/g) instead of (s=k.slice(0,i).join('')).match(/01/g) but I can't be bothered to rewrite my terrible explanation

Explained

// Take k ['01010', '01010']
// Convert it to s '01010'
// Then in the next loop s='0101001010'
// In s, count the occurences of 01
// Then count special case of first/last characters

// k has length N
k=>{for(let i=1;i<=k.length;i++) // Loop 'i' from 1 to N inclusive
console.log( // Output:

  (
    (s=k.slice(0,i).join('')) // Get bracelet up to current 'i'
    .match(/01/g)             // List of occurences of '01'
      ||[]                    // Default to empty list
  ).length                    // Get length
+
  !(+s.at(-1)-~-s[0]) // Is +s.at(-1)-~-s[0] equal to 0?
                      // (implicitly) convert to number

)}

But what is !(+s.at(-1)-~-s[0])?

s.at(-1) is the last element of s, and for the rest... well... I just threw a bunch of random stuff in there until it worked; please don't tell my coding teacher

With test cases

const f=

k=>{for(let i=1;i<=k.length;i++)console.log(((s=k.slice(0,i).join('')).match(/01/g)||[]).length+!(+s.at(-1)-~-s[0]))}

`
ABABA => 2
ABABA => 4
//
BA => 1
BABA => 3
BB => 3
BAAAAB => 4
//
ABABA => 2
ABABA => 4
//
BA => 1
BABA => 3
BB => 3
BAAAAB => 4
//
AB => 1
AAA => 1
B => 2
AB => 3
//
BAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAB => 1
A => 2
B => 2
A => 3
A => 3
B => 3
//
BABABABABABAB => 6
A => 7
`.slice(1,-1).replaceAll('A','0').replaceAll('B','1').split('\n//\n').forEach(testCase => {
    const parts = testCase.split('\n').map(x=>x.split(' => '));
    const input_ = parts.map(x=>x[0]);
    console.log('\n\nInput:',input_,'\nExpected output:');
    parts.forEach(x=>console.log(+x[1]));
    console.log('Output:');
    f(input_);
});
\$\endgroup\$
3
\$\begingroup\$

05AB1E (legacy), 6 bytes

ηJεĆT¢

I/O as a list. Uses characters 1 and 0 for A and B respectively.

Uses the legacy version of 05AB1E, because the new version of 05AB1E has a bug with multi-digit integers and the count builtin ¢, so it would require an additional § after the T.

Try it online! or verify all test cases.

Explanation:

η       # Get the prefixes of the (implicit) input-list
 J      # Join each inner list together to a single string
  ε     # Map over each string:
   Ć    #  Enclose; append its first character at the end
    T¢  #  Count how many times "10" occurs in this string
        # (after which the list of counts is output implicitly as result)
\$\endgroup\$
5
  • 1
    \$\begingroup\$ I noticed your first TIO link lead to new 05AB1E, so I edited it to be legacy 05AB1E for you :p \$\endgroup\$
    – lyxal
    Jul 24, 2023 at 12:36
  • \$\begingroup\$ @lyxal Oh, I copy-pasted it from another answer of mine, so apparently I've done it incorrectly before. 😅 \$\endgroup\$ Jul 24, 2023 at 12:45
  • \$\begingroup\$ Copy-pasting does tend to be like that sometimes. Keeping track of a mental clipboard is hard :p \$\endgroup\$
    – lyxal
    Jul 24, 2023 at 12:46
  • \$\begingroup\$ Still not using TIO's own TIO link generator then? \$\endgroup\$
    – Neil
    Jul 25, 2023 at 6:15
  • \$\begingroup\$ @Neil TIO's link generator links to the git home page, whereas I usually link to the Commands-page directly. For the legacy version, which is an older version of the new 05AB1E, I've apparently used the wrong git-hash before lyxal's edit. \$\endgroup\$ Jul 25, 2023 at 6:26
3
\$\begingroup\$

Scala, 139 61 bytes

Port of @Gábor Fekete's Python answer in Scala.


Golfed version. Attempt This Online!

Saved 78 bytes thanks to the comment of @corvus_192

var c="";def f(i:Any)={c+=i;(c+c(0))sliding 2 count(_=="AB")}

Ungolfed version. Attempt This Online!

import scala.collection.mutable.ArrayBuffer

object Main {

  var c: ArrayBuffer[String] = ArrayBuffer()

  def f(i: String): Int = {
    if (c.isEmpty) {
      c += i
    }
    else {
      c = ArrayBuffer(c.head + i)
    }
    (c.head + c.head(0)).sliding(2).count(_ == "AB")
  }

  def main(args: Array[String]): Unit = {
    val cases = Array(
      ("ABABA", 2),
      ("ABABA", 4),
      ("//", 0),
      ("BA", 1),
      ("BABA", 3),
      ("BB", 3),
      ("BAAAAB", 4),
      ("//", 0),
      ("AB", 1),
      ("AAA", 1),
      ("B", 2),
      ("AB", 3),
      ("//", 0),
      ("BAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAB", 1),
      ("A", 2),
      ("B", 2),
      ("A", 3),
      ("A", 3),
      ("B", 3),
      ("//", 0),
      ("BABABABABABAB", 6),
      ("A", 7)
    )

    for (caseValue <- cases) {
      caseValue._1 match {
        case "//" => 
          println("=" * 15)
          c = ArrayBuffer()
        case _ => 
          val t = f(caseValue._1)
          println(caseValue._1 + " " + caseValue._2 + " ; result: " + t)
      }
    }
  }
}

\$\endgroup\$
1
  • \$\begingroup\$ 61 bytes: var c="";def f(i:Any)={c+=i;(c+c(0))sliding 2 count(_=="AB")} \$\endgroup\$
    – corvus_192
    Jul 29, 2023 at 10:37
2
\$\begingroup\$

Charcoal, 19 bytes

WS«≔⁺ωιωI№⁺ω§ω⁰ABD⎚

Try it online! Link is to verbose version of code. Fully interactive version, so when run from the command line it will prompt for the next piece of necklace and output the count of ABs so far. Explanation:

WS«

Keep accepting pieces but stop when an empty piece is entered.

≔⁺ωιω

Concatenate the piece to the necklace so far.

I№⁺ω§ω⁰ABD⎚

Output the number of ABs so far.

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

Dyalog APL, 21 bytes

{∇⍵,⍞⊣⎕←+/'AB'⍷⍵,⊃⍵}⍞­⁡​‎‎⁡⁠⁢⁢⁡‏‏​⁡⁠⁡‌⁢​‎‎⁡⁠⁢⁣‏⁠‎⁡⁠⁢⁤‏‏​⁡⁠⁡‌⁣​‎‎⁡⁠⁣⁡‏⁠‎⁡⁠⁣⁢‏⁠‏​⁡⁠⁡‌⁤​‎‎⁡⁠⁣⁣‏⁠‎⁡⁠⁣⁤‏⁠‎⁡⁠⁤⁡‏⁠‎⁡⁠⁤⁢‏‏​⁡⁠⁡‌⁢⁡​‎‎⁡⁠⁤⁣‏⁠⁠⁠⁠‏​⁡⁠⁡‌⁢⁢​‎‎⁡⁠⁤⁤‏⁠‎⁡⁠⁢⁡⁡‏⁠‎⁡⁠⁢⁡⁢‏⁠‎⁡⁠⁢⁡⁣‏‏​⁡⁠⁡‌⁢⁣​‎‎⁡⁠⁢⁢‏‏​⁡⁠⁡‌⁢⁤​‎‎⁡⁠⁢‏‏​⁡⁠⁡‌⁣⁡​‎‎⁡⁠⁣‏⁠‎⁡⁠⁤‏⁠‎⁡⁠⁢⁡‏‏​⁡⁠⁡‌­
                    ⍞  # ‎⁡Take a line from standard input, and pass it to the following function:
      ⎕←               # ‎⁢  print
        +/             # ‎⁣  how many times
          'AB'         # ‎⁤  the string AB
              ⍷        # ‎⁢⁡  appears in
               ⍵,⊃⍵    # ‎⁢⁢  the string formed by concatenating the input and its first element
     ⊣                 # ‎⁢⁣  , then,
 ∇                     # ‎⁢⁤  call the same function
  ⍵,⍞                  # ‎⁣⁡  passing the input concatenated with another line from standard input
💎

Created with the help of Luminespire.

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

Swift 5.7 -enable-bare-slash-regex, 95 bytes

{var x=""
return $0.map{x+=$0
return x.ranges(of:/AB/).count+("B"==x.first&&"A"==x.last ?1:0)}}

Try it on SwiftFiddle! Without the -enable-bare-slash-regex flag, the regex literal /AB/ would be spelled #/AB/# on macOS, or try!Regex("AB") on Linux, so the flag is obvious. SwiftFiddle enables it by default on Swift 5.7 and later.

The code should be fairly straightforward: append the new element to what's been seen so far, then count the ranges that match /AB/, and check whether it starts with "B" and ends with "A".

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

Python, 67 65 55 bytes

lambda i,c=[]:c.extend(i)or''.join(c+c[:1]).count('AB')

Attempt This Online!

Using the default list argument to memorize the previous inputs.

edit: changed extend to append to save 2 bytes

edit: with the help of @Albert.Lang and @Jonathan Allan golfed an additional 10 bytes

\$\endgroup\$
3
  • 1
    \$\begingroup\$ You can use extend like so f=lambda i,c=[]:[c.extend(i),''.join(c+c[:1]).count('AB')][1] for -4. \$\endgroup\$ Jul 24, 2023 at 17:07
  • 1
    \$\begingroup\$ Not sure if you need the f= as it's not self-referencing (one has to either redefine the function or reset a local scope c to reuse it anyway). You can save four more bytes with lambda i,c=[]:c.append(i)or(''.join(c)+c[0][0]).count('AB') regardless. \$\endgroup\$ Jul 24, 2023 at 19:20
  • 1
    \$\begingroup\$ Combining with Albert.Lang's suggestion that's 55 bytes. \$\endgroup\$ Jul 24, 2023 at 19:24
2
\$\begingroup\$

Ruby -nl, 40 38 bytes

a="#{a}#$_"
p (a+a[0]).scan('AB').size

Attempt This Online!

ruby -nl                     # -n loops program over each line of input
                             # -l automatically trims trailing newlines

a="       "                  # Set a to...
   #{a}                      #  a, if already set (empty string otherwise)
       #$_                   #  plus most recent line of input
  (a+a[0])                   # Get a plus its first character
          .scan('AB').size   #  and count all instances of AB
p                            # Print that number
\$\endgroup\$
2
\$\begingroup\$

Jelly, 7 bytes

;\ŒgẈ:2

Attempt This Online!

Port of my Nibbles answer.

;\ŒgẈ:2
;\      Concatenate all prefixes
        For each concatenated prefix:
  Œg     Group runs of equal elements
    Ẉ    Length
     :2  Floor divide by two
\$\endgroup\$
1
  • 1
    \$\begingroup\$ Ah, I was basically trying this, but with instead. Off by one! \$\endgroup\$ Jul 29, 2023 at 20:59
2
\$\begingroup\$

Nibbles, 6 bytes

`\$:/,`=+$$~

Attempt This Online!

Works with any two distinct characters.

`\$:/,`=+$$~
             For each p in
`\ :          prefixes of
  $            the input
     ,        length of
      `=  $    group runs of identical elements in
        +$      p concatenated
    /      ~  floor-divided by 2
\$\endgroup\$
3
  • \$\begingroup\$ Are you sure that this satisfies the "clarify in your answer what the substring you're checking for is" requirement? The substring checked-for seems to depend on the first character of the input... \$\endgroup\$ Jul 27, 2023 at 15:06
  • \$\begingroup\$ @DominicvanEssen Since the strings are treated as cyclic, the number of occurences of AB and BA is always equal. \$\endgroup\$
    – xigoi
    Jul 27, 2023 at 15:07
  • \$\begingroup\$ Aha! Very clever observation! \$\endgroup\$ Jul 27, 2023 at 15:10
1
\$\begingroup\$

Excel, 80 bytes

=MAP(SCAN("",A1#,LAMBDA(a,b,a&b)),LAMBDA(c,ROWS(TEXTSPLIT(RIGHT(c)&c,,"AB"))-1))

Input is vertical spilled range #A1.

\$\endgroup\$
1
\$\begingroup\$

Thunno 2, 6 bytes

ƒıJẹTc

Attempt This Online!

Uses 1 and 0, and checks for the substring 10, like Vyxal and 05AB1E.

Explanation

ƒıJẹTc  # Implicit input
ƒı      # Map over prefixes
  Jẹ    #  Join and append first character
    Tc  #  Count occurrences of "10"
        # Implicit output
\$\endgroup\$
1
\$\begingroup\$

Pyth, 11 bytes

m/shBsd`T._

Try it online!

Uses characters "1" and "0" for "A" and "B" respectively.

Explanation

m/shBsd`T._Q    # implicitly add Q
                # implicitly assign Q = eval(input())
         ._Q    # prefixes of Q
m               # map over lambda d
     sd         #   concatenate list of strings
   hB           #   bifurcate into [str, first_char(str)]
  s             #   concatenate list of strings
 /     `T       #   count occurrences of "10"
\$\endgroup\$
1
\$\begingroup\$

Perl 5 -pl, 28 bytes

$,.=$_;$_=chop.$,;$_=s/AB//g

Try it online!

\$\endgroup\$
1
\$\begingroup\$

Jelly, 9 8 bytes

;\µṙ1<)§

Try it online!

Something cleverer still feels possible. Takes input as shown in the test cases, since counting substring occurrences is actually pretty expensive anyways.

;\          Scan by concatenate, creating a list of each cumulative necklace.
  µ   )     For each:
   ṙ1       rotate left once, and
       §    count how many
     <      are less than in the corresponding original positions.
\$\endgroup\$
1
\$\begingroup\$

Scala 3, 65 bytes

_.scanLeft("")(_+_).tail.map(s=>(s+s(0))sliding 2 count(_=="AB"))

Attempt This Online!

\$\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.