9
$\begingroup$

$[A ...] \to A [...]$

$[B ...] \to B [S [...]]$

$[S A ...] \to B ...$

$[S B ...] \to A [S ...]$

$[S] \to B$

$[ ] \to$

(E.g. $[AAB] \to AABB$)

But, $[????] \to BABBAB$

Bonus puzzle:

Characterize all sequences of A's and B's so that $[?] => sequence$, for some ? sequence of A's and B's

Improve this question
$\endgroup$
2
  • $\begingroup$ Hello! Welcome to puzzling SE! Please take the tour (you'll also get a badge, too) to get a better understanding of community expectations. $\endgroup$ – Prince North Læraðr Mar 8 '18 at 0:25
  • 5
    $\begingroup$ Wow is everyone overlooking that clever title ?! Made me chuckle about those decade old memes. Obligatory video and related required viewing. $\endgroup$ – Amit Naidu Mar 8 '18 at 5:43
8
$\begingroup$

The only four-letter sequence [????] that works is:

[BBBB]

This evaluates as

[BBBB] →
B[S[BBB]] →
B[SB[S[BB]]] →
B[SB[SB[S[B]]]] →
B[SB[SB[SB[S[]]]]] →
B[SB[SB[SB[S]]]] →
B[SB[SB[SBB]]] →
B[SB[SBA[SB]]] →
B[SB[SBAA[S]]] →
B[SB[SBAAB]] →
B[SBA[SAAB]] →
B[SBABAB] →
BA[SABAB] →

BABBAB

I found this through directed guessing:

I evaluated the 3 letter sequences [AAB], [BBA] and [BBB], and these gave me a good feel for what might work and what definitely wouldn't. Then I jumped to four letter sequences and took a couple wrong guesses before finding this solution.

 

Bonus:
I've now written some code to find generable outputs (and was able to confirm that the above solution is unique for four letter inputs). I believe that the rule is:

Treating "A" as 0 and "B" as 1, and evaluating the outputs that can be produced by this ruleset as binary, the possible outputs are all the multiples of 3. (Or, at minimum, they are all multiples of 3, even if not all such multiples can be generated.)

Here's what I've been able to find are the generable outputs:

length of 1: A B
length of 2: AA AB BA BB
length of 3: AAA AAB ABA ABB BAA BAB BBA BBB
length of 4: AAAA AAAB AABA AABB ABAA ABAB ABBA ABBB
        BAAA BAAB BABA BABB BBAA BBAB BBBA BBBB
where BOLD are generable outputs and ITALIC are outputs that cannot be generated.

The only generable outputs of length 5 are:
        AAAAA AAABB AABBA ABAAB ABBAA ABBBB
        BAABA BABAB BBAAA BBABB BBBBA

and for length 6 are:
        AAAAAA AAAABB AAABBA AABAAB AABBAA AABBBB
        ABAABA ABABAB ABBAAA ABBABB ABBBBA BAAAAB
        BAABAA BAABBB BABABA BABBAB BBAAAA BBAABB
        BBABBA BBBAAB BBBBAA BBBBBB

I finally noticed that ...

the generable outputs occur at intervals of 3.

Improve this answer
$\endgroup$
2
  • $\begingroup$ the bonus question is asking for a general rule of [?] where ? can represent any string of As and Bs $\endgroup$ – Praneetmek Mar 8 '18 at 1:04
  • $\begingroup$ The bonus question asks which sequences its possible to end up with given a start of A's and B's (there is a very simple rule to tell if a sequence is a possible output) $\endgroup$ – while1fork Mar 8 '18 at 1:11
1
$\begingroup$

Not sure if its a typo or not, but currently from the list of rules

[SAABBAB]= BABBAB

Improve this answer
$\endgroup$
8
  • $\begingroup$ Was thinking about the same $\endgroup$ – user45835 Mar 8 '18 at 0:35
  • 1
    $\begingroup$ I assumed "[????]" was seeking a four letter sequence. If not then yes, this is correct. $\endgroup$ – Rubio♦ Mar 8 '18 at 0:37
  • $\begingroup$ maybe OP meant [SA....]=B[...] and just typoed? $\endgroup$ – Praneetmek Mar 8 '18 at 0:38
  • 1
    $\begingroup$ @Rubio Either that or, from the way the bonus is phrased, ???? can only contain A's and B's, without any S's. $\endgroup$ – DqwertyC Mar 8 '18 at 0:40
  • 1
    $\begingroup$ Directed guessing. I tried 3 letter sequences [AAB], [BBA] and [BBB] and they gave me a good feel for what might work and what definitely wouldn't. Then jumped to four letter sequences and took a couple wrong guesses before finding that one. $\endgroup$ – Rubio♦ Mar 8 '18 at 1:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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