Post to walk to the Edge

Decide if it were or not possible, or even intractable

Juan Manuel Dato
Jun 11 · 6 min read

Entering to the code

def explodePost(dicc):
    Q = set([])
    newQ = clausure(('', ''), dicc)
    while newQ:
        query = newQ.pop()
        if query in Q:
            continue
        newQ.update(clausure(query, dicc))
        if ('', '') in newQ:
            return True
        Q.add(query)
    return Falsedef clausure(query, dicc):
    R = set([])
    q1, q2 = query
    for x1 in dicc.keys():
        qR = rest(q1+x1, q2+dicc[x1])
        if qR is not None:
            R.add(qR)
    return Rdef rest(str1, str2, CAB = "$_$"):
    if CAB + str1 in CAB + str2:
        return ('', str2[len(str1):])
    if CAB + str2 in CAB + str1:
        return (str1[len(str2):], '')
    return None
>>> rest('my cat', 'my dog')
>>> rest('my ', 'my dog')
('', 'dog')
>>> clausure(('', ''), {'a':'baa', 'ab':'aa', 'bba':'bb'})
{('a', '')}
>>> explodePost({'a':'baa', 'ab':'aa', 'bba':'bb'})
True
>>> explodePost({'a':'baa', 'ab':'aa', 'baa':'bb'})
False

Why it could not work

What I ensure about NP Vs P

def testPost(seq, items):
    A = ''
    B = ''
    for i in seq:
        A += items[i][0]
        B += items[i][1]
    return A == B>>> testPost((2, 1, 2, 0), 
       [('a', 'baa'), ('ab', 'aa'), ('bba', 'bb')])
True

Moreover

Conclusions

The Startup

Medium's largest active publication, followed by +469K people. Follow to join our community.

Juan Manuel Dato

Written by

Maybe I’m a John Doe, but I’m your John Doe.

The Startup

Medium's largest active publication, followed by +469K people. Follow to join our community.