11
$\begingroup$

Goal: Go from the initial string to the final string by applying a sequence of string replacement rules.

You are given the following:

Initial String - baa

Final String - bacaccacacccc

You can apply the following rules one application at a time.

Replacement Rules:

(1) replace every occurrence of a with aa

(2) replace every occurrence of aa with ac

For example, if you had the string abaca, the result of one application of rule 1 is aabaacaa.

Note: you have to solve this problem without the assistance of a computer.

Update 11/11/19

I decided to continue working on string replacement puzzles and made a little game out of it.

Here are the links in case anyone is interested:

Thank you again for your support and interest!

Improve this question
$\endgroup$
7
  • $\begingroup$ Also, if you know of any other puzzles similar to this, please let me know. I'm very interested in learning more about string-based puzzles. It's something that I really enjoy and am trying to learn more about. $\endgroup$
    – Michael Wehar
    Jan 23, 2017 at 0:20
  • 1
    $\begingroup$ Michael Wehar, I suggest looking into finite automata and context-free grammar. Cheers for the puzzle! $\endgroup$
    – Jakob Pamp Bengtsson
    Jan 23, 2017 at 7:47
  • 1
    $\begingroup$ @JakobPampBengtsson Thank you very much for the kind comment and suggestion!! Yes, I love formal language theory: finite automata, context-free grammars, regular expression, combinatorics on words, and reachability problems. :) $\endgroup$
    – Michael Wehar
    Jan 23, 2017 at 15:19
  • 1
    $\begingroup$ I happen to know some similar puzzles, which are called "mathematical conjectures". In some sense any conjecture (or theorem) in mathematics can be formulated as "applying rules" from the axioms and deciding whether a string (proposition) can be reached (many details here, though). If you ask whether there is a polynomial algorithm for that, then it becomes the PNP conjecture, as the problem should be NP complete. $\endgroup$
    – WhatsUp
    Nov 11, 2019 at 21:11
  • 1
    $\begingroup$ You might also find these of interest: www2.stetson.edu/~efriedma/puzzle/replace $\endgroup$
    – Zomulgustar
    Nov 13, 2019 at 4:28

3 Answers 3

Reset to default
15
$\begingroup$

The short answer is

Yes

Explanation:

baa
bac (Rule 2)
baac (1)
bacc (2)
baacc (1)
baaaacc (1)
bacaccc (2)
baacaaccc (1)
baaaacaaaaccc (1)
bacaccacacccc (2)

Question (to @Michael Wehar) why is there a 'b' at the front?

Improve this answer
$\endgroup$
4
  • 3
    $\begingroup$ Not an answer to the question, but the riddle reminds of Hofstadter's MU puzzle, in which there always is an M in front, possibly to avoid ever reaching the empty string (which isn't possible in this puzzle). $\endgroup$
    – Pål GD
    Jan 22, 2017 at 13:17
  • $\begingroup$ Woohoo!! You solved it and you solved it super fast. Thank you very much. :) $\endgroup$
    – Michael Wehar
    Jan 22, 2017 at 16:00
  • $\begingroup$ The b isn't really used, but because it is in the first position in the initial and final string, it does suggest that you have to apply replacement rules to build out the final string from left to right which also can be seen by the rules themselves. $\endgroup$
    – Michael Wehar
    Jan 22, 2017 at 16:02
  • $\begingroup$ @PålGD Thank you very much for sharing about the MU puzzle. This is quite a helpful reference!! :) $\endgroup$
    – Michael Wehar
    Jan 22, 2017 at 16:05
6
$\begingroup$

"a => aa" increases the length of the string by one. "aa => ac" does not change its length, but allows you to change an "a" to a "c".

The length of the string needs to increase from 3 to 13, so 10 Rule #1s are required. There are 8 (more) Cs, so 8 Rule #2s are required.

I would do 10 rule #1s followed by 8 rule #2s:

baa
  aa          (rule 1)
baaa
   aa         (rule 1)
baaaa
........
baaaaaaaaaaaa
           ac (rule 2)
baaaaaaaaaaac
          ac  (rule 2)
baaaaaaaaaacc
         ac   (rule 2)
...
baaaccacacccc
 ac           (rule 2)
bacaccacacccc
Improve this answer
$\endgroup$
3
  • 3
    $\begingroup$ ^vote for showing an analysis and for explaining your approach. Seems, though, that each time rule 1 or 2 is applied it is meant to replace all matching occurrences at once, not just a single match that may be selected. $\endgroup$
    – humn
    Jan 22, 2017 at 17:58
  • 3
    $\begingroup$ Yes, this is wrong. After the first rule, you should have baaaa, not baaa. It replaces every a with aa, thus the number of as should double. $\endgroup$
    – Pål GD
    Jan 22, 2017 at 18:06
  • $\begingroup$ Oops. Missed the "all occurrences" $\endgroup$
    – Justin
    Sep 16, 2017 at 14:59
4
$\begingroup$

Answer (albeit a bit late):

Yes.

Method:

Working backwards is often a good idea when dealing with mathematical puzzles. Starting with the goal string,
bacaccacacccc
the only possible operation previous to this is "aa" -> "ac", as there are no occurences of "aa" in it. We reverse the operation a step.
bacaccacacccc
baaaacaaaaccc
The step previous to this could not have used to "aa"->"ac" operation, since that would have removed all the "aa" we see in this string. Therefore, we reverse the "a"->"aa" operation.
baaaacaaaaccc
baacaaccc
The step previous to this could not have used "aa"->"ac", because that would have turned the first instance of "aa" in the string into ac, but we're left with a leading "aa". Therefore, we reverse the "a"->"aa" operation again.
baacaaccc
bacaccc
The "a"->"aa" operation would not have been available to us in the operation previous to this, making "aa"->"ac" the only possible operation. We reverse said operation.
bacaccc
baaaacc
Following the reason previously used, "aa"->"ac" wasn't used in the previous step since we have "aa" still occurring. Reverse "a"->"aa".
baaaacc
baacc
Again, "aa"->"ac" wouldn't have left us with this state, so we reverse "a"->"aa".
baacc
bacc
Only "aa"->"ac" could have been used to produce this. Reverse it.
bacc
baac
Since we have a leading "aa", "aa"->"ac" wasn't used. Reverse "a"->"aa".
baac
bac
The available operation is obvious; apply it.
bac
baa
And that's problem solved.

The answer is a bit lengthy, but I hope the explanation adds something. I'll also mention a general rule that was only briefly touched in the answer:

If we ever use "aa"->"ac", the "aa"->"ac" operation will never be available directly after; you always need "a"->"aa" after it.
E.g. baaa -> baca
Since we search from the left and the second "a" is changed, there are never instances where the unchanged "a" has another "a" next to it. In an odd-numbered "a" sequence, the final "a" remains unchanged next to a "c".

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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