k = 4

from functools import lru_cache
merken = lru_cache(maxsize=None)

from itertools import product

@merken
def LCS(a,b):
    la,lb = len(a),len(b)
    if la==0 or lb==0:
        return 0
    am = a[:la-1]
    bm = b[:lb-1]
    if a[-1]==b[-1]:
        return 1+LCS(am,bm)
    else:
        return max(LCS(am,b),LCS(a,bm))

@merken
def LCSdiag(a,b):
    l,lb = len(a),len(b)
    assert l==lb
    return max(LCS(a[:k],b[:l-k]) for k in range(l+1))
    
#print (LCS("1e32sejsl","43e11sjje14l"))
    
strs = tuple("".join(x) for x in product("01",repeat=k))
strs_ = tuple("".join(x) for x in product("01",repeat=k-1))
s0=strs[0]


v = {(a,b):0 for a in strs+strs_ for b in strs+strs_}

def iterate():
  done = True  
  for (a,b),val in v.items():
      if len(a)<k:
          new = -gamma + (v[a+'0',b]+v[a+'1',b])/2
      elif len(b)<k:
          new = -gamma + (v[a,b+'0']+v[a,b+'1'])/2
      elif a[0]==b[0]:
          new = 1 + v[a[1:],b[1:]]
      else:
          new = max(v[a[1:],b],v[a,b[1:]])
      if new < val:
          v[a,b] = new
          done = False
  return done  


def print_v():
    print(end=" "*(k+2))
    for b in strs:
        print ("{:6}".format(b), end = "")
    print()
    for u in strs:
        print(u, end="")
        for b in strs:
            erg = -v[u,b]#/(1-gamma)
            erg = 4+v[u,b]
            print ("{:6.3f}".format(erg), end = "")
        print()
    print()


gamma = 0.37928 # k = 4
#gamma = 0.382723 # k = 5  0.765446

done = False
i=1
while not done:
    done = iterate()
    if v[s0,s0]<0:
        print(i,v[s0,s0],"gamma too large")
        break
    if i%100 == 0: print(i)
    #print_v()
    if done:
        print ("iteration",i)
        print_v()
        break


print("alpha =",gamma,",  gamma >=",2*gamma)
"""
Es terminiert immer bei Iteration 1.
Der Algorithmus scheint ja den richtigen Riecher zu haben.
"""