Skip to content

Instantly share code, notes, and snippets.

@choltha
Created April 10, 2024 20:29
Show Gist options
  • Save choltha/4ccbd0f59ecb1912e2bdf82df1cd9f27 to your computer and use it in GitHub Desktop.
Save choltha/4ccbd0f59ecb1912e2bdf82df1cd9f27 to your computer and use it in GitHub Desktop.
You are given a problem which consists of a string of elements from a small vocabulary. You will apply logic to solve for
the answer, as we will demonstrate. At every step, we modify the previous string to a new string by looking at pairs of elements
(in rare cases, the last element doesn't have a pair and is unchanged).
For each pair you will apply a rule. A rule can cause the elements to be unchanged, deleted, or replaced. To improve
our answering, we will number the elements of the problem. The numbers will follow elements between steps to make it
easier to follow our logic. In other words, we do not re-number, and an element will keep its number even if changed by
the rule. Removed elements will have their numbers removed as well.
After you have applied a rule, you will indicate what will be added to make the string in the next step. Generally, if
the elements are deleted nothing is added, if the elements are replaced two elements are added, and if nothing is changed
only one element is added (because the second element may belong to a second pair). If nothing is changed on the final two elements,
make sure to add both!
After applying a rule to all the elements, move on to the next step. At the beginning of a step,
use the added elements to construct the current state of the problem.
Here are the transition rules:
A# A# - no change
A# B# - no change
B# A# - no change
B# B# - no change
#A #A - no change
#A #B - no change
#B #A - no change
#B #B - no change
#A A# - no change
#A B# - no change
#B A# - no change
#B B# - no change
A# #A - deleted
A# #B - replaced with #B A#
B# #A - replaced with #A B#
B# #B - deleted
<problem>#B A# #A A# A# #B B# B# B# #B #B #B</problem>
Init: #B 2. A# 3. #A 4. A# 5. A# 6. #B 7. B# 8. B# 9. B# 10. #B 11. #B 12. #B
1. #B 2. A# no change, +1. #B
2. A# 3. #A are deleted
4. A# 5. A# no change, +4. A#
5. A# 6. #B is updated, +5. #B +6. A#
7. B# 8. B# no change, +7. B#
8. B# 9. B# no change, +8. B#
9. B# 10. #B are deleted
11. #B 12. #B no change, +11. #B +12. #B
--- Next Step ---
Init: #B 4. A# 5. #B 6. A# 7. B# 8. B# 11. #B 12. #B
1. #B 4. A# no change, +1. #B
4. A# 5. #B is updated, +4. #B +5. A#
6. A# 7. B# no change, +6. A#
7. B# 8. B# no change, +7. B#
8. B# 11. #B are deleted
--- Next Step ---
Init: #B 4. #B 5. A# 6. A# 7. B# 12. #B
1. #B 4. #B no change, +1. #B
4. #B 5. A# no change, +4. #B
5. A# 6. A# no change, +5. A#
6. A# 7. B# no change, +6. A#
7. B# 12. #B are deleted
--- Next Step ---
Init: #B 4. #B 5. A# 6. A#
1. #B 4. #B no change, +1. #B
4. #B 5. A# no change, +4. #B
5. A# 6. A# no change, +5. A#
--- Next Step ---
Init: #B 4. #B 5. A# 6. A#
<solution>#B #B A# A#</solution>
<problem>#B A# B# #B A# B# B# A# #B #B #A #A</problem>
Init: #B 2. A# 3. B# 4. #B 5. A# 6. B# 7. B# 8. A# 9. #B 10. #B 11. #A 12. #A
1. #B 2. A# no change, +1. #B
2. A# 3. B# no change, +2. A#
3. B# 4. #B are deleted
5. A# 6. B# no change, +5. A#
6. B# 7. B# no change, +6. B#
7. B# 8. A# no change, +7. B#
8. A# 9. #B is updated, +8. #B +9. A#
10. #B 11. #A no change, +10. #B
11. #A 12. #A no change, +11. #A +12. #A
--- Next Step ---
Init: #B 2. A# 5. A# 6. B# 7. B# 8. #B 9. A# 10. #B 11. #A 12. #A
1. #B 2. A# no change, +1. #B
2. A# 5. A# no change, +2. A#
5. A# 6. B# no change, +5. A#
6. B# 7. B# no change, +6. B#
7. B# 8. #B are deleted
9. A# 10. #B is updated, +9. #B +10. A#
11. #A 12. #A no change, +11. #A +12. #A
--- Next Step ---
Init: #B 2. A# 5. A# 6. B# 9. #B 10. A# 11. #A 12. #A
1. #B 2. A# no change, +1. #B
2. A# 5. A# no change, +2. A#
5. A# 6. B# no change, +5. A#
6. B# 9. #B are deleted
10. A# 11. #A are deleted
--- Next Step ---
Init: #B 2. A# 5. A# 12. #A
1. #B 2. A# no change, +1. #B
2. A# 5. A# no change, +2. A#
5. A# 12. #A are deleted
--- Next Step ---
Init: #B 2. A#
1. #B 2. A# no change, +1. #B
--- Next Step ---
Init: #B 2. A#
<solution>#B A#</solution>
<problem>#A B# B# #B #B #A #B #A A# B# #B A#</problem>
Init: #A 2. B# 3. B# 4. #B 5. #B 6. #A 7. #B 8. #A 9. A# 10. B# 11. #B 12. A#
1. #A 2. B# no change, +1. #A
2. B# 3. B# no change, +2. B#
3. B# 4. #B are deleted
5. #B 6. #A no change, +5. #B
6. #A 7. #B no change, +6. #A
7. #B 8. #A no change, +7. #B
8. #A 9. A# no change, +8. #A
9. A# 10. B# no change, +9. A#
10. B# 11. #B are deleted
--- Next Step ---
Init: #A 2. B# 5. #B 6. #A 7. #B 8. #A 9. A# 12. A#
1. #A 2. B# no change, +1. #A
2. B# 5. #B are deleted
6. #A 7. #B no change, +6. #A
7. #B 8. #A no change, +7. #B
8. #A 9. A# no change, +8. #A
9. A# 12. A# no change, +9. A#
--- Next Step ---
Init: #A 6. #A 7. #B 8. #A 9. A# 12. A#
1. #A 6. #A no change, +1. #A
6. #A 7. #B no change, +6. #A
7. #B 8. #A no change, +7. #B
8. #A 9. A# no change, +8. #A
9. A# 12. A# no change, +9. A#
--- Next Step ---
Init: #A 6. #A 7. #B 8. #A 9. A# 12. A#
<solution>#A #A #B #A A# A#</solution>
<problem>#A B# #A #A B# B# #A B# A# #A #B #B</problem>
Init: #A 2. B# 3. #A 4. #A 5. B# 6. B# 7. #A 8. B# 9. A# 10. #A 11. #B 12. #B
1. #A 2. B# no change, +1. #A
2. B# 3. #A is updated, +2. #A +3. B#
4. #A 5. B# no change, +4. #A
5. B# 6. B# no change, +5. B#
6. B# 7. #A is updated, +6. #A +7. B#
8. B# 9. A# no change, +8. B#
9. A# 10. #A are deleted
11. #B 12. #B no change, +11. #B +12. #B
--- Next Step ---
Init: #A 2. #A 3. B# 4. #A 5. B# 6. #A 7. B# 8. B# 11. #B 12. #B
1. #A 2. #A no change, +1. #A
2. #A 3. B# no change, +2. #A
3. B# 4. #A is updated, +3. #A +4. B#
5. B# 6. #A is updated, +5. #A +6. B#
7. B# 8. B# no change, +7. B#
8. B# 11. #B are deleted
--- Next Step ---
Init: #A 2. #A 3. #A 4. B# 5. #A 6. B# 7. B# 12. #B
1. #A 2. #A no change, +1. #A
2. #A 3. #A no change, +2. #A
3. #A 4. B# no change, +3. #A
4. B# 5. #A is updated, +4. #A +5. B#
6. B# 7. B# no change, +6. B#
7. B# 12. #B are deleted
--- Next Step ---
Init: #A 2. #A 3. #A 4. #A 5. B# 6. B#
1. #A 2. #A no change, +1. #A
2. #A 3. #A no change, +2. #A
3. #A 4. #A no change, +3. #A
4. #A 5. B# no change, +4. #A
5. B# 6. B# no change, +5. B#
--- Next Step ---
Init: #A 2. #A 3. #A 4. #A 5. B# 6. B#
<solution>#A #A #A #A B# B#</solution>
<problem>A# #A #A A# #B #A A# A# B# B# #B A#</problem>
Init: A# 2. #A 3. #A 4. A# 5. #B 6. #A 7. A# 8. A# 9. B# 10. B# 11. #B 12. A#
1. A# 2. #A are deleted
3. #A 4. A# no change, +3. #A
4. A# 5. #B is updated, +4. #B +5. A#
6. #A 7. A# no change, +6. #A
7. A# 8. A# no change, +7. A#
8. A# 9. B# no change, +8. A#
9. B# 10. B# no change, +9. B#
10. B# 11. #B are deleted
--- Next Step ---
3. #A 4. #B 5. A# 6. #A 7. A# 8. A# 9. B# 12. A#
3. #A 4. #B no change, +3. #A
4. #B 5. A# no change, +4. #B
5. A# 6. #A are deleted
7. A# 8. A# no change, +7. A#
8. A# 9. B# no change, +8. A#
9. B# 12. A# no change, +9. B#
--- Next Step ---
3. #A 4. #B 7. A# 8. A# 9. B# 12. A#
3. #A 4. #B no change, +3. #A
4. #B 7. A# no change, +4. #B
7. A# 8. A# no change, +7. A#
8. A# 9. B# no change, +8. A#
9. B# 12. A# no change, +9. B#
--- Next Step ---
3. #A 4. #B 7. A# 8. A# 9. B# 12. A#
<solution>#A #B A# A# B# A#</solution>
<problem>#B #A B# #A B# #B B# #B B# A# A# B#</problem>
Init: #B 2. #A 3. B# 4. #A 5. B# 6. #B 7. B# 8. #B 9. B# 10. A# 11. A# 12. B#
1. #B 2. #A no change, +1. #B
2. #A 3. B# no change, +2. #A
3. B# 4. #A is updated, +3. #A +4. B#
5. B# 6. #B are deleted
7. B# 8. #B are deleted
9. B# 10. A# no change, +9. B#
10. A# 11. A# no change, +10. A#
11. A# 12. B# no change, +11. A# +12. B#
--- Next Step ---
Init: #B 2. #A 3. #A 4. B# 9. B# 10. A# 11. A# 12. B#
1. #B 2. #A no change, +1. #B
2. #A 3. #A no change, +2. #A
3. #A 4. B# no change, +3. #A
4. B# 9. B# no change, +4. B#
9. B# 10. A# no change, +9. B#
10. A# 11. A# no change, +10. A#
11. A# 12. B# no change, +11. A# +12. B#
--- Next Step ---
Init: #B 2. #A 3. #A 4. B# 9. B# 10. A# 11. A# 12. B#
<solution>#B #A #A B# B# A# A# B#</solution>
<problem>#A A# A# A# #B A# #B #B A# #B B# #B</problem>
Init: #A 2. A# 3. A# 4. A# 5. #B 6. A# 7. #B 8. #B 9. A# 10. #B 11. B# 12. #B
1. #A 2. A# no change, +1. #A
2. A# 3. A# no change, +2. A#
3. A# 4. A# no change, +3. A#
4. A# 5. #B is updated, +4. #B +5. A#
6. A# 7. #B is updated, +6. #B +7. A#
8. #B 9. A# no change, +8. #B
9. A# 10. #B is updated, +9. #B +10. A#
11. B# 12. #B are deleted
--- Next Step ---
Init: #A 2. A# 3. A# 4. #B 5. A# 6. #B 7. A# 8. #B 9. #B 10. A#
1. #A 2. A# no change, +1. #A
2. A# 3. A# no change, +2. A#
3. A# 4. #B is updated, +3. #B +4. A#
5. A# 6. #B is updated, +5. #B +6. A#
7. A# 8. #B is updated, +7. #B +8. A#
9. #B 10. A# no change, +9. #B
--- Next Step ---
Init: #A 2. A# 3. #B 4. A# 5. #B 6. A# 7. #B 8. A# 9. #B 10. A#
1. #A 2. A# no change, +1. #A
2. A# 3. #B is updated, +2. #B +3. A#
4. A# 5. #B is updated, +4. #B +5. A#
6. A# 7. #B is updated, +6. #B +7. A#
8. A# 9. #B is updated, +8. #B +9. A#
--- Next Step ---
Init: #A 2. #B 3. A# 4. #B 5. A# 6. #B 7. A# 8. #B 9. A# 10. A#
1. #A 2. #B no change, +1. #A
2. #B 3. A# no change, +2. #B
3. A# 4. #B is updated, +3. #B +4. A#
5. A# 6. #B is updated, +5. #B +6. A#
7. A# 8. #B is updated, +7. #B +8. A#
9. A# 10. A# no change, +9. A#
--- Next Step ---
Init: #A 2. #B 3. #B 4. A# 5. #B 6. A# 7. #B 8. A# 9. A# 10. A#
1. #A 2. #B no change, +1. #A
2. #B 3. #B no change, +2. #B
3. #B 4. A# no change, +3. #B
4. A# 5. #B is updated, +4. #B +5. A#
6. A# 7. #B is updated, +6. #B +7. A#
8. A# 9. A# no change, +8. A#
9. A# 10. A# no change, +9. A#
--- Next Step ---
Init: #A 2. #B 3. #B 4. #B 5. A# 6. #B 7. A# 8. A# 9. A# 10. A#
1. #A 2. #B no change, +1. #A
2. #B 3. #B no change, +2. #B
3. #B 4. #B no change, +3. #B
4. #B 5. A# no change, +4. #B
5. A# 6. #B is updated, +5. #B +6. A#
7. A# 8. A# no change, +7. A#
8. A# 9. A# no change, +8. A#
9. A# 10. A# no change, +9. A#
--- Next Step ---
Init: #A 2. #B 3. #B 4. #B 5. #B 6. A# 7. A# 8. A# 9. A# 10. A#
1. #A 2. #B no change, +1. #A
2. #B 3. #B no change, +2. #B
3. #B 4. #B no change, +3. #B
4. #B 5. #B no change, +4. #B
5. #B 6. A# no change, +5. #B
6. A# 7. A# no change, +6. A#
7. A# 8. A# no change, +7. A#
8. A# 9. A# no change, +8. A#
9. A# 10. A# no change, +9. A#
--- Next Step ---
Init: #A 2. #B 3. #B 4. #B 5. #B 6. A# 7. A# 8. A# 9. A# 10. A#
<solution>#A #B #B #B #B A# A# A# A# A#</solution>
<problem>#B #B A# #B B# A# #B #A #A #A #B B#</problem>
Init: #B 2. #B 3. A# 4. #B 5. B# 6. A# 7. #B 8. #A 9. #A 10. #A 11. #B 12. B#
1. #B 2. #B no change, +1. #B
2. #B 3. A# no change, +2. #B
3. A# 4. #B is updated, +3. #B +4. A#
5. B# 6. A# no change, +5. B#
6. A# 7. #B is updated, +6. #B +7. A#
8. #A 9. #A no change, +8. #A
9. #A 10. #A no change, +9. #A
10. #A 11. #B no change, +10. #A
11. #B 12. B# no change, +11. #B +12. B#
--- Next Step ---
Init: #B 2. #B 3. #B 4. A# 5. B# 6. #B 7. A# 8. #A 9. #A 10. #A 11. #B 12. B#
1. #B 2. #B no change, +1. #B
2. #B 3. #B no change, +2. #B
3. #B 4. A# no change, +3. #B
4. A# 5. B# no change, +4. A#
5. B# 6. #B are deleted
7. A# 8. #A are deleted
9. #A 10. #A no change, +9. #A
10. #A 11. #B no change, +10. #A
11. #B 12. B# no change, +11. #B +12. B#
--- Next Step ---
Init: #B 2. #B 3. #B 4. A# 9. #A 10. #A 11. #B 12. B#
1. #B 2. #B no change, +1. #B
2. #B 3. #B no change, +2. #B
3. #B 4. A# no change, +3. #B
4. A# 9. #A are deleted
10. #A 11. #B no change, +10. #A
11. #B 12. B# no change, +11. #B +12. B#
--- Next Step ---
Init: #B 2. #B 3. #B 10. #A 11. #B 12. B#
1. #B 2. #B no change, +1. #B
2. #B 3. #B no change, +2. #B
3. #B 10. #A no change, +3. #B
10. #A 11. #B no change, +10. #A
11. #B 12. B# no change, +11. #B +12. B#
--- Next Step ---
Init: #B 2. #B 3. #B 10. #A 11. #B 12. B#
<solution>#B #B #B #A #B B#</solution>
<problem>A# A# #A B# A# B# #B #A #A B# B# A#</problem>
Init: A# 2. A# 3. #A 4. B# 5. A# 6. B# 7. #B 8. #A 9. #A 10. B# 11. B# 12. A#
1. A# 2. A# no change, +1. A#
2. A# 3. #A are deleted
4. B# 5. A# no change, +4. B#
5. A# 6. B# no change, +5. A#
6. B# 7. #B are deleted
8. #A 9. #A no change, +8. #A
9. #A 10. B# no change, +9. #A
10. B# 11. B# no change, +10. B#
11. B# 12. A# no change, +11. B# +12. A#
--- Next Step ---
Init: A# 4. B# 5. A# 8. #A 9. #A 10. B# 11. B# 12. A#
1. A# 4. B# no change, +1. A#
4. B# 5. A# no change, +4. B#
5. A# 8. #A are deleted
9. #A 10. B# no change, +9. #A
10. B# 11. B# no change, +10. B#
11. B# 12. A# no change, +11. B# +12. A#
--- Next Step ---
Init: A# 4. B# 9. #A 10. B# 11. B# 12. A#
1. A# 4. B# no change, +1. A#
4. B# 9. #A is updated, +4. #A +9. B#
10. B# 11. B# no change, +10. B#
11. B# 12. A# no change, +11. B# +12. A#
--- Next Step ---
Init: A# 4. #A 9. B# 10. B# 11. B# 12. A#
1. A# 4. #A are deleted
9. B# 10. B# no change, +9. B#
10. B# 11. B# no change, +10. B#
11. B# 12. A# no change, +11. B# +12. A#
--- Next Step ---
9. B# 10. B# 11. B# 12. A#
9. B# 10. B# no change, +9. B#
10. B# 11. B# no change, +10. B#
11. B# 12. A# no change, +11. B# +12. A#
--- Next Step ---
9. B# 10. B# 11. B# 12. A#
<solution>B# B# B# A#</solution>
<problem>A# #B #B B# A# #A #A B# #B #A #A #B</problem>
Init: A# 2. #B 3. #B 4. B# 5. A# 6. #A 7. #A 8. B# 9. #B 10. #A 11. #A 12. #B
1. A# 2. #B is updated, +1. #B +2. A#
3. #B 4. B# no change, +3. #B
4. B# 5. A# no change, +4. B#
5. A# 6. #A are deleted
7. #A 8. B# no change, +7. #A
8. B# 9. #B are deleted
10. #A 11. #A no change, +10. #A
11. #A 12. #B no change, +11. #A +12. #B
--- Next Step ---
Init: #B 2. A# 3. #B 4. B# 7. #A 10. #A 11. #A 12. #B
1. #B 2. A# no change, +1. #B
2. A# 3. #B is updated, +2. #B +3. A#
4. B# 7. #A is updated, +4. #A +7. B#
10. #A 11. #A no change, +10. #A
11. #A 12. #B no change, +11. #A +12. #B
--- Next Step ---
Init: #B 2. #B 3. A# 4. #A 7. B# 10. #A 11. #A 12. #B
1. #B 2. #B no change, +1. #B
2. #B 3. A# no change, +2. #B
3. A# 4. #A are deleted
7. B# 10. #A is updated, +7. #A +10. B#
11. #A 12. #B no change, +11. #A +12. #B
--- Next Step ---
Init: #B 2. #B 7. #A 10. B# 11. #A 12. #B
1. #B 2. #B no change, +1. #B
2. #B 7. #A no change, +2. #B
7. #A 10. B# no change, +7. #A
10. B# 11. #A is updated, +10. #A +11. B#
--- Next Step ---
Init: #B 2. #B 7. #A 10. #A 11. B# 12. #B
1. #B 2. #B no change, +1. #B
2. #B 7. #A no change, +2. #B
7. #A 10. #A no change, +7. #A
10. #A 11. B# no change, +10. #A
11. B# 12. #B are deleted
--- Next Step ---
Init: #B 2. #B 7. #A 10. #A
1. #B 2. #B no change, +1. #B
2. #B 7. #A no change, +2. #B
7. #A 10. #A no change, +7. #A
--- Next Step ---
Init: #B 2. #B 7. #A 10. #A
<solution>#B #B #A #A</solution>
Solve your problem using the exact same approach above.
Remember, you are given a problem which consists of a string of elements from a small vocabulary. You will apply logic to solve for
the answer, as we will demonstrate. At every step, we modify the previous string to a new string by looking at pairs of elements
(in rare cases, the last element doesn't have a pair and is unchanged).
For each pair you will apply a rule. A rule can cause the elements to be unchanged, deleted, or replaced. To improve
our answering, we will number the elements of the problem. The numbers will follow elements between steps to make it
easier to follow our logic. In other words, we do not re-number, and an element will keep its number even if changed by
the rule. Removed elements will have their numbers removed as well.
After you have applied a rule, you will indicate what will be added to make the string in the next step. Generally, if
the elements are deleted nothing is added, if the elements are replaced two elements are added, and if nothing is changed
only one element is added (because the second element may belong to a second pair). If nothing is changed on the final two elements,
make sure to add both!
After applying a rule to all the elements, move on to the next step. At the beginning of a step,
use the added elements to construct the current state of the problem.
A# A# - no change
A# B# - no change
B# A# - no change
B# B# - no change
#A #A - no change
#A #B - no change
#B #A - no change
#B #B - no change
#A A# - no change
#A B# - no change
#B A# - no change
#B B# - no change
A# #A - deleted
A# #B - replaced with #B A#
B# #A - replaced with #A B#
B# #B - deleted
Remember, you only operate on pairs of elements, not single elements. Remember to copy unchanged elements to the next step.
Your problem:
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment