Skip to content

Instantly share code, notes, and snippets.

@sudhackar sudhackar/given.dot
Last active Sep 8, 2018

Embed
What would you like to do?
strict digraph "" {
graph [ordering="out"];
null[label=""];
C -> G;
C -> H;
G -> M;
G -> N;
F -> S;
F -> U;
H -> null;
H -> W;
J -> Z;
J -> A;
L -> P;
L -> Y;
O -> J;
O -> K;
P -> O;
P -> E;
S -> L;
T -> F;
T -> V;
W -> X;
W -> I;
Z -> C;
Z -> D;
}
Sorry, something went wrong. Reload?
Sorry, we cannot display this file.
Sorry, this file is invalid so it cannot be displayed.
debug = False
def the_process(stored, inp, size, fs):
if debug:
print '\t' * fs + \
"the_process({}, {}, {})".format(stored, "".join(inp), size)
idx = 0
global thstr
idx = stored.index(inp[0])
if idx:
the_process(stored[:idx], inp[1:], idx, fs + 1)
if size - 1 != idx:
the_process(stored[1 + idx:1 + idx + size - idx - 1],
inp[idx + 1:], size - idx - 1, fs + 1)
thstr.append(inp[0])
def rev_process(stored, inp, size, fs):
if debug:
print '\t' * fs + \
"rev_process({}, {}, {})".format(stored, "".join(inp), size)
if not size:
return
global thstr
mp = {stored[i]: i for i in xrange(len(stored))}
idx = mp[inp[-1]]
thstr.append(inp[-1])
if size == 1:
return
try:
less_part = max(
loc for loc,
val in enumerate(inp) if mp[val] < idx) + 1
except ValueError:
less_part = 0
rev_process(stored[:idx], inp[:less_part], less_part, fs + 1)
if less_part != size - 1:
rev_process(stored[idx + 1:], inp[less_part:-1],
size - less_part - 1, fs + 1)
if __name__ == "__main__":
thstr = []
stored = "MGNCHXWIZDJAOKPELYSFUTV"
input1 = "TFSLPOJZCGMNHWXIDAKEYUV"
target = "MNGHCWZIJDXOPKLESUVTFYA"
print "sample input : " + input1
the_process(stored, input1, 23, 0)
output1 = "".join(thstr)
print "sample output : " + output1
thstr = []
rev_process(stored, output1, 23, 0)
input1_rev = "".join(thstr)
assert input1 == input1_rev
thstr = []
print "target output : " + target
rev_process(stored, target, 23, 0)
target_rev = "".join(thstr)
print "target input : " + target_rev
thstr = []
the_process(stored, target_rev, 23, 0)
target_out = "".join(thstr)
assert target_out == target
strict digraph "" {
graph [ordering="out"];
A -> X;
X -> C;
C -> G;
G -> M;
G -> N;
C -> H;
X -> D;
D -> I;
I -> W;
I -> Z;
D -> J;
A -> Y;
Y -> E;
E -> K;
E -> L;
K -> O;
K -> P;
Y -> F;
F -> S;
F -> T;
T -> U;
T -> V;
}
Sorry, something went wrong. Reload?
Sorry, we cannot display this file.
Sorry, this file is invalid so it cannot be displayed.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.