Hairpin structure easy algorithm-CodePudding

I have a structure with letters A, Z, F, G.

A have a pair with Z, and F with G.

I have for example AAAFFZZGGFFGGAAAAZZZZ. And I need to "curve" structure and that fold will make a pairs

A A A F F Z Z G G F F -
  * *     * *     * *  |
  Z Z Z Z A A A A G G -

6 pairs in upper example.

But we can create structure like this:

      A A A F F Z Z G G -
      *             * *  |
Z Z Z Z A A A A G G F F -

And head is a fragment of structure where pairs cannot exists. For example head 2:

rozmiar. Na przykład head = 2:

                    F F
A A A F F Z Z G G  /   \
  * *     * *           |
  Z Z Z Z A A A A  \   /
                    G G

I don't know how to find maximal number of pairs that can be created in this structure

CodePudding user response：

You could start with testing the folding point in the center, and then fan out (in zig-zag manner) putting the folding point further from the center.

Then for a given folding point, count the allowed pairs. You can use slicing to create the two strips, one in reversed order, and then zip those to get the pairs.

The outer iteration (determining the folding point) can stop when the size of the shortest strip is shorter than the size of the best answer found so far.

Here is a solution, which also returns the actual fold, so it can be printed for verification:

def best_fold(chain):
    allowed = set(("AZ","ZA","FG","GF"))
    revchain = chain[::-1]
    maxnumpairs = 0
    fold = chain  # This represents "no solution"
    n = len(chain)
    head = n // 2
    for diff in range(n):
        head  = diff if diff % 2 else -diff
        if head - 2 < maxnumpairs or n - head - 2 < maxnumpairs:
            break
        numpairs = sum(a b in allowed
            for a, b in zip(revchain[-head 2:], chain[head 2:])
        )
        if numpairs > maxnumpairs:
            maxnumpairs = numpairs
            fold = chain[:head].rjust(n)   "\n"   revchain[:-head].rjust(n)        

    return maxnumpairs, fold

Here is how to run it on the example string:

numpairs, fold = best_fold("AAAFFZZGGFFGGAAAAZZZZ")
print(numpairs)  # 5
print(fold)      #   AAAFFZZGGF
                 #  ZZZZAAAAGGF

CodePudding user response：

To make the matching go faster you can prepare a second string (R) with the letters flipped to their corresponding values. This will allow direct comparisons of paired positions instead of going through an indirection n^2 times:

S = "AAAFFZZGGFFGGAAAAZZZZ"

match = str.maketrans("AZFG","ZAGF")
R = S.translate(match)                # flipped matching letters

mid = len(S)//2
maxCount,maxPos = 0,0
for d in range(mid 1):        # moving away from middle
    for p in {mid d,mid-d}:   # right them left  
        pairs = sum(a==b for a,b in zip(S[p-1::-1],R[p:])) # match fold
        if pairs>maxCount:
            maxCount,maxPos = pairs,p  # track best so far and fold position
    if p <= maxCount: break            # stop when impossible to improve 
        
print(maxCount)                         # 6 matches
print(maxPos)                           # folding at 11
print(S[:maxPos].rjust(len(S)))         #          AAAFFZZGGFF
print(S[maxPos:][::-1].rjust(len(S)))   #           ZZZZAAAAGG
                                        #           **  **  **