egor.okhterov's blog

By egor.okhterov, history, 8 years ago, In English

We have all the possible 3-grams of lower case letters (A = {a, b, c, ..., z}):
A3 = A × A × A = 
{
  (a, a, a), 
  (a, a, b), 
  (a, a, c), 
    ..., 
  (a, a, z), 
  (b, a, a), 
    ..., 
  (z, z, y), 
  (z, z, z), 
}

|A3| = 263 = 17576

  • If we try to merge aaa with bbb we have to append bbb to the end of aaa, because they don't overlap:
    merge(aaa, bbb) = aaabbb

  • If we merge aaa with aab we can create a smaller string:
    merge(aaa, aab) = aaab

In the best case, if we manage to always do a second kind of merge, we will be extending the resulting string by 1 character. There are 17576 triplets, so there can be at most 17575 single character extensions. This will result in 17575 + 3 = 17578 characters string.

In the worst case, we will append all of the 3-grams to each other, thus creating a 17576 * 3 = 52728 characters string.

How to combine all of them to get the total string of the minimum length?


Picture to attract people :)

  • Vote: I like it
  • +2
  • Vote: I do not like it

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Where is this problem from?

  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It is my problem inspired by Symbolic Sequence.

    For me it looks like the problem is pretty foundational, but I couldn't google neither the problem nor the solution. The closest problem that I found is the problem of assembling human genome, but again it is pretty different from what I am looking for.

    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it +11 Vote: I do not like it

      I believe this is exactly what you want.

      • »
        »
        »
        »
        8 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Thank you!
        But how did you google it? :)

        • »
          »
          »
          »
          »
          8 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          I just happen to know some old problem that is named after this sequence and asks to find exactly it.

          • »
            »
            »
            »
            »
            »
            8 years ago, # ^ |
            Rev. 2   Vote: I like it 0 Vote: I do not like it

            Эхх что за времена пошли два русских друг с другом на английском общаются.
            UPD И у самого страна Америка )))))))

            • »
              »
              »
              »
              »
              »
              »
              8 years ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              По нику не так просто понять кто есть кто =)