An alphabet with two letters A and B has rules for creating words:
1. Any A must be part of a string containing an even number of A's.
2. Any B must be part of a string of containing an odd number of B's.
For example two six letter words could be BBBAAB and AAAAAA but ABABBB would not be valid.
How many valid 15 letter words are there?
The table below starts by representing B and AA as the sole 1- and 2-letter words. Counts are kept separately for 1) words starting and ending with A (headed A...A), 2) words starting and ending with B (headed B...B), 3) words beginning with A and ending with B (A...B), and 4) words beginning with B and ending with A (B...A).
Each table row is based upon the two preceding rows.
While the count of types of words ending in A can be build only upon the length two short of the length being calculated, that is, two rows up, the count of words ending in B can be based on both the preceding two rows: one row higher for prior words ending in A, and two rows higher for prior words ending in B, as the odd parity must be preserved. The "starting with" letter of course never changes as you add on letters.
The explanation of the transition algorithm appears to the right of the table. The second preceding line is identified with values a, b, c and d. The line just prior to the line being built is labeled with values e, f, g and h. The bottom row, the line being built, shows what totals get placed on that line.
A...A B...B A...B B...A
1 1 a b c d
2 1 e f g h
3 1 1 1 a+c h+b e+c b+d
4 1 1
5 1 1 2 2
6 1 3 1 1
7 3 2 3 3
8 2 6 4 4
These agree with results obtained via a different algorithm further on down this post, for 5- and 8-letter "words":
AABAA
AABBB
AAAAB
BAAAA
BBBAA
BBBBB
AABAABAA
AABAABBB
AABAAAAB
AABBBAAB
AAAABAAB
AAAAAAAA
BAABAAAA
BAABBBAA
BAABBBBB
BAAAABAA
BAAAABBB
BAAAAAAB
BBBAABAA
BBBAABBB
BBBAAAAB
BBBBBAAB
The table can be continued, but it's easier to write a program than to risk inadvertent errors along the way:
b = 1: e = 1
For goal = 3 To 16
i = a + c: j = h + b: k = e + c: l = b + d
Text1.Text = Text1.Text & mform(goal, "#0") & mform(i, "####0") & mform(j, "####0") & mform(k, "####0") & mform(l, "####0") & crlf
a = e: b = f: c = g: d = h
e = i: f = j: g = k: h = l
Next
Text1.Text = Text1.Text & crlf
resulting in
3 0 1 1 1
4 1 1 0 0
5 1 1 2 2
6 1 3 1 1
7 3 2 3 3
8 2 6 4 4
9 6 6 5 5
10 6 11 10 10
11 11 16 11 11
12 16 22 21 21
13 22 37 27 27
14 37 49 43 43
15 49 80 64 64
16 80 113 92 92
The line for 15 letter words adds up to 49 + 80 + 64 + 64 = 257, the desired solution.
The respective totals for different numbers of letters are:
1 1
2 1
3 3
4 2
5 6
6 6
7 11
8 16
9 22
10 37
11 49
12 80
13 113
14 172
15 257
16 377
These were calculated via a different algorithm but verify the soundness of the above. The sequence is
A062200 in Sloane's OEIS.
The different algorithm is recursive in the sense that it builds the words by adding 1, 3, 5, etc. B's, if the preceding letter was A, or adding 2, 4, 6, etc. A's if the preceding letter was B. In both cases if the addition would go beyond the goal length, no longer additions are tried. But also if there was no preceding letter, at the beginning, A's or B's can be added. During debugging shorter length possibilities were explicitly written out as shown above for 5- and 8-letter words. This algorithm does not offer counts of the four types of word, and starts each length afresh as it does not build upon preceding length values. As the current puzzle is concerned with 15-letter words, that debugging facility was used to show all 257 15-letter words:
AABAABAABAABAAB
AABAABAABAAAAAA
AABAABAABBBAAAA
AABAABAABBBBBAA
AABAABAABBBBBBB
AABAABAAAABAAAA
AABAABAAAABBBAA
AABAABAAAABBBBB
AABAABAAAAAABAA
AABAABAAAAAABBB
AABAABAAAAAAAAB
AABAABBBAABAAAA
AABAABBBAABBBAA
AABAABBBAABBBBB
AABAABBBAAAABAA
AABAABBBAAAABBB
AABAABBBAAAAAAB
AABAABBBBBAABAA
AABAABBBBBAABBB
AABAABBBBBAAAAB
AABAABBBBBBBAAB
AABAAAABAABAAAA
AABAAAABAABBBAA
AABAAAABAABBBBB
AABAAAABAAAABAA
AABAAAABAAAABBB
AABAAAABAAAAAAB
AABAAAABBBAABAA
AABAAAABBBAABBB
AABAAAABBBAAAAB
AABAAAABBBBBAAB
AABAAAAAABAABAA
AABAAAAAABAABBB
AABAAAAAABAAAAB
AABAAAAAABBBAAB
AABAAAAAAAABAAB
AABAAAAAAAAAAAA
AABBBAABAABAAAA
AABBBAABAABBBAA
AABBBAABAABBBBB
AABBBAABAAAABAA
AABBBAABAAAABBB
AABBBAABAAAAAAB
AABBBAABBBAABAA
AABBBAABBBAABBB
AABBBAABBBAAAAB
AABBBAABBBBBAAB
AABBBAAAABAABAA
AABBBAAAABAABBB
AABBBAAAABAAAAB
AABBBAAAABBBAAB
AABBBAAAAAABAAB
AABBBAAAAAAAAAA
AABBBBBAABAABAA
AABBBBBAABAABBB
AABBBBBAABAAAAB
AABBBBBAABBBAAB
AABBBBBAAAABAAB
AABBBBBAAAAAAAA
AABBBBBBBAABAAB
AABBBBBBBAAAAAA
AABBBBBBBBBAAAA
AABBBBBBBBBBBAA
AABBBBBBBBBBBBB
AAAABAABAABAAAA
AAAABAABAABBBAA
AAAABAABAABBBBB
AAAABAABAAAABAA
AAAABAABAAAABBB
AAAABAABAAAAAAB
AAAABAABBBAABAA
AAAABAABBBAABBB
AAAABAABBBAAAAB
AAAABAABBBBBAAB
AAAABAAAABAABAA
AAAABAAAABAABBB
AAAABAAAABAAAAB
AAAABAAAABBBAAB
AAAABAAAAAABAAB
AAAABAAAAAAAAAA
AAAABBBAABAABAA
AAAABBBAABAABBB
AAAABBBAABAAAAB
AAAABBBAABBBAAB
AAAABBBAAAABAAB
AAAABBBAAAAAAAA
AAAABBBBBAABAAB
AAAABBBBBAAAAAA
AAAABBBBBBBAAAA
AAAABBBBBBBBBAA
AAAABBBBBBBBBBB
AAAAAABAABAABAA
AAAAAABAABAABBB
AAAAAABAABAAAAB
AAAAAABAABBBAAB
AAAAAABAAAABAAB
AAAAAABAAAAAAAA
AAAAAABBBAABAAB
AAAAAABBBAAAAAA
AAAAAABBBBBAAAA
AAAAAABBBBBBBAA
AAAAAABBBBBBBBB
AAAAAAAABAABAAB
AAAAAAAABAAAAAA
AAAAAAAABBBAAAA
AAAAAAAABBBBBAA
AAAAAAAABBBBBBB
AAAAAAAAAABAAAA
AAAAAAAAAABBBAA
AAAAAAAAAABBBBB
AAAAAAAAAAAABAA
AAAAAAAAAAAABBB
AAAAAAAAAAAAAAB
BAABAABAABAABAA
BAABAABAABAABBB
BAABAABAABAAAAB
BAABAABAABBBAAB
BAABAABAAAABAAB
BAABAABAAAAAAAA
BAABAABBBAABAAB
BAABAABBBAAAAAA
BAABAABBBBBAAAA
BAABAABBBBBBBAA
BAABAABBBBBBBBB
BAABAAAABAABAAB
BAABAAAABAAAAAA
BAABAAAABBBAAAA
BAABAAAABBBBBAA
BAABAAAABBBBBBB
BAABAAAAAABAAAA
BAABAAAAAABBBAA
BAABAAAAAABBBBB
BAABAAAAAAAABAA
BAABAAAAAAAABBB
BAABAAAAAAAAAAB
BAABBBAABAABAAB
BAABBBAABAAAAAA
BAABBBAABBBAAAA
BAABBBAABBBBBAA
BAABBBAABBBBBBB
BAABBBAAAABAAAA
BAABBBAAAABBBAA
BAABBBAAAABBBBB
BAABBBAAAAAABAA
BAABBBAAAAAABBB
BAABBBAAAAAAAAB
BAABBBBBAABAAAA
BAABBBBBAABBBAA
BAABBBBBAABBBBB
BAABBBBBAAAABAA
BAABBBBBAAAABBB
BAABBBBBAAAAAAB
BAABBBBBBBAABAA
BAABBBBBBBAABBB
BAABBBBBBBAAAAB
BAABBBBBBBBBAAB
BAAAABAABAABAAB
BAAAABAABAAAAAA
BAAAABAABBBAAAA
BAAAABAABBBBBAA
BAAAABAABBBBBBB
BAAAABAAAABAAAA
BAAAABAAAABBBAA
BAAAABAAAABBBBB
BAAAABAAAAAABAA
BAAAABAAAAAABBB
BAAAABAAAAAAAAB
BAAAABBBAABAAAA
BAAAABBBAABBBAA
BAAAABBBAABBBBB
BAAAABBBAAAABAA
BAAAABBBAAAABBB
BAAAABBBAAAAAAB
BAAAABBBBBAABAA
BAAAABBBBBAABBB
BAAAABBBBBAAAAB
BAAAABBBBBBBAAB
BAAAAAABAABAAAA
BAAAAAABAABBBAA
BAAAAAABAABBBBB
BAAAAAABAAAABAA
BAAAAAABAAAABBB
BAAAAAABAAAAAAB
BAAAAAABBBAABAA
BAAAAAABBBAABBB
BAAAAAABBBAAAAB
BAAAAAABBBBBAAB
BAAAAAAAABAABAA
BAAAAAAAABAABBB
BAAAAAAAABAAAAB
BAAAAAAAABBBAAB
BAAAAAAAAAABAAB
BAAAAAAAAAAAAAA
BBBAABAABAABAAB
BBBAABAABAAAAAA
BBBAABAABBBAAAA
BBBAABAABBBBBAA
BBBAABAABBBBBBB
BBBAABAAAABAAAA
BBBAABAAAABBBAA
BBBAABAAAABBBBB
BBBAABAAAAAABAA
BBBAABAAAAAABBB
BBBAABAAAAAAAAB
BBBAABBBAABAAAA
BBBAABBBAABBBAA
BBBAABBBAABBBBB
BBBAABBBAAAABAA
BBBAABBBAAAABBB
BBBAABBBAAAAAAB
BBBAABBBBBAABAA
BBBAABBBBBAABBB
BBBAABBBBBAAAAB
BBBAABBBBBBBAAB
BBBAAAABAABAAAA
BBBAAAABAABBBAA
BBBAAAABAABBBBB
BBBAAAABAAAABAA
BBBAAAABAAAABBB
BBBAAAABAAAAAAB
BBBAAAABBBAABAA
BBBAAAABBBAABBB
BBBAAAABBBAAAAB
BBBAAAABBBBBAAB
BBBAAAAAABAABAA
BBBAAAAAABAABBB
BBBAAAAAABAAAAB
BBBAAAAAABBBAAB
BBBAAAAAAAABAAB
BBBAAAAAAAAAAAA
BBBBBAABAABAAAA
BBBBBAABAABBBAA
BBBBBAABAABBBBB
BBBBBAABAAAABAA
BBBBBAABAAAABBB
BBBBBAABAAAAAAB
BBBBBAABBBAABAA
BBBBBAABBBAABBB
BBBBBAABBBAAAAB
BBBBBAABBBBBAAB
BBBBBAAAABAABAA
BBBBBAAAABAABBB
BBBBBAAAABAAAAB
BBBBBAAAABBBAAB
BBBBBAAAAAABAAB
BBBBBAAAAAAAAAA
BBBBBBBAABAABAA
BBBBBBBAABAABBB
BBBBBBBAABAAAAB
BBBBBBBAABBBAAB
BBBBBBBAAAABAAB
BBBBBBBAAAAAAAA
BBBBBBBBBAABAAB
BBBBBBBBBAAAAAA
BBBBBBBBBBBAAAA
BBBBBBBBBBBBBAA
BBBBBBBBBBBBBBB
DefDbl A-Z
Dim crlf$, s$, ct, goal
Private Sub Form_Load()
Form1.Visible = True
Text1.Text = ""
crlf = Chr$(13) + Chr$(10)
For goal = 1 To 16
s$ = "": ct = 0
Text1.Text = Text1.Text & goal & " "
If goal = 15 Then Text1.Text = Text1.Text & crlf
addOn
Text1.Text = Text1.Text & ct & crlf
Next goal
Text1.Text = Text1.Text & crlf & " done"
End Sub
Sub addOn()
For i = 2 To goal Step 2
If Len(s) = 0 Or Right(s, 1) = "B" Or Len(s) = goal Then
If Len(s) + i <= goal Then
s = s + String(i, "A")
If Len(s) = goal Then
ct = ct + 1
If goal = 15 Then Text1.Text = Text1.Text & s & crlf
Else
addOn
End If
s = Left(s, Len(s) - i)
End If
End If
Next
For i = 1 To goal Step 2
If Len(s) = 0 Or Right(s, 1) = "A" Or Len(s) = goal Then
If Len(s) + i <= goal Then
s = s + String(i, "B")
If Len(s) = goal Then
ct = ct + 1
If goal = 15 Then Text1.Text = Text1.Text & s & crlf
Else
addOn
End If
s = Left(s, Len(s) - i)
End If
End If
Next
End Sub
Function mform$(x, t$)
a$ = Format$(x, t$)
If Len(a$) < Len(t$) Then a$ = Space$(Len(t$) - Len(a$)) & a$
mform$ = a$
End Function
|
|
Posted by Charlie
on 2018-01-11 16:21:19 |
2 algorithms same answer--computer assisted (spoiler)
